﻿ 基于一个新的NCP函数的光滑牛顿法求解变分不等式问题

# 基于一个新的NCP函数的光滑牛顿法求解变分不等式问题Smooth Newton Method Based on a New NCP Function for Solving Variational Inequality Problems

Abstract: In this paper, we study the solution of the variational inequality KKT systems. A new NCP function is used to convert KKT conditions of variational inequalities into an equivalent smooth equation. And a smoothing Newton method for solving the nonlinear complementarity problem of NCP function is established, and the convergence and local convergence of the algorithm are obtained, and the accuracy of the theoretical analysis is verified by numerical experiments.

1. 引言和预备知识

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

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

${\varphi }_{1}\left(a,b\right)={\varphi }_{p}\left(a,b\right)-\alpha {a}_{+}{b}_{+}$ (3)

$〈x,y〉={x}^{\text{T}}y$

$‖x‖={\left(\underset{i=1}{\overset{n}{\sum }}{x}_{i}^{2}\right)}^{1/2}$

$X$$n$ 维欧式空间 ${R}^{n}$ 中的非空闭凸集，映射 $F:{R}^{n}\to {R}^{n}$$h:{R}^{n}\to {R}^{l}$ 为线性函数， $g:{R}^{n}\to {R}^{m}$ 为二次连续可微凸函数，则变分不等式(VI)问题：

$x\in X$ ，使

$F{\left(x\right)}^{\text{T}}\left(y-x\right)\ge 0$$\forall y\in X$ (4)

$X=\left\{x:h\left(x\right)=0,g\left(x\right)\le 0\right\}$ (5)

1) 如果 $X$ 取为 ${R}^{n}$ 中的开集，VI为广义方程组，即：

$F\left(x\right)=0$

2) 假设 $F\left(x\right)$ 的梯度 $\nabla F\left(x\right)$ 为对称阵，此时VI (4)~(5)对应于凸规划的KKT条件是：

$\mathrm{min}f\left( x \right)$

$\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}Ax=b$ (6)

$g\left(x\right)\le 0$

$x\in X$ ，使

$〈\nabla f\left(x\right),y-x〉\ge 0,\forall y\in X$

$X=\left\{x\in {R}^{n}:AX-b=0,-g\left(x\right)\ge 0\right\}$

2. KKT条件的方程重构

$F\left(x\right)+Jh{\left(x\right)}^{\text{T}}\mu -Jg{\left(x\right)}^{\text{T}}\lambda =0$

$h\left(x\right)=0$ (7)

$0\ge g\left(x\right)\perp \lambda \ge 0$

$0={\psi }_{i}\left(\epsilon ,x,\mu ,\lambda \right)=\left[\begin{array}{c}\epsilon \\ L\left(x,\mu ,\lambda \right)\\ -h\left(x\right)\\ {\varphi }_{1}\left(\epsilon ,-{g}_{1}\left(x\right),{\lambda }_{1}\right)\\ \begin{array}{c}⋮\\ {\varphi }_{1}\left(\epsilon ,-{g}_{m}\left(x\right),{\lambda }_{m}\right)\end{array}\end{array}\right]$ (8)

$L\left(x,\mu ,\lambda \right)\equiv F\left(x\right)+Jh{\left(x\right)}^{\text{T}}\mu +Jg{\left(x\right)}^{\text{T}}\lambda$

$J{\varphi }_{1}\left(\epsilon ,a,b\right)=\left(\frac{\partial {\varphi }_{1}}{\partial \epsilon },\frac{\partial {\varphi }_{1}}{\partial a},\frac{\partial {\varphi }_{1}}{\partial b}\right)=\left\{\begin{array}{l}\left(\frac{{\epsilon }^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}},\frac{{a}^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}}-1-\alpha {b}_{+}\partial {a}_{+},\frac{{b}^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}}-1-\alpha {a}_{+}\partial {b}_{+}\right)\hfill \\ \left(\frac{{\epsilon }^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}},\frac{\mathrm{sgn}\left(a\right)\cdot {a}^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}}-1-\alpha {b}_{+}\partial {a}_{+},\frac{\mathrm{sgn}\left(b\right)\cdot {b}^{p-1}}{{‖\left(\epsilon ,a,b\right)‖}_{p}^{p-1}}-1-\alpha {a}_{+}\partial {b}_{+}\right)\hfill \end{array}$ (9)

${\psi }_{i}:{R}_{+}×{R}_{n}×{R}^{l}×{R}^{m}\to {R}^{1+n+l+m}$

${a}_{i}^{\epsilon }\left(x,\lambda \right)=\left\{\begin{array}{l}\frac{-{\left({g}_{i}\left(x\right)\right)}^{p-1}}{{‖\left(\epsilon ,{g}_{i}\left(x\right),{\lambda }_{i}\right)‖}_{p}^{p-1}}-1-\alpha {\left({\lambda }_{i}\right)}_{+}\cdot \partial \left(-{g}_{i}{\left(x\right)}_{+}\right)\hfill \\ \frac{-\mathrm{sgn}\left({g}_{i}\left(x\right)\right){\left({g}_{i}\left(x\right)\right)}^{p-1}}{{‖\left(\epsilon ,{g}_{i}\left(x\right),{\lambda }_{i}\right)‖}_{p}^{p-1}}-1-\alpha {\left({\lambda }_{i}\right)}_{+}\cdot \partial \left(-{g}_{i}{\left(x\right)}_{+}\right)\hfill \end{array}$

${b}_{i}^{\epsilon }\left(x,\lambda \right)=\left\{\begin{array}{l}\frac{-{\left({\lambda }_{i}\right)}^{p-1}}{{‖\left(\epsilon ,{g}_{i}\left(x\right),{\lambda }_{i}\right)‖}_{p}^{p-1}}-1-\alpha \left(-{g}_{i}{\left(x\right)}_{+}\right)\cdot \partial {\left({\lambda }_{i}\right)}_{+}\hfill \\ \frac{-\mathrm{sgn}\left({\lambda }_{i}\right){\left({\lambda }_{i}\right)}^{p-1}}{{‖\left(\epsilon ,{g}_{i}\left(x\right),{\lambda }_{i}\right)‖}_{p}^{p-1}}-1-\alpha {\left({\lambda }_{i}\right)}_{+}\cdot \partial \left(-{g}_{i}{\left(x\right)}_{+}\right)\hfill \end{array}$

${D}_{g}^{\epsilon }=diag\left({a}_{1}^{\epsilon }\left(x,\lambda \right),\cdots ,{a}_{m}^{\epsilon }\left(x,\lambda \right)\right)$

${D}_{\lambda }^{\epsilon }=diag\left({b}_{1}^{\epsilon }\left(x,\lambda \right),\cdots ,{b}_{m}^{\epsilon }\left(x,\lambda \right)\right)$

$J{\psi }_{i}\left(\epsilon ,x,\mu ,\lambda \right)=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& {J}_{x}L\left(x,\mu ,\lambda \right)& Jh{\left(x\right)}^{\text{T}}& Jg{\left(x\right)}^{\text{T}}\\ 0& -Jh\left(x\right)& 0& 0\\ {E}_{1}& {E}_{2}& 0& {E}_{3}\end{array}\right]$

${E}_{1}=\left[\begin{array}{c}\frac{{\epsilon }^{p-1}}{{‖\left(\epsilon ,{g}_{1}\left(x\right),{\lambda }_{1}\right)‖}_{p}^{p-1}}e\\ \frac{{\epsilon }^{p-1}}{{‖\left(\epsilon ,{g}_{2}\left(x\right),{\lambda }_{2}\right)‖}_{p}^{p-1}}e\\ ⋮\\ \frac{{\epsilon }^{p-1}}{{‖\left(\epsilon ,{g}_{m}\left(x\right),{\lambda }_{m}\right)‖}_{p}^{p-1}}e\end{array}\right]$ (10)

${E}_{2}=-{D}_{g}^{\epsilon }{J}_{g}$

${E}_{3}={D}_{\lambda }^{\epsilon }$

(a) 梯度 $\left\{\nabla {h}_{j}\left(x\right):j=1,\cdots ,l\right\}\cup \left\{\nabla {g}_{i}\left(x\right):i\in {I}_{0}\right\}$ 是线性无关的。

(b) ${J}_{x}L\left(x,\mu ,\lambda \right)$ 在梯度 $\left\{\nabla {h}_{j}\left(x\right):j=1,\cdots ,l\right\}$ 的零空间内是正定的。

${I}_{0}=\left\{i:{g}_{i}\left(x\right)=0\le {\lambda }_{i},i=1,2,\cdots ,m\right\}$

${J}_{0}=\left[\begin{array}{ccc}{J}_{x}L\left(x,\mu ,\lambda \right)& Jh{\left(x\right)}^{\text{T}}& Jg{\left(x\right)}^{\text{T}}\\ -Jh\left(x\right)& 0& 0\\ {E}_{2}& 0& {E}_{3}\end{array}\right]$

${J}_{0}^{\text{T}}\left(u,v,t\right)=0$ (11)

$\left({J}_{x}{L}^{\text{T}}\right)u-\left(J{h}^{\text{T}}\right)v-\left(J{g}^{\text{T}}\right){E}_{2}t=0$ (12)

$\left(Jh\right)u=0$ (13)

$\left(Jg\right)u+{E}_{3}t=0$ (14)

${u}^{\text{T}}\left(J{h}^{\text{T}}\right)=0$

${u}^{\text{T}}$ ´ (12)，可以得到

${u}^{\text{T}}\left({J}_{x}{L}^{\text{T}}\right)u={u}^{\text{T}}\left(J{g}^{\text{T}}\right){E}_{2}t$ (15)

${t}^{\text{T}}$ ´ (14)，可以得到

${t}^{\text{T}}\left(Jg\right)u=-{t}^{\text{T}}{E}_{3}t$ (16)

$\underset{j=1}{\overset{m}{\sum }}\left({t}_{j}\underset{i=1}{\overset{n}{\sum }}\right)={t}^{\text{T}}\left(Jg\right)u\ge 0$

${u}^{\text{T}}\left(J{g}^{\text{T}}\right){E}_{2}t=\underset{j=1}{\overset{m}{\sum }}\left({a}_{j}{t}_{j}\underset{i=1}{\overset{n}{\sum }}\right)\le 0$

${u}^{\text{T}}\left({J}_{x}{L}^{\text{T}}\right)u\le 0$

$u=0$ (17)

$\left(J{h}^{\text{T}}\right)v+\left(J{g}^{\text{T}}\right){E}_{2}t=0$ (18)

$\left({D}_{\lambda }\right)t=0$ (19)

$\left(J{h}^{\text{T}}\right)v+\left(J{g}^{\text{T}}\right){E}_{2}\stackrel{¯}{t}=0$

$\stackrel{¯}{t}=\left[\begin{array}{c}{t}_{{I}_{0}}\\ {t}_{I-{I}_{0}}\end{array}\right]$ (20)

$v=0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}t=0$

3. 光滑牛顿算法

$z:=\left(\epsilon ,Y\right)=\left(\epsilon ,x,\mu ,\lambda \right)$

${z}^{k}:=\left({\epsilon }_{k},{Y}^{k}\right)=\left({\epsilon }_{k},{x}^{k},{\mu }^{k},{\lambda }^{k}\right)$

Step1：任意选取常数 $\delta ,\sigma ,\gamma \in \left(0,1\right)$ ，与 ${Y}^{0}\in {R}^{n}×{R}^{l}×{R}^{m}$ 。取 ${\epsilon }_{0}\in {R}_{++}$ ，故 $\gamma {\epsilon }_{0}<1$

${z}^{0}:=\left({\epsilon }_{0},{Y}^{0}\right)$$\stackrel{¯}{\epsilon }:={\epsilon }_{0}$$h:=\left(\stackrel{¯}{\epsilon },0\right)\in {R}_{++}×{R}^{n}×{R}^{l}×{R}^{m}$$k:=0$

Step2：如果 $‖{\psi }_{i}\left({z}^{k}\right)‖=0$ ，则终止计算，否则，令 $\beta \left({z}^{k}\right):=\gamma \mathrm{min}\left\{1,‖{\psi }_{i}\left({z}^{k}\right)‖\right\}$

Step3：求解下述方程组得到 $\Delta {z}^{k}:=\left(\Delta {\epsilon }_{k},\Delta {Y}^{k}\right)\in R×{R}^{n}×{R}^{l}×{R}^{m}$

$J{\psi }_{i}\left({z}^{k}\right)\Delta {z}^{k}=-{\psi }_{i}\left({z}^{k}\right)+\beta \left({z}^{k}\right)\stackrel{¯}{h}$ (21)

Step4：设 ${\alpha }_{k}$ 是满足下述不等式的最小的非负整数

$‖{\psi }_{i}\left({z}^{k}+{\alpha }_{k}\Delta {z}^{k}\right)‖\le \left[1-2\sigma \left(1-\gamma \stackrel{¯}{\epsilon }\right){\alpha }_{k}\right]‖{\psi }_{i}\left({z}^{k}\right)‖$ (22)

Step5：置 $k:=k+1$ ，转到步1。

${\epsilon }_{k+1}={\epsilon }_{k}+{\alpha }_{k}\Delta {\epsilon }_{k}=\left(1-{\alpha }_{k}\right){\epsilon }_{k}+{\alpha }_{k}\stackrel{¯}{\epsilon }\beta \left({z}^{k}\right)$ (23)

$R\left({z}^{k}\right)={\psi }_{i}\left({z}^{k}+\alpha \Delta {z}^{k}\right)-{\psi }_{i}\left({z}^{k}\right)+\alpha J{\psi }_{i}\left({z}^{k}\right)\Delta {z}^{k}$ (24)

$J{\psi }_{i}\left({z}^{k}\right)$ 的一致连续性知，对于 $z\in {R}_{++}×{R}^{n}$ ，有 $\underset{\alpha \to 0}{\mathrm{lim}}\frac{‖{R}^{k}\left(\alpha \right)‖}{\alpha }=0$ ，故对所有的 $\alpha \in \left(0,1\right)$$z\in {R}_{++}×{R}^{n}$ ，有

$\begin{array}{l}‖{\psi }_{1}\left({z}^{k}+{\alpha }_{k}\Delta {z}^{k}\right)‖\\ =‖R\left({z}^{k}\right)+{\psi }_{i}\left({z}^{k}\right)+\alpha J{\psi }_{i}\left({z}^{k}\right)\Delta {z}^{k}‖\\ =‖R\left({z}^{k}\right)+\left(1-\alpha \right){\psi }_{i}\left({z}^{k}\right)+\alpha \beta \left({z}^{k}\right)\stackrel{¯}{h}‖\\ \le ‖R\left({z}^{k}\right)‖+\left(1-\alpha \right)‖{\psi }_{i}\left({z}^{k}\right)‖+\alpha \stackrel{¯}{\mu }\beta \left({z}^{k}\right)\\ \le ‖R\left({z}^{k}\right)‖+\left[1-\alpha \left(1-\lambda \stackrel{¯}{\mu }\right)\right]‖{\psi }_{i}\left({z}^{k}\right)‖\end{array}$ (25)

$‖{\psi }_{i}\left({z}^{k}+{\alpha }_{k}\Delta {z}^{k}\right)‖\le \left[1-\sigma \left(1-\gamma \stackrel{¯}{\epsilon }\right){\alpha }_{k}\right]‖{\psi }_{i}\left({z}^{k}\right)‖$ (26)

(a) 由(23)式不难看出序列 $\left\{‖{\psi }_{i}\left({z}^{k}\right)‖\right\}$ 是单调递减的，这也暗示着序列 $\left\{‖\beta \left({z}^{k}\right)‖\right\}$ 是单调递减的。

(b) 设 $J\left(r\right):=\left\{\left(\epsilon ,Y\right)\in {R}_{+}×{R}^{n}×{R}^{l}×{R}^{m}:\stackrel{¯}{\epsilon }\beta \left(\epsilon ,Y\right)\le \epsilon \right\}$${z}^{0}\in J\left(r\right)$ 。实际上，对于所有的 $k\in N$${z}^{k}\in J\left(r\right)$ ，由于

$\begin{array}{l}{\epsilon }_{k+1}-\stackrel{¯}{\epsilon }\beta \left({z}^{k+1}\right)\\ =\left(1-{\tau }_{k}\right){\epsilon }_{k}+{\tau }_{k}\stackrel{¯}{\epsilon }\beta \left({z}^{k}\right)-\beta \left({z}^{k+1}\right)\\ \ge \stackrel{¯}{\epsilon }\left(\beta \left({z}^{k}\right)-\beta \left({z}^{k+1}\right)\right)\ge 0\end{array}$

(c) 结合式(23)与备注2的(4)，可以得到

${\epsilon }_{k+1}=\left(1-{\tau }_{k}\right){\epsilon }_{k}+{\tau }_{k}\stackrel{¯}{\epsilon }\beta \left({z}^{k}\right)\le \left(1-{\tau }_{k}\right){\epsilon }_{k}+{\tau }_{k}{\epsilon }_{k}={\epsilon }_{k}$

4. 数值实验

$〈\frac{1}{2}Dx,y-x〉\ge 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall y\in C$

$C=\left\{x\in {R}^{n}:Ax-a=0,Bx-b\le 0\right\}$

$n×n$ 正定矩阵， $A$$B$ 分别是 $l×n$$m×n$ 维矩阵。 $d$ 是一个 $n×1$ 维向量， $a$$b$ 分别是 $l×1$$m×1$ 维向量，并且 $l+m\le n$

$\delta =0.5,\text{\hspace{0.17em}}\sigma =1.0e-1,\text{\hspace{0.17em}}\gamma =0.1,\text{\hspace{0.17em}}{\epsilon }_{0}=0.2$

Table 1. System resulting data of example 1

5. 总结

[1] Huang, Z.H. and Ni, T. (2010) Smoothing Algorithms for Complementarity Problems over Symmetric Cones. Compu-tational Optimization and Applications, 45, 557-579.
https://doi.org/10.1007/s10589-008-9180-y

[2] Sun, J.H. and Wang, L. (2013) A Smoothing Newton Method Based on the Generalized Fischer-Burmeister Function for Varia-tional Inequality Problem. School of Science, 10, 151-160.

[3] Chen, J.S. (2007) On Some NCP-Function Based on the Generalized Fischer-Burmeister Function. Asia-Pacific Journal of Operational Research, 24, 401-420.
https://doi.org/10.1142/S0217595907001292

[4] Chen, X.D., Sun, D. and Sun, J. (2003) Complementarity Functions and Numerical Experiments on Some Smoothing Newton Methods for Second-Order-Cone Complementarity Problems. Computational Optimization and Applications, 25, 39-56.
https://doi.org/10.1023/A:1022996819381

[5] Fukushima, M., Luo, Z.Q. and Tseng, P. (2002) Smoothing Functions for Second-Order-Cone Complimentarity Problems. SIAM Journal on Optimization, 12, 436-460.
https://doi.org/10.1137/S1052623400380365

[6] Qi, L., Sun, D. and Zhou, G. (2000) A New Look at Smooth-ing Newton Method for Nonlinear Complementarity Problems and Box Constrained Variational Inequalities. Mathe-matical Programming, 87, 1-35.
https://doi.org/10.1007/s101079900127

[7] Sun, D. and Sun, J. (2005) Strong Semismoothness of the Fisch-er-Burmeister SDC and SOC Complementarity Functions. Mathematical Programming, 103, 575-581.
https://doi.org/10.1007/s10107-005-0577-4

[8] Sun, J.H., Chen, J.S. and Ko, C.H. (2012) Neural Networks for Solving Second-Order Cone Constrained Variational Inequality Problem. Computational Optimization and Applications, 51, 623-648.
https://doi.org/10.1007/s10589-010-9359-x

[9] Sun, J.H. and Zhang, L.W. (2009) A Globally Convergent Method Based on Fischer-Burmeister Operators for Solving Second-Order-Cone Constrained Variational Inequality Problems. Computers and Mathematics with Applications, 58, 1936-1946.
https://doi.org/10.1016/j.camwa.2009.07.084

[10] Tseng, P. (1998) Merit Functions for Semidefinite Comple-mentarity Problems. Mathematical Programming, 83, 159-185.
https://doi.org/10.1007/BF02680556

[11] Aghassi, M., Bertsimas, D. and Perakis, G. (2006) Solving Asymmet-ric Variational Inequalities via Convex Optimization. Operations Research Letters, 34, 481-490.
https://doi.org/10.1016/j.orl.2005.09.006

[12] Chen, J.S., Ko, C.H. and Pan, S.H. (2010) A Neural Network Based on the Generalized Fischer-Burmeister Function for Nonlinear Complementarity Problems. Information Sciences, 180, 697-711.
https://doi.org/10.1016/j.ins.2009.11.014

[13] Hu, S.L., Huang, Z.H. and Chen, J.S. (2009) Properties of a Fam-ily of Generalized NCP-Functions and a Derivative Free Algorithm for Complementarity Problems. Journal of Com-putational and Applied Mathematics, 230, 69-82.
https://doi.org/10.1016/j.cam.2008.10.056

[14] Facchiniei, F. and Pang, J.S. (2003) Finite-Dimensional Varia-tional Inequalities and Complementarity Problems. Volume 2, Springer-Verlag, New York.

[15] Fukushima, M. (1992) Equivalent Differentiable Optimization Problems and Descent Methods for Asymmetric Variational Inequality Problems. Mathematical Programming, 53, 99-110.
https://doi.org/10.1007/BF01585696

[16] Pan, S. and Chen, J. (2010) A Semismooth Newton Method for the SOCCP Based on a One-Parametric Class of SOC Complementarity Functions. Computational Optimization and Applications, 45, 59-88.
https://doi.org/10.1007/s10589-008-9166-9

Top