数据驱动的分布式鲁棒随机二次规划的收敛性分析

Convergence Analysis of Data-Driven Distributionally Robust Stochastic Quadratic Programming

摘要: 本文研究数据驱动的Wasserstein模糊集下分布式鲁棒随机二次规划的收敛性问题。首先，我们建立了目标函数的逐点Lipschitz性质。接着，当样本量趋于无穷大时，利用大数定律，Helly-Bray定理给出了分布式目标函数收敛于目标函数的期望值。最后，我们建立了分布式鲁棒随机二次规划收敛于通常的随机二次规划问题。

Abstract: In this paper, we study the convergence problem of distributionally robust stochastic quadratic programming under the data-driven Wasserstein ambiguity sets. First, we establish the point-by-point Lipschitz property of the objective function. Then, when the sample size tends to infinity, using the law of large numbers, the Helly-Bray theorem derives the expectation of the distributionally objective function converges to the objective function. Finally, we establish that the distributionally robust stochastic quadratic programming converges to the general stochastic quadratic programming problem.

1. 引言

最优解与最优值的收敛性是随机规划问题的重要性质之一，因而关于随机规划的收敛性分析得到了广泛关注和深入研究。2000年骆建文等 [1] 对随机规划的逼近解的收敛性做了探讨，证明了当随机序列依分布收敛时，随机规划问题的任何最优解序列将收敛到原问题的最优解，这为如何设计逼近算法来求解随机规划问题提供了理论基础。2012年霍永亮、刘三阳 [2] 指出关于随机规划逼近问题最优解集的上半收敛性结果依赖于概率度量(如Kolmogorov度量、Wasserstein度量、Fortet-Mourier度量)的收敛性 [3] [4] [5]。

虽然随机规划的定量稳定性研究取得硕果，却受限于复杂多变的实际问题。尤其是面对随机变量的概率分布模糊不清时非常棘手。为了更好地刻画实际问题，Ben-Tal [6] 和Ghaoui [7] 在鲁棒优化方向做出了奠基工作。然而随机规划与鲁棒随机优化虽能较好地刻画随机问题，但是前者需要知道随机变量的概率分布信息，后者虽可求解问题，但得到的解过于保守 [8]。分布式鲁棒随机优化则介于二者之间，它是从随机优化到鲁棒优化的桥梁，它不需要精确知道优化问题中的随机变量的概率分布，而且还易于求解。即使在相应的随机模型是#P-难的情况下，分布式鲁棒优化问题也是可求解的。分布式鲁棒随机优化方法的核心是模糊集的构造。现在熟知的构造模糊集的方法有如下三种：① 基于矩信息构造模糊集；② 基于概率度量(如Prohorov metric、K-L divergence、Wasserstein metric等)；③ 第三种构造模糊集为拟合优度检验的置信域。

关于Wasserstein度量下的收敛性的研究工作较为热门。2013年Nicolas Fournier [9] 等人给出了关于经验度量的Wasserstein距离的收敛速率，这为后续的分布式鲁棒随机优化的收敛性分析奠定了基础。2014年Zhao Chaoyue在其博士论文 [10] 中给出了Wasserstein度量下样本量N与其构造的模糊集半径关系的系统性描述。Peyman Mohajerin Esfahani和Daniel Kuhn [11] 在已有工作的基础之上，得到了有限样本保证(有限样本情况下给出分布式鲁棒随机优化问题的置信界)，渐近一致性及分布的收敛性。

本文基于上述工作，考虑当样本数据量趋于无穷时，Wasserstein度量下的分布式鲁棒随机二次规划的收敛性问题。

2. 模型介绍

2.1. 模型与符号

考虑如下模型：

$\underset{x\in X}{\min }\underset{P\in D}{\sup }{\displaystyle {\int }_{\Xi }f\left(x,\xi \right)P\text{d}\xi }$ (1)

其中，x为决策变量， $x\in X$ ， $X\subseteq R^n$ 为约束集。损失函数 $f:R^n\times R^m\to R$ 为随机二次函数，其形式如下：

$f\left(x,\xi \right)=\frac{1}{2}{x}^{\text{T}}Q\left(\xi \right)x+L^{\text{T}}\left(\xi \right)x+h\left(\xi \right)$ ,

$Q\left(\xi \right)$ ， $L\left(\xi \right)$ ， $h\left(\xi \right)$ 分别为关于 $\xi$ 的仿射函数。其中 $Q\left(\xi \right)={\displaystyle {\sum }_{i=1}^m{A}_i{\xi }_i+A_0}$ ， $i=1,2,\cdots ,m$ 为实对称矩阵且 $A_0$ 为实半正定矩阵； $L\left(\xi \right)=B\xi +B_0$ ， $B\in R^{n\times m}$ 为实矩阵， $B_0\in R^{n\times 1}$ 为常数向量； $h\left(\xi \right)=C^{\text{T}}\xi +c$ ， $C\in R^{m\times 1}$ 为常数向量，c为常数。 $\xi \in R^m$ 为随机向量，服从分布P，D为包含P的模糊集， $\Xi$ 是P的支撑集。

2.2. 数据驱动的分布式鲁棒随机二次规划模型

在诸多实际运用中，分布P是未知的，因此无法直接求解问题(1)。然而可以通过独立的历史样本数据观测到分布P的部分实现。若使用 ${\hat{\Xi }}_N:={\left\{\hat{\xi }\right\}}_{i\le N}\subseteq \Xi$ 表示包含样本的数据集，则可通过该数据集在某些概率距离下(如K-L散度、Prokhorov度量、Wasserstein度量等)构造的模糊集 ${\hat{D}}_N$ ，使该集以较高的置信度包含真实概率分布P。由于Wasserstein度量具有良好的性质 [9] [10] [11]，故本文利用Wasserstein距离来构造模糊集。

对于任意 $p\in \left[1,\infty \right)$ ，p-型Wasserstein度量 $W_p:M\left(\Xi \right)\times M\left(\Xi \right)\to R_{+}$ 定义为：对所有的分布 $Q_1,Q_2\in M\left(\Xi \right)$ ，

$W_p\left(Q_1,Q_2\right)={\left(\underset{\Pi }{\inf }{\displaystyle {\int }_{{\Xi }^2}{\Vert {\xi }_1-{\xi }_2\Vert }^p\Pi \left(\text{d}{\xi }_1,\text{d}{\xi }_2\right)}\right)}^{\frac{1}{p}}$ ,

其中， $M\left(\Xi \right)$ 表示支撑集 $\Xi$ 上的概率度量， $Q_1$ 是随机变量 ${\xi }_1$ 的概率分布， $Q_2$ 是随机变量 ${\xi }_2$ 的概率分布， $\Pi$ 是 $Q_1$ 和 $Q_2$ 的联合概率分布， $\Vert \cdot \Vert$ 表示 $R^m$ 中的任意范数。

当 $p=1$ 时，随机变量间的单位运输成本表示为 ${\Vert {\xi }_1-{\xi }_2\Vert }^1$ ，相应地

$W_1\left(Q_1,Q_2\right)=\underset{\Pi }{\inf }{\displaystyle {\int }_{{\Xi }^2}{\Vert {\xi }_1-{\xi }_2\Vert }^1\Pi \left(\text{d}{\xi }_1,\text{d}{\xi }_2\right)}$ 。此度量也是著名的Kantorovich度量。

根据Wasserstein 度量的良好收敛性质，本文采用1-型Wasserstein度量来构造模糊集，即

${\hat{D}}_N:=\left\{P\in M\left(\Xi \right):W_1\left(P,{\hat{P}}_N\right)\le \epsilon \right\}$ ,

其中， ${\hat{P}}_N$ 表示样本量为N的i.i.d.历史数据的经验分布。

故而，数据驱动的分布式鲁棒随机二次规划模型为：

$\underset{x\in X}{\min }\underset{P\in {\hat{D}}_N}{\sup }{\displaystyle {\int }_{\Xi }\left[\frac{1}{2}{x}^{\text{T}}Q\left(\xi \right)x+L^{\text{T}}\left(\xi \right)x+h\left(\xi \right)\right]P\text{d}\xi }$ . (2)

3. 收敛性分析

为了得到数据驱动的分布式鲁棒随机二次规划的收敛性分析，我们先给出如下的结论。

引理1 [11] 当 $\Xi$ 为紧集时，存在一个常数 $a>1$ ， $\forall N\ge 1$ ， $m\ne 2$ ， $\epsilon >0$ 有如下结论成立：

$A:=E^P\left[\exp \left({\Vert \xi \Vert }^a\right)\right]={\displaystyle {\int }_{\Xi }\exp \left({\Vert \xi \Vert }^a\right)P\left(\text{d}\xi \right)}<\infty$ ,

$P^N\left\{W_1\left(P,{\hat{P}}_N\right)\ge \epsilon \right\}\le \{\begin{array}{ll}{c}_1\exp \left(-c_{2}N{\epsilon }^{\max \left\{m,2\right\}}\right)\hfill & 若\epsilon \le 1,\hfill \\ c_1\exp \left(-c_{2}N{\epsilon }^a\right)\hfill & 若\epsilon >1,\hfill \end{array}$

其中， $c_1$ ， $c_2$ 是依赖于a，A，m的正数。

根据上述集中不等式，在给定置信水平 $\beta$ 下，样本量N与Kantorovich度量构造的模糊集的Wasserstein球的半径 $\epsilon$ 有如下关系：

${\epsilon }_N\left(\beta \right):=\{\begin{array}{ll}{\left(\frac{\log \left(c_1{\beta }^{-1}\right)}{c_{2}N}\right)}^{\frac{1}{\max \left\{m,2\right\}}}\hfill & 若N\ge \frac{\log \left(c_1{\beta }^{-1}\right)}{c_2},\hfill \\ {\left(\frac{\log \left(c_1{\beta }^{-1}\right)}{c_{2}N}\right)}^{\frac{1}{a}}\hfill & 若N<\frac{\log \left(c_1{\beta }^{-1}\right)}{c_2}.\hfill \end{array}$

引理2 (Helly-Bray定理)若随机函数 $g:R^m\to R$ 为有界连续函数，则 ${\xi }_n$ 依分布收敛于 $\xi$ 当且仅当 $E\left[g\left({\xi }_n\right)\right]\to E\left[g\left(\xi \right)\right]$ 。

为了建立分布式鲁棒随机二次规划问题的收敛性结果，首先考虑随机二次函数 $f\left(x,\xi \right)$ 的分析性质。

定理1 对于任意给定的 $x\in X$ ，任取 $\Xi$ 中的随机向量 $\xi$ ， $\eta$ 且 $\xi \ne \eta$ ，则有 $\frac{\left|f\left(x,\xi \right)-f\left(x,\eta \right)\right|}{\Vert \xi -\eta \Vert }\le K\left(x\right)$ 。

证明 首先，对于 $\forall \xi ,\eta \in \Xi$ 且 $\xi \ne \eta$ ，

$f\left(x,\xi \right)-f\left(x,\eta \right)=\frac{1}{2}{x}^{\text{T}}Q\left(\xi \right)x+L^{\text{T}}\left(\xi \right)x+h\left(\xi \right)-\left[\frac{1}{2}{x}^{\text{T}}Q\left(\eta \right)x+L^{\text{T}}\left(\eta \right)x+h\left(\eta \right)\right]$ .

将 $Q\left(\xi \right)={\displaystyle {\sum }_{i=1}^m{A}_i{\xi }_i+A_0}$ ， $L\left(\xi \right)=B\xi +B_0$ ， $h\left(\xi \right)=C^{\text{T}}\xi +c$ 代入得：

$\begin{array}{c}f\left(x,\xi \right)-f\left(x,\eta \right)=\frac{1}{2}{x}^{\text{T}}\left({\displaystyle {\sum }_{i=1}^m{A}_i{\xi }_i}+A_0\right)x-\frac{1}{2}{x}^{\text{T}}\left({\displaystyle {\sum }_{i=1}^m{A}_i{\eta }_i}+A_0\right)x+\left(B\xi +B_0\right)x-\left(B\eta +B_0\right)x+C^{\text{T}}\xi -C^{\text{T}}\eta \\ =\frac{1}{2}\langle x,\left({\displaystyle {\sum }_{i=1}^m{A}_i{\xi }_i}+A_0\right)x\rangle -\frac{1}{2}\langle x,\left({\displaystyle {\sum }_{i=1}^m{A}_i{\eta }_i}+A_0\right)x\rangle +\langle B\xi ,x\rangle -\langle B\eta ,x\rangle +C^{\text{T}}\left(\xi -\eta \right)\\ =\frac{1}{2}\langle x,\left({\displaystyle {\sum }_{i=1}^m{A}_i\left({\xi }_i-{\eta }_i\right)}\right)x\rangle +\langle B\left(\xi -\eta \right),x\rangle +C^{\text{T}}\left(\xi -\eta \right)\\ =\frac{1}{2}\langle \left(x^{\text{T}}{A}_{1}x,\cdots ,x^{\text{T}}{A}_{m}x\right),\left(\xi -\eta \right)\rangle +\langle \xi -\eta ,B^{\text{T}}x\rangle +C^{\text{T}}\left(\xi -\eta \right)\end{array}$

令 $H=\left[x^{\text{T}}{A}_{1}x,\cdots ,x^{\text{T}}{A}_{m}x\right]$ ，H为m维向量。则

$f\left(x,\xi \right)-f\left(x,\eta \right)=\left(\frac{1}{2}H+B^{\text{T}}x+C^{\text{T}}\right)\left(\xi -\eta \right)$ .

所以，

$\frac{\left|f\left(x,\xi \right)-f\left(x,\eta \right)\right|}{\Vert \xi -\eta \Vert }=\frac{\left|\left(\frac{1}{2}H+B^{\text{T}}x+C^{\text{T}}\right)\left(\xi -\eta \right)\right|}{\Vert \xi -\eta \Vert }\le \Vert \frac{1}{2}H+B^{\text{T}}x+C^{\text{T}}\Vert =K\left(x\right)$ .

定理2 对于每个给定的置信水平 $\beta$ 和决策 $x\in X$ 。在 $\Xi$ 为紧集的条件下，随着样本量 $N\to \infty$ 时，有模糊集半径 $\epsilon \to 0$ ， $\underset{N\to \infty }{\lim }\underset{Q\in {\hat{D}}_N}{\sup }{E}^Q\left[f\left(x,\xi \right)\right]=E^P\left[f\left(x,\xi \right)\right]$ 成立。

证明 首先利用引理1的结论，很容易得到当 $N\to \infty$ 时， $\epsilon \to 0$ 。

根据( [11], Theorem 4.2)证明过程中有如下结论：

$\underset{Q\in {\hat{D}}_N}{\sup }{E}^Q\left[f\left(x,\xi \right)\right]=\underset{\lambda \ge 0}{\inf }\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]$ (3)

由于随着 $N\to \infty$ ，在大数定律下经验分布 ${\hat{P}}_N$ 弱收敛于分布P。又 $f\left(x,\xi \right)$ 关于随机变量 $\xi$ 连续，则 $f\left(x,\xi \right)$ 在 $\Xi$ 上有界，利用引理2，我们有如下关系：

$\underset{N\to \infty }{\lim }\underset{Q\in {\hat{D}}_N}{\sup }{E}^Q\left[f\left(x,\xi \right)\right]\ge \underset{N\to \infty }{\lim }{E}^{{\hat{P}}_N}\left[f\left(x,\xi \right)\right]=E^P\left[f\left(x,\xi \right)\right]$ .

根据(3)式，接下来只需证明 $\underset{N\to \infty }{\lim }\underset{\lambda \ge 0}{\inf }\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\le E^P\left[f\left(x,\xi \right)\right]$ 成立即可。

由于

$\begin{array}{l}\underset{N\to \infty }{\lim }\underset{\lambda \ge 0}{\inf }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\\ \le \underset{\lambda \ge 0}{\inf }\underset{N\to \infty }{\lim \sup }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\end{array}$

因此只需证明(4)成立即可：

$\underset{\lambda \ge 0}{\inf }\underset{N\to \infty }{\lim \sup }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\le E^P\left[f\left(x,\xi \right)\right]$ . (4)

根据定理1知，存在一个常数 $L>0$ ，使得对于任意的 $x\in X$ ，有

$\left|f\left(x,\xi \right)\right|<L$ ， $\forall \xi \in \Xi$ . (5)

由于 $\Xi$ 为紧集，若令B为 $\Xi$ 的直径，则有

$0\le \Vert \xi -z\Vert \le B$ ， $\forall \xi ,z\in \Xi$ . (6)

对于任意 $\lambda \ge 0$ ，利用(5)和(6)可得：

$-L-\lambda B\le \underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\le L$ , $\forall z\in \Xi$ .

因此可进一步得到(7)：

$\begin{array}{l}\underset{N\to \infty }{\lim \sup }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\\ =\underset{N\to \infty }{\lim \sup }\left\{\lambda \epsilon +E^{{\hat{P}}_N}\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\\ =\underset{N\to \infty }{\lim }\lambda \epsilon +E^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\\ =E^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\end{array}$ (7)

现已将分布式鲁棒优化问题在样本量趋于无穷的情况下等价转化为鲁棒优化问题。接下来只需证明给定任意的 $x\in X$ ，(8)式成立即可。

$\underset{\lambda \ge 0}{\inf }{E}^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\le E^P\left[f\left(x,z\right)\right]$ . (8)

由于 $\underset{\lambda \ge 0}{\inf }{E}^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\le \underset{\lambda \to +\infty }{\lim \sup }{E}^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]$ 。因此需进一步证明下式成立即可：

$\underset{\lambda \to +\infty }{\lim \sup }{E}^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]\le E^P\left[f\left(x,z\right)\right]$ . (9)

接下来，问题(9)中的最优解是 ${\xi }^{\ast }\left(z\right)=z$ 。假设 ${\xi }^{\ast }\left(z\right)=\hat{z}\ne z$ ，根据定理1则有：

$\begin{array}{l}\left[f\left(x,z\right)-\lambda \Vert z-z\Vert \right]-\left[f\left(x,\hat{z}\right)-\lambda \Vert z-\hat{z}\Vert \right]\\ =f\left(x,z\right)-f\left(x,\hat{z}\right)+\lambda \Vert z-\hat{z}\Vert >\left(\lambda -K\left(x\right)\right)\Vert z-\hat{z}\Vert >0\end{array}$

与 ${\xi }^{\ast }\left(z\right)=\hat{z}\ne z$ 矛盾，因此可得：

$\underset{\lambda \to +\infty }{\lim \sup }{E}^P\underset{\xi \in \Xi }{\sup }\left[f\left(x,\xi \right)-\lambda \Vert \xi -z\Vert \right]=\underset{\lambda \to +\infty }{\lim \sup }{E}^P\left[f\left(x,z\right)\right]=E^P\left[f\left(x,z\right)\right]$ .

综上已经证得：

$\underset{N\to \infty }{\lim }\underset{\lambda \ge 0}{\inf }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\ge E^P\left[f\left(x,\xi \right)\right]$ ，

$\underset{N\to \infty }{\lim }\underset{\lambda \ge 0}{\inf }\left\{\lambda \epsilon +\frac{1}{N}{\displaystyle {\sum }_{i=1}^N\underset{\xi \in \Xi }{\sup }}\left[f\left(x,\xi \right)-\lambda \Vert \xi -{\hat{\xi }}_i\Vert \right]\right\}\le E^P\left[f\left(x,\xi \right)\right]$ .

故定理2得证。

由于定理2的结论对于任意给定的 $x\in X$ 都成立。同时， $K\left(x\right)$ 是关于x的二次向量值函数的范数。而当X为紧集时，该向量中每一个分量都是有限的。因而，存在某个常数 $K>0$ ，使得 $K\left(x\right)\le K$ ，从而有下面的定理。

定理3 对于每个给定的置信水平 $\beta$ 及任意决策 $x\in X$ 。在X与 $\Xi$ 为紧集的条件下，我们有

$\underset{N\to \infty }{\lim }\underset{x\in X}{\min }\underset{Q\in {\hat{D}}_N}{\sup }{E}^Q\left[f\left(x,\xi \right)\right]=\underset{x\in X}{\min }{E}^P\left[f\left(x,\xi \right)\right]$ 成立，即分布式鲁棒随机二次规划收敛于通常的随机二次规划。

4. 结论

当模糊集由概率分布的Kantorovich度量构成时，本文对数据驱动的分布式鲁棒二次规划的收敛性问题进行了研究。在建立了目标函数关于随机变量是逐点Lipschitz连续性的基础上，当样本量N趋于无穷时，我们得到了最坏情况下的随机二次规划问题逐点收敛于通常的随机二次规划问题。进而，在决策变量集合为紧集时，我们获得分布式鲁棒随机二次规划问题收敛于通常的随机二次规划问题。这些结果不仅丰富了分布式鲁棒优化的理论，还为进一步设计求解算法奠定了理论基础。

基金项目

本研究受国家自然科学基金11501434资助。

参考文献

NOTES

^*共同第一作者。