The values of the dualbounds are all 0 in the inner problm of my MaxMin problem.

[Shuai Lu]

Dear Prof. Löfberg,
I tried to solve a bilevel problem as follows:

Maxmin f(x,u)
s.t. g(x,u)<=0
     h(x,u) = 0

f, g, and h are all linear. The decision variables of the inner problem are x and that of the outer problem are u.
I used the kkt function to obtain the kkt conditions of the inner problem, i.e. [K,details] = kkt( [g(x,u) <= 0, h(x,u) == 0], f(x,u), x ). The  results shown is as follows:

Removed 864 duplicated or redundant inequalities
Starting derivation of dual bounds (can be turned off using option kkt.dualbounds)
*Computing 2617 primal bounds (required for dual bounds)
*Computing 4231 dual bounds
*Success: All dual upper bounds are finite
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|   ID|                       Constraint|                                             Tag|
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|   #1|       Complementarity constraint|   Compl. slackness and primal-dual inequalities|
|   #2|       Equality constraint 2215x1|                                 Primal feasible|
|   #3|   Element-wise inequality 4231x1|                            Upper bound on duals|
|   #4|       Equality constraint 2617x1|                                    Stationarity|
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

details =

            info: 'min c'x s.t. Ax<b, Ex=f'
               c: [2617x1 double]
               Q: [2617x2617 double]
               A: [4231x2617 double]
               b: [4231x1 double]
               E: [2215x2617 double]
               f: [2215x1 double]
            dual: [4231x1 sdpvar]
          dualeq: [2215x1 sdpvar]
          primal: [2617x1 sdpvar]
    inequalities: [1x1 constraint]
      equalities: [1x1 constraint]
      dualbounds: [4231x1 double]

However, the values of the dualbounds are all 0 and I donnot know why. Then I calculated this bilevel problem by  solvesdp( [ g(x,u) <= 0, h(x,u) == 0, K], -f(x,u) ), the results of which is feasible.
I greatly appreciate your help!

Best,
Shuai

[Johan Löfberg]

You would have to supply a reproducible example

[Johan Löfberg]

The inner constraints are not even feasible...

optimize([In_Cons])

Academic license - for non-commercial use only

Optimize a model with 7310 rows, 2617 columns and 12288 nonzeros

Coefficient statistics:

  Matrix range     [8e-05, 6e+03]

  Objective range  [0e+00, 0e+00]

  Bounds range     [0e+00, 0e+00]

  RHS range        [2e-04, 5e+05]

Presolve removed 292 rows and 168 columns

Presolve time: 0.03s

Solved in 0 iterations and 0.04 seconds

Infeasible model

ans = 

  struct with fields:

    yalmiptime: 0.4460

    solvertime: 0.0710

          info: 'Infeasible problem (GUROBI-GUROBI)'

       problem: 1

[Johan Löfberg]

this is trivially infeasible (look at the data...)

Cons = ((1-ratio_uncertainty)*Tau_Building_amb <= Tau_Building_amb_var <= (1+ratio_uncertainty)*Tau_Building_amb);

optimize(Cons)

[Shuai Lu]

Yes.

The direction of the this constraint is opposite and it should be

Cons = ((1+ratio_uncertainty)*Tau_Building_amb <= Tau_Building_amb_var <= (1-ratio_uncertainty)*Tau_Building_amb);

Now this problem is feasible and I am solving the kkt conditions.

It is so magical that you found this infeasible constraint quicky. Can you tell me how you do? Thank you very much.

[Johan Löfberg]

Add constraints until it becomes infeasible. In this case, it immediately became infeasible, so trivial

As always in debugging. Simplify, clean, reduce, and simplify more

[Shuai Lu]

I see. It is indeed a good way. Thank you.

You see in my problem, the constraints in the inner problem are too many. The calculation of the kkt conditions consumes much time. Are there some other methods to deal with such a problem?

[Johan Löfberg]

As it says, you probably have to turn off dualbounds and add manual upper bounds, if you re talking about the derivation of the kkt condition

If you are talking about bilevel problems in general (your problems appears intractably large), it is not my field of expertise, but it is generally intractable so don't expect that there is some magic way to solve it

[Shuai Lu]

I see. Thank you for your help.

[Shuai Lu]

Dear Prof. Löfberg,

I am sorry to disturb you again.

The attachment is the updated file. Now the inter problem is feasible as the line #106 in this file. But the K constraints produced by kkt function is still infeasible as the line #121. The decision variables of the inner problem have been ensured. Could you help me in this problem? . 

Regards,

Shuai

[Johan Löfberg]

I don't see anything, too large and complicated model. Maybe the dual variables are huge in all optimal solutions, and YALMIPs default bounds of 1e4 will render the problem infeasible or something like that. Or there is a bug in the kkt operator...or the bilevel problem is ill-posed somehow

This is feasible (stationarity removed, complementarity and feasibility kept)

optimize([K([1 3])])

[Johan Löfberg]

parameters in kkt is supposed to be a vector. You are sending a cell, which doesn't work

[Shuai Lu]

Yes, I am sending a cell as a parameter. The rows of the variables in the inner problem are not the same so I cannot put them in one vector. This is indeed a headache problem。

[Johan Löfberg]

you simply put them all in one long vector [a(:);b(:)...

[Johan Löfberg]

and the parameters in a kkt is not the inner variables, but the outer variables

[Shuai Lu]

OK. I will have a try. Thank you very much.

[Shuai Lu]

Dear Prof. Löfberg,

Now, my inner problem is feasible but the kkt constraints is infeasible. As you said, YALMIP's default bounds of 1e4 may render the problem infeasible, so I want to try if it is. How can I modify this bounds?

Best,
Shuai

[Johan Löfberg]

The model looks weird as Q_Building_delta is part of the inner objective,is not a parameter and is not constrained in any sense, hence the objective is unbounded, and kkt should be infeasible

[Shuai Lu]

Dear Professor,

There are some constraints on Q_Building_delta in the file "BuildingsModel_2.m".

In addtion,  solvesdp(In_Cons+Out_Cons, In_Object) is also feasible.

So I think it should not caused by Q_Building_delta.

[Shuai Lu]

solvesdp(In_Cons, In_Object) is also feasible.

[Johan Löfberg]

the problem is likely that your dual variables are very large in any optimal solution due to some scaling in your model). YALMIPs default bounds when none are detected are 1e4, and that is too small.

The problem appears to become feasible i(at least not trivially infeasible) if I edit modelComplementarityConstraints and replace M1 and M2 on line 19 with 100*M1 and 100*M2

[Johan Löfberg]

maybe not 

the problem remains infeasible even if we supply huge dual bounds

optimize([K,details.dual <= 1e7])

The problem is that there are no explicit bounds on all primal variables in the inner problem, so the big-M model for comp,ementarity has no good big-M value, and thus default value 1e4 is used, which is too small. Adding primal bounds and it works

optimize([K,recover(depends(In_Cons)) <= 1e6])

It is up to you come up with a good small but large enough upper bound, or better yet specific bounds on individual variables

[Shuai Lu]

What is the meaning of "recover(depends(In_Cons)) <= 1e6"? Does it bounds the variables with 1e6 in the inner problem?


[Shuai Lu]

Dear Prof. Löfberg,

Owing to the KKT method introduces too many dual variables and Increases the scale of the problem, it is very slow to solve it.

Now I want to try the dual method that converts the inner problem into its dual problem. The original problem is as

Maxmin Ax+Bu
s.t. Cx = D - Eu

      Fx <= G - Hu

x is the inner variables and u is the outer variables.

The orginal problem can be transformed as

Max (D-Eu)*λ1+(G-Hu)*λ2

s.t    λ2 <= 0

       C*λ1+F*λ2 = A

However, writing this constraints manually is fussy and heavy. Is there any function in the Yalmip to obtain these dual constraints directly?

    

[Johan Löfberg]

you've got the data in the details output

note, don't reinvent the wheel. YALMIP has support for robust worst-case optimization, if that is what you are trying to do

[Shuai Lu]

Dear Prof. Löfberg,

My problem is

max min f(x,u)

where u is variables in the outer problem and it is in a uncertainty set.

The robust optimization in the yalmip is as

min max f(x,u)

where u is variables in the inner problem.

So I think it they are not the same problem and the robust solver in yalmip is not suitable.