基于修正的Carroll函数的概率约束优化问题的对偶算法

A Dual Algorithm for Probabilistic Constrained Optimization Problems Based on Modified Carroll Functions

摘要: 本文用连续可微非凸函数描述的概率约束分析非线性随机优化问题。为此描述了潜在概率函数的水平集的切锥和法锥，并在此基础上，提出p-有效点的定义，形成问题的一阶和二阶最优性条件，基于p-有效点生成的概率函数的水平集，通过修正的Carroll函数生成一个对偶算法。

Abstract: In this paper, probabilistic constraints described by continuously differentiable non-convex functions are used to analyze nonlinear stochastic optimization problems. To this end, the tangent and normal cones of the level set of potential probability functions are described, and on this basis, the definition of p-effective points is proposed to form the first and second order optimality conditions of the problem. Based on the water-level set of probability functions generated by p-effective points, a dual algorithm is generated by the modified Carroll function.

1. 引言

目前，很多有重要价值的实际问题都属于概率约束优化问题，因而概率约束优化问题的研究具有重要的理论意义和应用价值。

如风险优化中的风险值计算问题，含新能源电力系统化调度问题，移动网络中的路线定位处理问题等均可建模为下述概率约束优化问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. Pr}\left[g\left(x\right)\ge Y\right]\ge p\text{,}\\ x\in X,\end{array}$ (PCOP)

其中$f:{ℝ}^n\to ℝ$ ，$g\left(x\right)=\left(g_1\left(x\right),\cdots ,g_m\left(x\right)\right)$ ，$g_i:{ℝ}^n\to {ℝ}^m$ ，是二次连续可微函数，$X\subset {ℝ}^n$ 是一个闭凸集，$Y\in {ℝ}^m$ 是随机的，概率$p\in \left(0,1\right)$ 是置信水平，Pr代表概率。

对于$p\in \left(0,1\right)$ ，Y的分布函数的水平集为

${\mathfrak{L}}_p=\left\{y\in R^m:\text{Pr}\left[Y\le y\right]\ge p\right\}$ .

由分布函数的单调性和右连续性易知，集合${\mathfrak{L}}_p$ 是非空且闭的，问题(PCOP)可表示为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)\in {\mathfrak{L}}_p,\\ x\in X.\end{array}$ (1)

非线性Lagrange函数是经典的Lagrange函数的修正形式，它关于乘子向量或约束函数是非线性函数；基于非线性Lagrange函数建立的求解非线性优化问题的对偶方法即为非线性Lagrange方法。由于对偶方法对原始变量的可行性没有限制。因此非线性Lagrange方法在求解约束优化问题中扮演着重要的角色。

2. 概率约束优化问题(PCOP)的凸近似形式

对于$y\in {ℝ}^m$ ，Y的分布函数为：

$F_Y\left(y\right)=\mathrm{Pr}\left[Y\le y\right]$ .

定义1 [1] 对于$p\in \left(0,1\right)$ ，$v\in {ℝ}^m$ 被称为概率分布函数$F_Y$ 的一个p-有效点，如果$F_Y\left(v\right)\ge p$ ，并且不存在$y\le v$ ，$y\ne v$ ，使得$F_Y\left(y\right)\ge p$ 。

对于$p\in \left(0,1\right)$ ，记

$ℰ=\left\{v|v是F_Y\left(y\right)的p\text{-}有效�\right\}$ ,

对于$v^j\in ℰ$ ，$j\in J$ ，定义

$K_j=v^j+{ℝ}_{+}^m$ ,

这里的J是一个任意集合。

命题1 [1] ${\mathfrak{L}}_p={\displaystyle \underset{j\in J}{\cup }{K}_j}$ 。

用${\mathcal{S}}_{m+1}$ 表示${ℝ}^{m+1}$ 中的单纯形，即

${\mathcal{S}}_{m+1}=\left\{\alpha \in {ℝ}^{m+1}:{\displaystyle \sum _{i=1}^{m+1}{\alpha }_i}=1,{\alpha }_i\ge 0,i=1,\cdots ,m+1\right\}$ ,

p-有效点集的凸包$coℰ$ 表示如下：

$coℰ=\left\{{\displaystyle \sum _{i=1}^{m+1}{\alpha }_i{v}^{j_i}}:\alpha \in {\mathcal{S}}_{m+1},j_i\in J\right\}$ .

命题2 [1] 对于每一个$p\in \left(0,1\right)$ ，集合$co{\mathfrak{L}}_p$ 是闭的。

定义2 设S为非空凸集，$x\in S$ ，若x不能用S中的两个不同点的凸组合表示，即不存在$x_1\in S$ ，$x_2\in S$ ，$x_1\ne x_2$ ，使

$x=\alpha x_1+\left(1-\alpha \right)x_2,0<\alpha <1,$

成立，则称x为S的一个极点。

命题3 [1] 对于每个点$p\in \left(0,1\right)$ ，有

$co{\mathfrak{L}}_p=coℰ+{ℝ}_{+}^m,$

$co{\mathfrak{L}}_p$ 的极点集$E\ne \varnothing$ ，且$E\subset coℰ$ 。

对于任意$p\in \left(0,1\right)$ ，${\mathfrak{L}}_p$ ，$co{\mathfrak{L}}_p$ 和$ℰ$ 有下界[1]。

引理1 [2] $co{\mathfrak{L}}_p=coE+{ℝ}_{+}^m$ 。

由此，问题(1)近似于如下问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)\in co{\mathfrak{L}}_p,\\ x\in X.\end{array}$ (2)

3. 最优性条件

记问题(2)的可行域为：

$\Phi =\left\{x|g\left(x\right)\in co{\mathfrak{L}}_p,x\in X\right\}$ .

$\nabla f\left(x\right)$ 为f在x处的梯度。为g在x处的Jacobian。

令$\widehat{x}\in \Phi$ ，则存在$\widehat{\omega }\in ℰ$ ，$\widehat{y}\in {ℝ}_{+}^m$ 使得$g\left(\widehat{x}\right)=\widehat{\omega }+\widehat{y}$ ，记

$I_0\left(\widehat{x}\right)=\left\{i|{\widehat{y}}_i=0,1\le i\le m\right\}$

是$\widehat{x}$ 处的积极约束，${\mathcal{K}}_X\left(\widehat{x}\right)$ 是集合X在$\widehat{x}\in X$ 处的可行方向锥，向量$\delta \in {\mathcal{K}}_X\left(\widehat{x}\right)$ 和一个p-有效点${\omega }_i^0$ 的凸组合有如下关系：

$\forall i\in I_0\left(\widehat{x}\right)$ , $g_i\left(\widehat{x}\right)+\langle \nabla g_i\left(\widehat{x}\right),\delta \rangle >{\omega }_i^0$ . (3)

条件(3)等价于问题(2)在可行点$\widehat{x}$ 处的Robinson’s约束规范条件。

命题4 [2] 在可行点$\widehat{x}\in \Phi$ 处的约束规范(3)条件下，记

$T_{\Phi }\left(\widehat{x}\right)=\left\{\delta \in T_X\left(\widehat{x}\right):\exists \omega \in ℰ,\exists \beta >0:g_i\left(\widehat{x}\right)+\langle \nabla g_i\left(\widehat{x}\right),\beta \delta \rangle \ge {\omega }_i\forall i\in I_0\left(\widehat{x}\right)\right\}$

为可行集$\Phi$ 在$\widehat{x}$ 处的切锥。

定义$L\left(x,u\right)=f\left(x\right)-\langle u,g\left(x\right)\rangle$ 。记${\mathcal{N}}_A\left(z\right)$ 为集合A在$z\in A$ 处的法锥。

定理1 [2] 假设$\widehat{x}$ 是问题(2)的一个局部最优解，且在$\widehat{x}$ 处满足条件(3)，则存在一个向量$\widehat{u}\in {ℝ}_{+}^m$ ，使得

$-{\nabla }_{x}L\left(\widehat{x},\widehat{u}\right)\in {\mathcal{N}}_X\left(\widehat{x}\right)$ , $-\widehat{u}\in {\mathcal{N}}_{co{\mathfrak{L}}_p}\left(g\left(\widehat{x}\right)\right)$ (4)

如果函数f是凸的，g是一个凹映射，存在某一向量$\widehat{u}\in {ℝ}_{+}^m$ ，使得$\widehat{x}\in \Phi$ 满足条件(4)，则$\widehat{x}$ 是问题(2)的一个全局最优解。

记

$\Lambda \left(\widehat{x}\right)=\left\{\widehat{u}|0\in {\nabla }_{x}L\left(\widehat{x},\widehat{u}\right)+{\mathcal{N}}_{co{\mathfrak{L}}_p}\left(g\left(\widehat{x}\right)\right)\right\}$ .

记切锥

$T_X\left(\widehat{x}\right)=\underset{t\searrow 0}{\lim }\sup \frac{X-x}{t}.$

定理2 [2] 假设$\widehat{x}\in \Phi$ 满足条件(3)和(4)，对于$u\in \Lambda \left(\widehat{x}\right)$ ，以及对于每个满足条件

$\langle \nabla f\left(\widehat{x}\right),\delta \rangle =0$ 且$\langle u,\nabla g\left(\widehat{x}\right)\delta \rangle =0$

的非零的$\delta \in T_X\left(\widehat{x}\right)$ ，有

$\langle \delta ,{\nabla }_x^{2}L\left(\widehat{x},u\right)\delta \rangle >0$ , (5)

则$\widehat{x}$ 是问题(2)的一个局部极小解。

记$I\subset J$ 是问题(2)的p-有效点集的子集，$\left|I\right|$ 表示它的基数。由引理1可知，

$g\left(x\right)={\displaystyle \sum _{j\in J}{\lambda }_j}{v}^j+y_i,v^j\in ℰ,\lambda \in {�}_{\left|I\right|},y_i\in {ℝ}_{+}^m$ .

于是，问题(2)的近似问题如下：

$\begin{array}{l}\underset{x,\lambda }{\min }f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)\ge {\displaystyle \sum _{j\in I}{\lambda }_j{v}^j},\\ x\in X,\\ \lambda \in S_{\left|I\right|}.\end{array}$ (6)

注意，当I = J时，问题(6)和(2)重合。

4. 求解问题(3)的对偶算法

考虑Polyak [3]在1992年提出的修正的Carroll函数：

$C\left(x,u,k\right)=\{\begin{array}{l}{f}_0\left(x\right)-k^{-1}{\displaystyle \sum _{i=1}^m{u}_i}\left[1-{\left(k{f}_i\left(x\right)+1\right)}^{-1}\right],x\in \mathrm{int}{\Omega }_k,\\ +\infty ,x\notin \mathrm{int}{\Omega }_k\text{,}\end{array}$

其中k > 0是惩罚参数，${\Omega }_k=\left\{x|1+k{f}_i\left(x\right)\ge 0,i=1,\cdots ,m\right\}$ ，则问题(6)的修正的Carroll函数有如下形式：

$F_{\rho }\left(x,\lambda ,u\right)=f\left(x\right)-{\rho }^{-1}{\displaystyle \sum _{i=1}^m{u}_i\left[1-{\left(\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right)+1\right)}^{-1}\right]},x\in \mathrm{int}{\Omega }_{\rho },$

其中，

${\Omega }_{\rho }=\left\{x|1+\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right)\ge 0,i=1,\cdots ,m\right\}$ .

对偶算法

步0选择一个p-有效点$v^1$ 使得存在一点$\tilde{x}\in X$ 满足$g\left(\tilde{x}\right)>v^1$ 。

令$J_1=\left\{v^1\right\}$ ，$k=1$ 。且选择$u^1\ge 0$ 。

步1 解决主问题

$\begin{array}{l}\underset{x,\lambda }{\min }{F}_{\rho ,k}\left(x,\lambda ,u^k\right)\\ x\in X,\lambda \in S_k\end{array}$ ,

设$\left(x^k,{\lambda }^k\right)$ 是这个问题的解。

步2 如果$k>1$ 且$\Vert u^k-u^{k-1}\Vert <\epsilon$ ，那么停止，否则继续步3。

步3 计算

$u_i^{k+1}=u_i^k\frac{1}{\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right)+1}$ .

步4 找到一个p-有效点$v^{k+1}$ 作为如下问题的解：

$\underset{z\in co{\mathfrak{L}}_p}{\min }\langle u^{k+1},z\rangle$ ,

令$J_{k+1}=\left\{v^{k+1}\right\}\cup J_k$ 。

步5 令$k\to k+1$ ，然后转步1。

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

A1存在一个数$d>0$ ，使得随机向量Y的两个实现间的距离大于d。

A2集合X是凸的、紧致的。

定理3 [2]存在一个有限子集$I\subseteq J$ ，使得问题(2)的局部一阶最优性条件和问题(6)的等价。

定理4 假设A1和A2，且问题(2)的可行域非空，则对于参数$\rho >0$ ，由对偶算法产生的序列$\left\{x^k\right\}$ 和$\left\{u^k\right\}$ 的聚点$\widehat{x}$ ，$\widehat{u}$ ，满足问题(2)的一阶最优性条件，此外，若$\widehat{x}$ 满足条件(3)和(5)，那么$\widehat{x}$ 是问题(2)的一个局部极小解。

证明：由于在A1下，只存在许多有限的p-有效点，算法没有产生p-有效点的非有限序列。因此，在某次迭$k_0$ 后，没有新的p-有效点在步4中出现，当X紧致，$\left\{x^k\right\}$ 有一个收敛到子序列的聚点。由于g的连续性，${\left\{g\left(x^k\right)\right\}}_{k\in K}$ 有一个聚点$g\left(\widehat{x}\right)$ 。我们记$z^k={\displaystyle \sum _{j\in J_k}{\lambda }_j^k{v}^j}$ 。由于有限个p-有效点存在，集合$ℰ$ 是有界的且${\left\{z_k\right\}}_{k\in K}$ 在$co{\mathfrak{L}}_p$ 中有一聚点，我们记作$\widehat{z}$ 。相似地，序列$\left\{{\lambda }^k\right\}$ 有聚点$\widehat{\lambda }\in S_{k_0}$ 且$\widehat{z}={\displaystyle \sum _{j\in J_k}{\widehat{\lambda }}_j{}^k{v}^j}$ 。我们可以选择一个迭代序列$\mathcal{K}\subset \left\{1,2,3,\cdots \right\}$ 以至于这些聚点是相关子序列的极限。记$J=\left\{i:\widehat{z}<g\left(\widehat{x}\right)\right\}$ 我们注意到对于足够大的$k\in \mathcal{K}$ ，$\rho$ 足够大的时候，我们得到$u_i^k=0$ 。而且，根据算法步3，对于$i\notin J$ ，有

$u_i^{k+1}=\frac{1}{\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right)+1}$ . (7)

我们将证明对于$i\notin J$ ，${\widehat{z}}_i=g_i\left(\widehat{x}\right)$ 。假设对于某个$i\notin J$ ，${\widehat{z}}_i>g_i\left(\widehat{x}\right)$ 成立，那么$\underset{k\to \infty }{\lim }{u}_i^k=\infty$ 。此外，k足够大时，修正的Carroll函数有如下形式：

$F_{\rho }\left(x,\lambda ,u\right)=f\left(x\right)-{\rho }^{-1}{\displaystyle \sum _{i=1}^m{u}_i\left[1-{\left(\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right)+1\right)}^{-1}\right]}$ .

因此，$\underset{k\to \infty }{\lim }{F}_{\rho }\left(x^k,{\lambda }^k,u^k\right)=\infty$ 。另一方面，设$\tilde{\lambda }={\left(1,0,\cdots ,0\right)}^{{\rm T}}\in S_{J_k}$ ，我们得到$\left(\tilde{x},\tilde{\lambda }\right)\in X\times S_{J_k}$ 。当k足够大时，

$F_{\rho }\left(\tilde{x},\tilde{\lambda },u\right)=f\left(\tilde{x}\right)-{\rho }^{-1}{\displaystyle \sum _{i=1}^m{u}_i\left[1-{\left(\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\tilde{\lambda }}_j{v}_i^j}\right)+1\right)}^{-1}\right]}\le f\left(\tilde{x}\right)<F_{\rho ,k}\left(x^k,{\lambda }^k,u^k\right)$

这和$\left(x^k,{\lambda }^k\right)$ 是步骤一中主问题的解的结论是矛盾的，因此${\widehat{z}}_i\le g_i\left(\widehat{x}\right)$ ，这表明对于所有的$i\notin J$ ，${\widehat{z}}_i=g_i\left(\widehat{x}\right)$ 。结合(7)式得到，$\left\{u^k\right\}$ 有一个聚点$\widehat{u}$ ，使得对于所有$i:\widehat{u}>0$ ，有${\widehat{z}}_i=g_i\left(\widehat{x}\right)$ 。

步1中主问题的最优性条件是：

对于足够大的$k\in \mathcal{K}$ ，我们可以将步1中主问题的最优性条件写成

$-\nabla F\left(x^k,u^{k+1}\right)\in {\mathcal{N}}_X\left(x^k\right)$ (8)

$-V_{J_0}^{{\rm T}}{u}^k\in {\mathcal{N}}_{S_{k_0}}\left({\lambda }^k\right)$ (9)

条件(9)意味着

$0\ge \langle -u^k,V_{J_0}\left(\lambda -{\lambda }^k\right)\rangle =\langle -u^k,V_{J_0}\lambda -z^k\rangle$ (10)

假设存在一点$\omega \in co{\mathfrak{L}}_p\backslash co\left\{v^j,j\in J_k\right\}$ 使得$\langle u^k,\omega -z^k\rangle <0$ ，应用这个假设和(10)，我们得到

$\langle -u^k,\omega -v^k\rangle =\langle -u^k,\omega -z^k\rangle +\langle -u^k,z^k-v^k\rangle >\langle -u^k,z^k-v^k\rangle \ge 0$ .

不等式$\langle -u^k,\omega -v^k\rangle >0$ 和问题$\underset{z\in co{\mathfrak{L}}_p}{\min }\langle u^{k+1},z\rangle$ 的最优性条件是矛盾的，这说明$-u^k\in N_{co{\mathfrak{L}}_p}\left(v^k\right)$ 。因此，$-u^k\in N_{co{\mathfrak{L}}_p}\left(z^k\right)$ ，结合(8)，表明

$-\nabla F\left(x^k,u^{k+1}\right)\in {\mathcal{N}}_X\left(x^k\right)$ (11)

$-u^{k+1}\in {\mathcal{N}}_{co{\mathfrak{L}}_p}\left(z^{k+1}\right)$ (12)

对k取极限，并将Ruszczynski [4]中的引理2.42应用到(11)-(12)，我们得到

$-\nabla F\left(\widehat{x},\widehat{u}\right)\in {\mathcal{N}}_X\left(\widehat{x}\right)$ , $-\widehat{u}\in {\mathcal{N}}_{co{\mathfrak{L}}_p}\left(g\left(\widehat{x}\right)\right)$ .

因此，$\widehat{x}$ 满足问题(2)的条件(4)，根据定理2，$\widehat{x}$ 是问题(2)的一个局部极小解。证毕。