【OR】YALMIP Bilevel规划_solvebilevel

Bilevel Programming

YALMIP有内置求解器处理bilevel programming问题.

You can of course set them up yourself, by manually deriving the KKT conditions and solving them using various techniques in YALMIP, or by using YALMIP high-level kkt operator

KKT conditions in bilevel programming

YALMIP可以求解的bilevel programming问题需要具有如下leader-follower结构
min ⁡ f ( x , y ∗ ) s . t . ( x , y ∗ ) ∈ C y ∗ = arg ⁡ min ⁡ 1 2 [ x y ] T [ H 1 H 2 H 2 T H 3 ] [ x y ] + [ e 1 T e 2 T ] [ x y ] s . t . [ ] s . t . [ F 1 F 2 ] [ x y ] ≤ h \min f(x, y^*)\\ s.t. \quad (x, y^*)\in\mathcal{C}\\ y^*=\arg\min \frac{1}{2} \left[

$$\begin{matrix} x\\ y \end{matrix}$$ \right]^T \left[ $$\begin{matrix} H_1 & H_2\\ H_2^T & H_3 \end{matrix}$$ \right] \left[ $$\begin{matrix} x\\ y \end{matrix}$$ \right]+ \left[ $$\begin{matrix} e_1^T & e_2^T \end{matrix}$$ \right] \left[ $$\begin{matrix} x\\ y \end{matrix}$$ \right]\\ s.t.\quad \left[ $$\begin{matrix} \end{matrix}$$ \right]\\ s.t. \left[ $$\begin{matrix} F_1\quad F_2 \end{matrix}$$ \right] \left[ $$\begin{matrix} x\\ y \end{matrix}$$ \right]\leq h minf(x,y∗)s.t.(x,y∗)∈Cy∗=argmin21​[xy​]T[H1​H2T​​H2​H3​​][xy​]+[e1T​​e2T​​][xy​]s.t.[]s.t.[F1​F2​​][xy​]≤h
内部QP问题求解变量$y$，外部问题可以是YALMIP可处理的任意形式.

The bilevel solver that is available in YALMIP replaces the optimality condition on $y^{\ast }$ with the KKT conditions.

{ H 3 y + H 2 T x + e 2 − F 2 T λ = 0 λ ≥ 0 h − F 1 x − F 2 y ≥ 0 λ T ( h − F 1 x − F 2 y ) = 0 \left\{

$$\begin{aligned} &H_3y+H_2^Tx+e_2-F_2^T\lambda =0\\ &\lambda \geq 0\\ &h-F_1x-F_2y\geq 0\\ &\lambda^T(h-F_1x-F_2y)=0 \end{aligned}$$ \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​H3​y+H2T​x+e2​−F2T​λ=0λ≥0h−F1​x−F2​y≥0λT(h−F1​x−F2​y)=0​

Bilevel linear and quadratic programming

定义外部变量(leader variable)$x$和内部变量(follower variable)$y$

sdpvar x1 x2
sdpvar y1 y2 y3
1
2

定义外部约束和目标函数

% outer constraint and objective
OO = -8*x1-4*x2+4*y1-40*y2+4*y3;
CO = [[y1 y2 y3]>=0, [x1 x2]>=0];
1
2
3

定义内部约束和目标函数

OI = x1 + 2*x2 + y1 + y2 + 2*y3;
CI = [-y1 + y2 + y3 <= 1,
      2*x1 - y1 + 2*y2 - 0.5*y3 <= 1,
      2*x2 + 2*y1 - y2 - 0.5*y3 <= 1,
                     [y1 y2 y3] >= 0,
                        [x1 x2] >= 0];
1
2
3
4
5
6

定义好优化问题的结构后，需要调用bilevel solver并且告诉求解器那些变量是内部变量.

% solve
solvebilevel(CO, OO, CI, OI, [y1 y2 y3]);
value([y1 y2 y3])
1
2
3

Adding additional complicating constraints is allowed, as long as YALMIP can identify a solver which is capable of solving the outer problem appended with KKT conditions, excluding the nonconvex complementary slackness.

加入整数约束求解(貌似无法求解)

%% integer
solvebilevel([CO, integer(y2)], OO, CI, OI, [y1 y2 y3]);
value([y1 y2 y3])
1
2
3

目标函数转为QP形式求解

%% qp form
solvebilevel(CO, OO+OO^2, CI, OI^2, [y1 y2 y3]);
value([y1 y2 y3])
1
2
3

Bilevel programming with general problem

A strong feature of the built-in solver is that it builds upon the infrastructure in YALMIP, and easily hooks up to almost any kind of outer problem.

%%
CO = [[y1 y2 y3]>=0, [x1 x2]>=0];
CO = [CO, [1 x1+x2; x1+x2 1/2]>=0];
solvebilevel(CO, OO, CI, OI, [y1 y2 y3]);
value([y1 y2 y3])
1
2
3
4
5

bilevel solver限制内部问题必须为convex quadratic，但是外部问题不需要满足convexity.

The bilevel solver solves the outer problem repeatedly in a branch-and-bound procedure, with additional equality constraints derived from complementary slackness appended.

%%
OO = -8*x1 - 4*x2 + 4*y1 - 40*y2 + 4*y3;
CO = [[y1 y2 y3] >= 0,[x1 x2] >= 0];
OI = x1 + 2*x2 + y1 + y2 + 2*y3;
CI = [-y1 + y2 + y3 <= 1,
      2*x1 - y1 + 2*y2 - 0.5*y3 <= 1,
      2*x2 + 2*y1 - y2 - 0.5*y3 <= 1,
                     [y1 y2 y3] >= 0,
                        [x1 x2] >= 0];
ops = sdpsettings('bilevel.outersolver','bmibnb');
solvebilevel(CO,OO-OO^2,CI,OI,[y1 y2 y3],ops);

value([y1 y2 y3])
1
2
3
4
5
6
7
8
9
10
11
12
13

References

Bilevel programming