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
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[H1H2TH2H3][xy]+[e1Te2T][xy]s.t.[]s.t.[F1F2][xy]≤h 内部QP问题求解变量 y y y，外部问题可以是YALMIP可处理的任意形式.
The bilevel solver that is available in YALMIP replaces the optimality condition on y ∗ y^* y∗ 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. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧H3y+H2Tx+e2−F2Tλ=0λ≥0h−F1x−F2y≥0λT(h−F1x−F2y)=0
定义外部变量(leader variable) x x x和内部变量(follower variable) y y y
sdpvar x1 x2 sdpvar y1 y2 y3定义外部约束和目标函数
% outer constraint and objective 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];定义好优化问题的结构后，需要调用bilevel solver并且告诉求解器那些变量是内部变量.
% solve solvebilevel(CO, OO, CI, OI, [y1 y2 y3]); value([y1 y2 y3])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])目标函数转为QP形式求解
%% qp form solvebilevel(CO, OO+OO^2, CI, OI^2, [y1 y2 y3]); value([y1 y2 y3])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])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])Bilevel programming
