随机二阶锥规划样本均值近似问题的一阶最优性条件的相容性分析

Compatibility Analysis of First-Order Optimality Conditions for Sample Average Approximation Problem of Stochastic Sec-ond-Order Cone Programming

摘要: 本文利用样本均值近似方法对随机二阶锥规划的最优解集以及稳定点条件进行了相容性分析。在理论上，我们提出了一些命题与假设并建立了随机二阶锥规划问题的样本均值近似问题的一阶最优性条件的相容性理论。

Abstract: In this paper, the sample mean approximation method is used to analyze the compatibility of the optimal solution set and stable point conditions of stochastic second-order cone programming. In theory, we propose some propositions and assumptions, and establish the compatibility theory of the first-order optimality condition of the sample mean approximation problem of stochastic sec-ond-order cone programming problem.

1. 引言

二阶锥规划作为数学规划领域的一个重要问题，具有广泛的应用价值和实际意义，这个问题可以应用到金融、对策论、经济学等众多领域。学者们已经对二阶锥规划进行了广泛深入的研究，Gu [1] 利用非线性规划问题分析了提出的非线性Lagrange函数的性质，建立了非凸二阶锥规划的重新尺度化方法的理论框架。Fang [2] 分析了二阶锥规划的中心路径条件，定义了中心路径的一个宽领域，并给出二阶锥规划问题的一个宽领域原始–对偶路径跟踪内点算法。Lu [3] 讨论了基于空间分解的随机二阶锥规划问题的样本均值近似方法，并基于分解理论给出了SAA问题的超线性收敛算法框架。Ren [4] 探讨了两阶段随机二阶锥规划问题的最优性条件，并给出了具有离散分布的两阶段随机二阶锥规划问题的最优性条件。本文的研究目的是利用样本均值近似方法对随机二阶锥规划的最优解集以及稳定点条件进行相容性分析。

本文我们考虑如下形式的二阶锥规划问题：

$\begin{array}{l}\underset{x\in S}{\text{min}}\mathbb{E}\left[f\left(x,\xi \right)\right]\\ \text{s}.\text{t}.\mathbb{E}\left[G\left(x,\xi \right)\right]\in K,\\ \mathbb{E}\left[A\left(\xi \right)\right]x=b,\end{array}$ (1.1)

其中S是 $R^m$ 上的一个非空闭凸集， $K=K_{m_1+1}\times \cdots \times K_{m_J+1}$ 为 $R^m$ 上的二阶锥， $f:R^n\times R^k\to R$ 和 $G:R^n\times R^k\to R^m$ 是两个实值连续函数， $\xi$ 是一个定义在概率空间 $\left(\Xi ,\mathcal{F},P\right)$ 上的实值随机向量， $\mathbb{E}[\cdot ]$ 是期望， $A(\cdot ):R^k\to R^{m\times n}$， $b\in R^m$。

而在实际中，通常取 $\xi$ 的独立同分布的样本 ${\xi }_1,\cdots ,{\xi }_N$，则问题(1)的样本均值近似问题为：

$\begin{array}{l}\underset{x\in S}{\text{min}}{\hat{f}}_N\left(x\right)\\ \text{s}.\text{t}.{\hat{G}}_N\left(x\right)\in K,\\ A_{N}x-b=0,\end{array}$ (1.2)

其中 ${\hat{f}}_N\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(x,{\xi }_i\right)}$， ${\hat{G}}_N\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}G\left(x,{\xi }_i\right)}$， $A_N=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}A\left({\xi }_i\right)}$。

我们将问题(1.1)称为真问题，问题(1.2)称为样本均值近似(SAA)问题。

接下来，我们研究它们最优解集的相容性以及稳定点的相容性。

2. 最优解集的相容性

首先让我们给出一些概念：

${\mathbb{Z}}_0:=\left\{x|\mathbb{E}\left[G\left(x,\xi \right)\right]\in K,\mathbb{E}\left[A\left(\xi \right)\right]x=b\right\}.$

${\mathbb{Z}}_N:=\left\{x|G_N\left(x\right)\in K,A_N\left(x\right)-b=0\right\}.$

$K_0:=\inf \left\{\mathbb{E}\left[f\left(x,\xi \right)\right]|x\in {\mathbb{Z}}_0\right\}.$

$S_0:=\arg \min \left\{\mathbb{E}\left[f\left(x,\xi \right)\right]|x\in {\mathbb{Z}}_0\right\}.$

$S_N:=\arg \min \left\{{\hat{f}}_N\left(x\right)|x\in {\mathbb{Z}}_N\right\}.$

在下面的命题中我们给出一个关于当 $N\to +\infty$ 时， ${\mathbb{Z}}_N$ 的一个收敛结论。

命题2.1对于 $\forall x\in {\mathbb{Z}}_0$， $\mathbb{E}\left[G\left(x,\xi \right)\right]\in \mathrm{int}K$， $\mathbb{E}\left[A\left(\xi \right)\right]$ 行满秩，则 $\underset{N\to +\infty }{\text{lim}}{\mathbb{Z}}_N={\mathbb{Z}}_0$ w.p.1。

证明：假设 $x_N$ 是SAA问题的可行解，则

${\hat{G}}_N\left(x_N\right)\in K,A_N{x}_N-b=0.$ (2.1)

假设 $x_N\to \bar{x}$，则有，

$\mathbb{E}\left[G\left(\bar{x},\xi \right)\right]\in K,\mathbb{E}\left[A\left(\xi \right)\right]\bar{x}=b.$ (2.2)

则 ${\mathbb{Z}}_N$ 外半连续收敛到 ${\mathbb{Z}}_0$，即

$\underset{N\to +\infty }{\lim \sup }{\mathbb{Z}}_N\subseteq {\mathbb{Z}}_0.$ (2.3)

对于 $\forall x_0\in {\mathbb{Z}}_0$， $E\left[G\left(x_0,\xi \right)\right]\in \mathrm{int}K$， $\mathbb{E}\left[A\left(\xi \right)\right]$ 行满秩，所以存在 $x_N$ 满足 $G_N\left(x_N\right)\in K,A_N{x}_N=b$，且 $x_N\to x_0$，因此由 $x_0$ 任意性，

${\mathbb{Z}}_0\subseteq \underset{N\to +\infty }{\lim \inf }{\mathbb{Z}}_N.$ (2.4)

综上所述， $\underset{N\to +\infty }{\text{lim}}{\mathbb{Z}}_N={\mathbb{Z}}_0$。

接下来，受到 [5] 的启示，我们得到如下定理：

定理2.1 假设对于每一个N， $x_N$ 是SAA问题的最优解， $\bar{x}$ 是序列 $\left\{x_N\right\}$ 的聚点，如果命题2.1的条件成立且 $K_0$ 有限，则 $\bar{x}$ 以概率1是真问题(1.1)的最优解。

证明：因为 $K_0$ 有限，则 $-\infty <\inf \bar{f}<+\infty$，且 ${\bar{f}}_N$ 上图收敛于 $\bar{f}$ (根据 [6]，定理7.31)，则意味着

$\underset{N\to +\infty }{\lim \sup }\arg \min {\bar{f}}_N\subseteq \arg \min \bar{f}$ w.p.1. (2.5)

除此之外， $-\infty <K_0<+\infty$ 意味着 ${\mathbb{Z}}_0\ne \varphi$，则存在 $\tilde{x}\in {\mathbb{Z}}_0$ 使 $\mathbb{E}\left[f\left(\tilde{x},\xi \right)\right]$ 是有限的，那么我们可以得到

$\arg \min \bar{f}=S_0.$ (2.6)

根据命题1.1，当N足够大时， ${\mathbb{Z}}_N\ne \varphi$ w.p.1且存在 ${\tilde{x}}_N\in {\mathbb{Z}}_N$ w.p.1使得 ${\hat{f}}_N\left({\tilde{x}}_N\right)$ 是有限的。那么我们由(2.5)和(2.6)能够得到

$\arg \min {\bar{f}}_N=S_N.$ (2.7)

因此是真问题(1.1)的最优解.

3. 稳定点的相容性

在本节我们将研究二阶锥规划问题的SAA稳定点的相容性。

首先给出真问题(1.1)的Lagrange函数：

$L\left(x,\lambda ,\mu ,\xi \right)=f\left(x,\xi \right)+G{\left(x,\xi \right)}^{\text{T}}\lambda +{\left[A\left(\xi \right)x-b\right]}^{\text{T}}\mu .$ (3.1)

记 $\left(x^{*},{\lambda }^{*},{\mu }^{*}\right)$ 是问题(1.1)的KKT点，则 $\left(x^{*},{\lambda }^{*},{\mu }^{*}\right)$ 满足如下KKT条件：

$\{\begin{array}{l}0={\nabla }_x\mathbb{E}\left[L\left(x^{*},{\lambda }^{*},{\mu }^{*},\xi \right)\right]\\ \mathbb{E}\left[A\left(\xi \right)\right]x^{*}-b=0\end{array},{\lambda }^{*}\in N_K\left(\mathbb{E}\left[G\left(x^{*},\xi \right)\right]\right).$ (3.2)

则称 $x^{*}$ 是真问题(1.1)的一个稳定点。其中 $K=K_{m_1+1}\times \cdots \times K_{m_J+1}$。

下面给出随机二阶锥规划问题的Robinson约束规范和一阶最优性条件：

· Robinson约束规范：

$0\in \mathrm{int}\left\{\left(\begin{array}{c}\mathbb{E}\left[A\left(\xi \right)\right]x^{*}-b\\ \mathbb{E}\left[G\left(x^{*},\xi \right)\right]\end{array}\right)+\left(\begin{array}{c}\mathbb{E}\left[A\left(\xi \right)\right]\\ {\mathcal{J}}_x\mathbb{E}\left[G\left(x^{*},\xi \right)\right]\end{array}\right)R^n-\left\{0\right\}\times K\right\}.$ (3.3)

· $\left(x^{*},{\lambda }^{*},{\mu }^{*}\right)$ 满足一阶最优性条件：

$0={\nabla }_x\mathbb{E}\left[f\left(x^{*},\xi \right)\right]+{\mathcal{J}}_x\mathbb{E}{\left[G\left(x^{*},\xi \right)\right]}^{\text{T}}{\lambda }^{*}+\mathbb{E}{\left[A\left(\xi \right)\right]}^{\text{T}}{\mu }^{*},\lambda \in N_K\left(\mathbb{E}\left[G\left(x^{*},\xi \right)\right]\right).$ (3.4)

$\left(x^{*},{\lambda }^{*},{\mu }^{*}\right)$ 满足一阶最优性条件当且仅当 $\left(x^{*},{\lambda }^{*},{\mu }^{*}\right)$ 满足下列广义方程：

$0\in \mathbb{E}\left[\Phi \left(x^{*},{\lambda }^{*},{\mu }^{*},\xi \right)\right]+N_C\left(x^{*},{\lambda }^{*},{\mu }^{*}\right),$ (3.5)

其中

$\Phi \left(x^{*},{\lambda }^{*},{\mu }^{*},\xi \right)=\left(\begin{array}{c}{\nabla }_{x}f\left(x^{*},\xi \right)+{\mathcal{J}}_{x}G{\left(x^{*},\xi \right)}^{\text{T}}{\lambda }^{*}+A{\left(\xi \right)}^{\text{T}}{\mu }^{*}\\ -G\left(x^{*},\xi \right)\\ A\left(\xi \right)x^{*}-b\end{array}\right),C=R^n\times \left(-K\right)\times R^m.$

假设 $\left(\hat{x},\hat{\lambda },\hat{\mu }\right)$ 满足SAA问题的最优性条件，则 $\left(\hat{x},\hat{\lambda },\hat{\mu }\right)$ 满足下列广义方程：

$0\in \left(\begin{array}{c}{\nabla }_x{\hat{f}}_N\left(\hat{x}\right)+{\mathcal{J}}_x{\hat{G}}_N\left(\hat{x}\right)\hat{\lambda }+A_N\hat{\mu }\\ -{\hat{G}}_N\left(\hat{x}\right)\\ A_N\hat{x}-b\end{array}\right)+N_C\left(\hat{x},\hat{\lambda },\hat{\mu }\right).$ (3.6)

接下来，我们做出如下假设：

假设1. 样本 ${\xi }_1,\cdots ,{\xi }_N$ 是独立同分布的。

假设2. 对于几乎每一个 $\xi$， $G\left(\cdot ,\xi \right),f\left(\cdot ,\xi \right)$ 在S上是连续可微的。

假设3. 对于所有 $z\in S$ 和几乎每一个 $\xi$， $\left|G\left(z,\xi \right)\right|\le K\left(\xi \right)$，其中 $K\left(\xi \right)$ 是P-可积函数。

在假设1~3都满足的情况下，根据 [7] 我们能得到如下定理：

定理3.1 设S是 $R^m$ 中的紧子集，使 $S^{*}\subseteq S$，假设 $N\to +\infty$ 时， $S_N^{*}\subseteq S$， $S_N^{*}\ne \varphi$，则 $D\left(S_N^{*},S\right)\to 0$ w.p.1.

现在我们建立随机二阶锥规划问题的SAA稳定点的相容性。

定理3.2 若假设1~3都成立， ${\xi }_1,\cdots ,{\xi }_N$ 是独立同分布的， $x_N$ 是SAA问题(1.2)的一个稳定点， $x^{*}$ 是 $\left\{x_N\right\}$ 的聚点，则一定存在 $x_N$ 的子列 $\left\{x_{N_k}\right\}$ 收敛到 $x^{*}$， ${\lambda }_{N_k}$ 是关于 $\left\{x_{N_k}\right\}$ 的Lagrange乘子， $\left\{{\lambda }_{N_k}\right\}$ 如果有一个极限点 ${\lambda }^{*}$，则 $x^{*}$ 以概率为1是真问题(1.1)的一个稳定点。

证明：由于 $x_N$ 是SAA问题的一个稳定点，因此有

$0\in \left(\begin{array}{c}{\nabla }_x{\hat{f}}_N\left(x_N\right)+{\mathcal{J}}_x{\hat{G}}_N\left(x_N\right){\lambda }_{N_k}+A_N{\mu }^{*}\\ -{\hat{G}}_N\left(x_N\right)\\ A_N{x}_N-b\end{array}\right)+N_C\left(x_N,{\lambda }_{N_k},{\mu }^{*}\right),$ (3.7)

其中 $x_N\to x^{*}$， ${\lambda }_{N_k}\to {\lambda }^{*}$。

由一致大数定律知，当 $N\to +\infty$ 时，w.p.1，

$\begin{array}{l}\underset{x\in \mathbb{B}\left(x^{*},\delta \right)}{\text{sup}}\Vert {\hat{G}}_N(x_N)-\mathbb{E}\left[G\left(x_N,\xi \right)\right]\Vert \to 0,\\ \underset{x\in \mathbb{B}\left(x^{*},\delta \right)}{\text{sup}}\Vert {\hat{f}}_N(x_N)-\mathbb{E}\left[f\left(x_N,\xi \right)\right]\Vert \to 0,\\ \underset{x\in \mathbb{B}\left(x^{*},\delta \right)}{\text{sup}}\Vert A_N{x}_N-\mathbb{E}\left[A\left(\xi \right)\right]x_N\Vert \to 0,\end{array}$ (3.8)

因此w.p.1，

$\begin{array}{l}{\hat{G}}_N\left(x_N\right)-\mathbb{E}\left[G\left(x_N,\xi \right)\right]\to 0,\\ {\hat{f}}_N\left(x_N\right)-\mathbb{E}\left[f\left(x_N,\xi \right)\right]\to 0,\\ A_N{x}_N-\mathbb{E}\left[A\left(\xi \right)\right]x_N\to 0,\end{array}$ (3.9)

又因为G是实值连续函数，所以有w.p.1，

$\begin{array}{l}\mathbb{E}\left[G\left(x_N,\xi \right)\right]\to \mathbb{E}\left[G\left(x^{*},\xi \right)\right],\\ \mathbb{E}\left[f\left(x_N,\xi \right)\right]\to \mathbb{E}\left[f\left(x^{*},\xi \right)\right],\\ \mathbb{E}\left[A\left(\xi \right)\right]x_N\to \mathbb{E}\left[A\left(\xi \right)\right]x^{*},\end{array}$ (3.10)

于是当 $N\to +\infty$ 时， ${\hat{G}}_N\left(x_N\right)\to \mathbb{E}\left[G\left(x^{*},\xi \right)\right]$， ${\hat{f}}_N\left(x_N\right)\to \mathbb{E}\left[f\left(x^{*},\xi \right)\right]$， $A_N{x}_N\to \mathbb{E}\left[A\left(\xi \right)\right]x^{*}$。

w.p.1.

然后根据法锥的外半连续性，有

$\underset{N\to +\infty }{\lim \sup }{N}_C\left(x_N,{\lambda }_{N_k},{\mu }^{*}\right)\subseteq N_C\left(x^{*},{\lambda }^{*},{\mu }^{*}\right),$ (3.11)

所以

$0\in \mathbb{E}\left[\Phi \left(x^{*},{\lambda }^{*},{\mu }^{*},\xi \right)\right]+N_C\left(x^{*},{\lambda }^{*},{\mu }^{*}\right),$ (3.12)

其中

$\Phi \left(x^{*},{\lambda }^{*},{\mu }^{*},\xi \right)=\left(\begin{array}{c}{\nabla }_{x}f\left(x^{*},\xi \right)+{\mathcal{J}}_{x}G{\left(x^{*},\xi \right)}^{\text{T}}{\lambda }^{*}+A{\left(\xi \right)}^{\text{T}}{\mu }^{*}\\ -G\left(x^{*},\xi \right)\\ A\left(\xi \right)x^{*}-b\end{array}\right),C=R^n\times \left(-K\right)\times R^m.$

因此 $x^{*}$ 是真问题(1.1)的稳定点。

定理3.3 若假设1~3都成立， ${\xi }_1,\cdots ,{\xi }_N$ 是独立同分布的， $x_N$ 是SAA问题(1.2)的一个稳定点， $x^{*}$ 是 $\left\{x_N\right\}$ 的聚点， ${\lambda }_N$ 是关于 $\left\{x_N\right\}$ 的Lagrange乘子，则在Robinson约束规范(3.3)下， $x^{*}$ 以概率为1是真问题(1.1)的稳定点。

证明：不妨设 $x_N\to x^{*}$，由于 $x_N$ 是SAA问题的一个稳定点，则 $x_N$ 满足KKT条件，即

$0\in \left(\begin{array}{c}{\hat{f}}_N\left(x_N\right)+{\mathcal{J}}_x{\hat{G}}_N\left(x_N\right){\lambda }_N+A_N{\mu }^{*}\\ {\hat{G}}_N\left(x_N\right)\\ A_N{x}_N-b\end{array}\right)+N_{R^n\times \left(-K\right)\times R^m}\left(x_N,{\lambda }_N,{\mu }^{*}\right),$ (3.13)

不妨假设 $\left\{{\lambda }_N\right\}$ 无界，即 $\Vert {\lambda }_N\Vert \to +\infty$， $N\to +\infty$。

又因为 $\frac{{\lambda }_N}{\Vert {\lambda }_N\Vert }\to \bar{\lambda }$ 且 $\Vert \bar{\lambda }\Vert =1$，在(3.13)两端同时乘以 $\frac{1}{\Vert {\lambda }_N\Vert }$ 得

$0\in \frac{1}{\Vert {\lambda }_N\Vert }{\hat{f}}_N\left(x_N\right)+{\mathcal{J}}_x{\hat{G}}_N{\left(x_N\right)}^{\text{T}}\frac{{\lambda }_N}{\Vert {\lambda }_N\Vert }+\frac{1}{\Vert {\lambda }_N\Vert }{A}_N{\mu }^{*}+N_{R^n\times \left(-K\right)\times R^m}\left(x_N,{\lambda }_N,{\mu }^{*}\right),$ (3.14)

$\frac{{\lambda }_N}{\Vert {\lambda }_N\Vert }\in N_k\left({\hat{G}}_N\left(x_N\right)\right),$ (3.15)

令 $N\to +\infty$，则

$0\in \mathbb{E}{\left[G\left(x^{*},\xi \right)\right]}^{\text{T}}\bar{\lambda },$ (3.16)

$\bar{\lambda }\in N_k\left(\mathbb{E}\left[G\left(x^{*},\bar{\xi }\right)\right]\right),$ (3.17)

由Robinson约束规范得 $\bar{\lambda }=0$，与 $\Vert \bar{\lambda }\Vert =1$ 矛盾, 故 $\left\{{\lambda }_N\right\}$ 有界。不妨设 ${\lambda }_N\to {\lambda }^{*}$，则由定理3.2， $x^{*}$ 以概率为1是真问题(1.1)的稳定点。证毕。

4. 结论

本文基于样本均值近似的方法分析了随机二阶锥规划问题样本均值近似问题的相容性，建立了随机二阶锥规划问题的样本均值近似问题的最优解集以及稳定点的相容性理论。我们在随机二阶锥规划问题的Robinson约束规范和一阶最优性条件、以及真问题和SAA问题的随机广义方程的基础上，证明了随机二阶锥规划问题的样本均值近似问题的最优解集以及稳定点的相容性。