决策依赖模糊集下的分布鲁棒优化的重构

Reconstruction of Distributed Robust Optimization under Decision-Dependent Ambiguity Set

摘要: 本文考虑一类分布鲁棒优化问题，其中随机变量的概率分布依赖于决策变量。模糊集由带有参数均值和协方差矩阵的集合定义，且不确定参数的均值与决策相关。当支撑集为全空间时，本文利用Lagrange对偶理论证明了原问题等价于半定规划问题，且可以转化成形式更简单的非光滑凸问题，进而可得到为更易处理的二阶锥优化问题。

Abstract: In this paper we consider a class of Distributionally Robust Optimization (DRO) Problems where the probability distribution of random variables depends on decision variables and the ambiguity set is defined through a set with parameter mean and covariance matrix, and the mean of uncertain pa-rameters is dependent on decision. Under the condition of the support set is the whole space, We demonstrate the original problem is equivalent to the semidefinite programming problem by using Lagrange duality theory. Moreover, it can be transformed into a simpler form of non-smooth convex problem, and we further obtain a more tractable second-order cone optimization.

1. 引言

考虑下述分布鲁棒优化问题

$\underset{x\in X}{\min }\underset{P\in U\left(x\right)}{\max }{{\rm E}}_P\left[f\left(x,\xi \right)\right]$ (1.1)

其中X是 ${ℝ}^n$ 上的闭集， $f:{ℝ}^n\times {ℝ}^k\to ℝ$ 是连续函数， $\xi :\Omega \to \Xi$ 是定义在可测空间 $\left(\Omega ,\mathcal{F}\right)$ 上的随机变量，它的概率分布P以 $\Xi \subset {ℝ}^k$ 为支撑。 $U\left(x\right)$ 是包含随机变量 $\xi$ 的真实概率分布P的随机分布集合，且该集合于决策相关， ${{\rm E}}_P[\cdot ]$ 表示关于 $P\in U\left(x\right)$ 的数学期望。显然，这个模型中的关键是概率分布集 $U\left(x\right)$ ，我们称之为模糊集。在早期的研究中，学者们普遍假设不能获得随机变量的真实概率分布，只能知道局部的矩条件，并且这些条件独立于决策变量，在此基础上，可以构建模糊集来解决优化问题。Bertsima，Popescu [1] 考虑了随机变量 $\xi$ 的均值和协方差矩阵，以此建立模糊集：

$U_1=\left\{P\in \Gamma |\begin{array}{c}P\left(\xi \in \Xi \right)=1\\ {{\rm E}}_P\left[\xi \right]=\mu \\ {{\rm E}}_P\left[\left(\xi -\mu \right){\left(\xi -\mu \right)}^{{\rm T}}\right]=\Sigma \end{array}\right\}$ (1.2)

其中 $\Gamma$ 表示 $\left(\Omega ,\mathcal{F}\right)$ 空间中所有概率测度的集合，但是他们也证明了在模糊集 $U_1$ 下的模型是难以处理的。随后，Wiesemann，Kuhn，Sim [2] 等人将 $U_1$ 中的 $\Sigma$ 改为协方差的上界，得到了新的模糊集：

$U_2=\left\{P\in \Gamma |\begin{array}{c}P\left(\xi \in \Xi \right)=1\\ {{\rm E}}_P\left[\xi \right]=\mu \\ {{\rm E}}_P\left[\left(\xi -\mu \right){\left(\xi -\mu \right)}^{{\rm T}}\right]\preccurlyeq \Sigma \end{array}\right\}$ (1.3)

并证明了在模糊集 $U_2$ 下的线性鲁棒优化问题是可处理的。Delage，Ye [3] 则在 $U_1$ 的基础上进一步作出改进，令 $r_1\ge 0,r_2\ge 1$ ，且 $\delta >0$ 是已知的参数，则得到下列模糊集：

$U_3=\left\{P\in \Gamma |\begin{array}{c}P\left(\xi \in \Xi \right)=1\\ {\left({{\rm E}}_P\left[\xi \right]-\mu \right)}^{{\rm T}}{\Sigma }^{-1}\left({{\rm E}}_P\left[\xi \right]-\mu \right)\le r_1\\ {{\rm E}}_P\left[\left(\xi -\mu \right){\left(\xi -\mu \right)}^{{\rm T}}\right]\preccurlyeq r_2\Sigma \end{array}\right\}$ (1.4)

并证明了在适当的条件下真概率测度 $P_0\in U_3$ 的置信度 $\alpha \ge 1-\delta$ 。刘强 [4] 以模糊集 $U_3$ 为基础，讨论了基于一阶矩和二阶矩信息的不确定分布及的分布鲁棒优化问题，值得注意的是，支撑集 $\Xi$ 在分布鲁棒优化的重构问题的可处理性上有着重要影响。

在以上这些工作中，概率测度的分布集合都与决策无关。但在实际问题中，往往需要考虑决策变量对模糊集的影响，Zhang等人 [5] 考虑了一类模糊集依赖于决策变量x的分布鲁棒优化模型，并对其进行定量稳定性分析。其中模糊集表示为：

$U_4\left(x\right)=\left\{P\in \Gamma |{{\rm E}}_P\left[\Psi \left(x,\xi \right)\right]\in {\rm K}\right\}$ (1.5)

这里 $\Psi$ 是具有可测随机分量的向量或矩阵的随机映射， $\Psi$ 的取值依赖于x，K是闭凸锥；石楠 [6] 考虑了仅可估计参数均值的情况，并假设均值与决策相关，以此构建了决策相关的模糊集。这类问题在实际应用中非常广泛，例如，Basciftci等人 [7] 考虑到选址决策会影响客户需求，从而提出了一个需求不确定性下的分布鲁棒设施选址问题；Doan [8] 考虑了决策相关模糊集下的分布鲁棒优化及其在改造规划中的应用。

本文结合 $U_3$ 和 $U_4\left(x\right)$ 两个集合，构造了一个全新的模糊集，它类似 $U_3$ 且随机变量的概率分布与决策变量相关，该集合含如下矩信息：

$U\left(x\right)=\left\{P\in \Gamma |\begin{array}{c}P\left(\xi \in \Xi \right)=1\\ {{\rm E}}_P\left[\xi \right]\in \left[A_{m\times n}x,B_{m\times n}x\right]\\ {{\rm E}}_P\left[\xi {\xi }^{{\rm T}}\right]\preccurlyeq \Sigma \end{array}\right\}$ (1.6)

其中 $\Xi$ 是 ${ℝ}^m$ 上的闭凸集， $A_{m\times n},B_{m\times n}$ 是 $m\times n$ 阶矩阵。

本文的剩余部分如下，第2章讨论了在(1.6)的条件下，问题(1.1)的等价形式，使原问题更易处理；第3章考虑了当支撑集 $\Xi$ 是全空间时，原问题可转化为半定规划；第4章在第3章的条件下进一步证明了半定规划可转化为二阶锥规划。

2. 原问题的重新表示

本章给出了问题(1.1)在模糊集(1.6)的条件下的重新表示。首先，我们给定 $f\left(x,\xi \right)$ 的具体表达，定义 $f\left(x,\xi \right)=c^{{\rm T}}x+{\left(E_{m\times n}x\right)}^{{\rm T}}\xi$ ，令：

$h\left(x,{\alpha }_0,\alpha ,Y\right)=\underset{\xi \in {\rm E}}{\sup }\left\{f\left(x,\xi \right)-{\alpha }_0-{\alpha }^{{\rm T}}\xi -{\xi }^{{\rm T}}Y\xi \right\}.$ (2.1)

我们可以得到问题(1.1)的重新表示：

命题2.1：问题(1.1)可以重新表示为下面的约束优化问题

$\begin{array}{l}\min {\alpha }_0+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+\langle \Sigma ,Y\rangle \\ \text{s}\text{.t}\text{.}h\left(x,{\alpha }_0,\alpha ,Y\right)\le 0,\\ x\in X,Y\succcurlyeq 0.\end{array}$ (2.2)

其中 ${\alpha }_{+}=\max \left\{\alpha ,0\right\}$ 。

证明：定义问题(1.1)的内极大问题 $p\left(x\right)=\underset{P\in U\left(x\right)}{\max }{{\rm E}}_P\left[f\left(x,\xi \right)\right]$ ，令

$U\left(\mu \left(x\right)\right)=\left\{P\in \Gamma |P\left(\xi \in \Xi \right)=1,{{\rm E}}_P\left[\xi \right]=\mu \left(x\right),{{\rm E}}_P\left[\xi {\xi }^{{\rm T}}\right]\preccurlyeq \Sigma \right\},$

$\Psi \left(x,\mu \left(x\right)\right)=\underset{P\in U\left(\mu \left(x\right)\right)}{\max }{{\rm E}}_P\left[f\left(x,\xi \right)\right].$

故而

$p\left(x\right)=\max \left\{\Psi \left(x,\mu \left(x\right)\right):\mu \left(x\right)\in \left[A_{m\times n}x,B_{m\times n}x\right]\right\}.$ (2.3)

由模糊集(1.6)的结构，可以写出下述内极大问题，即

$\begin{array}{l}\underset{\text{d}P\left(\xi \right)\ge 0}{\max }{\displaystyle {\int }_{\Xi }f\left(x,\xi \right)\text{d}P\left(\xi \right)}\\ \text{s}\text{.t}\text{.}{\displaystyle {\int }_{\Xi }\text{d}}P\left(\xi \right)=1,\\ {\displaystyle {\int }_{\Xi }\xi \text{d}}P\left(\xi \right)=\mu \left(x\right),\\ {\displaystyle {\int }_{\Xi }\xi {\xi }^{{\rm T}}\text{d}}P\left(\xi \right)\preccurlyeq \Sigma .\end{array}$ (2.4)

且 $\Psi \left(x,\mu \left(x\right)\right)$ 是问题(2.4)的最优值。进一步，(2.4)的Lagrange函数为

$\begin{array}{c}L\left(\text{d}P,{\alpha }_0,\alpha ,Y\right)={\displaystyle {\int }_{\Xi }f\left(x,\xi \right)\text{d}}P\left(\xi \right)-{\alpha }_0\left({\displaystyle {\int }_{\Xi }\text{d}}P\left(\xi \right)-1\right)-{\left({\displaystyle {\int }_{\Xi }\xi \text{d}}P\left(\xi \right)-\mu \left(x\right)\right)}^{{\rm T}}\alpha -{\left({\displaystyle {\int }_{\Xi }\xi {\xi }^{{\rm T}}\text{d}}P\left(\xi \right)-\Sigma \right)}^{{\rm T}}Y\\ ={\alpha }_0+\mu {\left(x\right)}^{{\rm T}}\alpha +\langle \Sigma ,Y\rangle +{\displaystyle {\int }_{\Xi }\left[f\left(x,\xi \right)-{\alpha }_0-{\alpha }^{{\rm T}}\xi -{\xi }^{{\rm T}}Y\xi \right]\text{d}}P\left(\xi \right).\end{array}$

其中 ${\alpha }_0,\alpha ,Y$ 分别为对应的Lagrange乘子。由Shapiro [9] 对偶理论可得，

$\begin{array}{l}\Psi \left(x,\mu \left(x\right)\right)=\underset{{\alpha }_0,\alpha ,Y\succcurlyeq 0}{\min }\underset{P\left(\xi \right)\ge 0}{\max }L\left(\text{d}P,{\alpha }_0,\alpha ,Y\right)=\underset{{\alpha }_0,\alpha ,Y\succcurlyeq 0}{\min }{\alpha }_0+\mu {\left(x\right)}^{{\rm T}}\alpha +\langle \Sigma ,Y\rangle \\ \text{s}\text{.t}\text{.}f\left(x,\xi \right)-{\alpha }_0-{\alpha }^{{\rm T}}\xi -{\xi }^{{\rm T}}Y\xi \le 0,\forall \xi \in \Xi .\end{array}$ (2.5)

再由 $h\left(x,{\alpha }_0,\alpha ,Y\right)$ 的定义可知，

$\begin{array}{c}p\left(x\right)=\max \Psi \left(x,\mu \left(x\right)\right)\\ =\underset{\mu \left(x\right)}{\max }\underset{{\alpha }_0,\alpha ,Y\succcurlyeq 0}{\min }\left\{{\alpha }_0+\mu {\left(x\right)}^{{\rm T}}\alpha +\langle \Sigma ,Y\rangle :h\left(x,{\alpha }_0,\alpha ,Y\right)\le 0,\mu \left(x\right)\in \left[A_{m\times n}x,B_{m\times n}x\right]\right\}\\ =\underset{{\alpha }_0,\alpha ,Y\succcurlyeq 0}{\min }\underset{\mu \left(x\right)}{\max }\left\{{\alpha }_0+\mu {\left(x\right)}^{{\rm T}}\alpha +\langle \Sigma ,Y\rangle :h\left(x,{\alpha }_0,\alpha ,Y\right)\le 0\right\}\\ =\underset{{\alpha }_0,\alpha ,Y\succcurlyeq 0}{\min }\left\{{\alpha }_0+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+\langle \Sigma ,Y\rangle :h\left(x,{\alpha }_0,\alpha ,Y\right)\le 0\right\}.\end{array}$

所以问题(1.1)等价于 $\underset{x\in X}{\min }p\left(x\right)$ ，即原问题等价于约束优化问题(2.2)。

3. 原问题等价于半定规划问题

在这一章中，我们考虑当支撑集 $\Xi$ 是全空间时的情况，可以证明，当 $\Xi ={ℝ}^m$ 时，原问题可以转化成一个半定规划问题，令

$G\left(x,{\alpha }_0,\alpha ,Y\right)=\left(\begin{array}{cc}{c}^{{\rm T}}x-{\alpha }_0& \frac{{\left(E_{m\times n}x-\alpha \right)}^{{\rm T}}}{2}\\ \frac{E_{m\times n}x-\alpha }{2}& -Y\end{array}\right),$ (3.1)

可以得到下面的定理：

定理3.1：令 $f\left(x,\xi \right)=c^{{\rm T}}x+{\left(E_{m\times n}x\right)}^{{\rm T}}\xi$ ，则问题(1.1)可以转化成如下半定规划问题：

$\begin{array}{l}\underset{x,{\alpha }_0,\alpha ,Y}{\min }{\alpha }_0+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+\langle \Sigma ,Y\rangle \\ \text{s}\text{.t}\text{.}G\left(x,{\alpha }_0,\alpha ,Y\right)\preccurlyeq 0,\\ x\in X,Y\succcurlyeq 0.\end{array}$ (3.2)

证明：由(2.5)可知， $\Psi \left(x,\mu \left(x\right)\right)$ 的约束条件是 $f\left(x,\xi \right)-{\alpha }_0-{\alpha }^{{\rm T}}\xi -{\xi }^{{\rm T}}Y\xi \le 0,\forall \xi \in \Xi$ 。它可以等价地写成与 $G\left(x,{\alpha }_0,\alpha ,Y\right)$ 相关的不等式，即

${\left(\begin{array}{c}1\\ \xi \end{array}\right)}^{{\rm T}}\left(\begin{array}{cc}{c}^{{\rm T}}x-{\alpha }_0& \frac{{\left(E_{m\times n}x-\alpha \right)}^{{\rm T}}}{2}\\ \frac{E_{m\times n}x-\alpha }{2}& -Y\end{array}\right)\left(\begin{array}{c}1\\ \xi \end{array}\right)\le 0,\forall \xi \in \Xi .$

这恰好等价于 $G\left(x,{\alpha }_0,\alpha ,Y\right)\preccurlyeq 0$ ，证毕。

4. 原问题等价于二阶锥规划问题

接下来，我们将问题(3.2)转化成更简单的非光滑凸问题，进而转化为二阶锥规划问题。

定理4.1：假设X是 ${ℝ}^n$ 上的非空紧集，则(3.2)等价于下述非光滑凸问题：

$\begin{array}{l}\underset{x,\alpha }{\min }{c}^{{\rm T}}x+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+\Vert {\Sigma }^{\frac{1}{2}}\left(\alpha -E_{m\times n}x\right)\Vert \\ \text{s}\text{.t}\text{.}x\in X.\end{array}$ (4.1)

证明：问题(3.2)的Lagrange函数是

$L\left(x,{\alpha }_0,\alpha ,Y,\Omega \right)={\alpha }_0+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+\langle \Sigma ,Y\rangle +\langle \Omega ,G\left(x,{\alpha }_0,\alpha ,Y\right)\rangle ,$

其中 $\Omega =\left(\begin{array}{cc}{z}_0& z^{{\rm T}}\\ z& {\rm M}\end{array}\right),z_0\in ℝ,z\in {ℝ}^m,{\rm M}\in {\mathbb{S}}^{m\times m}$ 。故 $L\left(x,{\alpha }_0,\alpha ,Y,\Omega \right)$ 可以表示成如下形式：

$L\left(x,{\alpha }_0,\alpha ,Y,\Omega \right)={\alpha }_0+{(A_{m\times n}x)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}+z_0\left(c^{{\rm T}}x-{\alpha }_0\right)+z^{{\rm T}}\left(E_{m\times n}x-\alpha \right)+\langle \Sigma -{\rm M},Y\rangle ,$

整理后得，

$L\left(x,{\alpha }_0,\alpha ,Y,\Omega \right)={\alpha }_0(1-z_0)+\left[{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}{\alpha }_{+}-z^{{\rm T}}\alpha \right]+z_0{c}^{{\rm T}}x+z^{{\rm T}}\left(E_{m\times n}x\right)+\langle \Sigma -{\rm M},Y\rangle ,$

考虑到问题(3.2)满足Slater条件，则其解必然满足下列KKT条件：

$\{\begin{array}{l}0\in A_{m\times n}^{{\rm T}}\alpha +{\left(B_{m\times n}-A_{m\times n}\right)}^{{\rm T}}{\alpha }_{+}+c^{{\rm T}}{z}_0+z^{{\rm T}}{E}_{m\times n},\\ 0\in A_{m\times n}x+\left(B_{m\times n}x-A_{m\times n}x\right)\partial {\alpha }_{+}-z,\\ 1-z_0=0,\\ \Sigma -{\rm M}=0,\\ 0\preccurlyeq \Omega \perp G\left(x,{\alpha }_0,\alpha ,Y\right)\preccurlyeq 0,\end{array}$ (4.2)

通过(4.2)第三个条件和第四个条件，可以得到 $\Omega$ 的具体表达形式：

$\Omega =\left(\begin{array}{cc}1& z^{{\rm T}}\\ z& \Sigma \end{array}\right),$

又 $0\preccurlyeq \Omega \perp G\left(x,{\alpha }_0,\alpha ,Y\right)\preccurlyeq 0$ ，可知 $-G\left(x,{\alpha }_0,\alpha ,Y\right)$ 是零矩阵或秩为1的半正定矩阵，下面分情况讨论：

1) 若 $-G\left(x,{\alpha }_0,\alpha ,Y\right)$ 是零矩阵，则 $c^{{\rm T}}x={\alpha }_0$ ， $E_{m\times n}x=\alpha$ ， $Y=0$ 。

2) 若 $-G\left(x,{\alpha }_0,\alpha ,Y\right)$ 是秩为1的半正定矩阵，则存在 $r_0\in ℝ$ ， $r\in {ℝ}^m$ ，使得 $\left(\begin{array}{cc}{r}_0& r^{{\rm T}}\end{array}\right)\ne 0$ 且

$-G\left(x,{\alpha }_0,\alpha ,Y\right)=\left(\begin{array}{c}{r}_0\\ r\end{array}\right)\left(\begin{array}{cc}{r}_0& r^{{\rm T}}\end{array}\right).$ (4.3)

假设 $r_0=0$ ，则 $-G\left(x,{\alpha }_0,\alpha ,Y\right)=\left(\begin{array}{cc}{r}_0{r}_0& r_0{r}^{{\rm T}}\\ r_{0}r& r{r}^{{\rm T}}\end{array}\right)=\left(\begin{array}{cc}0& 0\\ 0& r{r}^{{\rm T}}\end{array}\right)$ ，结合(3.1)可得 $Y=r{r}^{{\rm T}}$ 。又 $\langle G\left(x,{\alpha }_0,\alpha ,Y\right),\Omega \rangle =0$ ，故 $r^{{\rm T}}\Sigma r=0$ ，则 $r=0$ ，与 $\left(\begin{array}{cc}{r}_0& r^{{\rm T}}\end{array}\right)\ne 0$ 矛盾，故 $r_0\ne 0$ 。现将(3.1)代入到(4.3)中，可以得到下述等式关系：

$\{\begin{array}{l}{r}_0{r}_0={\alpha }_0-c^{{\rm T}}x,\\ r=\frac{\alpha -E_{m\times n}x}{2r_0},\\ r{r}_0=Y.\end{array}$

因此，

$\langle \Sigma ,Y\rangle =r_0^2+c^{{\rm T}}x+r^{{\rm T}}\Sigma r=c^{{\rm T}}x+r_0^2+\frac{{\left(\alpha -E_{m\times n}x\right)}^{{\rm T}}\Sigma \left(\alpha -E_{m\times n}x\right)}{4r_0^2}\ge c^{{\rm T}}x+\Vert {\Sigma }^{\frac{1}{2}}\left(\alpha -E_{m\times n}x\right)\Vert .$

综上所述，问题(3.2)可以转化为问题(4.1)，且 ${\alpha }_0=c^{{\rm T}}x$ ，证毕。

根据上述定理，我们显然可以将问题(4.1)等价地表示为一个二阶锥规划问题：

$\begin{array}{l}\min c^{{\rm T}}x+{\left(A_{m\times n}x\right)}^{{\rm T}}\alpha +1_{m}q+t\\ \text{s}\text{.t}\text{.}{\left(B_{m\times n}x-A_{m\times n}x\right)}^{{\rm T}}\circ \alpha -q\le 0,\\ \left({\Sigma }^{\frac{1}{2}}\left(\alpha -E_{m\times n}x\right),t\right)\in K_{m+1},\\ q\ge 0.\end{array}$ (4.4)

其中 $K_{m+1}\subset {ℝ}^{m+1}$ 是二阶锥，定义为 $K_{m+1}=\left\{\left(\omega ,{\omega }_0\right)\in {ℝ}^{m+1}:\Vert \omega \Vert \le {\omega }_0\right\}$ 。

5. 结论

本文研究了一类带有依赖决策矩约束的分布鲁棒优化的重构问题，利用Lagrange对偶理论将其转化为半定规划，进而得到了易于求解的二阶锥规划问题，该问题可以利用神经网络等算法求解，具有较高的理论价值和现实意义。

NOTES

^*通讯作者。