minimum value optimization of matrix with constraints
4 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Hajar Alshaikh
le 14 Mar 2023
Commenté : Bruno Luong
le 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 commentaires
Réponse acceptée
Bruno Luong
le 15 Mar 2023
Modifié(e) : Bruno Luong
le 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 commentaires
Plus de réponses (1)
Matt J
le 14 Mar 2023
Modifié(e) : Matt J
le 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 commentaires
Matt J
le 15 Mar 2023
Modifié(e) : Matt J
le 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
Voir également
Catégories
En savoir plus sur Surrogate Optimization dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!