minimum value optimization of matrix with constraints

6 views (last 30 days)
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)))

Accepted Answer

Bruno Luong
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
A = 3×3
0.3736 -0.1307 -0.3455 -0.1307 0.5302 0.1397 -0.3455 0.1397 0.3202
Iunknown=A<0;
Adecimation = A;
Adecimation(Iunknown) = 0
Adecimation = 3×3
0.3736 0 0 0 0.5302 0.1397 0 0.1397 0.3202
i = 1:n;
Iunknown = Iunknown & i>=i'; % work only unknown in upper triangular part
x0=zeros(nnz(Iunknown),1);
norm(A,'fro')
ans = 0.9139
x=fmincon(@(x) fronorm(x,Iunknown,A),x0,[],[],[],[],[],[],@(x) nonlcon(x,Iunknown,A));
Local minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the value of the optimality tolerance, and constraints are satisfied to within the value of the constraint tolerance.
Afmincon = CompletionA(x, Iunknown, Adecimation),
Afmincon = 3×3
0.3736 0.2020 -0.1010 0.2020 0.5302 0.1397 -0.1010 0.1397 0.3202
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

More Answers (1)

Matt J
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
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 + "%")
Success rate = 100%
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

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!