单调向量函数在变分不等式和互补问题(variational inequality/complementarity problem, Ⅵ/CP)中有着重要意义, 正如凸函数在优化问题中有着重要作用一般. 特别地, 在$\xi$ -单调条件下, Ⅵ解的唯一性和存在性能够得到保证(参考文献, 如[1]中定理 2.3.3). 本文研究一类$\xi$ -单调的变分不等式问题(Ⅰ), 记为Ⅵ$(K,F)$, 问题表述如下: 求解 $x\in K\subseteq R^n$, 使得

$(y-x)^T F(x)\geq 0,\forall y\in K,$

(1)

$K=\{x|g^i(x)\leq 0,i\in I\},I=\{1,2,\cdots,m\},g^i(x)$ 是凸函数, $F(x)$是$\xi$ -单调的, 且$0<\xi\leq2,$ 即存在常数 $\alpha >0, 0<\xi\leq2$ 使得

$(y-x)^T (F(y)-F(x))\geq \alpha\parallel x-y\parallel^\xi_2,\forall x,y\in R^n.$

(2)

当$\xi=2$ 时, 称$F(x)$是一致单调的.

对于上述类型的问题, 至今已深入研究了很多方法, 具体可参考文献[1-3]. 本文中, 我们首先利用KKT条件(假设$g(x)$在解$x$处满足LICQ)将原问题转换成如下等价问题(Ⅱ): 求解向量$x\in R^n, \lambda\in R^m$ 使得

$0\leq \lambda\perp -g(x)\geq 0,F(x)+\sum\limits^{m}_{i=0} \lambda_i\cdot\bigtriangledown g_i(x)=0,$

(3)

$\lambda$ 是关于问题(Ⅰ)的Lagrangian 乘子向量. 经分析, 问题(Ⅱ)又可以转换为关于$\lambda$ 的非线性互补问题. 由此 我们可以用那些解决NCP的算法解决原问题.

非线性互补问题 (NCP)即求解向量 $x\in R^n $,使得

$x\geq 0, F(x)\geq 0, x^T\cdot F(x)=0,$

(4)

其中$F(x):R^n\rightarrow R^n$ . 若$F(x)$关于$R^n_+=\{x\in R^n |x\geq0\}$是连续单调的,且当$F(x)=Mx+q (M\in R^{n\times n},q\in R^{n\times 1}) $ 是线性映射时, 这类问题已被大量研究, 尤其当$M$是半正定矩阵时, 已有很多有效算法被提出, 如文[4]; 而当$F(x)$非线性, 且问题(4)的解集非空时, 邻近点算法(proximal point algorithm, PPA)是一个相当有效的工具. PPA是由Martinet提出 (参看文献[5]), 并经很多研究人员推广, 如文[6-7], 已发展出一套成熟的理论框架. 给定$x^k\in R^n_+,\beta_k\geq\beta>0$,新的迭代点$x^{k+1}$是如下NCP的唯一解:

${\rm{(PPA)}}x\geq0,\beta_k\cdot F(x)+(x-x^k)\geq0 \text{及} x^T(\beta_k\cdot F(x)+(x-x^k))=0.$

(5)

相比于问题(4), 问题(5)是强单调的, 更便于操作.

本文所用的LQP法, 最初出现于文献[8-9], 是上述PPA的一种推广. 由于LQP法所产生的迭代序列 严格位于$R^n_+$ 的内部 (记为$R^n_{++}$),因此非常适合用于求解(4)类问题, 且每步迭代任务等价于求解方程组.

具体地, 给定 $x^k\in R^n_{++}:={\rm int} R_+^n,\beta_k\geq\beta>0$,由LQP法产生的新的迭代点$x^{k+1}$是如下非线性互补问题的唯一解: 求解向量 $x\in R^n $,使得

$x\geq0,\beta_kF(x)+\bigtriangledown_xD(x,x^k)\geq0 \text{及} x^T(\beta_kF(x)+\bigtriangledown_xD(x,x^k))=0,$

其中 $\bigtriangledown_xD(x,x^k)=(x-x^T)+\mu(x^k-X^2_k\cdot x^{-1})$, 参数

$\mu\in(0,1), \beta_k>0,X_k={\rm diag}(x^k_1,x^k_2,\cdots,x^k_n), x^{-1}$

的第$j$元为$1/x_j(j=1,2,\cdots,n)$. 由于满足$D(x^k,x^k)=0$的$\bigtriangledown_xD(x,x^k)$的积分形式为

$D(x,{x^k}) = {\rm{ }}\left\{ {_{ + \infty ,其他,}^{\frac{1}{2}\parallel x - {x^k}{\parallel ^2} + \mu \sum\limits_{j = 1}^n {((} x_j^k{)^2}log\frac{{x_j^k}}{{{x_j}}} + {x_j}x_j^k - {{(x_j^k)}^2}),x \in R_{ + + }^n,}} \right.$

故称为LQP法, 其中$\bigtriangledown_xD(x,x^k)$的第二项保证了新的迭代点位于$R^n_{++}$. 而上述非线性互补问题等价于求解 以下方程组的正值向量解:

$\beta_kF(x)+\bigtriangledown_xD(x,x^k)=0,$

即

$\beta_k\cdot F(x)+x-(1-\mu)x^k-\mu\cdot X^2_k\cdot x^{-1}=0.$

(6)

一般来讲, 问题(6)比(4)要更加容易处理. 因此LQP法提供了一种全新的算法--即通过求解如(6)形式的方程组来解决问题(4).

对于问题(Ⅲ), 用LQP法我们可得到下述迭代形式: 给定$\lambda^k\in R^m_{++},\lambda^{k+1}$ 是以下方程组的解

$\left\{ \begin{aligned} -\beta_k\cdot g(x)+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,\\ F(x)+(\bigtriangledown g(x))^T\cdot\lambda=0, \end{aligned} \right.$

(7)

其中$\Psi_k={\rm diag}(\lambda^k_1,\lambda^k_2,\cdots,\lambda^k_m),$ 向量$\lambda^{-1}$ 的第$j$元为$1/\lambda_j(j=1,2,\cdots,m)$.

我们首先给出引理 2.1, 其证明可参见文献 [11] 中定理 2.4.3.

引理 2.1 若映射$F:D\subset R^n\rightarrow R^n$在开凸集$D_0\subset D$上是连续可微的, $F$在$D_0$上单调的当且仅当$\bigtriangledown F(x)$ 对所有$x\in D_0$是半正定的. 特别地, 当$F$是$\xi$ -单调的, 且$0<\xi\leq2$时, $\bigtriangledown F(x)$ 对所有$x\in D_0$是正定的.

再分析(3)式, 并记$G(x,\lambda)=F(x)+(\bigtriangledown g(x))^T\cdot\lambda$,可得引理2.2.

引理 2.2当$\lambda\geq0$时, 由$G(x,\lambda)=0$唯一决定$x=x(\lambda)$.

证 $g_i(x)$是凸函数, 可知$\bigtriangledown g_i(x)$是单调的$(\forall x\in R^n)$ (参见文献[11]中定理3.4.5). 又$F(x)$是$\xi$ -单调的, $\forall\lambda\geq0$ 有

$(x_1-x_2)^T(G(x_1,\lambda)-G(x_2,\lambda))\\ =(x_1-x_2)^T(F(x_1)-(x_2))+\sum\limits_{i = 1}^m {{\lambda _i}} \cdot ({x_1} - {x_2})^T(\bigtriangledown g_i(x_1)-\bigtriangledown g_i(x_2))\\ {\geq}\alpha\parallel x_1-x_2\parallel_2^{\xi}(\forall x_1,x_2\in R^n,\lambda\geq0).$

因此 $\forall\lambda\geq0$, $G(x,\lambda)$ 关于$x\in R^n$是$\xi$ -单调的. 由此可得 $\forall\lambda\geq0$, $G(x,\lambda)=0$ 有唯一解$x=x(\lambda)$.

对方程$G(x,\lambda)=0$ 用隐函数定理, 有

$\bigtriangledown_xG(x,\lambda)\cdot\bigtriangledown x(\lambda)+\bigtriangledown_\lambda G(x,\lambda)=0,$

(8)

$F(X)$是$\xi$ -单调的, 由引理2.1, $\bigtriangledown F(x)$ 对所有$x\in R^n$是正定的, 计算$G(x,\lambda)$ 对于$x$的偏导数

$\bigtriangledown_x G(x,\lambda) =\bigtriangledown_x(F(x)+\sum\limits_{i=1}^m\lambda_i\cdot\bigtriangledown g_i(x))\\ =\bigtriangledown F(x)+\sum\limits_{i=1}^m \lambda_i\cdot\bigtriangledown^2 g_i(x),$

$\bigtriangledown^2 g_i(x)$是$g_i(x)$的Hessian矩阵. $g_i(x)$是凸函数, 可知$\bigtriangledown ^2 g_i(x)$是半正定的$(\forall x\in R^n)$. 因此$\bigtriangledown_x G(x,\lambda) (\forall x\in R^n,\lambda\geq0)$是正定的, $\bigtriangledown_x^{-1} G(x,\lambda) (\forall x\in R^n,\lambda\geq0)$是正定的. 由(8)式得

$\bigtriangledown x(\lambda)=-(\bigtriangledown_xG(x,\lambda))^{-1}\cdot\bigtriangledown_\lambda G(x,\lambda)\\ =-(\bigtriangledown F(x)+\sum\limits_{i=1}^m\lambda_i\cdot\bigtriangledown^2g_i(x))^{-1}\cdot(\bigtriangledown g(x))^T.$

由上述分析, 问题(Ⅱ)等价于求解下述问题(Ⅲ): 求解向量$\lambda\in R^m$ 使得 $0\leq\lambda\perp-g(x(\lambda))\geq0, $ 其中$x(\lambda)$由方程组$G(x,\lambda)=0$决定. 记$h(\lambda)=-g(x(\lambda))$, 计算$\bigtriangledown h(\lambda)$

$\bigtriangledown h(\lambda)=-\bigtriangledown g(x)\cdot\bigtriangledown x(\lambda)\\ =\bigtriangledown g(x)\cdot(\bigtriangledown F(x)+\sum\limits_{i=1}^m\lambda_i\cdot\bigtriangledown^2g_i(x))^{-1}\cdot(\bigtriangledown g(x))^T,$

故$\bigtriangledown h(\lambda)$ $\forall\lambda\geq0$是半正定的, 由引理2.1, $h(\lambda)$关于$\lambda\geq0$是单调的.

因为原问题(Ⅰ)有唯一解, 可知问题(Ⅲ)的解集非空, 问题(Ⅲ)可用LQP法得到以下迭代形式

$-\beta_k\cdot g(x(\lambda))+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,$

于是得到一般的等价形式:

$\left\{ \begin{aligned} -\beta_k\cdot g(x)+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,\\ F(x)+(\bigtriangledown g(x))^T\cdot\lambda=0. \end{aligned} \right.$

算法 2.1

步骤 0 初始值: 给定$\varepsilon>0,\mu\in(0,1),\beta>0,\beta_k\geq\beta,\lambda^0>0$.令$k=0$.

步骤 1 迭代: 已知$\lambda^k$, $\lambda^{k+1}$ 是下列方程组的解

$\left\{ \begin{aligned} -\beta_k\cdot g(x)+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,\\ F(x)+(\bigtriangledown g(x))^T\cdot\lambda=0, \end{aligned} \right.$

(9)

其中$\Psi_k={\rm diag}(\lambda^k_1,\lambda^k_2,\cdots,\lambda^k_m),\lambda^{-1}$ 的第$j$元$1/\lambda_j(j=1,2,\cdots,m)$.

步骤 2 收敛条件: 若$\parallel\lambda^k-\lambda^{k+1}\parallel_\infty<\varepsilon$, 停止迭代；否则令$k:=k+1$, 并返回步骤1.

收敛性分析

类似文献[8,12-13]中LQP法的收敛性分析, 同样可得由算法2.1所得序列$\{\lambda^k\}$的收敛性. 又由 隐函数定理可知$x(\lambda)(\lambda\geq0)$的连续性, 故当$\lambda^k\rightarrow\lambda^\ast$时, $x^k\rightarrow x^\ast$($x^{k+1}$由方程组(9)所得).

注 2.1 当$g(x)=-x$, 原问题即为NCP, 相应的迭代方程组变为

$\left\{ \begin{aligned} \beta_k\cdot x+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,\\ F(x)-\lambda=0. \end{aligned} \right.$

注 2.2 类似方法可用于下述数学规划问题:

$\min f(x),\\ x\in K=\{x\in R^n|g(x)\leq0\}, g(x)= \begin{pmatrix} g_1(x)\leq0\\ \vdots\\g_m(x)\leq0 \end{pmatrix},$

其中$f(x)$是一致凸函数, $g_i(x)$是凸函数. 显然$\bigtriangledown f(x)$是一致单调算子, 由KKT条件可得类似(3)式所示问题, 便得到相同的基于LQP的算法.

受文献 [10, 12-13] 中改进的 LQP 算法的启发, 下面给出算法 2.1 的改良算法.

算法3.1 令$\mu,\nu\in(0,1),\beta>0$, 给定$\lambda^k>0$及$\beta_k\geq\beta$, 改进算法中新的迭代点$\lambda^{k+1}$ 由下述步骤产生:

对数-二次邻近步 解方程组

$\left\{ \begin{aligned} -\beta_k\cdot g(x)+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,\\ F(x)+(\bigtriangledown g(x))^T\cdot\lambda=0, \end{aligned} \right.$

(10)

解记为$(x^{k+1},\widetilde{\lambda}^k).$

扩展 新的迭代点$\lambda^{k+1}(\alpha)$为下述方程组的正解

$-\alpha\cdot\beta_k\cdot g(x^{k+1})+\lambda-(1-\nu)\cdot\lambda^k-\nu\cdot\Psi^2_k\cdot\lambda^{-1}=0,$

(11)

其中$\alpha$是正的标量, 据文[12]中的讨论, 选取$0\leq\nu\leq\frac{\mu^2}{2-\mu^2},\alpha=\frac{1-\nu}{(1+\mu)^2}$.

注 3.1 比较前面两种算法, 可知$\widetilde{\lambda}^k$是算法2.1中的新的迭代点, 算法3.1增加的计算量相当小. 事实上, 方程组(11)的解的每个元素可以由下面的显式直接计算可得

$\lambda_j^{k+1}=\frac{(1-\nu)\lambda_j^k+\alpha\beta_k\cdot g_j(x^{k+1})+\sqrt{((1-\nu)\lambda^k_j+\alpha\beta_k\cdot g_j(x^{k+1}))^2+4\nu(\lambda^k_j)^2}}{2},$

而且, 当$\lambda^k>0$时, 容易验证$\lambda^{k+1}>0$, 因此算法3.1产生的所有迭代点均为$R^m_{++}$的内点, 从而新算法很好的 保留的原LQP算法的理论性质.

算法 3.2 类似于文献[10]中所讨论的基于LQP的内点预估-校正算法, 可以下列步骤产生新的迭代点$\lambda^{k+1}$:给定 $\mu\in(0,1),\beta>0,\lambda^k>0,\beta_k\geq\beta.$

预测 求解$\widetilde{\lambda}^k\in R^m_{++},x^{k+1}\in R^n$, 以及$\zeta^k\in R^m$, 使得下式成立

$\left\{ \begin{aligned} \zeta^k:=-\beta_k\cdot g(x^{k+1})+\widetilde{\lambda}^k-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot(\widetilde{\lambda}^k)^{-1}\approx0,\\ F(x^{k+1})+(\bigtriangledown g(x^{k+1}))^T\cdot\widetilde{\lambda}^k=0, \end{aligned} \right.$

其中$\zeta^k$满足 $\parallel\zeta^k\parallel\leq\eta\sqrt{1-\mu^2}\parallel\lambda^k-\widetilde{\lambda}^k\parallel. $

校正 取下面非线性方程组的正解为算法新的迭代点$\lambda^{k+1}$:

$-\tau\cdot\beta_k\cdot g(x^{k+1})+\lambda-(1-\mu)\cdot\lambda^k-\mu\cdot\Psi^2_k\cdot\lambda^{-1}=0,$

(12)

$\tau$可看作纠正步骤(12)的步长. 据文[10]中的讨论, $\tau$值可由下面的方法选取:

$\tau:=\tau_k=\frac{(1-\mu)(\parallel\lambda^k-\widetilde{\lambda}^k\parallel^2+(\lambda^k-\widetilde{\lambda}^k)^T\zeta^k)} {(1+\mu)^2\parallel\lambda^k-\widetilde{\lambda}^k+\frac{1}{1+\mu}\zeta^k\parallel^2}.$

当然, $\tau$值也可以按文[13]中所讨论的策略选取.

由 KKT 条件和隐函数定理, 得到原问题 (Ⅰ) 的等价形式, 即问题 (Ⅲ). 问题 (Ⅲ) 是典型的 NCP, 因此可用 LQP 法解决, 且可以保证所有迭代点均位于 $R_ + ^m$ 的内部. 最后, 受文献[10,12-13 ] 提出的改进 LQP 算法的启发, 提出了相应的算法 2.1 的两种改进算法.