求解随机广义垂直线性互补问题的随机近似方法

Stochastic Approximation Approaches to Stochastic Extended Vertical Complementarity Problem

摘要: 近几年随机广义垂直线性互补问题的求解方法不断完善。本文提出了一种新型的求解随机广义垂直线性互补问题(SEVLCP)的方法，即随机近似(SA)算法。基于Fischer-Burmeister函数的性质，先将随机广义垂直线性互补问题转化为无约束极小化问题，再利用随机近似算法进行求解。本文详细讨论了原问题的重新构造过程，并提出了一种有效求解的迭代格式，以及在适当的条件下，得到了所提出方法的全局收敛结果。

Abstract: In recent years, the solution methods of stochastic extended vertical linear complementarity prob-lems have been continuously improved. In this paper, a new method for solving stochastic extended vertical linear complementarity problem (SEVLCP) is proposed, namely stochastic approximation (SA) methods. Based on the properties of the Fischer-Burmeister function, the stochastic extended vertical linear complementarity problem is reformulated in terms of the unconstrained minimiza-tion problem, and then solved by the stochastic approximation methods. This paper discusses the reformulation process of the original problem in detail, and proposes an iterative scheme for effec-tive solving, and obtains the global convergence results of the proposed method under appropriate conditions.

1. 引言

本文研究如下的随机广义垂直线性互补问题：求 $x\in {ℝ}^n$ ，使得

$\min \left\{F_1\left(x\right),F_2\left(x\right),F_3\left(x\right)\right\}=0,$ (1)

$F_i\left(x\right)=E\left[M_i\left(\xi \left(\omega \right)\right)\right]x+E\left[q_i\left(\xi \left(\omega \right)\right)\right],i=1,2,3,$

其中， $M_i(\cdot ):{ℝ}^m\to {ℝ}^{n\times n},q_i(\cdot ):{ℝ}^m\to {ℝ}^n,i=1,2,3$ 为随机映射， $\xi :\Omega \to \Xi \subset {ℝ}^m$ 是概率空间 $\left(\Omega ,F,P\right)$ 上的随机向量，E表示数学期望，min表示极小化函数。在本文中，假设 $M_i\left(\xi \left(\omega \right)\right),q_i\left(\xi \left(\omega \right)\right),i=1,2,3$ 是 $\omega$ 的可测函数并满足

$E\left[{\displaystyle \underset{i=1}{\overset{3}{\sum }}\Vert M_i\left(\xi \left(\omega \right)\right)\Vert +\Vert q_i\left(\xi \left(\omega \right)\right)\Vert }\right]<+\infty$ ,

为简单起见，我们把 $\xi \left(\omega \right)$ 记为 $\xi$ ，但要与上下文中 $\Xi$ 中的确定性向量 $\xi$ 区分开。

广义垂直线性互补问题在工业工程、经济管理、博弈论和网络中的应用已经成为数学规划中一个成熟而富有成果的学科，在许多文献中都研究了广义垂直线性互补问题的解和算法的存在性，如 [1] 。为了将现实中的不确定因素考虑其中，带有随机变量的垂直线性互补问题受到了学者们的广泛关注。求解问题(1)的关键在于处理 $M_i\left(\xi \right)$ 和 $q_i\left(\xi \right)$ 的期望值，如果能够准确地计算出问题(1)所涉及的数学期望，则问题就转化为确定型广义随机线性互补问题，这已经具有了成熟的求解方法，如对数指数正则法 [2] 和人工神经网络法 [3] 等。本文假设问题(1)中的期望值难于计算或计算成本很高，因此选用随机近似方法将其转化成确定型问题进行求解和近似。

随机近似方法可追溯到Robbins和Monro在1951年发表的论文 [4] ，自此以后随机近似算法被广泛用于解决随机问题，如文献 [5] [6] [7] 。经典的随机近似算法分析在文献 [8] 中进行了详细的介绍。该算法的一个重要改进是由Polyak [9] 和Polyak和Juditsky [10] 提出的，利用已知步长的平均值来获得更长的步长。在本文中，将利用该方法求解随机广义垂直线性互补问题(1)，证明了其收敛性。

问题(1)是随机线性互补问题的一个延伸，当 $i=1,E\left[M_0\left(\xi \left(\omega \right)\right)\right]=I,E\left[q_0\left(\xi \left(\omega \right)\right)\right]=0$ 时，就简化为随机线性互补问题：寻找 $x\in {ℝ}^n$ ，使得

$x\ge 0,F_1\left(x\right)\ge 0,F_1{\left(x\right)}^{\text{T}}x=0,$ (2)

$F_1\left(x\right)=E\left[M_1\left(\xi \left(\omega \right)\right)\right]x+E\left[q_1\left(\xi \left(\omega \right)\right)\right],$

它是随机非线性互补问题的一个特例，可以追溯到King和Rockafellar [11] 。因此，可以利用随机近似算法对垂直互补问题进行求解。

2. 问题的重新构造

我们将问题(1)重新表述为一个随机非光滑方程组，然后通过最小平方最小化来求解方程组。首先回顾Fischer-Burmeister函数 $\varphi :{ℝ}^2\to ℝ$

$\varphi \left(a,b\right)=\sqrt{a^2+b^2}-a-b.$

利用该函数有

$\min \left\{a,b\right\}=\varphi \left(a,b\right),$

基于上述函数提出求解广义垂直线性互补问题的函数如下：

$\min \left\{a,b,c\right\}=\varphi \left(\varphi \left(a,b\right),c\right).$

设

$\phi \left(a,b,c\right)=\varphi \left(\varphi \left(a,b\right),c\right).$

问题(1)等价于下列随机方程组

$G\left(x\right)=\left(\begin{array}{c}\phi \left(F_{11}\left(x\right),F_{21}\left(x\right),F_{31}\left(x\right)\right)\\ ⋮\\ \phi \left(F_{1n}\left(x\right),F_{2n}\left(x\right),F_{3n}\left(x\right)\right)\end{array}\right)=0$ (3)

式(1)和式(3)的解集是重合的，使用Fischer-Burmeister函数的主要好处之一是它在任何地方都是半光滑的，并且在除原点以外的任何点上都是连续可微的，并且该函数是全局Lipschitz连续的。对于随机垂直线性互补问题(1)的解，提出求解随机方程组(3)的随机近似算法是很自然的 [5] 。在接下来的内容中，我们考虑基于(1)的最小化重构的SA方法。令

$\underset{x}{\min }\Psi \left(x\right)=\frac{1}{2}{\Vert G\left(x\right)\Vert }^2=\frac{1}{2}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\phi {\left(F_{1j}\left(x\right),F_{2j}\left(x\right),F_{3j}\left(x\right)\right)}^2}.$ (4)

为方便下面的证明，不妨令

$g_j\left(x\right)=\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right),j=1,\cdots ,n,$

$\psi \left(a,b\right)=\varphi {\left(a,b\right)}^2,$

则

$\min \Psi \left(x\right)=\frac{1}{2}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\varphi {\left(g_j\left(x\right),F_{3j}\left(x\right)\right)}^2}=\frac{1}{2}{\displaystyle \underset{j=1}{\overset{n}{\sum }}\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right).}$ (5)

考虑以下的迭代格式求解上述问题

$x^{k+1}=x^k-a_k\left(d^k+{\omega }^k\right)$ (6)

其中，

$d^k=-\frac{1}{2}\nabla \Psi \left(x^k\right),$

${\omega }^k$ 是随机变量为确定值 ${\xi }^k$ 时得到的 $d^k$ 的近似值的随机误差。例如，如果 ${\xi }^k$ 是 $\xi \left(\omega \right)$ 的一个样本，那么选择

$d^k+{\omega }^k=-\frac{1}{2}\nabla \Psi \left(x^k,{\xi }^k\right).$

在 [12] 中利用这种搜索方向建立了求解非线性互补问题的无导数迭代格式。下面的结果表明，在适当的条件下， $d^k$ 是 $\Psi$ 在 $x^k$ 处的下降方向，并且当 $d^k=0$ 时 $x^k$ 是问题(4)的一个解。

命题2.1：假设F是全局Lipschitz连续的并且二次连续可微，存在正的常数 $C_1,C_2,C_3$ 使得

$\underset{j}{\max }\left(\Vert x\Vert +C_1\right)\Vert {\nabla }^2{F}_{ij}\left(x\right)\Vert \le C_2,i=1,2,3,j=1,\cdots ,n,$

$\underset{j}{\max }\left(\Vert x\Vert +C_1\right)\Vert {\nabla }^2{g}_j\left(x\right)\Vert \le C_3,j=1,\cdots ,n,\forall x\in {ℝ}^n.$

那么， $\nabla \Psi$ 在 ${ℝ}^n$ 上是全局Lipschitz连续的。

证：由定义(5)可知

$\nabla \Psi \left(x\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}\left[{\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla g_j\left(x\right)+{\nabla }_2\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla F_{3j}\left(x\right)\right],}$

要证 $\nabla \Psi$ 是全局Lipschitz连续的，只需证 ${\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla g_j\left(x\right)$ 和 ${\nabla }_2\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla F_{3j}\left(x\right)$ 分别是全局Lipschitz连续的。

由( [5] , Proposition 5.1)的证明有 ${\nabla }_2\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla F_{3j}\left(x\right)$ 是全局Lipschitz连续的。接下来证明 ${\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla g_j\left(x\right)$ 是全局Lipschitz连续的。当且仅当它的雅可比矩阵包含在

$\Omega \equiv \nabla g_j\left(x\right)\partial {\nabla }_1\psi {\left(g_j\left(x\right),F_{3j}\left(x\right)\right)}^{\text{T}}+{\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right){\nabla }^2{g}_j(\; x\; )$

中， $\Omega$ 是有界的。首先，由( [5] , Lemma 5.2)知 $\partial {\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)$ 有界。其次，由

$g_j\left(x\right)=\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right),$

得

$\nabla g_j\left(x\right)=\nabla \varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right)={\nabla }_1\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right)\nabla F_{1j}\left(x\right)+{\nabla }_2\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right)\nabla F_{2j}\left(x\right).$

因为

$\left|{\nabla }_1\varphi \left(a,b\right)\right|=\left|\frac{a}{\sqrt{a^2+b^2}}-1\right|\le 1,\left|{\nabla }_2\varphi \left(a,b\right)\right|=\left|\frac{b}{\sqrt{a^2+b^2}}-1\right|\le 1,$

从而 ${\nabla }_1\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right)$ 和 ${\nabla }_2\varphi \left(F_{1j}\left(x\right),F_{2j}\left(x\right)\right)$ 是有界的。并且 $F_i\left(x\right),i=1,2,3$ 是Lipschitz连续的，则 $\nabla F_{ij}\left(x\right)$ 有界，所以 $\nabla g_i\left(x\right)$ 有界。

又

$\begin{array}{l}\Vert {\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\Vert \\ =2\Vert \varphi \left(g_j\left(x\right),F_{3j}\left(x\right)\right){\nabla }_1\varphi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\Vert \\ \le 4\max \left\{\left|g_j\left(x\right)\right|,\left|F_{3j}\left(x\right)\right|\right\}\\ \le 8\max \left\{\left|F_{1j}\left(x\right)\right|,\left|F_{2j}\left(x\right)\right|,\left|F_{3j}\left(x\right)\right|\right\}\\ ={\rm O}\left(\Vert x\Vert +C_1\right).\end{array}$

根据命题2.1可知 $\Omega$ 有界，从而 ${\nabla }_1\psi \left(g_j\left(x\right),F_{3j}\left(x\right)\right)\nabla g_j\left(x\right)$ 是全局Lipschitz连续的。

综上， $\nabla \Psi$ 是全局Lipschitz连续的。

3. 收敛性分析

为证明在迭代格式(5)下 $\Psi$ 的收敛性，作出下列假设：

假设2.1：1) 步长 $a_k$ 满足 $a_k>0,a_k\to 0,{\displaystyle {\sum }_{k=0}^n{a}_k}=\infty ,{\displaystyle {\sum }_{k=0}^n{\left(a_k\right)}^2}<\infty$ ；

2) 问题 $E\left[{\omega }^k|{\mathcal{F}}_k\right]=0$ 。

3) ${\displaystyle {\sum }_{k=1}^{\infty }{\left(a_k\right)}^{2}E\left[{\Vert {\omega }^k\Vert }^2|{\mathcal{F}}_k\right]}<\infty$ 几乎确定成立。

4) $F_i,i=1,2,3$ 在空间 $\mathcal{Y}$ 上是以模量L全局Lipschitz的。

5) $F_i,i=1,2,3$ 在空间 $\mathcal{Y}$ 上是以模量 $\sigma$ 全局强单调的。

6) 矩阵 $F=\left(F_1\left(x\right),F_2\left(x\right),F_3\left(x\right)\right)$ 有行 $\omega$ -性质 [13] 。

我们关于随机近似算法的收敛结果使用了下面的引理，它是鞅收敛定理的推广。

引理3.1： [14] 令 ${\mathcal{F}}_k$ 是 $\sigma$ -代数的一个递增序列， $V_k,{\alpha }_k,{\beta }_k$ 和 ${\gamma }_k$ 是适应于 ${\mathcal{F}}_k$ 非负随机变量。如果

${\displaystyle {\sum }_{k=1}^{\infty }{\alpha }_k}<\infty ,{\displaystyle {\sum }_{k=1}^{\infty }{\beta }_k}<\infty ,$

并且

$\mathrm{E}\left(V_{k+1}|{\mathcal{F}}_k\right)\le \left(1+{\alpha }_k\right)V_k-{\gamma }_k+{\beta }_k,$

那么 $\left\{V_k\right\}$ 是几乎确定收敛的，以及有 ${\displaystyle {\sum }_{k=1}^{\infty }{\gamma }_k}<\infty$ 几乎确定成立。

定理3.1：假设在假设2.1中的1)，2)，3)成立，在给定得迭代格式(6)下，设 $F_i,i=1,2,3$ 都是二次连续可微的，存在 $t\in \left(1,2\right),C_i>0$ 和一个连续函数 ${\sigma }_i\left(x\right)>0$ ，使得

${\left(F_i\left(y\right)-F_i\left(x\right)\right)}^{\text{T}}\left(y-x\right)\ge \min \left\{{\sigma }_i\left(x\right){\Vert y-x\Vert }^2,C_i{\Vert y-x\Vert }^t\right\},\forall y\in {ℝ}^n$ ,

以及步长满足

$0\le a_k\le \min \left\{\frac{\sigma \left(x^k\right)}{2L},\frac{1}{2L}\right\},$

那么由迭代生成的序列 $\left\{x^k\right\}$ 几乎确定收敛到随机广义垂直线性互补问题(1)唯一解 $x^{\ast }$ 。

证：由中值定理可知，在 $x^k$ 和 $x^{k+1}$ 之间存在 $y^k$ 使得

$\Psi \left(x^{k+1}\right)=\Psi \left(x^k\right)+\nabla \Psi {\left(y^k\right)}^{\text{T}}\left(x^{k+1}-x^k\right).$

由命题2.1， $\nabla \Psi$ 是全局Lipschitz连续的。因此，存在常数 $L>0$ ，使得

$\Vert \nabla \Psi \left(y^k\right)-\nabla \Psi \left(x^k\right)\Vert \le L\Vert x^{k+1}-x^k\Vert .$

由迭代(6)可得

$\begin{array}{l}\mathrm{E}\left[\Psi \left(x^{k+1}\right)|{\mathcal{F}}_k\right]\\ =\mathrm{E}\left[\Psi \left(x^k\right)+\nabla \Psi {\left(y^k\right)}^{\text{T}}\left(x^{k+1}-x^k\right)|{\mathcal{F}}_k\right]\\ =\mathrm{E}\left[\Psi \left(x^k\right)+a_k\nabla \Psi {\left(y^k\right)}^{\text{T}}\left(d^k+{\omega }^k\right)|{\mathcal{F}}_k\right]\\ =\Psi \left(x^k\right)+a_k\mathrm{E}\left[\nabla \Psi {\left(y^k\right)}^{\text{T}}\left(d^k+{\omega }^k\right)|{\mathcal{F}}_k\right]\\ =\Psi \left(x^k\right)+a_k\mathrm{E}\left[\nabla \Psi {\left(x^k\right)}^{\text{T}}\left(d^k+{\omega }^k\right)|{\mathcal{F}}_k\right]+a_k\mathrm{E}\left[{\left(\nabla \Psi \left(y^k\right)-\nabla \Psi \left(x^k\right)\right)}^{\text{T}}\left(d^k+{\omega }^k\right)|{\mathcal{F}}_k\right]\end{array}$

$\begin{array}{l}=\Psi \left(x^k\right)+a_k\nabla \Psi {\left(x^k\right)}^{\text{T}}{d}^k+0+a_k\mathrm{E}\left[{\left(\nabla \Psi \left(y^k\right)-\nabla \Psi \left(x^k\right)\right)}^{\text{T}}\left(d^k+{\omega }^k\right)|{\mathcal{F}}_k\right]\\ \le \Psi \left(x^k\right)+a_k\nabla \Psi {\left(x^k\right)}^{\text{T}}{d}^k+a_k\mathrm{E}\left[L\Vert y^k-x^k\Vert \cdot \Vert d^k+{\omega }^k\Vert |{\mathcal{F}}_k\right]\\ \le \Psi \left(x^k\right)+a_k\nabla \Psi {\left(x^k\right)}^{\text{T}}{d}^k+L{a}_k^2\mathrm{E}\left[{\Vert d^k+{\omega }^k\Vert }^2|{\mathcal{F}}_k\right]\\ \le \Psi \left(x^k\right)+a_k\nabla \Psi {\left(x^k\right)}^{\text{T}}{d}^k+2L{a}_k^2\mathrm{E}\left[{\Vert d^k\Vert }^2+{\Vert {\omega }^k\Vert }^2|{\mathcal{F}}_k\right]\end{array}$

$\begin{array}{l}=\Psi \left(x^k\right)+a_k\nabla \Psi {\left(x^k\right)}^{\text{T}}{d}^k+2L{a}_k^2{\Vert d^k\Vert }^2+2L{a}_k^2\mathrm{E}\left[{\Vert {\omega }^k\Vert }^2|{\mathcal{F}}_k\right]\\ \le \Psi \left(x^k\right)-a_k{\Vert d^k\Vert }^2+2L{a}_k^2{\Vert d^k\Vert }^2+2L{a}_k^2\mathrm{E}\left[{\Vert {\omega }^k\Vert }^2|{\mathcal{F}}_k\right]\\ =\Psi \left(x^k\right)+a_k\left(2L{a}_k-1\right){\Vert d^k\Vert }^2+2L{a}_k^2\mathrm{E}\left[{\Vert {\omega }^k\Vert }^2|{\mathcal{F}}_k\right]\\ =\Psi \left(x^k\right)-{\gamma }_k+{\beta }_k.\end{array}$

其中，

${\gamma }_k=-a_k\left(2L{a}_k-1\right){\Vert d^k\Vert }^2,$

${\beta }_k=2L{a}_k^2\mathrm{E}{\left[{\Vert {\omega }^k\Vert }^2|\mathcal{F}\right]}_k.$

下面证明对应 $\Psi \left(x^k\right)$ 收敛的每个迭代路径 $\left\{x^k\right\}$ ，有 $\Psi \left(x^k\right)$ 收敛到0。首先根据( [5] , Theorem 5.1)的证明可知序列 $\left\{x^k\right\}$ 有界，则存在 $\hat{\sigma }>0$ ，使得 $\sigma \left(x^k\right)\ge \hat{\sigma }>0$ 。由

${\displaystyle {\sum }_{k=1}^{\infty }{\gamma }_k}<\infty$

可得，当 $k\to \infty$ 时 $d^k\to 0$ 。由 $d^k$ 的定义有 $\nabla \Psi \left(x^k\right)\to 0$ 。说明序列 $\left\{x^k\right\}$ 收敛到某一点 $x^{\ast }$ 。其次证明 $x^{\ast }$ 是 $\Psi \left(x^k\right)$ 的极小点：

$\nabla \Psi \left(x^{\ast }\right)={\displaystyle \underset{j=1}{\overset{n}{\sum }}\varphi \left(g_j\left(x^{\ast }\right),F_{3j}\left(x^{\ast }\right)\right)\nabla \varphi \left(g_j\left(x^{\ast }\right),F_{3j}\left(x^{\ast }\right)\right)}=0,$

则

$\varphi \left(g_j\left(x^{\ast }\right),F_{3j}\left(x^{\ast }\right)\right)=0$ 或 $\nabla \varphi \left(g_j\left(x^{\ast }\right),F_{3j}\left(x^{\ast }\right)\right)=0.$

由于

$\nabla \varphi \left(a,b\right)={\nabla }_1\varphi \left(a,b\right)+{\nabla }_2\varphi \left(a,b\right)=\left(\frac{a}{\sqrt{a^2+b^2}}-1\right)+\left(\frac{b}{\sqrt{a^2+b^2}}-1\right),$

由假设2.1中6)知 $F$ 有行 $\omega$ -性质，存在 $i\in \left\{1,2,3\right\}$ 使得 $\nabla F_{ij}\left(x^{\ast }\right)\ne 0$ 。则有

$\varphi \left(g_j\left(x^{\ast }\right),F_{3j}\left(x^{\ast }\right)\right)=0,j=1,\cdots ,n.$

即 $G\left(x^{\ast }\right)=0$ ，因此 $\Psi \left(x^{\ast }\right)=0$ 。

4. 结论

本文利用随机近似方法求解了随机广义垂直线性互补问题，基于Fischer-Burmeister函数将随机广义垂直线性互补问题转化为一个无约束极小化问题，构造了一个迭代格式，证明了在合适的条件下这种迭代格式所产生的序列收敛性以及原问题的可解性。

NOTES

^*通讯作者。