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

A Dual Algorithm for Probabilistic Constraint Problems Based on Modified Exponential Functions

摘要: 本文通过连续可微的非凸函数所形成的概率约束，来分析概率约束问题。描述了潜在的概率函数的水平集的切锥和法锥。进一步，基于p-有效点的概念，形成这些问题的一阶和二阶最优性条件。对于离散分布函数的这种情况，产生一个基于修正的指数函数的对偶算法来解决概率约束问题。

Abstract: In this paper, the problem of probability constraints is analyzed by means of the probability constraints formed by continuously differentiable non-convex functions. The tangent and normal cones of the level set of potential probability functions are described. Further, based on the concept of p-efficient points, the first and second order optimality conditions of these problems are formed. For this case of the discrete distribution function, a dual algorithm based on the modified exponential function is generated to solve the probability constraint problem.

1. 引言

近年来，概率约束优化问题成为备受关注的研究热点之一。该类问题在随机优化领域具有重要的理论意义和应用价值，已经广泛地应用于很多实际问题中。

很多实际问题可以通过概率约束优化问题进行解决，如现金匹配、风险优化、供应链管理、水资源管理等，该类问题均可建模为：

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

其中，$f:{ℝ}^n\to ℝ$ ，$g:{ℝ}^n\to {ℝ}^m$ 是二次连续可微函数，且

$g\left(x\right)=\left(g_1\left(x\right),g_2\left(x\right),\cdots ,g_m\left(x\right)\right).$

$\mathfrak{D}\subset {ℝ}^n$ 是一个闭凸集，$Y\in {ℝ}^m$ 是随机变量，$p\in \left(0,1\right)$ 为置信水平，Pr代表概率。

对于概率约束优化问题，国内外众多学者给出过不同的研究方法，Ruszczynski等学者[1]在2000年关于“包含整数值随机变量的概率约束优化问题”作出研究，基于p-有效点的定义，推导出各种等价问题的形式，又引入r-凹离散概率分布的概念解决“具有离散随机变量的概率约束优化问题”；Ruszczynski [2]在2002年针对“具有概率约束的随机优化问题”进行研究，这些约束涉及具有离散分布的随机变量，提出解决概率约束优化问题的“有效不等式和一般迭代算法”；Ruszczynski等人[3]在2004年，引入了p-有效点的概念后，将其应用于得到带有概率约束的非线性随机优化问题的等价问题以及最优性的充分必要条件中，从而提出了“概率约束问题的对偶方法”；Luedtke [4]在2010年针对联合概率约束线性规划的可行域非凸的问题，提出一个“混合整数规划公式”。Ruszczynski等人[5]又在2012年又提出了增广Lagrange方法。

非线性Lagrange函数是经典的Lagrange函数的修正形式，它关于乘子向量或约束函数是非线性函数；基于非线性Lagrange函数建立的求解非线性优化问题的对偶方法即为非线性Lagrange方法。由于对偶方法对原始变量的可行性没有限制。因此其在求解约束优化问题中扮演着重要的角色。Hestenes [6]与Powell [7]在1969年各自独立提出了近似增广Lagrange函数来求解具有等式约束的非线性优化问题。Boggs & Tolle [8]在1980年引入了一类新的乘子法，发展了对偶理论，对于具有不等式约束问题，Bertsekas [9]在1982年提出了非凸规划问题的修正的指数Lagrange函数，Polyak [10]在1992年给出了修正的Frish函数和修正的Carroll函数，提出相应的对偶算法。鉴于非线性优化问题对偶算法的有效性，本文基于修正的指数函数求解概率约束优化问题(1)的对偶算法。

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

定义2.1 [3]问题(1) Y的分布函数为

$F_Y\left(y\right)=\mathrm{Pr}\left[y\in {ℝ}^m:Y\le y\right]$ .

定义2.2 [3]对于$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^j|v^j是p\text{-}有效点,j\in J\right\}$

是Y的p-有效点集，其中J是一个任意集合。

对于$p\in \left(0,1\right)$ ，由于分布函数的单调性和右连续性易知，Y的分布函数的水平集

${\mathfrak{L}}_p=\left\{y\in {ℝ}^m:F_Y\left(y\right)\ge p\right\}$

是非空闭集，水平集${\mathfrak{L}}_p$ 的凸包$co{\mathfrak{L}}_p$ 也是闭的[3]。

则问题(1)表示为

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

定义

$K_j=v^j+{ℝ}_{+}^m,v^j\in ℰ,j\in J.$

命题2.1 [5]水平集可表示为

${\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\},$

那么，${\mathfrak{L}}_p$ 的凸包$c\text{o}{\mathfrak{L}}_p$ 也有下述表示。

命题2.2 [5]对于每个$p\in \left(0,1\right)$ ，有$co{\mathfrak{L}}_p=coℰ+{ℝ}_{+}^m$ 。

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

$co{\mathfrak{L}}_p$ 中的极点是p-有效点。记${ℰ}_0$ 为$co{\mathfrak{L}}_p$ 的极点集，${ℰ}_0$ 非空，且它包含于p-有效点集$ℰ$ [5]。

引理2.1 [5]集合$c\text{o}{\mathfrak{L}}_p$ 有如下表示：

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

问题(2)中${\mathfrak{L}}_p$ 凸化后，问题(2)转化为下述问题

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

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

记问题(3)的可行域为

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

设$K_{\mathfrak{D}}\left(\widehat{x}\right)$ ，$N_{\mathfrak{D}}\left(\widehat{x}\right)$ ，$T_{\mathfrak{D}}\left(\widehat{x}\right)$ 分别表示$\mathfrak{D}$ 在$\widehat{x}$ 处的可行方向锥，法锥，切锥。

给定可行点$\widehat{x}\in \Phi$ ，则存在$\widehat{\omega }\in coℰ$ ，$\widehat{y}\in {ℝ}_{+}^m$ ，使得$g\left(\widehat{x}\right)=\widehat{\omega }+\widehat{y}$ 。记$\widehat{x}$ 处的积极约束指标集为

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

对于向量$\delta \in K_{\mathfrak{D}}\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$ . (4)

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

定义Lagrange函数

$L\left(x,u\right)=f\left(x\right)-\langle u,g\left(x\right)\rangle .$

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

$-{\nabla }_{x}L\left(\widehat{x},\widehat{u}\right)\in N_{\mathfrak{D}}\left(\widehat{x}\right)$ , $-\widehat{u}\in N_{co{\mathfrak{L}}_p}\left(g\left(\widehat{x}\right)\right)$ , (5)

记$\Lambda \left(\widehat{x}\right)$ 为满足(5)中出现的Lagrange乘子的集合。记$\mathcal{J}g\left(x\right)$ 为g在x处的Jacobian。

定理3.2 [5]设$\widehat{x}\in \Phi$ 满足条件(4)和(5)，且对于$u\in \Lambda \left(\widehat{x}\right)$ ，以及使得

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

成立的每个非零的$\delta \in T_{\mathfrak{D}}\left(\widehat{x}\right)$ ，有下述不等式成立，

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

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

设$I\subset J$ 是问题(3)的p-有效点集中的极点集，$\left|I\right|$ 是它的基数，我们考虑由问题(3)转化成的近似问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)\ge {\displaystyle \sum _{j\in I}{\lambda }_j}{v}^j\text{,}\\ x\in \mathfrak{D},\lambda \in {\mathcal{S}}_{\left|I\right|}.\end{array}$ (7)

当$I=J$ 时，(7)与(3)重合。

考虑Bertsekas (1982) [9]提出的修正的指数函数

$F\left(x,u,k\right)=f_0\left(x\right)-k^{-1}{\displaystyle \sum _{i=1}^m{u}_i}\left[1-{\text{e}}^{-k{f}_i\left(x\right)}\right];$

其中，$k>0$ 是惩罚参数，则问题(2)的修正的指数函数

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

其中，$F_{\rho ,\left|I\right|}:{ℝ}^m\times {\mathcal{S}}_{m+1}\times {ℝ}^m\to ℝ$ ，子集$I\subseteq J$ ，$\rho >0$ 是惩罚参数。

对偶算法 下述算法中，我们用$\epsilon$ 作为一个准确参数

步骤0：选择一个p-有效点$v^1$ ，使得存在一点$\tilde{x}\in \mathfrak{D}$ ，满足$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 \mathfrak{D},\lambda \in {\mathcal{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{\text{e}}^{-\rho \left[g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j{v}_i^j}\right]}$ , $i=1,\cdots ,k$ .

步骤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) 存在一个数$\kappa \text{>0}$ ，使得随机向量Y的两个实现间的距离大于$\kappa$ ；

(A2) 集合$\mathfrak{D}$ 凸且紧致。

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

因此，问题(3)在$\left(\widehat{x},\widehat{\lambda }\right)$ 处关于$\widehat{u}$ 的一阶最优性条件是：

$-{\nabla }_{x}L\left(\widehat{x},\widehat{u}\right)\in N_{\mathfrak{D}}\left(\widehat{x}\right)$ , $-v_I^{{\rm T}}\widehat{u}\in N_{{\mathcal{S}}_{\left|I\right|}}\left(\widehat{\lambda }\right)$ .

定理3.4在假设(A1)和(A2)成立的基础上，假设问题(3)有可行域非空，则参数$\rho >0$ 的修正的指数函数方法产生的序列$\left\{x^k\right\}$ 和$\left\{u^k\right\}$ 的聚点$\widehat{x}$ 和$\widehat{u}$ ，满足(3)的一阶最优性条件，此外，若$\widehat{x}$ 满足条件(6)和(4)，那么$\widehat{x}$ 是(3)的一个局部极小解。

证明：由于在(A1)下，只存在许多有限的p-有效点，算法没有产生p-有效点的非有限序列。因此，在某次迭$k_0$ 后，没有新的p-有效点在步骤4中产生，当$\mathfrak{D}$ 紧致，$\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-有效点存在，集合

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

是有界的且${\left\{z_k\right\}}_{k\in K}$ 在$co{\mathfrak{L}}_P$ 中有一聚点，我们记作$\widehat{z}$ 。相似地，序列$\left\{{\lambda }^k\right\}$ 有聚点$\widehat{\lambda }\in {\mathcal{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}=u_i^k{\text{e}}^{-\rho \left[g_i\left(x\right)-{\displaystyle \sum _{j\in I}{z}_i^k}\right]}$ . (8)

我们将证明对于$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足够大时，修正的指数函数有如下形式：

$F_{\rho ,k}\left(x^k,{\lambda }^k,u^k\right)=f\left(x\right)-{\rho }^{-1}{\displaystyle \sum _{i=1}^k{u}_i^k\left[1-{\text{e}}^{-\rho \left(g_i\left(x\right)-z_i^k\right)}\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 {\mathcal{S}}_{J_k}$ ，我们得到$\left(\tilde{x},\tilde{\lambda }\right)\in \mathfrak{D}\times {\mathcal{S}}_{J_k}$ 。当k足够大时，得到

$F_{\rho ,k}\left(\tilde{x},\tilde{\lambda },u^k\right)=f\left(\tilde{x}\right)-{\rho }^{-1}{\displaystyle \sum _{i=1}^k{u}_i^k\left[1-{\text{e}}^{-\rho \left(g_i\left(\tilde{x}\right)-v_i^1\right)}\right]}$,

所以

$F_{\rho ,k}\left(\tilde{x},\tilde{\lambda },u^k\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)$ 。结合(8)式得到，$\left\{u^k\right\}$ 有一个聚点$\widehat{u}$ ，使得对于所有$i:\widehat{u}>0$ ，有${\widehat{z}}_i=g_i\left(\widehat{x}\right)$ 。

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

$-\nabla f\left(x^k\right)+{\displaystyle \sum _{i=1}^k{u}_i^k}{\text{e}}^{-\rho \left(g_i\left(x\right)-{\displaystyle \sum _{j\in I}{\lambda }_j^k{v}_i^j}\right)+1}\nabla g_i\left(x^k\right)\in {{\rm N}}_{\mathfrak{D}}\left(x^k\right)$ (9)

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

对于足够大的$k\in \mathcal{K}$ ，我们可以改写(9)式为

$-\nabla F\left(x^k,u^{k+1}\right)\in {{\rm N}}_{\mathfrak{D}}\left(x^k\right)$ (11)

条件(10)意味着

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

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

$\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(z\right)$ 是矛盾的，这说明$-u^k\in {{\rm N}}_{co{\mathfrak{L}}_p}\left(v^k\right)$ 。因此，$-u^k\in {{\rm N}}_{co{\mathfrak{L}}_p}\left(z^k\right)$ ，结合(11)，表明

$-\nabla F\left(x^k,u^{k+1}\right)\in {{\rm N}}_{\mathfrak{D}}\left(x^k\right)$ (13)

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

在$k\in \kappa$ 上取极限，并应用(06年的文献)到(13)~(14)，我们得到

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

因此，$\widehat{x}$ 满足问题(3)的条件(5)，根据定理4，点$\widehat{x}$ 是(3)的局部极小解。 $\square$

本文通过运用在p-有效点的概念下产生的基于修正的指数函数的对偶算法来解决概率约束问题，目前该方法仍存在不完善之处，在后续的研究中将进一步探索其可应用的范围，以及在实际问题中的运用，望能更好地为社会创造价值。

NOTES

^*通讯作者。