Structured polynomial optimization

[Adkitta]

Dear Dr. Löfberg,

I have two question/clarifications regarding polynomial optimization in YALMIP.

1) The moment module in YALMIP implements the 'dense' version of hierarchy of SDP relaxation as per Lasserre 2001. If the structured sparsity is known by the user, is it possible to use this to build the moment matrices in YALMIP? In other words, are you planning to implement the 'sparse' version of hierarchy of SDP relaxation in YALMIP? I realize that this is a hidden feature in GloptiPoly 3 but I would rather like to work with the YALMIP framework.

2) Is it possible to extract *minimizers* from sum-of-squares module by using the automatic dualization feature in YALMIP? Specifically, if I construct custom SOS relaxation using YALMIP and lets say that we find the global minimum for some higher order relaxation, can I extract the decision variable(s) in such a situation? Here, I am assuming that the flat extension condition is satisfied and hence the dual of the SOS SDP could be potentially used to get the minimizers.

I will appreciate some insight from your end.

Thanks!

[Johan Löfberg]

For sparse moments in YALMIP, use sparsepop as the solver

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.SparsePOP

Extracting solutions from solvesos is not supported. The code below shows how you could do it manually (copied from old discussion)

sdpvar x t
n = 1
p = x^4-2*x+1;

[~,~,info] = solvemoment([],p);
% Lower bound
relaxdouble(p)
% Rank-1 moment matrix from which solution is extracted
% Simple case, rank-1
info.moment{end}
eig(info.moment{end})
% the n first monomials are linear
sdisplay(info.monomials)
assign(info.monomials(2:2+n-1),info.moment{end}(1,(2:2+n-1)))
double(p)

% SOS approach, exploits structure if available
% Unfortunately, I don't seem to return dual information, i.e., the moment
% matrix
[sol,m,B,residual,more] = solvesos(sos(p-t),-t);

% Hence, let YALMIP compile the SOS program, and go from there
[F,h] = compilesos(sos(p-t),-t);
solvesdp(F,h);
M = double(F(1));
% If the ordering of monomials is the same, these two coincide
info.moment{end}
M = M/M(1,1)

% A bit messy, since compilesos does not return ordering of monomials, so
% we have to reuse info from solvesos...
assign(m{1}(2:2+n-1),M(1,(2:2+n-1)))
double(p)

[Adkitta]

Thank you for the example. It is good to know that (and how) the decision variables can be extracted from the SOS module.

I feel that sparsePOP is very useful if the correlative sparsity matrix is sparse. Do you think it is possible that the optimization problem may satisfy the sparse property as per Lasserre 2006 but may not be have sparse csp matrix? In that case, defining the subsets will be more efficient (although harder in terms of coding).

[Johan Löfberg]

Don't know

[Adkitta]

Thank you for your help!