Extra Variables in optimize for sos optimization

[Muhammad Ali Murtaza]

Hi,

I was trying to code an SOS example using Yalmip. My example was close to the example you mentioned on https://math.stackexchange.com/questions/2392394/sostools-getting-example-to-work/2396495#2396495 . I am just pasting the code you wrote there

sdpvar x1 x2 u1 u2;

f = [x2; u1*u2 - 10*u1; x2*u2; -x2*u1];

c1 = sdpvar(5,1);
c2 = sdpvar(4,1);    
V = c1'*[1; u2; u2^2; u1^2; x2^2];
s1 = c2'*[x1^2; x2^2; u1^2; u2^2]
g1 = u1^2 + u2^2 - 1;

Model = [sos(V-0.1*(1-u2)-0.1*x2^2) + sos(-jacobian(V,[x1;x2;u1;u2])*f + s1*g1)];    
Model = [Model, sum(c1(1:3)) == 0]; 
optimize(Model,norm(c1 - [4.8931;-6.689;1.7959;1.4615;0.33445]),[],[c1;c2])
value(c1)


I tried understanding it but I couldnot find the options of implying optimize with ([],[c1;c2]) parameters. I did found optimizer but I am not sure what is happening here with optimize. 
If I remove [], it gives me error. AS per my understanding, it seems like [] is the default options of sdp setting.
If I remove [c1;c2], problem becomes infeasible. If I just add [c2], problem is still feasible but with just [c1] problem is still infeasible.
If I am not wrong, it seems that we are specifying the variables [c1;c2] to be optimize. Please correct me if I am wrong. 

Will you be kind enough to explain the extra parameters in detail of our selection in choosing it but not (x1,x2,u1,u2). Also why problem is still feasible with c2 but not c1.

If there is a wiki for extra parameters of optimize(not sdp setting), can you point me towards it. 

I will really appreciate your guidance in this matter.

Thanks

[Johan Löfberg]

Works here

    yalmipversion: '20181012'

       yalmiptime: 6.1480

       solvertime: 0.6590

             info: 'Successfully solved (MOSEK)'

          problem: 0

I don't understand what you mean with "implying optimize with ([],[c1;c2]) parameters"

you are declaring c1 and c2 as parameters, i.e. variables to be found such that the polynomial is sos in x and u. I don't think this is official use of optimize, you normally use solvesos

[Muhammad Ali Murtaza]

Thank you for the answer. I was asking I could not find the option of optimize with additional parameters anywhere in wiki but since you mentioned that its not official use, I think it solves my problem.

I verified that both solvesos and optimize with additional parameters yield the same result.

However if I just parametrize with respect to c2 only, it still gives me optimal solution but if I parametrize with respect c1 only, it gives me 'Unbounded objective function (MOSEK)' error. Here c2 is just langrange multiplier but it seems it is necessary.

Because of this it may seems that c1 as parameter may be unnceassary since c2 as parameter also yields the same result.

Can you please explain this part to me as well.

Thanks

[Johan Löfberg]

c1 is part of the objective, hence it is obviously not a variable you are performing sos over, and thus a parameter

[Muhammad Ali Murtaza]

Respected Professor Johan,

Thank you for the reply and explanation. I know if we have both langrange multiple and some polynomial function (say V here), we optimize with respect to coefficient of both variables (c1 and c2) in our case.

I wish to ask just cause we were able to optimize with c2 only and get the same result was due to the problem formulation or we just got lucky.

Since technically coefficients of monomial of V are c1 and coefficients of langrange multiplier is c2. Because I see in the initial yalmip message that we have 10 parametric variables and 4 independent variables,

irrespective if we chose decision variable as either c1 or c2.

In addition, if I further add the following condition of s1 being sos, I get Mosek error: MSK_RES_TRM_STALL () message but it still solves the problem. Do adding this constraint explicitly is valid?

Since I have seen it explicitly defined separately in literature or in implementation there is no need?

If it is valid and correct, do you have an idea why is stalling error generated and how to get rid of it or do it in the correct way.

I will highly appreciate if you can answer this question and increase my understanding.

Thanks

[Johan Löfberg]

As I already said, since c1 is part of the objective, YALMIP knows it is a parameter, so you have never solved any problem with only c2 being parameters.

[Muhammad Ali Murtaza]

Thank You Professor Johan. That perfectly explains it.

Can you also let me know if I add  additional constraint in the same problem of s1 being sos (Model = [Model, sos(s1)];), I get Mosek error: MSK_RES_TRM_STALL () message but it still solves the problem. Do adding this constraint explicitly is valid?

[Johan Löfberg]

How do you know/ what do you mean with it still solves the problem. Mosek is telling you it stalled, so you have to be careful with what has been returned, i.e you have to check that it actually computed something sensible

[Johan Löfberg]

I don't get any stall though when I add sos(s1) to the model, finishes without issues

[Muhammad Ali Murtaza]

Thank you Professor Johan. I get the following output with Model = [Model, sos(s1)];  added to the problem

Optimizer summary
  Optimizer                 -                        time: 0.31   
    Interior-point          - iterations : 35        time: 0.27   
      Basis identification  -                        time: 0.00   
        Primal              - iterations : 0         time: 0.00   
        Dual                - iterations : 0         time: 0.00   
        Clean primal        - iterations : 0         time: 0.00   
        Clean dual          - iterations : 0         time: 0.00   
    Simplex                 -                        time: 0.00   
      Primal simplex        - iterations : 0         time: 0.00   
      Dual simplex          - iterations : 0         time: 0.00   
    Mixed integer           - relaxations: 0         time: 0.00   

Mosek error: MSK_RES_TRM_STALL ()

sol =

  struct with fields:

    yalmipversion: '20181012'
       yalmiptime: 0.8679
       solvertime: 0.4076

             info: 'Successfully solved (MOSEK)'
          problem: 0

I know it is still the solution because the solution is

valc1 =

    3.1968
   -6.2935
    3.0967
    2.7821
    0.3147

is very close to original solution(except the first value which has a difference of 1e-4).

Whereas if I remove it, I see that interior point iterations are 33 and I get the same answer(except the first variable).

valc1 =

    3.1967
   -6.2935
    3.0967
    2.7821
    0.3147

Thanks