两阶段鲁棒优化及列和约束生成算法

两阶段鲁棒优化及列和约束生成算法

1. 前言

2. 两阶段RO

3. Benders对偶割平面法

4. 列和约束生成(C&CG)算法

5 存在的难点

1. 前言

有同学私信我两阶段鲁棒优化的问题，自己之前主要研究单阶段的鲁棒优化，对于两阶段优化不太懂。查了点资料，通过翻译和自己的理解，写下这篇博文，抛砖引玉，以供大家共同学习交流。

2. 两阶段RO

本文主要翻译自2013年Bo Zeng 博士的高被引论文《Solving two-stage robust optimization problems using a column-and-constraint generation method》[1]。

由于传统单阶段的鲁棒优化对于所有不确定性是完全免疫的，求出的结果一般过于保守、比较悲观。两阶段RO也称鲁棒可调优化或者自适应优化，它的引入就是为了应对传统RO存在的上述问题。两阶段RO是指，在作出第一阶段的决策和不确定性部分展现出来之后，再进行第二阶段的决策。 由于改进的建模能力，两阶段RO，广泛应用于网络/运输问题、投资组合优化和电力系统调度等问题。

文献[1]假设一阶段和二阶段决策问题都是线性规划，并且不确定性集合 U \bf U U是离散有限的点集或者多面体。使用 y \bf y y表示第一阶段决策变量， x \bf x x表示第二阶段决策变量， u ∈ U u \in \bf U u∈U表示不确定矢量。在此假设下的两阶段RO的一般形式为： min ⁡ y c T y + max ⁡ u ∈ U min ⁡ x ∈ F ( y , u ) b T x (1) \min_{\bf y } \bf c^{\rm T}y+\rm \max_{u \in \bf U} \min_{\bf x \in F(y,\rm u)} \bf b^{\rm T}x \tag{1} ymin​cTy+u∈Umax​x∈F(y,u)min​bTx(1) s . t . A T y ≥ d , y ∈ S y \rm s.t. \quad \bf A^{\rm T}y \geq d,y \in S_{y} s.t.ATy≥d,y∈Sy​

其中， F ( y , u ) = { x : G x ≥ h − E y − M u , x ∈ S x } \bf F(y,\rm u)=\{\bf x: Gx \geq h-Ey-M \rm u,\bf x \in S_{x}\} F(y,u)={

x:Gx≥h−Ey−Mu,x∈Sx​}， S y ⊆ R + n \bf S_{y}\subseteq \Bbb R_{+}^{n} Sy​⊆R+n​， S x ⊆ R + m \bf S_{x}\subseteq \Bbb R_{+}^{m} Sx​⊆R+m​，向量 c , b , d , h \bf c,b,d,h c,b,d,h和矩阵 A , G , E , M \bf A,G,E,M A,G,E,M都是确定性的数值，不确定性体现在向量 u u u上。注意到第二阶段优化的约束条件 F ( y , u ) \bf F(y,\rm u) F(y,u)是关于不确定性 u u u的线性函数。

两阶段RO有优势，当然有缺点。即便是最简单的两阶段RO，也可以是NP-hard问题，计算复杂度很高。为了减轻计算负担，一般有两种方法。第一种是使用近似算法，该种方法假设第二阶段的决策是关于不确定性的简单函数，例如仿射函数。第二种方法试图根据Benders分解得出精确解，即它们使用第二阶段决策问题的对偶解，逐步构造第一阶段决策的值函数（value function）。一般称为Benders对偶割平面算法。

3. Benders对偶割平面法

由于第二阶段的决策是关于 x \bf x x的线性规划问题，可以作以下假设（relatively complete recourse assumption）：该线性规划对于任意给定的 y \bf y y和 u u u是可行的，也即是有解 (该假设不是很理解)。假设第二阶段的线性规划的对偶变量为 π \pi π，则将其转化为对偶问题为： S P 1 : O ( y ) = max ⁡ u , π { ( h − E y − M u ) T π } (2) \rm {SP_{1}}: \mathcal O(\bf y) =\rm \max_{u,\pi} \{ \bf (h-Ey-M \rm u)^{T}\pi\} \tag{2} SP1​:O(y)=u,πmax​{

(h−Ey−Mu)Tπ}(2) s . t . G T π ≤ b , u ∈ U , π ≥ 0 s.t. \; \bf G^{\rm T}\pi \leq b, \rm u \in \bf U, \pi \geq \bf 0 s.t.GTπ≤b,u∈U,π≥0

在对偶问题中，目标函数从原始的最小化转换为关于对偶变量 π \pi π的最大化，同时与(1)式中的最大化 u u u合并，得到上述子问题(2)。此时不确定性向量转化为对偶问题(2)的决策变量，需要注意到子问题(2)是存在 u T π u^{T}\pi uTπ的双线性项。此时问题(2)被称为关于 u , π u,\pi u,π的双线性规划。对于双线性规划的求解，放在后面再说。

假设对于给定的 y k ∗ \bf y_{\mathit k}^{*} yk∗​，子问题(2) 的最优解为 ( u k ∗ , π k ∗ ) (u_{ k}^{*},\pi_{ k}^{*}) (uk∗​,πk∗​)，根据对偶定理，则可以构建以下割平面： η ≥ ( h − E y − M u k ∗ ) T π k ∗ (3) \eta \geq \bf (h-Ey-M \rm u_{\mathit k}^{*})^{T}\pi_{ \mathit k}^{*} \tag{3} η≥(h