I have a problem with two-layer optimization (call one optimizer when defiing the other optimization problem).

[Renjie Li]

Dear Johan,

What I want to do is to optimize one problem, of which the constraints contain another optimization problem.

The code is as below:

========================================================

%% Two-layer optimization

clear;clc;

r = sdpvar(2,1);

x = sdpvar([2,2],[1,1]);

u = sdpvar(1,1);

% Optimization problem 1

Objective_1 = (x{2}-r)'*(x{2}-r); 

Constraints_1 = [x{2} == 2*x{1}+[2;3]*u];

Opt_1 = optimizer(Constraints_1,Objective_1,[],{x{1},r},u);

optu_1 = Opt_1{{[0;0],[2;3]}}; % problem 1 can be solved very well

% Optimization problem 2

Objective_2 = (x{2}-r)'*(x{2}-r);

Constraints_2 = [x{2} == 2*x{1}+[2;3]*(u+Opt_1{{x{2},r}})]; % contraints of problem 2 contains optimizer 1

Opt_2 = optimizer(Constraints_2,Objective_2,[],{x{1},r},u);

optu_2 = Opt_2{{[0;0],[2;3]}};

========================================================

The error message is like this:

Adding NaN to an SDPVAR makes no sense.

Constraints_2 = [x{2} == 2*x{1}+[2;3]*(u+Opt_1{{x{2},r}})]; % contraints of problem 2 contains optimizer 1

I believe there is something wrong with the overloading of '+' between 'u' and 'Opt_1{{x{2},r}}'. Do you have any clue that I can make this two-layer optimization possible?

If I make x defined as a matrix rather than a cell array, it still doesn't help:

========================================================

%% Two-layer optimization 2

clear;clc;

r = sdpvar(2,1);

x = sdpvar(2,2,'full');

u = sdpvar(1,1);

% Optimization problem 1

Objective_1 = (x(:,2)-r)'*(x(:,2)-r); 

Constraints_1 = [x(:,2) == 2*x(:,1)+[2;3]*u];

Opt_1 = optimizer(Constraints_1,Objective_1,[],{x(:,1),r},u);

optu_1 = Opt_1{{[0;0],[2;3]}}; % problem 1 can be solved very well

% Optimization problem 2

Objective_2 = (x(:,2)-r)'*(x(:,2)-r);

Constraints_2 = [x(:,2) == 2*x(:,1)+[2;3]*(u+Opt_1{{x(:,2),r}})]; % contraints of problem 2 contains optimizer 1

Opt_2 = optimizer(Constraints_2,Objective_2,[],{x(:,1),r},u);

optu_2 = Opt_2{{[0;0],[2;3]}};

========================================================

But if I make the two-layer optimization problem simpler, it would work:

========================================================

%% Two-layer optimization 3

clear;clc;

r = sdpvar(2,1);

x = sdpvar(2,1);

% Optimization problem 1

Objective_1 = (x-r)'*(x-r); 

Constraints_1 = [x(2) == 2*x(1)];

Opt_1 = optimizer(Constraints_1,Objective_1,[],r,x(1));

optu_1 = Opt_1{[2;3]};

% Optimization problem 2

Objective_2 = (x-r)'*(x-r); 

Constraints_2 = [x(2) == 2*x(1)+Opt_1{r}]; % contraints of problem 2 contains optimizer 1

Opt_2 = optimizer(Constraints_2,Objective_2,[],r,x);

optu_2 = Opt_2{[3;4]};

% Problem 2 can be solved

========================================================

Looking forward to your answer. I will appreciate it very much! 

Renjie

[Johan Löfberg]

Using optimizer objects in this bilevel setting is not officially supported and is experimental, and as you see, still buggy.

However, if you want to solve this bilevel problem, it is a bilevel convex QP, so you should be able to write it as such (although I fail to see the  relevance of posing an MPC computation this way, considering the intractability of bilevel programming, but perhaps you are doing something else)

https://yalmip.github.io/tags/#bilevel-programming

[Renjie Li]

Dear Johan,

Following your suggestions, I have tried using solvebilevel to solve the following leader-follower game:

============================================================================

%% Two-layer optimization

clear;clc;

yalmip('clear')

r = sdpvar([2,2],[1,1]); % reference

x = sdpvar([2,2,2],[1,1,1]); % state

u_A = sdpvar([1,1],[1,1]); % follower input 

u_D = sdpvar([1,1],[1,1]); % leader input

% Optimization problem 1 (of follower)

Objective_1 = (x{2}-r{1})'*(x{2}-r{1})+(x{3}-r{2})'*(x{3}-r{2})+u_A{1}'*u_A{1}+u_A{2}'*u_A{2}; 

Constraints_1 = [x{2} == 2*x{1}+[2;3]*(u_A{1}+u_D{1}),x{3} == 2*x{2}+[2;3]*(u_A{2}+u_D{2})];

Constraints_1 = [Constraints_1,x{1} == [0;0],r{1} == [1;1],r{2} == [2;2]];

% Optimization problem 2 (of leader)

Objective_2 = (x{2}-r{1})'*(x{2}-r{1})+(x{3}-r{2})'*(x{3}-r{2})+u_D{1}'*u_D{1}+u_D{2}'*u_D{2}; 

Constraints_2 = [x{2} == 2*x{1}+[2;3]*(u_A{1}+u_D{1}),x{3} == 2*x{2}+[2;3]*(u_A{2}+u_D{2})]; 

Constraints_2 = [Constraints_2,x{1} == [0;0],r{1} == [1;1],r{2} == [2;2]];

solvebilevel(Constraints_1,Objective_1,Constraints_2,Objective_2,u_A);

============================================================================

The error message is "undefined variable 'y_var'". Do you have any clue how to solve this leader-follower game using solvebilevel. Thank you very much!

[Johan Löfberg]

the inner variables should be a vector, not a cell

It will crash though as it expects inequalities in the model, so to have it run you would have to add some (redundant)

Since the inner problem is an equality-constrained QP, you can solve it analytically and simply plug into the outer program. Going via bilevel optimization is a massive overkill

[Renjie Li]

Dear Johan, 

Thank you for your quick response! I've changed the inner variables to vector format and added an inequaliti constraint as you suggested. But there is still some bug. Should I change all the varialbles of the inner problem into vectors, including x and r? 

I am aware that there is an analytical solution for the inner problem. But the problem I am really working on is more complicated than the present one, so I think it would be a good start if I can solve this basic problem at first. 

============================================================================

%% Two-layer optimization

clear;clc;

yalmip('clear')

r = sdpvar([2,2],[1,1]); % reference

x = sdpvar([2,2,2],[1,1,1]); % state

u_A = sdpvar(2,1); % follower input 

u_D = sdpvar(2,1); % leader input

% Optimization problem 1 (of follower)

Objective_1 = (x{2}-r{1})'*(x{2}-r{1})+(x{3}-r{2})'*(x{3}-r{2})+u_A(1)^2+u_A(2)^2; 

Constraints_1 = [x{2} == 2*x{1}+[2;3]*(u_A(1)+u_D(1)),x{3} == 2*x{2}+[2;3]*(u_A(2)+u_D(2))];

Constraints_1 = [Constraints_1,x{1} == [0;0],r{1} == [1;1],r{2} == [2;2]];

Constraints_1 = [Constraints_1,u_A >= 0];

% Optimization problem 2 (of leader)

Objective_2 = (x{2}-r{1})'*(x{2}-r{1})+(x{3}-r{2})'*(x{3}-r{2})+u_D(1)^2+u_D(2)^2; 

Constraints_2 = [x{2} == 2*x{1}+[2;3]*(u_A(1)+u_D(2)),x{3} == 2*x{2}+[2;3]*(u_A(2)+u_D(2))]; % contraints of problem 2 contains optimizer 1

Constraints_2 = [Constraints_2,x{1} == [0;0],r{1} == [1;1],r{2} == [2;2]];

solvebilevel(Constraints_1,Objective_1,Constraints_2,Objective_2,u_A);

===========================================================================

[Johan Löfberg]

You've switched the order on outer an inner problem (outer first)

solvebivel works here, but in general using the KKT operator and rely on a MIQP solver is more efficient

https://yalmip.github.io/command/kkt/

[Renjie Li]

Dear Johan,

Thank you for pointing out my stupid mistake :p 

Could explain more specifically how to use KKT and MIQP to solve this leader-follower game? As I can see from https://yalmip.github.io/command/kkt/, the KKT operator can only take one constraint set and one objective function.

One more question, is it possible to make solvebivel receive arguments like optimizer such that I can solve the leader-follower game with arbitrary intial condition x{0} and reference r? For the time being I can only define the initial condition and reference within the constraints. 

Best Regards.

[Johan Löfberg]

A bilevel solution using kkt is illustrated on the kkt page. Simply compute kkt conditions of inner problem with outer variables as parameters, and add that model to the outer model.

You can have what ever you want as parameters, as long as the inner problem is a convex QP

solvebilevel can only only handle inner convex QP , outer problem is arbitrary. Same things if you use manual approach with kkt operator

[Mark L. Stone]

It looks like there are typos in help solvebilevel.

>>  help solvebilevel
 solvebilevel Simple global bilevel solver
 
    min        CO(x,y)
    subject to OO(x,y)>0
               y = arg min OI(x,y)
               subject to CI(x,y)>0
 
    [DIAGNOSTIC,INFO] = solvebilevel(CO, OO, CI, OI, y, options)
 
    diagnostic : Struct with standard YALMIP diagnostics
    info       : Bilevel solver specific information
 
    Input
       CI       : Outer constraints (linear elementwise)
       OI       : Outer objective (convex quadratic)
       CI       : Inner constraints (linear elementwise)
       OI       : Inner objective (convex quadratic)
       y        : Inner variables
       options  : solver options from SDPSETTINGS.
...

I think the first two lines of Input should be:

       CO       : Outer constraints (linear elementwise)
       OO       : Outer objective (arbitrary)

[Johan Löfberg]

indeed, thank you