minimum value optimization of matrix with constraints
6 views (last 30 days)
Show older comments
Hajar Alshaikh
on 14 Mar 2023
Commented: Bruno Luong
on 15 Mar 2023
i have a matrix A of size n×n such that all of its entries are known excpt m number of entries are unknown.
then how i will calculate the minimum of follwing objective function subject to A are symmetric positive semidefinite (i.e. all eigenvalue of A are greater than or equal to 0)
obj = @(A) 0.5 * norm(A, 'fro')^2
constraint = @(A) (all (eig(X_new>=0)))
0 Comments
Accepted Answer
Bruno Luong
on 15 Mar 2023
Edited: Bruno Luong
on 15 Mar 2023
Straighforward implementation, it seems more reliable than Matt's square-root parametrization.
The square-root makes the gradient close to 0 close to the boundary of the admissible set, and it can create somewhat difficulty of the convergence by gradient descend methods such as fmincon.
while true
n=3;
[Q,~]=qr(randn(n));
d=[rand(n-1,1);0];
A=Q*diag(d)*Q';
if any(A < 0, 'all')
break
end
end
A
Iunknown=A<0;
Adecimation = A;
Adecimation(Iunknown) = 0
i = 1:n;
Iunknown = Iunknown & i>=i'; % work only unknown in upper triangular part
x0=zeros(nnz(Iunknown),1);
norm(A,'fro')
x=fmincon(@(x) fronorm(x,Iunknown,A),x0,[],[],[],[],[],[],@(x) nonlcon(x,Iunknown,A));
Afmincon = CompletionA(x, Iunknown, Adecimation),
c=nonlcon(x,Iunknown,Adecimation);
% Check validity of the solution
OK = norm(Afmincon,'fro')-norm(A,'fro') < 1e-6 || ...
c >= 0;
if ~OK
fprintf('fails to find global minima solution\n')
norm(Afmincon,'fro')
norm(A,'fro')
end
function A = CompletionA(x, Iunknown, Adecimation)
A=Adecimation;
A(Iunknown) = x;
A = 0.5*(A+A.');
end
function f=fronorm(x,Iunknown,Adecimation);
A = CompletionA(x, Iunknown, Adecimation);
f = sum(A.^2,"all");
end
function [c,ceq]=nonlcon(x,Iunknown,Adecimation)
ceq=[];
A = CompletionA(x, Iunknown, Adecimation);
c=min(eig(A));
end
0 Comments
More Answers (1)
Matt J
on 14 Mar 2023
Edited: Matt J
on 15 Mar 2023
Perhaps as follows:
%L=unknown parameter matrix (nxn) where A=L.'*L
%Iknown=indices of known elements of A (mx1)
%Aknown=known A values (mx1)
L0=Init(Iknown,Aknown,n);
L=fmincon(@(L) 0.5*norm(L*L.', 'fro')^2, L0,[],[],[],[],[],[],...
@(L) nonlcon(L,Iknown,Aknown), options );
A=L*L.'; %optimal A
function [c,ceq]=nonlcon(L,Iknown,Aknown)
c=[];
A=L*L.';
ceq=A(Iknown)-Aknown;
end
function L0=Init(Iknown,Aknown,n)
A=zeros(n);
A(Iknown)=Aknown;
A=A-(min(eig(A))-0.01)*eye(n);
L0=chol(A);
end
3 Comments
Matt J
on 15 Mar 2023
Edited: Matt J
on 15 Mar 2023
This initialization scheme seems to work well:
k=0;
N=300;
while k<N
OK=doOptim();
if OK
k=k+1;
else
break;
end
end
disp("Success rate = " + 100*k/N + "%")
function OK=doOptim()
while true
n=3;
[Q,~]=qr(randn(n));
d=[rand(n-1,1);0];
A=Q*diag(d)*Q';
if any(A < 0, 'all')
break
end
end
Iknown=A>=0;
Aknown = A(Iknown);
L0=Init(Iknown,Aknown,n);
obj = @(L) 0.5*norm(L*L.', 'fro')^2;
opts=optimoptions('fmincon','Display','none');
warning off
L=fmincon(obj,L0,[],[],[],[],[],[],@(L) nonlcon(L,Iknown,Aknown) ,opts);
warning on
Afmincon=L*L.'; %optimal A
OK = norm(Afmincon,'fro')-norm(A,'fro') < 1e-6;
end
function [c,ceq]=nonlcon(L,Iknown,Aknown)
%L=unknown variables (nxn)
%Iknown=indices of known matrix elements (mx1)
%Aknown=known matrix values 9mx1)
c=[];
A=L*L.';
ceq=A(Iknown)-Aknown;
end
function L0=Init(Iknown,Aknown,n)
A=zeros(n);
A(Iknown)=Aknown;
A=A-(min(eig(A))-0.01)*eye(n);
L0=chol(A);
end
See Also
Categories
Find more on Surrogate Optimization in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!