随机对称锥规划问题的一阶最优性条件的相容性分析

Compatibility Analysis of First-Order Optimality Conditions for Stochastic Symmetric Cone Programming

摘要: 随机对称锥规划问题是一类应用十分广泛的问题，在工程设计、通讯、控制等实际领域有着重要的应用。随着优化问题不断的深入研究和对称锥规划理论的完善，许多很难甚至不能解决的问题，都可以转化为对称锥优化模型。因此，关于随机对称锥规划问题的研究有着重要的价值。对于随机对称锥规划问题的研究，本文采用了基于样本的近似方法，通常需要考虑样本均值近似问题的相容性，本文将对随机对称锥规划问题的样本均值近似问题的最优值和一阶最优性条件的相容性进行分析。

Abstract: Stochastic symmetric cone programming problem is a very wide range of problems, which has im-portant applications in engineering design, communication, control and other practical fields. With the continuous in-depth study of optimization problems and the improvement of symmetric cone programming theory, many difficult or even unsolvable problems can be transformed into symmet-ric cone optimization model. Therefore, the research on stochastic symmetric cone programming is of great value. For the research of stochastic symmetric cone programming, this paper adopts the sample based approximation method, which usually needs to consider the compatibility of the sample mean approximation problem. This paper will analyze the compatibility of the optimal val-ue and the first-order optimality condition of the sample mean approximation problem of stochastic symmetric cone programming.

1. 引言

随机规划问题就是通过使用随机变量，在问题中引入不确定性的数学规划问题，最开始是由Dantzing和Ferguson [1] 在研究某航线航班的数量最优化问题中提出的，并在解决问题的过程中，建立了有偿的两阶段随机规划问题。Dai [2] 等人对一类两阶段随机规划问题进行了研究，并将其中的目标函数用其样本均值替代，其研究是将一个随机优化问题转化为一个确定的问题。关于对称锥优化问题，Faybusovich [3] 提出了利用内点法来解决线性对称锥规划问题，并指出了其中涉及到的多项式的复杂性，在此之后，Schmieta和Alizadeh [4] 提出了利用牛顿法对线性对称锥规划问题的KKT系统进行求解。随着对称锥优化问题研究的不断深入，许多问题都可以转化为对称锥优化模型，并可以进行求解，得到比较满意的结果，Lieven [5] 和Klerk [6] 等学者在对称锥优化问题中的半定规划的问题的研究上取得了很多的成果。Bastin [7] 等学者提出了带有等式和不等式约束的随机规划问题：

$\underset{z\in S}{\min }g\left(z\right)={\mathbb{E}}_p\left[G\left(z,\xi \right)\right]$

$\text{s}\text{.t}.c_j\left(z\right)\ge 0,j=1,\cdots ,k,$

$c_j\left(z\right)=0,j=k+1,\cdots ,M.$

Bastin等学者利用了蒙特卡罗 [8] 工具来解决这个问题，得到了对应的样本均值近似问题： $\underset{z\in S}{\min }{\hat{g}}_N(\; z\; )$

$\text{s}\text{.t}.{\hat{c}}_{j_N}\left(z\right)\ge 0,j=1,\cdots ,k,$

${\hat{c}}_{j_N}\left(z\right)=0,j=k+1,\cdots ,M.$

其中， ${\hat{g}}_N\left(z\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}G\left(z,{\xi }_i\right)}$， ${\hat{c}}_{j_N}\left(z\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}{A}_j}\left(z,{\xi }_i\right)$。在本文中我们将要研究一类更广泛的随机对称锥

规划问题，考虑如下随机对称锥规划问题：

$\underset{x\in X}{\min }g\left(x\right)=\mathbb{E}\left[F\left(x,\xi \right)\right]$ (p1)

$\text{s}\text{.t}.\mathbb{E}\left[G\left(x,\xi \right)\right]\in K,$

其中， $x\in X$ 是决策变量，X是 $R^n$ 中的一个非空闭凸集且为这个问题的可行解集， $\xi$ 是定义在概率空间 $\left(\Xi ,\mathcal{F},P\right)$ 上的实随机向量。F是 $R^n\times R^m\to R$ 的实值函数， $\mathbb{E}$ 表示数学期望， $K\subseteq R^n$ 是对称锥，如学者Faraut [9] 文章中所示，对称锥要满足如下条件：

1) K是齐次的，

2) K是自对偶的。

在本文的研究中，我们将对称锥用一个具体的模型表达 [9]：

$K=\left\{y\circ y|y\in \epsilon \right\},$

其中， $\epsilon$ 是一个具有内积运算的有限维空间； $\circ$ 是一个双线性映射，且满足如下三个条件：对于所有的 $y,z,w\in \epsilon$，

a) $y\circ z=z\circ y,$

b) $y\circ \left(y^2\circ z\right)=y^2\circ \left(y\circ z\right),$

c) $\langle y\circ z,w\rangle =\langle y,z\circ w\rangle .$

对于满足上述条件的 $\langle \epsilon ,\circ \rangle$，我们称之为欧式Jordan代数。为解决(p1)问题，本文采取样本均值近似方法。对于 $\xi$ 的N个独立同分布样本 ${\xi }_1,\cdots ,{\xi }_N$，(p1)问题相应的样本均值近似问题为：

$\underset{x\in X}{\min }{\hat{g}}_N\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}F}\left(x,{\xi }_i\right),$ (p2)

$\text{s}\text{.t}.{\hat{G}}_N\left(x\right)=\frac{1}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}G\left(x,{\xi }_i\right)}=y\circ y.$

我们将(p1)称为原问题，(p2)称为样本均值近似问题。

接下来我们研究样本均值近似问题的最优值的相容性以及一阶最优性条件的相容性。注意到问题(p1)和(p2)的稳定点条件均可写为下列广义方程的形式：

$0\in \mathbb{E}\left[H\left(x,\xi \right)\right]+N\left(x\right),$ (p3)

其中，H是向量值函数，N是集值映射。

2. 一阶最优性条件的相容性分析

为研究方便，我们先给出如下假设。

A.0 对于 $\xi$ 的抽样是满足独立同分布的。

A.1 对于每一个 $\xi$，函数 $F\left(·,\xi \right)$ 和 $G\left(·,\xi \right)$ 在X上是连续可微的。

A.2 对于所有的 $x\in X$ 和几乎每个 $\xi$，都有 ${\mathbb{E}}_p\left[k\right]$ 是有限的，且 $\Vert F\left(x,\xi \right)\Vert ,\Vert G\left(x,\xi \right)\Vert$ 都小于等于 $k\left(\xi \right)$，其中 $k\left(\xi \right)$ 为P-可积函数。

A.3 每个梯度分量 $\frac{\partial }{\partial {\left[x\right]}_{\mathcal{l}}}F\left(x,\xi \right)$ 和 $\frac{\partial }{\partial {\left[x\right]}_{\mathcal{l}}}G\left(x,\xi \right)$ 是被P-可积函数控制的。

我们用 $S^{*}$ 和 $S_N^{\ast }$ 分别表示广义方程(p3)和SAA问题的解集，则我们可以根据 [10] 得到如下结果。

定理1.1：设C为 $R^n$ 上的一个紧子集，如果

1) (p1)问题的最优解集为 $S^{*}$ 且 $\varnothing \ne S^{*}\subseteq C$。

2) $\mathbb{E}\left[H\left(x,\xi \right)\right]$ 在C上是连续实值函数。

3) 当N足够大时， $\varnothing \ne S_N^{\ast }\subseteq C$。

则 $\mathbb{D}\left(S_N^{\ast },S^{*}\right)\to 0\text{w}\text{.p}\text{.1}$ 当 $N\to +\infty$ 时成立。

我们假设条件A.0~A.3成立，且对于其中每一个 $\xi$， $G\left(·,\xi \right)$ 关于 $-K$ 是凸的，对于每一个 $\xi$ 来说，映射 $x\mapsto G\left(·,\xi \right)-K$ 是集值映射，并有下列约束条件成立：

$0\in \mathrm{int}\left\{\mathbb{E}\left[G\left(x,\xi \right)\right]-K\right\}.$

根据Shapiro [11] 的研究成果可知，如果 $x^{*}$ 为局部最优解，则存在 ${\lambda }^{*}\in N_K\left\{\mathbb{E}\left[G\left(x^{*},\xi \right)\right]\right\}$，使得 $\left(x^{*},{\lambda }^{*}\right)$ 满足：

$0\in {\nabla }_x\mathbb{E}\left[F\left(x^{*},\xi \right)\right]+{\mathcal{J}}_x\mathbb{E}{\left[G\left(x^{*},\xi \right)\right]}^{\top }{\lambda }^{*}+N_K\left(x^{*}\right).$ (1.1)

最优性条件(1.1)也可以写成如下形式：

$0\in \mathbb{E}\left[P\left(x^{*},{\lambda }^{*},\xi \right)\right]+N_{X\times K}\left(x^{*},{\lambda }^{*}\right),$

其中，

$P\left(x,\lambda ,\xi \right)=\left(\begin{array}{c}L\left(x,\lambda ,\xi \right)\\ G\left(x,\xi \right)\end{array}\right),$

$L\left(x,\lambda ,\xi \right)={\nabla }_{x}F\left(x,\xi \right)+{\mathcal{J}}_{x}G{\left(x,\xi \right)}^{\top }\lambda ,$

P为 $R^n\times R^n\times \Xi \to R^{2n}$ 上的连续函数。相应地，如果 $x_N$ 是问题(p2)的局部最优解，则应存在 ${\lambda }_N$ 且 $\left(x_N,{\lambda }_N\right)$ 满足如下条件：

$0\in P_N\left(x_N,{\lambda }_N\right)+N_{X\times K}\left(x_N,{\lambda }_N\right),$ (1.2)

其中，

${\hat{P}}_N\left(x,\lambda ,\xi \right)=\left(\begin{array}{c}{\hat{L}}_N\left(x,\lambda ,\xi \right)\\ {\hat{G}}_N\left(x,\xi \right)\end{array}\right),$

${\hat{L}}_N\left(x,\lambda \right)=\nabla {\hat{F}}_N\left(x,\xi \right)+{\mathcal{J}}_{X}G{\left(x^{*},\xi \right)}^{\top }\lambda .$

下面我们建立SAA问题的一阶最优性条件的相容性。

令

$S=\left\{\left(x^{*},{\lambda }^{*}\right)\in X\times K\text{|}\mathbb{E}\left[P\left(x^{*},{\lambda }^{*},\xi \right)\right]+N_{X\times K}\left(x^{*},{\lambda }^{*}\right)\right\},$

${\hat{S}}_N=\left\{\left(x_N,{\lambda }_N\right)\in X\times K\text{|}\mathbb{E}\left[{\hat{P}}_N\left(x_N,{\lambda }_N\right)\right]+N_{X\times K}\left(x_N,{\lambda }_N\right)\right\}.$

定理1.2：X是 $R^n$ 中的非空闭凸集，设假设A.0-A.1条件成立，如果有

$0\in P_N\left(x_N,{\lambda }_N\right)+N_{X\times K}\left(x_N,{\lambda }_N\right),$

$x^{*}$ 是 $\left\{x_N\right\}$ 的聚点且存在 $\left\{x_N\right\}$ 的子列 $\left\{x_{N_K}\right\}$ 收敛到 $x^{*}$。 ${\lambda }_{N_K}$ 是 $x_{N_K}$ 相应的一个Lagrange乘子且当N趋于无穷大时， $\left\{{\lambda }_{N_K}\right\}$ 收敛到 ${\lambda }^{*}$，则有 $0\in \mathbb{E}\left[P\left(x^{*},{\lambda }^{*},\xi \right)\right]+N_{X\times K}\left(x^{*},{\lambda }^{*}\right)$，即 $x^{*}$ 为原问题(p1)的稳定点。

证明：由于 $0\in \mathbb{E}\left[P_N\left(x_N,{\lambda }_N\right)\right]+N_{X\times K}\left(x_N,{\lambda }_N\right)$，所以 $-{\hat{P}}_N\left(x_N,{\lambda }_N\right)\in N_{X\times K}\left(x_N,{\lambda }_N\right)$。又因为在A.0-A.3条件下，g和 ${\hat{g}}_N$ 均为 $R^n\times R^m\to R$ 的连续实值函数且 ${\hat{g}}_N(·)$ 一致收敛到 $g(·)$， $G\left(·,\xi \right)$ 在X上是连续可微的，不妨设当 $N\to +\infty$ 时，有 $x_N\to x^{*}$， ${\lambda }_N\to {\lambda }^{*}$。根据 [11] 命题5.1可知，

$\Vert {\hat{P}}_N\left(x_N,\xi ,{\lambda }_N\right)-\mathbb{E}\left[P\left(x_N,\xi ,{\lambda }_N\right)\right]\Vert \to 0\text{w}\text{.p}\text{.1,}N\to \text{+}\infty ,$

所以

${\hat{P}}_N\left(x_N,\xi ,{\lambda }_N\right)\to \mathbb{E}\left[P\left(x_N,\xi ,{\lambda }_N\right)\right],$

进而

$\hat{P}\left(x_N,\xi ,{\lambda }_N\right)\to \mathbb{E}\left[P\left(x^{*},\xi ,{\lambda }^{*}\right)\right],$

根据法锥的外半连续性，我们有

$\underset{N\to \infty }{\lim \sup }{N}_{X\times K}\left(x_N,{\lambda }_N\right)\subseteq N_{X\times K}\left(x^{*},{\lambda }^{*}\right),$

这可以得到

$-\mathbb{E}\left[P\left(x^{*},\xi ,{\lambda }^{*}\right)\right]\in N_{X\times K}\left(x^{*},{\lambda }^{*}\right),$

即

$0\in \mathbb{E}\left[P\left(x^{*},{\lambda }^{\ast },\xi \right)\right]+N_{X\times K}\left(x^{*},{\lambda }^{*}\right).$

综上， $\left(x^{*},{\lambda }^{*}\right)$ 以概率1满足原问题的一阶最优性条件。

在定理1.2中，我们假设拉格朗日乘子是有界的，那么如果假设乘子是无界的，也可以通过增加条件得到类似的结果。

定理1.3：X是 $R^n$ 中的非空闭凸集，在A.0~A.3的假设下， $x^{*}$ 是 $\left\{x_N\right\}$ 的聚点。如果 $\left(x_N,{\lambda }_N\right)$ 满足SAA问题的一阶最优性条件，则在下列约束规范下，

$0\in \mathrm{int}\left\{\mathbb{E}\left[G\left(x^{*},\xi \right)\right]-K\right\}$

$\left\{{\lambda }_N\right\}$ 有界且我们有 $x^{*}$ 以概率1满足原问题的一阶最优性条件。

证明：假设 $\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$。

在(1.2)式两侧同时乘 $\frac{1}{\Vert {\lambda }_N\Vert }$ 得

$0=\frac{1}{\Vert {\lambda }_N\Vert }{\hat{F}}_N\left(x_N\right)+\mathcal{J}{\hat{G}}_N{\left(x_N\right)}^{\top }\frac{{\lambda }_N}{\Vert {\lambda }_N\Vert }.$

令 $N\to +\infty$ 可得

$0=\mathbb{E}{\left[G\left(x^{*},\xi \right)\right]}^{\top }\bar{\lambda },$

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

由 $0\in \mathrm{int}\left\{\mathbb{E}\left[G\left(x^{*},\xi \right)\right]-K\right\}$，可知 $\bar{\lambda }=0$，这与假设矛盾，所以 $\left\{{\lambda }_N\right\}$ 有界，所以不妨设 ${\lambda }_N\to {\lambda }^{*}$，接下来的证明同定理1.2。

3. 最优值的相容性分析

下面我们对(p1)和(p2)问题的最优值进行相容性分析。设 $V^{*}$ 和 $V_N^{\ast }$ 分别为(p1)和(p2)问题的最优值，我们给出如下定理。

定理2.1：在定理1.1假设的前提下， $X_N$ 为 $R^n$ 的一个子集，令 $Z_N$ 是SAA问题的可行集，Z为原问题的可行集，满足：

(1) 如果 $x_N\in Z_N$ 并且 $x_N\to x$，其中 $x\in Z$，

(2) 对于某个点 $x\in S^{*}$，存在一个序列 $x_N\in Z_N$ 使得 $x_N\to x\text{w}\text{.p}\text{.1}$，

那么 $V_N^{*}\to V^{*}\text{w}\text{.p}\text{.1}$，当 $N\to \infty$ 时。

证明：假设 $x_N\in S_N^{\ast }$，因为 $S_N^{\ast }$ 为紧集，不妨假设 $x_N\to x^{*}\text{w}\text{.p}\text{.1}$。因为 $S_N^{\ast }\subset X_N$，有 $x_N\in Z_N$。又条件(2)成立，所以 $x^{*}\in Z$。根据 [11] 中命题5.1，有

$V_N^{\ast }={\hat{g}}_N\left(x_N\right)\to g\left(x^{*}\right)\text{w}\text{.p}\text{.1,}N\to \infty$

并且

$\underset{N\to \infty }{\lim \inf }{V}_N^{*}\ge V^{*}\text{w}\text{.p}\text{.1}$.

另一方面，由条件(3)得，存在一个序列 $x_N\in X_N$ 收敛到一个 $x\in S^{*}\text{w}\text{.p}\text{.1}$。因此当 $N\to \infty$ 时，

$V_N^{*}\le {\hat{g}}_N\left(x_N\right)\to g\left(x\right)=V^{*}\text{w}\text{.p}\text{.1}$

因为 $\underset{N\to \infty }{\lim \sup }{V}_N^{*}\le V^{*}\text{w}\text{.p}\text{.1}$，所以当 $N\to \infty$，有 $V_N^{*}\to V^{*}\text{w}\text{.p}\text{.1}$。

4. 结论

本文利用样本均值近似方法来对随机对称锥规划问题的相容性进行分析，建立了随机对称锥规划问题的样本均值近似问题的一阶最优性条件的相容性理论和最优值相容性理论。我们在Shapiro介绍的随机广义方程样本均值近似问题相容性的基础上，给出了我们的结论，并在一定约束规范条件下，建立了随机对称锥规划问题的一阶最优性条件的相容性理论。