How to use the kkt function to obtain the dual problem?

[Shuai Lu]

Dear Prof. Löfberg,

I hope to get some introduction about the kkt function.

 [KKTsystem, details] = kkt(Constraint,Objective,z) 

The details.dual and details.dualeq are separately the dual variables of Ax<=b and Ex==f', then can the dual problem be solved as follows ?

 Obj = (details.b'*details.dual + details.f'*details.dualeq);                                (1)
 optimize([details.A'*details.dual + details.E'*details.dualeq == details.c], -Obj);         (2)

Is the above optimization problem (1) & (2) equal to the dual problem of the primal one? If not, how to revise it？
Thank you very much.

Best regards,
Shuai

[Johan Löfberg]

looks right except you are missing non-negativity of duals

[Shuai Lu]

As I have described before, my problem is

     max min c'x                                                  (P1)

     s.t.     Ax <= b - Du   : λ1

               Ex == f - Fu    : λ2                           

               g(u) <= 0

wherein u is the outer decision variables and x is the inners.

Before, I have tried to use KKT method to render it but it seems impractical because the KKT method introduces many dual variables and constraints.

So, now I will try the dual method, i.e

     max -(b - Du)*λ1+(f - Fu)*λ2                             (P2)

     s.t.    -A* λ1+E*λ2=c

              λ1>=0

              g(u)<=0

So, using the kkt function, we can get that details.b = b - D*u and details.f = f - F*u.

But, I donnot know whether the sdpvars in details.b and details.f is the u of the primal problem or not.

How to give the constrints for u in the problem (P2)?

The constraints [-details.A'*details.dual + details.E'*details.dualeq == details.c 0<=details.dual<=M - M<=details.dualeq<= M g(u)<=0] seems not enough.

The u seems not correspond to the sdpvars details.b and details.f.

 

[Shuai Lu]

So, I hope to know the relationship of between the sdpvars in the details.b as well as details.f and u. Are they linked? If not, how to link them?

[Johan Löfberg]

but this is nothing better, as you essentially have derived the KKT conditions, but kept the nonconvex bilinear expressions explicitly, instead of ,modelling them using binary variables. This problem is just as hard.

[Shuai Lu]

Yes. As you said, there are bilinear expressions in the objective function of the dual problem. But the set of u has a special structure and the bilinear expressions can be converted to linear by introducing a few binary variables.

Owing to the sdpvars in the details.b and details.f are disordered. I donnot know their relationship with u. So I donnot know how to add the contraints g(u)<=0 in the dual problem. Is there any method?

[Johan Löfberg]

Don't understand what you are talking about when you talk about sdpvars and b (as b is a constant).

If you mean how the extracted model is ordered etc corresponding to your variables and constraints, that is not easy. You will simply have to figure that out by reverse engineering it. Typically, it would be in order of definition, but there is no promise on that in the functionality

[Shuai Lu]

 Owing to the u is variables, I used kkt([Ax <= b - Du Ex == f - Fu], Objective, u ), so there are some variables in the details.b and details.f  (I think these variables should be about u).

So, adding the constraints g(u)<=0 to the dual problem seems difficult, for that there is no clear relationship between u and the the variables in details.b and details.f.

Maybe I should conclude thest dual constraints Manually .

[Johan Löfberg]

to get the variable indicies of an expression, you use getvariables, and to see the basis that defines an expression in those variable indicies, you use getbase. From there, you will have to start to work with that low-level knowledge to match stuff

[Shuai Lu]

Ok, I will have a try. Thank you very much.

Best regards,

Shuai

[Shuai Lu]

Could you recommend some materials for me?

[Johan Löfberg]

there is no documentation on that you will have to experiment with simple expressions to understand what the numbers mean