双层规划

双层规划是一类带有最优反应约束的优化问题：上层先选一个决策，下层在看到它以后解决自己的优化问题，上层必须把这种反应算进去。企业定价后消费者如何选购、管理者规定资源后使用者如何调度，都具有这种先后结构。

与普通联合优化相比，关键限制是下层变量不能由上层任意指定。即使一对变量同时满足全部普通不等式，只要下层并不愿意选择其中的反应，它也不是双层问题的可行解。

反应集与数学模型

用 $x\in X$ 表示上层决策，$y$ 表示下层决策。下层目标为 $f(x,y)$，可行域为 $Y(x)$，定义最优反应集 $$S(x)={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{y\in Y(x)}f(x,y).$$ 取最小值写法时，一个基本双层模型为 $$\underset{x\in X,y\in S(x)}{min}F(x,y).$$ 这里的 $F$ 是上层目标，与 $f$ 可以完全不同。模型包含 $y\in S(x)$，不是仅包含 $y\in Y(x)$。

须先检查下层可行且最优值能取到。若下层无界或只有下确界而没有极小点，$S(x)$ 可以为空；这样的 $x$ 不能直接作为具有正常下层反应的可行决策。上层最优解存在还需要额外的紧性、闭性等条件，并非把上下层均写成线性式就自动有解。

当 $S(x)$ 不止一个元素时，上式允许选择其中使上层最有利的反应，称为乐观模型。对于没有额外反应依赖上层约束的基本情形，悲观模型则考虑 $$\underset{x\in X}{min}\underset{y\in S(x)}{sup}F(x,y).$$ 如果内层最大值能取到，可以把上确界写成最大值。两种约定代表不同的平局处理或承诺能力，必须在求解前说明。它们及单层等价转化的条件可参见Schmidt与Beck的讲义。

严格凸下层的完整算例

设 $0\le x\le 4$。下层在非负数中选择 $y$，使它尽量接近 $3-x$： $$\underset{y\ge 0}{min}\frac{1}{2}(y-(3-x){)}^2.$$ 无约束最小点是 $3-x$；若它为负，只能在可行边界零处取最小值。严格凸性保证反应唯一，因此 $$y^{\ast }(x)=max\{0,3-x\}.$$ 上层同时希望 $x$ 和下层反应都接近二，目标为 $$F(x,y)=(x-2{)}^2+(y-2{)}^2.$$

可行反应是一条折线。普通联合优化会误选二二，因为它忽略了下层在x等于二时只愿意选择y等于一。

把反应代回上层目标，而不是把两个目标相加： $$F(x,y^{\ast }(x))=\{\begin{array}{cc}2x^2-6x+5,& 0\le x\le 3,\\ (x-2{)}^2+4,& 3\le x\le 4.\end{array}$$ 第一段配方为 $$2(x-\frac{3}{2}{)}^2+\frac{1}{2},$$ 在 $x=3/2$ 取得最小值 $1/2$。第二段中 $x\ge 3$，故 $(x-2{)}^2\ge 1$，最小值为五，在三处取得。比较两段，得到 $$x^{\ast }=\frac{3}{2},y^{\ast }=\frac{3}{2},F^{\ast }=\frac{1}{2}.$$ 检验下层：$3-x^{\ast }=3/2\ge 0$，下层目标为零，确实是唯一最优反应。

若误作联合优化，会选 $(2,2)$ 并报告目标零；但此时下层选一可使自己的目标从 $1/2$ 降至零，故这对变量不满足最优反应约束。

上层偏好改变的变式

保留下层，把上层目标改为 $(x-2{)}^2+y^2$。在第一段代入反应，得到 $$(x-2{)}^2+(3-x{)}^2=2(x-\frac{5}{2}{)}^2+\frac{1}{2}.$$ 第二段的最小值为一，在 $x=3$ 处取得。因此新的双层最优解为 $(5/2,1/2)$，目标仍为 $1/2$。同一反应机制可以对应不同上层最优决策。

KKT转化的成立条件

本例的下层拉格朗日函数取为 $$ℒ(y,\lambda ;x)=\frac{1}{2}(y-(3-x){)}^2-\lambda y.$$ 其KKT条件为 $$\begin{array}{cc}y-(3-x)-\lambda & =0,\\ y\ge 0,\lambda \ge 0,\lambda y& =0.\end{array}$$ 若 $y>0$，互补条件给出 $\lambda =0$，所以 $y=3-x$；若 $y=0$，站立性给出 $\lambda =x-3\ge 0$。两种情形恰好重建上述反应。

对这个下层，目标严格凸、约束仿射，且存在严格可行点 $y>0$，KKT条件既必要又充分。因此可以把它们代入上层，得到等价的单层互补约束问题。转化后并未变成普通凸规划：乘积约束 $\lambda y=0$ 仍是非凸限制。

一般凸下层也需要认真核对可微性、约束资格及最优解存在等条件；“把下层目标求导等于零”远不够。带整数变量的下层不能直接以连续KKT条件代替。

非凸下层的站立点陷阱

令下层为 $$\underset{-2\le y\le 2}{min}(y^2-1{)}^2.$$ 导数是 $4y(y^2-1)$，所以零与正负一都是内部站立点；但下层目标在正负一为零，在零为一。真正的最优反应集只有 $\{-1,1\}$。

若上层要最小化 $F(y)=y^2$，真正最优值是一。只把下层站立性搬上来，会允许 $y=0$ 并误报最优值零。零甚至是下层的严格局部极大点，不能代表理性最小化反应。

站立性只检验一阶变化。非凸下层中，需要区分全部KKT点和全局最优反应。

多重反应与平局约定

取离散上层决策 $x\in \{0,1\}$，下层目标恒为零，约束 $0\le y\le 1$。于是两个上层决策的反应集均为整个单位区间。设 $$F(x,y)=(1-x)y+0.6x.$$ 当 $x=0$ 时，上层目标在反应集中可为零至一；当 $x=1$ 时，目标恒为 $0.6$。乐观约定在第一种情形选 $y=0$，故上层选零，值为零。悲观约定在第一种情形考虑 $y=1$，故上层改选一，值为 $0.6$。

这个差别由“下层有多个最优反应后怎样选择”造成。一次数值求解器随意返回其中一个反应，不能代替模型对此作出规定。

求解时，低维唯一反应可先解析消去；凸下层可在条件充分时采用KKT或最优值函数转化；离散下层通常需要专门分解或搜索。无论用何种算法，最终都应把候选上层决策固定，再独立解一次下层问题，检查报告的反应是否真正最优。