#### 期刊菜单

A SQP Method for Linear Complementary Constraints Problem
DOI: 10.12677/AAM.2019.88164, PDF, HTML, XML, 下载: 930  浏览: 5,812  科研立项经费支持

Abstract: In this paper, equilibrium problem with linear equilibrium constrains is studied. By using a smoothing complimentarily function which is differentiable everywhere, when smoothing parameter tends to zero, the original problem is equivalently transformed to a smoothing nonlinear optimization, then the smooth nonlinear optimization is solved by SQP algorithm. The algorithm converges globally under certain conditions. Finally, numerical experiments are given to prove the effectiveness of the algorithm.

1. 引言

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x,y\right)\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}Ax\le b,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}w=Nx+My+q,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le w\perp y\ge 0,\end{array}$ (1.1)

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

Zang在文献 [3] 提出一个如下形式的光滑函数：

${\varphi }_{2}\left(a,\mu \right)=\left\{\begin{array}{l}0,\text{​}\text{​}\text{​}\text{​}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}a\le -\frac{\mu }{2},\\ \frac{1}{2\mu }{\left(a+\frac{\mu }{2}\right)}^{2},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}-\frac{\mu }{2}

Song Xu在文献 [4] 中提出一个如下形式的新的光滑函数：

${\varphi }_{3}\left(a,\mu \right)=\mu \mathrm{ln}\underset{i=1}{\overset{m}{\sum }}{\text{e}}^{\frac{{a}_{i}}{\mu }}.$

$w\perp y$ 光滑化，将问题(1.1)转化为一光滑非线性规划的一般约束优化问题，然后借助罚函数型SQP方法思想，通过求解后者逼近前者的解，并证明该算法是全局收敛的.

$\begin{array}{l}z=\left(x,y,w\right),\text{\hspace{0.17em}}s=\left(x,y\right),\text{\hspace{0.17em}}t=\left(y,w\right),\text{\hspace{0.17em}}{z}^{k}=\left({x}^{k},{y}^{k},{w}^{k}\right),\text{\hspace{0.17em}}{s}^{k}=\left({x}^{k},{y}^{k}\right),\text{\hspace{0.17em}}{t}^{k}=\left({y}^{k},{w}^{k}\right),\\ {t}_{i}=\left({y}_{i},{w}_{i}\right),\text{\hspace{0.17em}}\text{d}z=\left(\text{d}x,\text{d}y,\text{d}w\right),\text{\hspace{0.17em}}\text{d}{z}^{k}=\left(\text{d}{x}^{k},\text{d}{y}^{k},\text{d}{w}^{k}\right),\text{\hspace{0.17em}}X=\left\{z\in {X}_{0}|0\le w\perp y\ge 0\right\},\\ {X}_{0}=\left\{z|Ax\le b,w=Nx+My+q\right\},\text{\hspace{0.17em}}{A}^{\text{T}}=\left({a}_{1}^{\text{T}},\cdots ,{a}_{p}^{\text{T}}\right),\text{\hspace{0.17em}}{b}^{\text{T}}=\left({b}_{1},\cdots ,{b}_{p}\right).\end{array}$

${R}^{n}$ 表示一个实n维Euclide空间。

e 表示各分量均为1的列向量。

$\nabla f\left(x\right)$ 表示函数 $f\left(x\right)$ 的一阶导数或梯度。

${\nabla }^{2}f\left(x\right)$ 表示函数 $f\left(x\right)$ 的二阶导数或 Hessian 矩阵。

$u>0$ 表示向量u的每一个分量 ${u}_{j}>0$

$u\ge 0$ 表示向量u的每一个分量 ${u}_{j}\ge 0$

${x}^{\text{T}}$${A}^{\text{T}}$ 分别表示向量x和矩阵A的转置。

$diag\left({a}_{j},j=1,2,~,m\right)$ 表示以 ${a}_{j}$ 为对角元素的m阶对角矩阵。

2. 问题光滑化

$L\left(z,F\right)=\left\{d=\underset{k\to \infty }{\mathrm{lim}}\frac{{z}^{k}-z}{\tau }:{z}^{k}\in F,\underset{k\to \infty }{\mathrm{lim}}{z}^{k}=z,{\tau }_{k}↓0\right\},$

H 2.1 问题(1.1)中的矩阵M是一个 ${P}_{0}$ 矩阵，即所有的主子式均非负。

H 2.2 对任意的 $z\in {X}_{0}$ ，矩阵A的行向量组 $\left\{{a}_{j}|j\in L\left(z\right)\right\}$ 线性无关。

H 2.3 问题(1.1)的可行域非空。

H 2.4 函数 $f\left(x,y\right)$ 为二阶连续可微的。

$\text{d}z=\left(\text{d}x,\text{d}y,\text{d}w\right)\in \Gamma \left(X;{z}^{\ast }\right)⇒\nabla f{\left({x}^{\ast },{y}^{\ast }\right)}^{\text{T}}\text{d}s\ge 0,$

$\left({y}_{i},{w}_{i}\right)\ne \left(0,0\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i=1,\cdots ,m,$

${z}^{\ast }$ 为问题(1.1)的一个稳定点的充分必要条件是存在乘子 $\left({\lambda }^{\ast },{u}^{\ast },{v}^{\ast }\right)$ ，使得下面的方程组成立：

$\begin{array}{l}\left(\begin{array}{c}\nabla {f}_{x}\left({x}^{\ast },{y}^{\ast }\right)\\ \nabla {f}_{y}\left({x}^{\ast },{y}^{\ast }\right)\\ 0\end{array}\right)+\left(\begin{array}{c}{A}^{\text{T}}\\ 0\\ 0\end{array}\right){\lambda }^{\ast }+\left(\begin{array}{c}{N}^{\text{T}}\\ {M}^{\text{T}}\\ -I\end{array}\right){u}^{\ast }+\left(\begin{array}{c}0\\ {W}^{\ast }\\ {Y}^{\ast }\end{array}\right){v}^{\ast }=0,\\ {\left(A{x}^{\ast }-b\right)}^{\text{T}}{\lambda }^{\ast }=0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}A{x}^{\ast }-b\ge 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\lambda }^{\ast }\ge 0,\end{array}$ (2.1)

$\phi \left(y,w\right)=\mathrm{min}\left\{y,w\right\}$ ，其中 $\mathrm{min}\left\{y,w\right\}$ 定义为 $\mathrm{min}\left\{{y}_{i},{w}_{i}\right\}e,i=1,\cdots ,m$$e={\left(1,\cdots ,1\right)}^{\text{T}}\in {R}^{m}$

${y}^{\text{T}}w=0,y\ge 0,w\ge 0⇔\phi \left(y,w\right)=\mathrm{min}\left\{y,w\right\}=0.$ (2.2)

$\Phi \left(a,b,\mu \right)=\left(\begin{array}{c}\varphi \left({a}_{1},{b}_{1},\mu \right)\\ ⋮\\ \varphi \left({a}_{m},{b}_{m},\mu \right)\end{array}\right),$ (2.3)

$\varphi \left(a,b,\mu \right)=-\mu \mathrm{ln}\left(1+{\text{e}}^{-\frac{a}{\mu }}\right)-\mu \mathrm{ln}\left(1+{\text{e}}^{-\frac{b}{\mu }}\right),$ (2.4)

$\begin{array}{l}\nabla \varphi \left(y,w,\mu \right)\\ =\left(\begin{array}{l}{\nabla }_{y}\varphi \left(y,w,\mu \right)\\ \nabla w\varphi \left(y,w,\mu \right)\end{array}\right)\\ ={\left(\frac{\partial \varphi \left({y}_{1},{w}_{1},\mu \right)}{\partial {y}_{1}},\cdots ,\frac{\partial \varphi \left({y}_{m},{w}_{m},\mu \right)}{\partial {y}_{m}},\frac{\partial \varphi \left({y}_{1},{w}_{1},\mu \right)}{\partial {w}_{1}},\cdots ,\frac{\partial \varphi \left({y}_{m},{w}_{m},\mu \right)}{\partial {w}_{m}}\right)}^{\text{T}}\\ ={\left(\frac{{\text{e}}^{-\frac{{y}_{1}}{\mu }}}{1+{\text{e}}^{-\frac{{y}_{1}}{\mu }}},\cdots ,\frac{{\text{e}}^{-\frac{{y}_{m}}{\mu }}}{1+{\text{e}}^{-\frac{{y}_{m}}{\mu }}},\frac{{\text{e}}^{-\frac{{w}_{1}}{\mu }}}{1+{\text{e}}^{-\frac{{w}_{1}}{\mu }}},\cdots ,\frac{{\text{e}}^{-\frac{{w}_{m}}{\mu }}}{1+{\text{e}}^{-\frac{{w}_{m}}{\mu }}}\right)}^{\text{T}}.\end{array}$ (2.5)

$\varphi \left(a,b,\mu \right)$ 有一些很好的性质：

$\underset{\mu \to 0}{\mathrm{lim}}\varphi \left(a,b,\mu \right)=\underset{\mu \to 0}{\mathrm{lim}}-\mu \mathrm{ln}\left(1+{\text{e}}^{-\frac{a}{\mu }}\right)-\mu \mathrm{ln}\left(1+{\text{e}}^{-\frac{b}{\mu }}\right)=0,$

$\underset{\mu \to 0}{\mathrm{lim}}\Phi \left(y,w,\mu \right)=\phi \left(y,w\right)=0.$ (2.6)

$\Phi \left(y,w,0\right)=\phi \left(y,w\right),$ (2.7)

$\underset{\mu \to 0}{\mathrm{lim}}\varphi \left(y,w,\mu \right)=\varphi \left(y,w,0\right).$ (2.8)

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}f\left(x,y\right)\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}Ax\le b,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}w=Nx+My+q,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\Phi \left(y,w,\mu \right)=0,\end{array}$ (2.9)

$\mu \ge 0$ 且充分逼近于0时，问题(2.9)是原问题(1.1)的一个近似逼近；当 $\mu =0$ 时，问题(2.9)是原问题(1.1)的等价；当 $\mu >0$ 时，问题(2.9)是一个一般的可微非线性规划问题。

$\phi \left(z,\epsilon ,\mu \right)=f\left(x,y\right)+\epsilon \underset{i=1}{\overset{m}{\sum }}|\varphi \left({y}_{i},{w}_{i},\mu \right)|,$ (2.10)

$\begin{array}{l}{\phi }^{\prime }\left(z,\epsilon ,\mu ,\text{d}z\right)\\ =\nabla f{\left(s\right)}^{\text{T}}\text{d}s+\epsilon \underset{i\in {I}_{+}}{\sum }\nabla \varphi {\left({t}_{i},\mu \right)}^{\text{T}}\text{d}{t}_{i}+\epsilon \underset{i\in {I}_{0}}{\sum }|\nabla \varphi {\left({t}_{i},\mu \right)}^{\text{T}}\text{d}{t}_{i}|-\epsilon \underset{i\in {I}_{-}}{\sum }|\nabla \varphi {\left({t}_{i},\mu \right)}^{\text{T}}\text{d}{t}_{i}|,\end{array}$ (2.11)

$\begin{array}{l}{I}_{+}\equiv {I}_{+}\left(y,w,\mu \right)=\left\{i|\varphi \left({y}_{i},{w}_{i},\mu \right)>0\right\},\\ {I}_{0}\equiv {I}_{0}\left(y,w,\mu \right)=\left\{i|\varphi \left({y}_{i},{w}_{i},\mu \right)=0\right\},\\ {I}_{-}\equiv {I}_{-}\left(y,w,\mu \right)=\left\{i|\varphi \left({y}_{i},{w}_{i},\mu \right)<0\right\}.\end{array}$

3. 预备知识与算法

$0<{\partial }_{a}\varphi \left(a,b,{\mu }_{k}\right)<1,0<{\partial }_{b}\varphi \left(a,b,{\mu }_{k}\right)<1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}i=1,\cdots ,m,$ (3.1)

$0<{\left(\frac{\partial \varphi \left(a,b,{\mu }_{k}\right)}{\partial a}\right)}^{2}+{\left(\frac{\partial \varphi \left(a,b,{\mu }_{k}\right)}{\partial b}\right)}^{2}\le 2$ (3.2)

$\begin{array}{l}{\left(\frac{\partial \varphi \left(y,w,{\mu }_{k}\right)}{\partial y}\right)}^{2}+{\left(\frac{\partial \varphi \left(y,w,{\mu }_{k}\right)}{\partial w}\right)}^{2}\\ ={\left(\frac{{\text{e}}^{-\frac{y}{\mu }}}{1+{\text{e}}^{-\frac{y}{\mu }}}\right)}^{2}+{\left(\frac{{\text{e}}^{-\frac{w}{\mu }}}{1+{\text{e}}^{-\frac{w}{\mu }}}\right)}^{2}\\ \le {\left(\frac{{\text{e}}^{-\frac{y}{\mu }}}{{\text{e}}^{-\frac{y}{\mu }}}\right)}^{2}+{\left(\frac{{\text{e}}^{-\frac{w}{\mu }}}{{\text{e}}^{-\frac{w}{\mu }}}\right)}^{2}\\ =2.\end{array}$

${z}^{k}=\left({x}^{k},{y}^{k},{w}^{k}\right)\in {X}_{0}$ ，是算法第k步的迭代点， $\mu >0$${B}_{k}$ 是一个 $n+2m$ 阶的对称正定矩阵，在算法的第k步迭代中，求解以下二次序列子问题

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\nabla f{\left({x}^{k}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{y}^{k}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}x\\ \text{d}y\end{array}\right)+\frac{1}{2}\left(\text{d}{x}^{\text{T}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{d}{y}^{\text{T}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{d}{w}^{\text{T}}\right){B}_{k}\left(\begin{array}{c}\text{d}x\\ \text{d}y\\ \text{d}w\end{array}\right),\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}A{x}^{k}+A\text{d}x-b\le 0,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{d}w-N\text{d}x-M\text{d}y=0,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\Phi \left({t}^{k},{\mu }^{k}\right)+{\nabla }_{t}\Phi {\left({t}^{k},\mu \right)}^{\text{T}}\text{d}t=0.\end{array}$ (3.3)

$\nabla \Phi \left({y}^{k},{w}^{k},{\mu }^{k}\right)=\left(\begin{array}{c}{D}_{y}^{k}\\ {D}_{w}^{k}\end{array}\right),$ (3.4)

$\begin{array}{l}{D}_{y}^{k}=diag\left({\partial }_{{y}_{i}}\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right)\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}i=1,\cdots ,m\\ {D}_{w}^{k}=diag\left({\partial }_{{w}_{i}}\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right)\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}i=1,\cdots ,m\end{array}$

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\nabla f{\left({x}^{k}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{y}^{k}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}x\\ \text{d}y\end{array}\right)+\frac{1}{2}\left(\text{d}{x}^{\text{T}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{d}{y}^{\text{T}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{d}{w}^{\text{T}}\right){B}_{k}\left(\begin{array}{c}\text{d}x\\ \text{d}y\\ \text{d}w\end{array}\right),\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}A{x}^{k}+A\text{d}x-b\le 0,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(\begin{array}{lll}N\hfill & M\hfill & -I\hfill \\ 0\hfill & {D}_{y}^{k}\hfill & {D}_{w}^{k}\hfill \end{array}\right)\left(\begin{array}{c}\text{d}x\\ \text{d}y\\ \text{d}w\end{array}\right)+\left(\begin{array}{c}0\\ \Phi \left({y}_{i},{w}_{i},\mu \right)\end{array}\right)=0.\end{array}$ (3.5)

QP子问题(3.3)是一个带线性约束的凸规划问题，所以问题(3.5)的最优解与KKT点等价，进而其KKT系统可以写成：

$\left(\begin{array}{c}\nabla f\left({x}^{k}\right)\\ \nabla f\left({y}^{k}\right)\\ 0\end{array}\right)+{B}_{k}\left(\begin{array}{c}\text{d}x\\ \text{d}y\\ \text{d}w\end{array}\right)+\left(\begin{array}{cc}{N}^{\text{T}}& 0\\ {M}^{\text{T}}& {D}_{y}^{k}\end{array}\right)\left(\begin{array}{c}l\\ m\end{array}\right)+\left(\begin{array}{c}{A}^{\text{T}}\\ 0\\ 0\end{array}\right)\lambda =0,$ (3.6)

$0\le \left(b-A{x}^{k}-A\text{d}x\right)\perp \lambda \ge 0,$ (3.7)

$\left(\begin{array}{lll}N\hfill & M\hfill & -I\hfill \\ 0\hfill & {D}_{y}^{k}\hfill & {D}_{w}^{k}\hfill \end{array}\right)\text{d}z+\left(\begin{array}{c}0\\ \Phi \left({y}_{i},{w}_{i},\mu \right)\end{array}\right)=\text{0}，$ (3.8)

$\phi \left({z}^{k}+{\delta }^{{m}_{k}}\text{d}{z}^{k},\epsilon ,{\mu }_{k}\right)\le \phi \left({z}^{k},\epsilon ,{\mu }_{k}\right)+\sigma {\delta }^{{m}_{k}}{\phi }^{\prime }\left({z}^{k},\epsilon ,{\mu }_{k};\text{d}{z}^{k}\right).$ (3.9)

${\epsilon }_{k}=\left\{\begin{array}{l}{\epsilon }_{k-1},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\epsilon }_{k-1}\ge {‖{c}^{k}‖}_{\infty }+\xi ,\\ \mathrm{max}\left\{{‖{c}^{k}‖}_{\infty }+\xi ,{\epsilon }_{k-1}+2\xi \right\},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\epsilon }_{k-1}<{‖{c}^{k}‖}_{\infty }+\xi ,\end{array}$ (3.10)

${\phi }^{\prime }\left({z}^{k},{\epsilon }^{k},{\mu }_{k};\text{d}{z}^{k}\right)\le {\left(-\text{d}{z}^{k}\right)}^{\text{T}}{B}_{k}\text{d}{z}^{k}<0$ (3.11)

$\phi \left({z}^{k}+\rho \text{d}z,\epsilon ,{\mu }_{k}\right)\le \phi \left({z}^{k},\epsilon ,{\mu }_{k}\right)+\sigma \rho {\phi }^{\prime }\left({z}^{k},\epsilon ,{\mu }_{k};\text{d}{z}^{k}\right).$ (3.12)

${D}_{y}^{k}\text{d}{y}^{k}+{D}_{w}^{k}\text{d}{w}^{k}+\Phi \left({y}^{k},{w}^{k},{\mu }_{k}\right)=0,$

${\left(\begin{array}{c}{\nabla }_{y}\varphi \left({y}_{i},{w}_{i},\mu \right)\\ {\nabla }_{w}\varphi \left({y}_{i},{w}_{i},\mu \right)\end{array}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}{y}_{i}^{k}\\ \text{d}{w}_{i}^{k}\end{array}\right)+\Phi \left({y}_{i}^{k},{w}_{i}^{k},\mu \right)=0.$ (3.13)

${\phi }^{\prime }\left({z}^{k},{\epsilon }_{k},{\mu }_{k};\text{d}{z}^{k}\right)=\nabla f{\left({x}^{k}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{y}^{k}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}{x}^{k}\\ \text{d}{y}^{k}\end{array}\right)-{\epsilon }_{k}\sum |\varphi \left({y}^{k},{w}^{k},{\mu }_{k}\right)|\text{\hspace{0.17em}}.$ (3.14)

$\begin{array}{l}\nabla f{\left({x}^{k}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{y}^{k}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}{x}^{k}\\ \text{d}{y}^{k}\end{array}\right)+{\left({\lambda }^{k}\right)}^{\text{T}}A\text{d}{x}^{k}+{\left(\text{d}{z}^{k}\right)}^{\text{T}}{B}_{k}\text{d}{z}^{k}\\ +{\left({l}^{k}\right)}^{\text{T}}\left(N\text{d}x+M\text{d}y-\text{d}{w}^{k}\right)+{\left({m}^{k}\right)}^{\text{T}}\left({D}_{y}^{k}\text{d}{y}^{k}+{D}_{w}^{k}\text{d}{w}^{k}\right)=0,\end{array}$

$\begin{array}{l}\nabla f{\left({x}^{k}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{y}^{k}\right)}^{\text{T}}\left(\begin{array}{c}\text{d}{x}^{k}\\ \text{d}{y}^{k}\end{array}\right)+{\left(\text{d}{z}^{k}\right)}^{\text{T}}{B}_{k}\text{d}{z}^{k}-{\left({m}^{k}\right)}^{\text{T}}\Phi \left({y}^{k},{w}^{k},{\mu }_{k}\right)\\ ={\left({\lambda }^{k}\right)}^{\text{T}}\left(Ax-b\right)\le 0.\end{array}$ (3.15)

$\begin{array}{l}{\phi }^{\prime }\left({z}^{k},{\epsilon }_{k},{\mu }_{k};\text{d}{z}^{k}\right)\\ \le -{\left(\text{d}{z}^{k}\right)}^{\text{T}}{B}_{k}\text{d}{z}^{k}+\underset{i\in {I}_{+}^{k}}{\sum }\left({c}_{i}^{k}-{\epsilon }_{k}\right)\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right)+\underset{i\in {I}_{-}^{k}}{\sum }\left({c}_{i}^{k}+{\epsilon }_{k}\right)\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right),\end{array}$

${I}_{+}^{k}=\left\{i:\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right)>0\right\},$

${I}_{-}^{k}=\left\{i:\varphi \left({y}_{i}^{k},{w}_{i}^{k},{\mu }_{k}\right)<0\right\}.$

${\phi }^{\prime }\left({z}^{k},{\epsilon }^{k},{\mu }_{k};\text{d}{z}^{k}\right)\le {\left(-\text{d}{z}^{k}\right)}^{\text{T}}{B}_{k}\text{d}{z}^{k}<0.$

4. 收敛性分析

H4.1 无穷点列 $\left\{{z}_{k}\right\}$ 有界。

H4.2 若H4.1成立，序列 $\left\{{z}_{k}\right\}$ 的每个极限点 ${z}^{\ast }=\left({x}^{\ast },{y}^{\ast },{w}^{\ast }\right)$ ，满足下层非退化条件： $\left({y}^{\ast },{w}^{\ast }\right)\ne \left(0,0\right),i=1,\cdots ,m.$

H4.3 存在常数 $a,b>0$ ，有

$a{‖z‖}^{2}\le {z}^{\text{T}}{B}_{k}z\le b‖z‖{|}^{2},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall z\in {R}^{n+2m},k=1,2,\cdots .$

1) 存在一个常数 $C>0$ ，有

$‖{\left(\begin{array}{cc}M& -I\\ {D}_{y}^{k}& {D}_{W}^{k}\end{array}\right)}^{-1}‖\le C,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k\in K.$

2) 序列 $\left\{\left({\lambda }^{k},{l}^{k},{m}^{k}\right)\right\}$$\left\{\text{d}{z}^{k}\right\}$ 有界。

3) 存在一个正整数 ${k}_{0}$ ，使得 ${\epsilon }_{k}={\epsilon }_{{k}_{0}}=\epsilon ,\forall k\ge {k}_{0}$

${v}_{k}\ge 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\underset{k=1}{\overset{\infty }{\sum }}{v}_{k}<\infty ,\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\gamma }_{k+1}\le {\gamma }_{k}+{v}_{k},\text{\hspace{0.17em}}\text{\hspace{0.17em}}k=1,2,\cdots .$ (4.1)

1) 数列 $\left\{{\gamma }_{k}\right\}$ 有上界。即

$\underset{k\to \infty }{\overset{____}{\mathrm{lim}}}{\gamma }_{k}<+\infty ;$

2) 数列 $\left\{{\gamma }_{k}\right\}$ 整列收敛。

$|\varphi \left({y}^{k},{w}^{k},{\delta }_{2}\right)|\le |\varphi \left({y}^{k},{w}^{k},{\delta }_{1}\right)|+2\left(\mathrm{ln}2+\frac{\stackrel{˜}{M}}{{\delta }_{2}}\right){\delta }_{1}$

$\begin{array}{l}|\varphi \left({y}^{k},{w}^{k},{\delta }_{2}\right)|\\ \le |\varphi \left({y}^{k},{w}^{k},{\delta }_{1}\right)+{{\varphi }^{\prime }}_{\mu }\left({y}^{k},{w}^{k},\stackrel{¯}{\delta }\right)\left({\delta }_{2}-{\delta }_{1}\right)|\\ \le |\varphi \left(y,w,{\delta }_{1}\right)|+\left[\mathrm{ln}\left(1+{\text{e}}^{-\frac{y}{\mu }}\right)+\frac{\frac{y}{\mu }\cdot {\text{e}}^{-\frac{y}{\mu }}}{1+{\text{e}}^{-\frac{y}{\mu }}}+\mathrm{ln}\left(1+{\text{e}}^{-\frac{w}{\mu }}\right)+\frac{\frac{w}{\mu }\cdot {\text{e}}^{-\frac{w}{\mu }}}{1+{\text{e}}^{-\frac{w}{\mu }}}\right]\left({\delta }_{2}-{\delta }_{1}\right)\\ \le |\varphi \left(y,w,{\delta }_{1}\right)|+\left[2\mathrm{ln}2+\frac{1}{\mu }\left(\frac{y}{\mu }+\frac{w}{\mu }\right)\right]\left({\delta }_{2}-{\delta }_{1}\right)\end{array}$

$\begin{array}{l}\le |\varphi \left(y,w,{\delta }_{1}\right)|+\left[2\mathrm{ln}2+\frac{2}{{\mu }^{2}}\mathrm{max}\left\{y,w\right\}\right]\left({\delta }_{2}-{\delta }_{1}\right)\\ \le |\varphi \left(y,w,{\delta }_{1}\right)|+2\left[\mathrm{ln}2+\frac{1}{\delta }\mathrm{max}\left\{y,w\right\}\right]\left({\delta }_{2}-{\delta }_{1}\right)\\ \le |\varphi \left({y}^{k},{w}^{k},{\delta }_{1}\right)|+2\left(\mathrm{ln}2+\frac{\stackrel{˜}{M}}{{\delta }_{2}}\right){\delta }_{1}.\end{array}$

$\underset{k\to \infty }{\mathrm{lim}}\phi \left({z}^{k},{\epsilon }^{k},{\mu }_{k}\right)=\underset{k\to \infty }{\mathrm{lim}}\phi \left({z}^{k+1},{\epsilon }^{k},{\mu }_{k}\right)=\phi \left({z}^{\ast },\epsilon ,0\right).$

$\text{d}{z}^{k}=\text{d}{z}^{\ast }=\left(\text{d}{x}^{\ast },\text{d}{y}^{\ast },\text{d}{w}^{\ast }\right),{x}^{k}\to {x}^{\ast },{B}_{k}\to {B}_{\ast },{l}^{k}\to {l}^{\ast },{m}^{k}\to {m}^{\ast },k\in K.$ (4.2)

$\underset{k\in K}{\mathrm{lim}}\text{d}{z}^{k}=\text{d}{z}^{\ast }=0.$ (4.3)

${\phi }^{\prime }\left({z}^{\ast },\epsilon ,0;\text{d}{z}^{k}\right)=-{\left(\text{d}{z}^{\ast }\right)}^{\text{T}}{B}_{\ast }\text{d}{z}^{\ast }<0.$

$k\to \infty$ ，序列 $\left\{{z}^{k}\right\}$ 收敛于 ${z}^{\ast }$ ，记

$\underset{k\in K}{\mathrm{lim}}{\phi }^{\prime }\left({z}^{k},\epsilon ,{\mu }_{k};\text{d}{z}^{k}\right)={\phi }^{\prime }\left({z}^{\ast },\epsilon ,0;\text{d}{z}^{\ast }\right).$

${\alpha }_{k}\ge {\alpha }_{\ast }=\mathrm{inf}\left({\alpha }_{k},k\in K\right)>0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}k\in K.$

$0=\underset{k\in K}{\mathrm{lim}}\left(\phi \left({z}^{k+1},\epsilon ,{\mu }_{k}\right)-\phi \left({z}^{k},\epsilon ,{\mu }_{k}\right)\right)\le \underset{k\in K}{\mathrm{lim}}\delta \alpha {\phi }^{\prime }\left({z}^{k},\epsilon ,{\mu }_{k};\text{d}{z}^{k}\right)\le \frac{1}{2}\delta {\alpha }_{\ast }{\phi }^{\prime }\left({z}^{k},\epsilon ,0;\text{d}{z}^{k}\right),$

$k\in K,k\to \infty$ 时。这与(3.12)矛盾，从而假设 $\text{d}{z}^{\ast }\ne 0$ 不成立，即(4.3)成立.

$A{x}^{\ast }\le b,\text{\hspace{0.17em}}\text{\hspace{0.17em}}{w}^{\ast }=N{x}^{\ast }+M{y}^{\ast }+q,$

$\begin{array}{l}\nabla f\left({x}^{\ast },{y}^{\ast }\right)+{A}^{\text{T}}{\lambda }^{\ast }+{N}^{\text{T}}{l}^{\ast }=0,\\ {M}^{\text{T}}{l}^{\ast }+{D}_{y}^{\ast }{m}^{\ast }=0,\\ {l}^{\ast }={D}_{w}^{\ast }{m}^{\ast },\\ 0\le {\lambda }^{\ast }\perp \left(b-A{x}^{\ast }\right)\ge 0,\\ \underset{k\to \infty }{\mathrm{lim}}\Phi \left(a,b,{\mu }_{k}\right)=\mathrm{min}\left(a,b\right)=0,\end{array}$ (4.4)

${D}_{y}^{\ast }=diag\left({\nabla }_{{y}_{i}}\varphi \left({y}_{i}^{\ast },{w}_{i}^{\ast },0\right),i=1,\cdots ,m\right),$

${D}_{w}^{\ast }=diag\left({\nabla }_{{w}_{i}}\varphi \left({y}_{i}^{\ast },{w}_{i}^{\ast },0\right),i=1,\cdots ,m\right).$

$0\le {w}^{\ast }\perp {y}^{\ast }\ge 0,$

${z}^{\ast }\in {X}_{0}$ ，从而有 ${z}^{\ast }\in X$

5. 数值实验

${B}_{k}$ 采用BFGS公式修正：

${B}_{k+1}={B}_{k}-\frac{{B}_{k}{\stackrel{^}{s}}_{k}{\left({B}_{k}{\stackrel{^}{s}}_{k}\right)}^{\text{T}}}{{\stackrel{^}{s}}_{k}^{\text{T}}{B}_{k}{\stackrel{^}{s}}_{k}}+\frac{{\stackrel{^}{\eta }}_{k}{\stackrel{^}{\eta }}_{k}^{\text{T}}}{{\stackrel{^}{s}}_{k}^{\text{T}}{\stackrel{^}{\eta }}_{k}},$

${\stackrel{^}{\gamma }}_{k}=\nabla {L}_{z}\left({z}^{k}+{\stackrel{^}{s}}_{k},{\mu }_{k}\right)-\nabla {L}_{z}\left({z}^{k},{\mu }_{k}\right),$

$\theta =\left\{\begin{array}{l}1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\stackrel{^}{s}}_{k}{\stackrel{^}{\gamma }}_{k}\ge 0.2{\stackrel{^}{s}}_{k}^{\text{T}}{B}_{k}{\stackrel{^}{s}}_{k}\\ \frac{0.8{\stackrel{^}{s}}_{k}^{\text{T}}{B}_{k}{\stackrel{^}{s}}_{k}}{{\stackrel{^}{s}}_{k}^{\text{T}}{B}_{k}{\stackrel{^}{s}}_{k}-{\stackrel{^}{s}}_{k}{\stackrel{^}{\gamma }}_{k}},否则.\end{array}$

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x\right)=\frac{1}{2}{x}^{2}+\frac{1}{2}xy-95x\\ \text{s}\text{.t}.\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le x\le 200,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le w\perp y\ge 0.\end{array}$

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x\right)=\frac{1}{2}\left[{\left({x}_{1}+{x}_{2}+{y}_{1}-15\right)}^{2}+{\left({x}_{1}+{x}_{2}+{y}_{2}-15\right)}^{2}\right]\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le x\le 10,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}w=Nx+My+q,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le w\perp y\ge 0,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left(x,y,w\right)\in {R}^{2}×{R}^{2}×{R}^{2}.\end{array}$

$q=\left(\begin{array}{c}-36\\ -25\end{array}\right),\text{\hspace{0.17em}}M=\left(\begin{array}{cc}2& 8/3\\ 5/4& 2\end{array}\right),\text{\hspace{0.17em}}N=\left(\begin{array}{cc}8/3& 2\\ 2& 5/4\end{array}\right).$

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x,y\right)=\frac{1}{2}{\left({x}_{1}+3{y}_{1}-4{y}_{2}-5\right)}^{2}+{\left({x}_{2}-\frac{15}{8}{y}_{1}+3{y}_{2}-9\right)}^{2}\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le {x}_{1}\le 10,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }0\le {x}_{2}\le 10,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }0\le y\perp \left[{\left(\begin{array}{cc}0& -1\\ -1& 0\end{array}\right)}^{\text{T}}x+{\left(\begin{array}{cc}3& -\frac{15}{8}\\ -4& 3\end{array}\right)}^{\text{T}}y+\left(\begin{array}{c}10\\ 6\end{array}\right)\right]\ge 0.\end{array}$

$\begin{array}{l}\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x\right)=\frac{1}{2}{x}^{\text{T}}x+{e}^{\text{T}}y\\ \text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}Ax\le b,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}w=Nx+My+q,\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\le w\perp y\ge 0.\end{array}$

Table 1. The numerical experiment results of problem 1 - problem 3

Table 2. The numerical experiment results of problem 4

 [1] Yu, B., Mitchell, J.E. and Pang, J.-S. (2019) Solving Linear Programs with Complementarity Constraints Using Branch-and-Cut. Mathematical Programming Computation, 11, 267-310. https://doi.org/10.1007/s12532-018-0149-2 [2] 吴学谦, 李声杰. 随机线性互补问题的无约束优化再定式[J]. 数学年刊A辑(中文版), 2019, 40(1): 43-54. [3] Zang, I. (1980) A Smoothing-Out Technique for Min-Max Optimization. Mathematical Programming, 19, 61-71. https://doi.org/10.1007/BF01581628 [4] Song, X. (2001) Smoothing Method for Minimax Problems. Computational Optimization and Applications, 20, 267-279. https://doi.org/10.1023/A:1011211101714 [5] Luo, Z.Q., Pang, J.S. and Ralph, D. (1996) Mathematical Program with Equilibrium Constraints. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511983658 [6] 简金宝. 光滑约束优化快速算法[M]. 北京: 科学出版社, 2010.