基于Mangasarian函数的松弛方法的收敛性研究

Convergence Research of Relaxation Methods Based on Mangasarian Function

摘要: 本文讨论互补约束优化问题(MPCC)。MPCC在金融经济，交通规划，网络设计等领域有着重要的应用。由于MPCC的特殊结构，MPCC在可行点处不满足大多数的约束规范。因此，MPCC问题在理论分析和算法设计上都是较难处理的。本文基于Mangasarian互补函数构造出的松弛问题，证明在MPCC-rCPLD约束规范条件下，松弛问题的稳定点列收敛于MPCC的M-稳定点。并且证明如果增强假设条件，松弛问题的稳定点列收敛于MPCC的强稳定点。

Abstract: This paper discusses mathematical programs with complementarity constraints (MPCC for short). MPCC plays an important role in many fields, such as finance and economics, transportation planning, and network design. Due to the unique structure of MPCC, MPCC does not satisfy most of the constraint qualifications at feasible points. Therefore, MPCC is rather difficult to handle both in theoretical analysis and algorithm design. This paper is based on the relaxed problem constructed by Mangasarian complementary functions, and proves that under the MPCC-rCPLD constraint qualifications, the sequence of stationary points of the relaxed problem converges to M-stationary point of MPCC. Moreover, it is proved that the sequence of stationary points of the relaxed problem converges to the strongly stationary points of the MPCC if some additional conditions hold.

1. 引言

本文讨论一类特殊的约束优化问题，即互补约束优化问题(简记为MPCC)：

$\begin{array}{l}\min f\left(z\right)\\ \text{s}\text{.t}.g_i\left(z\right)\le 0,i\in I,\\ h_i\left(z\right)=0,i\in I_e,\\ G_i\left(z\right)\ge 0,H_i\left(z\right)\ge 0,G_i\left(z\right)H_i\left(z\right)\le 0,i\in I_c.\end{array}$

其中$f,g_i,h_{i,}{G}_i,H_i:{ℝ}^n\to ℝ$ 均为连续可微函数。MPCC问题在金融经济，交通规划，网络设计等许多领域都有着广泛的应用，因此研究MPCC问题具有重要的理论价值和实际意义。

由于MPCC存在互补约束，MPCC在其可行点处均不满足Mangasarian-Fromovite约束规范(简称MFCQ)，这导致了很多非线性规划问题的算法无法直接应用于求解MPCC。

近年来，许多学者致力于MPCC的研究，提出了MPCC的稳定点[1]，包括弱稳定点，C-稳定点，M-稳定点和强稳定点等。为了确保局部极小点是稳定点，我们需要约束规范。如MPCC-LICQ，MPCC-MFCQ，MPCC-CPLD，MPCC-rCPLD和AM-正则性等。其中MPCC约束规范之间的强弱关系如下图1所示：

Figure 1. The strength of the relationship between the various constraint qualifications for MPCC

图1. MPCC的各约束规范强弱关系

为了求解MPCC，文献中有几种不同的方法。例如松弛方法[2]，罚函数法[3]，分支定界法[4]，内点算法[5]，光滑化算法[5]等。松弛方法的主要思想是通过引进参数，得到MPCC的松弛问题。通过应用非线性规划问题的算法来求解松弛问题，得到原MPCC问题的解。Scholtes在2001年提出了一个松弛方法[2]，并证明了在MPCC-LICQ假设条件下，松弛问题稳定点列收敛到MPCC的C-稳定点。2005年，Lin和Fukushima提出新的松弛方法并同样证明在MPCC-LICQ假设条件下，松弛问题的稳定点列收敛到MPCC的C-稳定点[6]。Kadrani，Dussault等学者在2009年提出了一个新的松弛方法[7]，在MPCC-LICQ假设条件下，松弛问题的稳定点列收敛到MPCC的M-稳定点。2010年，Steffensen等学者提出的松弛方法证明在较弱的MPCC-CRCQ的条件下收敛到MPCC的C-稳定点[8]。Kanzow等学者引进互补函数提出新的松弛问题，证明在MPCC-CPLD条件下松弛问题的稳定点列收敛到MPCC的M-稳定点[9]。2014年，黄小津通过Mangasarian互补函数[10]对MPCC的互补约束进行处理，提出了一个新的松弛问题[11]，并进行收敛性分析。在MPCC-CPLD等条件下证明松弛问题的稳定点列收敛到MPCC的M-稳定点。进一步地，如果增强假设条件，则收敛到MPCC的强稳定点。

基于Mangasarian互补函数[10]，本文研究MPCC的松弛问题[11]。如图1所示，在比MPCC-CPLD更弱的MPCC-rCPLD约束规范条件下，证明了松弛问题的稳定点列收敛到MPCC问题的M-稳定点。并证明如果增强假设条件，松弛问题的稳定点列收敛到MPCC问题的强稳定点。

2. 基础知识

本节介绍需要用到的一些基本概念和指标集。

非线性规划问题(简记为NLP)可表示为：

$\begin{array}{l}\min f\left(z\right)\\ \text{s}\text{.t}.g_i\left(z\right)\le 0,i\in I,\\ h_i\left(z\right)=0,i\in I_e.\end{array}$

其中$f,g_i,h_i:{ℝ}^n\to ℝ$ 是连续可微的，$f,g_i\left(i\in I\right),h_i\left(z\right)\left(i\in I_e\right)$ 中至少有一个是非线性函数。

NLP的Lagrange函数定义为$L\left(z,\alpha ,\beta \right)=f\left(z\right)+{\displaystyle \sum _{i\in I}{\alpha }_i{g}_i\left(z\right)+{\displaystyle \sum _{i\in I_e}{\beta }_i{h}_i\left(z\right)}}$ 。

其中$\alpha =\left({\alpha }_i\right)\in {ℝ}^m,\beta =\left({\beta }_i\right)\in {ℝ}^{m_e}$ 。

定理2.1 (一阶最优性条件) [12] 设$z^{\ast }$ 是NLP问题的一个局部极小解，且在$z^{\ast }$ 处满足某个约束规范，则存在向量${\alpha }^{\ast }\in {ℝ}^m,{\beta }^{\ast }\in {ℝ}^{m_e}$ ，使得

$\begin{array}{l}{\nabla }_{z}L\left(z^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)=0,\\ h_i\left(z^{\ast }\right)=0\left(i\in I_e\right),g_i\left(z^{\ast }\right)\le 0\left(i\in I\right),\\ {\alpha }_i^{\ast }\ge 0,{\alpha }_i^{\ast }{g}_i\left(z^{\ast }\right)=0\left(i\in I\right).\end{array}$

此时称$z^{\ast }$ 是NLP的KKT点，上述条件成为KKT条件。${\alpha }^{\ast },{\beta }^{\ast }$ 称为Lagrange乘子，$\left(z^{\ast },{\alpha }^{\ast },{\beta }^{\ast }\right)$ 称为KKT点对。

引进如下指标集：

$\begin{array}{l}{I}_{0+}\left(z^{\ast }\right)=\left\{i\in I_c|G_i\left(z^{\ast }\right)=0,H_i\left(z^{\ast }\right)>0\right\},\\ I_{00}\left(z^{\ast }\right)=\left\{i\in I_c|G_i\left(z^{\ast }\right)=0,H_i\left(z^{\ast }\right)=0\right\},\\ I_{+0}\left(z^{\ast }\right)=\left\{i\in I_c|G_i\left(z^{\ast }\right)>0,H_i\left(z^{\ast }\right)=0\right\}.\end{array}$

其中$z^{\ast }$ 为MPCC的可行点。

定义2.1 [1] 设$z^{\ast }$ 为MPCC可行点，如果存在$\alpha \in {ℝ}^m,\beta \in {ℝ}^{m_e},\gamma ,\delta \in {ℝ}^{m_c}$ ，使得如下条件成立

$0=\nabla f\left(z^{\ast }\right)+{\displaystyle \sum _{i\in I}{\alpha }_i\nabla g_i\left(z^{\ast }\right)}+{\displaystyle \sum _{i\in I_e}{\beta }_i\nabla h_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\gamma }_i\nabla G_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\delta }_i\nabla H_i\left(z^{\ast }\right)}$

${\alpha }_i\ge 0,{\alpha }_i{g}_i\left(z^{\ast }\right)=0\left(i\in I\right),{\gamma }_i=0\left(i\in I_{+0}\left(z^{\ast }\right)\right),{\delta }_i=0\left(i\in I_{0+}\left(z^{\ast }\right)\right),$

则称$z^{\ast }$ 为MPCC的一个弱稳定点。

(a) 若弱稳定点$z^{\ast }$ 满足${\gamma }_i{\delta }_i\ge 0,\forall i\in I_{00}\left(z^{\ast }\right)$ ，则称$z^{\ast }$ 为MPCC的一个C-稳定点。

(b) 若弱稳定点$z^{\ast }$ 满足${\gamma }_i>0,{\delta }_i>0$ 或${\gamma }_i{\delta }_i=0,\forall i\in I_{00}\left(z^{\ast }\right)$ ，则称$z^{\ast }$ 为MPCC的一个M-稳定点。

(c) 若弱稳定点$z^{\ast }$ 满足${\gamma }_i,{\delta }_i\ge 0,\forall i\in I_{00}\left(z^{\ast }\right)$ ，则称$z^{\ast }$ 为MPCC的一个强稳定点。

由以上稳定点的定义可知稳定点有如下关系：

$强稳定点\Rightarrow \text{M-}稳定点\Rightarrow \text{C-}稳定点\Rightarrow 弱稳定点$

并且强稳定点是MPCC的KKT点。

定义2.2 [9] 设$z^{\ast }$ 为MPCC的可行点，MPCC的可行点$z^{\ast }$ 满足MPCC-CPLD当且仅当对于所有的$I_1\subseteq I_g\left(z^{\ast }\right)$ ，$I_2\subseteq I_e$ ，$I_3\subseteq I_{00}\left(z^{\ast }\right)\cup I_{0+}\left(z^{\ast }\right),I_4\subseteq I_{00}\left(z^{\ast }\right)\cup I_{+0}\left(z^{\ast }\right)$ ，如果梯度向量组$\left\{\nabla g_i\left(z^{\ast }\right)|i\in I_1\right\}\cup \left\{\nabla h_i\left(z^{\ast }\right)|i\in I_2\right\}\cup \left\{\nabla G_i\left(z^{\ast }\right)|i\in I_3\right\}\cup \left\{\nabla H_i\left(z^{\ast }\right)|i\in I_4\right\}$ 线性相关，则存在$z^{\ast }$ 的一个邻域$U\left(z^{\ast }\right)$ ，使得对$\forall z\in U\left(z^{\ast }\right)$ ，梯度向量组$\left\{\nabla g_i\left(z\right)|i\in I_1\right\}\cup \left\{\nabla h_i\left(z\right)|i\in I_2\right\}\cup \left\{\nabla G_i\left(z\right)|i\in I_3\right\}\cup \left\{\nabla H_i\left(z\right)|i\in I_4\right\}$ 线性相关。

定义2.3 [13] 设$z^{\ast }$ 为MPCC的可行点，令$I^{\prime }\subseteq I_e$ ，使得$\left\{\nabla h_i\left(z^{\ast }\right)|i\in I^{\prime }\right\}$ 是生成空间$\left\{\nabla h_i\left(z^{\ast }\right)|i\in I_e=1,\cdots ,q\right\}$ 的一组基。MPCC的可行点$z^{\ast }$ 满足MPCC-rCPLD当且仅当存在$z^{\ast }$ 的一个邻域$U\left(z^{\ast }\right)$ ，使得对于$\forall z\in U\left(z^{\ast }\right)$ ，$\left\{\nabla h_i\left(z^{\ast }\right)|i\in I_e\right\}$ 有相同的秩，并且对于所有的$I_1\subseteq I_g\left(z^{\ast }\right)$ ，$I_2\subseteq I_{0+}\left(z^{\ast }\right)\cup I_{00}\left(z^{\ast }\right)$ ，$I_3\subseteq I_{+0}\left(z^{\ast }\right)\cup I_{00}\left(z^{\ast }\right)$ ，如果梯度向量组$\left\{\nabla g_i\left(z^{\ast }\right)|i\in I_1\right\}\cup \left\{\nabla h_i\left(z^{\ast }\right)|i\in I^{\prime }\right\}\cup \left\{\nabla G_i\left(z^{\ast }\right)|i\in I_2\right\}\cup \left\{\nabla H_i\left(z^{\ast }\right)|i\in I_3\right\}$ 线性相关，则存在$z^{\ast }$ 的一个邻域$U\left(z^{\ast }\right)$ ，使得对$\forall z\in U\left(z^{\ast }\right)$ ，梯度向量组$\left\{\nabla g_i\left(z\right)|i\in I_1\right\}\cup \left\{\nabla h_i\left(z\right)|i\in I^{\prime }\right\}\cup \left\{\nabla G_i\left(z\right)|i\in I_2\right\}\cup \left\{\nabla H_i\left(z\right)|i\in I_3\right\}$ 线性相关。

以上提到的MPCC的各种约束规范之间的关系如下：

$\text{MPCC-CPLD}\Rightarrow \text{MPCC-rCPLD}$

定义2.4 [14] 对任何给定的向量$c={\left(c_1,\cdots ,c_n\right)}^{\text{T}}\in {ℝ}^n$ ，定义指标集

$supp\left(c\right)=\left\{i|c_i\ne 0,i=1,\cdots ,n\right\},$

则称$supp\left(c\right)$ 为向量$c$ 的支撑。

3. 松弛问题的收敛性分析

Mangasarian互补函数[10]对MPCC的互补约束松弛得到新的松弛问题[11]，本节基于新的松弛问题进行收敛性分析。在MPCC-rCPLD约束规范条件下，证明松弛问题稳定点列收敛到MPCC的M-稳定点。如果增强假设条件，则进一步收敛到MPCC强稳定点。

定义3.1 基于互补函数$\varphi$ [10]的性质，MPCC的松弛约束$G_i\left(z\right)\ge 0,H_i\left(z\right)\ge 0,G_i\left(z\right)H_i\left(z\right)=0$ 可松弛为$G_i\left(z\right)\ge -t,H_i\left(z\right)\ge -t,{\Phi }_i\left(z;t\right)\le 0$ ，从而得到MPCC的如下形式的松弛问题，记为NLP(t)：

$\begin{array}{l}\min f\left(z\right)\\ \text{s}\text{.t}\text{. }{g}_i\left(z\right)\le 0,i\in I,\\ h_i\left(z\right)=0,i\in I_e,\\ G_i\left(z\right)\ge -t,H_i\left(z\right)\ge -t,{\Phi }_i\left(z;t\right)\le 0,i\in I_c.\end{array}$

其中参数$t\ge 0$ 。

$\begin{array}{l}{\Phi }_i\left(z;t\right)=\varphi \left(G_i\left(z\right)-t,H_i\left(z\right)-t\right)\\ =\{\begin{array}{c}-2{\left(G_i\left(z\right)-t\right)}^2-2{\left(H_i\left(z\right)-t\right)}^2+2\left(G_i\left(z\right)-t\right)\left(H_i\left(z\right)-t\right),G_i\left(z\right)-t<0,H_i\left(z\right)-t<0,\\ -2{\left(G_i\left(z\right)-t\right)}^2+2\left(G_i\left(z\right)-t\right)\left(H_i\left(z\right)-t\right),G_i\left(z\right)-t<0,H_i\left(z\right)-t\ge 0,\\ -2{\left(H_i\left(z\right)-t\right)}^2+2\left(G_i\left(z\right)-t\right)\left(H_i\left(z\right)-t\right),G_i\left(z\right)-t\ge 0,H_i\left(z\right)-t<0,\\ 2\left(G_i\left(z\right)-t\right)\left(H_i\left(z\right)-t\right),G_i\left(z\right)-t\ge 0,H_i\left(z\right)-t\ge 0,\end{array}\end{array}$

其中t为任意非负参数。

$\begin{array}{l}\nabla {\Phi }_i\left(z;t\right)\\ =\{\begin{array}{c}2\left(H_i\left(z\right)-4G_i\left(z\right)+2t\right)\nabla G_i\left(z\right)+\left(2G_i\left(z\right)-4H_i\left(z\right)+2t\right)\nabla H_i\left(z\right),G_i\left(z\right)-t<0,H_i\left(z\right)-t<0\\ 2\left(H_i\left(z\right)-4G_i\left(z\right)+2t\right)\nabla G_i\left(z\right)+2\left(G_i\left(z\right)-t\right)\nabla H_i\left(z\right),G_i\left(z\right)-t<0,H_i\left(z\right)-t\ge 0\\ 2\left(H_i\left(z\right)-t\right)\nabla G_i\left(z\right)+2\left(G_i\left(z\right)-4H_i\left(z\right)+2t\right)\nabla H_i\left(z\right),G_i\left(z\right)-t\ge 0,H_i\left(z\right)-t<0\\ 2\left(H_i\left(z\right)-t\right)\nabla G_i\left(z\right)+2\left(G_i\left(z\right)-t\right)\nabla H_i\left(z\right),G_i\left(z\right)-t\ge 0,H_i\left(z\right)-t\ge 0\end{array}\end{array}$ (1)

当$i\in I_{\Phi }^{00}\left(z;t\right)$ 时$\nabla {\Phi }_i\left(z;t\right)=0$ 。

设$z$ 为松弛问题NLP(t)的可行点，定义如下积极集：

$\begin{array}{l}{I}_g\left(z\right)=\left\{i\in I|g_i\left(z\right)=0\right\},I_G\left(z;t\right)=\left\{i\in I_c|G_i\left(z\right)=-t\right\},\\ I_H\left(z;t\right)=\left\{i\in I_c|H_i\left(z\right)=-t\right\},I_{\Phi }\left(z;t\right)=\left\{i\in I_c|{\Phi }_i\left(z;t\right)=0\right\}\end{array}$

${\Phi }_i\left(z;t\right)=0\iff G_i\left(z\right)-t\ge 0,H_i\left(z\right)-t\ge 0,\left(G_i\left(z\right)-t\right)\left(H_i\left(z\right)-t\right)=0$

定义$I_{\Phi }\left(z;t\right)$ 的一个剖分：

$\begin{array}{l}{I}_{\Phi }^{0+}\left(z;t\right)=\left\{i\in I_{\Phi }\left(z;t\right)|G_i\left(z\right)-t=0,H_i\left(z\right)-t>0\right\},\\ I_{\Phi }^{00}\left(z;t\right)=\left\{i\in I_{\Phi }\left(z;t\right)|G_i\left(z\right)-t=0,H_i\left(z\right)-t=0\right\},\\ I_{\Phi }^{+0}\left(z;t\right)=\left\{i\in I_{\Phi }\left(z;t\right)|G_i\left(z\right)-t>0,H_i\left(z\right)-t=0\right\}.\end{array}$

显然$I_{\Phi }^{0+}\left(z;t\right)\cap I_{\Phi }^{00}\left(z;t\right)\cap I_{\Phi }^{+0}\left(z;t\right)=\varnothing ,I_{\Phi }^{0+}\left(z;t\right)\cup I_{\Phi }^{00}\left(z;t\right)\cup I_{\Phi }^{+0}\left(z;t\right)=I_{\Phi }\left(z;t\right)$ 。

定理3.1 令$\left\{t_k\right\}$ 为单调下降收敛到0的正数序列，$\left\{\left(z^k,{\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^k\right)\right\}$ 为NLP$\left(t_k\right)$ 的KKT点对，且$z^k\to z^{\ast }$ 。假设MPCC-rCPLD在$z^{\ast }$ 处成立，则$z^{\ast }$ 为MPCC的一个M-稳定点。

证明：因为$z^k$ 为NLP$\left(t_k\right)$ 的KKT点，所以

$g_i\left(z^k\right)\le 0,i\in I,h_i\left(z^k\right)=0,i\in I_e,$

$G_i\left(z^k\right)\ge -t_k,H_i\left(z^k\right)\ge -t_k,{\Phi }_i\left(z^k;t_k\right)\le 0,i\in I_c$

由$g_i,h_i,G_i,H_i,{\Phi }_i$ 的连续性及 $z^k\to z^{\ast },t_k\to 0$ 知道当$k$ 充分大时，$z^{\ast }$ 为MPCC的可行点，即

$g_i\left(z^{\ast }\right)\le 0,i\in I,h_i\left(z^{\ast }\right)=0,i\in I_e,$

$G_i\left(z^{\ast }\right)\ge 0,H_i\left(z^{\ast }\right)\ge 0,{\Phi }_i\left(z^{\ast };0\right)\le 0,i\in I_c$

且下面指标集的包含关系成立：

$I_g\left(z^k\right)\subseteq I_g\left(z^{\ast }\right),$

$I_G\left(z^k;t_k\right)\cup I_{\Phi }^{00}\left(z^k;t_k\right)\cup I_{\Phi }^{0+}\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right)\cup I_{0+}\left(z^{\ast }\right),$ (2)

$I_H\left(z^k;t_k\right)\cup I_{\Phi }^{00}\left(z^k;t_k\right)\cup I_{\Phi }^{+0}\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right)\cup I_{+0}\left(z^{\ast }\right).$

因$\left(z^k,{\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^k\right)$ 为NLP$\left(t_k\right)$ 的KKT点对，则有

$\begin{array}{c}0=\nabla f\left(z^k\right)+{\displaystyle \sum _{i\in I}{\alpha }_i^k\nabla g_i\left(z^k\right)}+{\displaystyle \sum _{i\in I_e}{\beta }_i^k\nabla h_i\left(z^k\right)}-{\displaystyle \sum _{i\in I_c}{\gamma }_i^k\nabla G_i\left(z^k\right)}\\ -{\displaystyle \sum _{i\in I_c}{\delta }_i^k\nabla H_i\left(z^k\right)}+{\displaystyle \sum _{i\in I_c}{\nu }_i^k\nabla {\Phi }_i\left(z^k;t_k\right)}\end{array}$ (3)

${\alpha }_i^k\{\begin{array}{c}\ge 0,i\in I_g\left(z^k\right),\\ =0,i\notin I_g\left(z^k\right);\end{array}{\gamma }_i^k\{\begin{array}{c}\ge 0,i\in I_G\left(z^k;t_k\right),\\ =0,i\notin I_G\left(z^k;t_k\right);\end{array}$ (4)

${\delta }_i^k\{\begin{array}{c}\ge 0,i\in I_H\left(z^k;t_k\right),\\ =0,i\notin I_H\left(z^k;t_k\right);\end{array}{\nu }_i^k\{\begin{array}{c}\ge 0,i\in I_{\Phi }\left(z^k;t_k\right),\\ =0,i\notin I_{\Phi }\left(z^k;t_k\right);\end{array}$

由(1)知

$\nabla {\Phi }_i\left(z^k;t_k\right)=\{\begin{array}{c}2\left(H_i\left(z^k\right)-t_k\right)\nabla G_i\left(z^k\right),i\in I_{\Phi }^{0+}\left(z^k;t_k\right),\\ 2\left(G_i\left(z^k\right)-t_k\right)\nabla H_i\left(z^k\right),i\in I_{\Phi }^{+0}\left(z^k;t_k\right),\\ \text{0, }i\in I_{\Phi }^{00}\left(z^k;t_k\right).\end{array}$

定义

${\nu }_i^{G,k}=\{\begin{array}{c}2{\nu }_i^k\left(H_i\left(z^k\right)-t_k\right),i\in I_{\Phi }^{0+}\left(z^k;t_k\right)\\ 0,其它.\end{array}{\nu }_i^{H,k}=\{\begin{array}{c}2{\nu }_i^k\left(G_i\left(z^k\right)-t_k\right)\text{, }i\in I_{\Phi }^{+0}\left(z^k;t_k\right)\\ 0,其它.\end{array}$

注意到$I_{\Phi }\left(z^k;t_k\right)=I_{\Phi }^{0+}\left(z^k;t_k\right)\cup I_{\Phi }^{00}\left(z^k;t_k\right)\cup I_{\Phi }^{+0}\left(z^k;t_k\right)$ ，于是(2)可以改写成如下形式：

$\begin{array}{l}0=\nabla f\left(z^k\right)+{\displaystyle \sum _{i\in I}{\alpha }_i^k\nabla g_i\left(z^k\right)}+{\displaystyle \sum _{i\in I_e}{\beta }_i^k\nabla h_i\left(z^k\right)}-{\displaystyle \sum _{i\in I_c}{\gamma }_i^k\nabla G_i\left(z^k\right)}\\ -{\displaystyle \sum _{i\in I_c}{\delta }_i^k\nabla H_i\left(z^k\right)}+{\displaystyle \sum _{i\in I_c}{\nu }_i^{G,k}\nabla G_i\left(z^k\right)+}{\displaystyle \sum _{i\in I_c}{\nu }_i^{H,k}\nabla H_i\left(z^k\right)}\end{array}$ (5)

注意到(5)中的乘子都是非负的，根据([8]，引理A.1)，不妨假设(5)中非零乘子对应的梯度向量组线性无关。已知MPCC-rCPLD在$z^{\ast }$ 处成立，存在$z^{\ast }$ 的一个邻域$U\left(z^{\ast }\right)$ ，对于$\forall z\in U\left(z^{\ast }\right)$ ，$\left\{\nabla h_i\left(z\right)|i\in I_e\right\}$ 有相同的秩，且$\left\{\nabla h_i\left(z^{\ast }\right)|i\in I^{\prime }\right\}$ 是生成空间$\left\{\nabla h_i\left(z^{\ast }\right)|i\in I_e\right\}$ 的一组基。当$k$ 充分大时，$z^k\in U\left(z^{\ast }\right)$ ，$rank\left\{\nabla h_i\left(z^k\right)|i\in I_e\right\}=rank\left\{\nabla h_i\left(z^k\right)|i\in I^{\prime }\right\}$ ，由假设知非零乘子对应的梯度向量组无关，所以当$i\in I_e\backslash I^{\text{'}}$ 时，${\beta }_i^k=0$ 。因此${\displaystyle \sum _{i\in I_e}{\beta }_i^k\nabla h_i\left(z^k\right)=}{\displaystyle \sum _{i\in I^{\text{'}}}{\beta }_i^k\nabla h_i\left(z^k\right)}$ ，满足$\left\{{\beta }_i^k>0|i\in I^{\prime }\right\}$ 且$\left\{\nabla h_i\left(z^k\right)|i\in I^{\prime }\right\}$ 线性无关，(5)可表示为

$\begin{array}{l}0=\nabla f\left(z^k\right)+{\displaystyle \sum _{i\in I}{\alpha }_i^k\nabla g_i\left(z^k\right)}+{\displaystyle \sum _{i\in I^{\text{'}}}{\beta }_i^k\nabla h_i\left(z^k\right)}-{\displaystyle \sum _{i\in I_c}{\gamma }_i^k\nabla G_i\left(z^k\right)}\\ -{\displaystyle \sum _{i\in I_c}{\delta }_i^k\nabla H_i\left(z^k\right)}+{\displaystyle \sum _{i\in I_c}{\nu }_i^{G,k}\nabla G_i\left(z^k\right)+}{\displaystyle \sum _{i\in I_c}{\nu }_i^{H,k}\nabla H_i\left(z^k\right)}\end{array}$ (6)

下面证明乘子序列$\left\{\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\right\}$ 有界。

(反证)假设$\left\{\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\right\}$ 无界，则存在一个无穷子列$K$ ，使得

$\frac{\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)}{\Vert \left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\Vert }\stackrel{K}{\to }\left(\alpha ,\beta ,\gamma ,\delta ,{\nu }^G,{\nu }^H\right)\ne 0$

对(6)两边同除以$\Vert \left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\Vert$ ，并取极限，

$\begin{array}{l}0={\displaystyle \sum _{i\in I}{\alpha }_i\nabla g_i\left(z^{\ast }\right)}+{\displaystyle \sum _{i\in I^{\text{'}}}{\beta }_i\nabla h_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\gamma }_i\nabla G_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\delta }_i\nabla H_i\left(z^{\ast }\right)}\\ +{\displaystyle \sum _{i\in I_c}{\nu }_i^G\nabla G_i\left(z^{\ast }\right)+}{\displaystyle \sum _{i\in I_c}{\nu }_i^H\nabla H_i\left(z^{\ast }\right)},\end{array}$

由此可知以下梯度向量组

$\begin{array}{l}\left\{\nabla g_i\left(z^{\ast }\right)|i\in supp\left(\alpha \right)\right\}\cup \left\{\nabla h_i\left(z^{\ast }\right)|i\in I^{\prime }\right\}\cup \left\{\nabla G_i\left(z^{\ast }\right)|i\in supp\left(\gamma \right)\cup supp\left({\nu }^G\right)\right\}\\ \cup \left\{\nabla H_i\left(z^{\ast }\right)|i\in supp\left(\delta \right)\cup supp\left({\nu }^H\right)\right\}\end{array}$ (7)

是正线性相关的。

因MPCC-rCPLD在$z^{\ast }$ 处成立，所以存在$z^{\ast }$ 的一个邻域$U\left(z^{\ast }\right)$ ，$\forall z\in U\left(z^{\ast }\right)$ ，梯度向量组

$\begin{array}{l}\left\{\nabla g_i\left(z\right)|i\in supp\left(\alpha \right)\right\}\cup \left\{\nabla h_i\left(z\right)|i\in I^{\prime }\right\}\cup \left\{\nabla G_i\left(z\right)|i\in supp\left(\gamma \right)\cup supp\left({\nu }^G\right)\right\}\\ \cup \left\{\nabla H_i\left(z\right)|i\in supp\left(\delta \right)\cup supp\left({\nu }^H\right)\right\}\end{array}$

线性相关。注意到当$k$ 充分大时有$supp\left(\alpha ,\beta ,\gamma ,\delta ,{\nu }^G,{\nu }^H\right)\subseteq supp\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)$ ，于是上述结论与之在$z^k$ 处的梯度向量组：

$\begin{array}{l}\left\{\nabla g_i\left(z^k\right)|i\in supp\left({\alpha }^k\right)\right\}\cup \left\{\nabla h_i\left(z^k\right)|i\in I^{\prime }\right\}\cup \left\{\nabla G_i\left(z^k\right)|i\in supp\left({\gamma }^k\right)\cup supp\left({\nu }^{G,k}\right)\right\}\\ \cup \left\{\nabla H_i\left(z^k\right)|i\in supp\left({\delta }^k\right)\cup supp\left({\nu }^{H,k}\right)\right\}\end{array}$

线性无关，矛盾。因此乘子序列$\left\{\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\right\}$ 有界。

不失一般性，假设乘子序列$\left\{\left({\alpha }^k,{\beta }^k,{\gamma }^k,{\delta }^k,{\nu }^{G,k},{\nu }^{H,k}\right)\right\}$ 收敛到$\left({\alpha }^{\ast },{\beta }^{\ast },{\gamma }^{\ast },{\delta }^{\ast },{\nu }^{G,\ast },{\nu }^{H,\ast }\right)$ 。由于$I_G\left(z^k;t_k\right)\cap I_{\Phi }^{0+}\left(z^k;t_k\right)=\varnothing ,I_H\left(z^k;t_k\right)\cap I_{\Phi }^{+0}\left(z^k;t_k\right)=\varnothing$ 因此定义

${\tilde{\gamma }}_i=\{\begin{array}{l}{\gamma }_i^{\ast }，i\in supp\left({\gamma }^{\ast }\right)\hfill \\ -{\nu }_i^{G,\ast },i\in supp\left({\nu }^{G,\ast }\right)\hfill \\ 0,其它.\hfill \end{array}{\tilde{\delta }}_i=\{\begin{array}{l}{\delta }_i^{\ast },i\in supp\left({\delta }^{\ast }\right)\hfill \\ -{\nu }_i^{H,\ast },i\in supp\left({\nu }^{H,\ast }\right)\hfill \\ \text{0}，其它.\hfill \end{array}$ (8)

于是在(6)取极限，即有

$0=\nabla f\left(z^{\ast }\right)+{\displaystyle \sum _{i\in I}{\alpha }_{{}_i}^{\ast }\nabla g_i\left(z^{\ast }\right)}+{\displaystyle \sum _{i\in I^{\text{'}}}{\beta }_i^{\ast }\nabla h_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\tilde{\gamma }}_i\nabla G_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in I_c}{\tilde{\delta }}_i\nabla H_i\left(z^{\ast }\right)}$ (9)

其中${\alpha }^{\ast }\ge 0$ ，且对足够大的$k$ ，有

$supp\left({\alpha }^{\ast }\right)\subseteq I_g\left(z^k;t_k\right)\subseteq I_g\left(z^{\ast }\right)$ ,

$supp\left(\tilde{\gamma }\right)=supp\left({\gamma }^{\ast }\right)\cup supp\left({\nu }^{G,\ast }\right)\subseteq I_G\left(z^k;t_k\right)\cup I_{\Phi }^{0+}\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right)\cup I_{0+}\left(z^{\ast }\right),$ (10)

$supp\left(\tilde{\delta }\right)=supp\left({\delta }^{\ast }\right)\cup supp\left({\nu }^{H,\ast }\right)\subseteq I_H\left(z^k;t_k\right)\cup I_{\Phi }^{+0}\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right)\cup I_{+0}\left(z^{\ast }\right).$

由(10)知，${\tilde{\gamma }}_i=0,i\in I_{+0}\left(z^{\ast }\right);{\tilde{\delta }}_i=0,i\in I_{0+}\left(z^{\ast }\right)$，即$z^{\ast }$ 是MPCC的一个弱稳定点。

接下来证明$z^{\ast }$ 是M-稳定点。

(反证)假设存在一个$i\in I_{00}\left(z^{\ast }\right)$ ，使得${\tilde{\gamma }}_i<0$ 且${\tilde{\delta }}_i\ne 0$ 。据(8)和(10)可知当$k$ 充分大时，$i\in supp\left({\nu }^{G,\ast }\right)\subseteq I_{\Phi }^{0+}\left(z^k;t_k\right).$ 又$I_{\Phi }^{0+}\left(z^k;t_k\right)\cap \left(I_H\left(z^k;t_k\right)\cup I_{\Phi }^{+0}\left(z^k;t_k\right)\right)=\varnothing$ ，因此由(8)知${\tilde{\delta }}_i=0$ ，这与${\tilde{\delta }}_i\ne 0$ 矛盾。(对于${\tilde{\gamma }}_i\ne 0$ 且${\tilde{\delta }}_i<0$ 的情形，可类似证明)因此$z^{\ast }$ 为MPCC的M-稳定点。

定理3.2若$\left\{z_k\right\}$ 满足$I_{\Phi }^{0+}\left(z_k;t_k\right)=I_{\Phi }^{+0}\left(z_k;t_k\right)=\varnothing$ ，则$z^{\ast }$ 为MPCC的强稳定点。

证明：由(10)知(9)可改写为

$\begin{array}{l}0=\nabla f\left(z^{\ast }\right)+{\displaystyle \sum _{i\in supp\left({\alpha }^{\ast }\right)}{\alpha }_i^{\ast }\nabla g_i\left(z^{\ast }\right)}+{\displaystyle \sum _{i\in I^{\text{'}}}{\beta }_i^{\ast }\nabla h_i\left(z^{\ast }\right)}\\ -{\displaystyle \sum _{i\in supp\left(\tilde{\gamma }\right)}{\tilde{\gamma }}_i\nabla G_i\left(z^{\ast }\right)}-{\displaystyle \sum _{i\in supp\left(\tilde{\delta }\right)}{\tilde{\delta }}_i\nabla H_i\left(z^{\ast }\right)}\end{array}$

已知$I_{\Phi }^{0+}\left(z_k;t_k\right)=I_{\Phi }^{+0}\left(z_k;t_k\right)=\varnothing$ ，由(10)可以得出

$supp\left(\tilde{\gamma }\right)=supp\left({\gamma }^{\ast }\right)\subseteq I_G\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right),$

$supp\left(\tilde{\delta }\right)=supp\left({\delta }^{\ast }\right)\subseteq I_H\left(z^k;t_k\right)\subseteq I_{00}\left(z^{\ast }\right).$

由(4) (8)得到${\tilde{\gamma }}_i={\gamma }_i^{\ast }\ge 0,{\tilde{\delta }}_i={\delta }_i^{\ast }\ge 0,i\in I_{00}\left(z^{\ast }\right)$，所以$z^{\ast }$ 满足条件${\gamma }_i,{\delta }_i\ge 0,\forall I_{00}\left(z^{\ast }\right),$ 则称$z^{\ast }$ 为MPCC的一个强稳定点。

4. 总结

本文主要研究MPCC松弛问题的收敛性分析。Mangasarian互补函数对MPCC互补约束进行松弛，得到松弛问题。在较弱的MPCC-rCPLD约束规范条件下证明了松弛问题的KKT点列收敛到MPCC的M-稳定点。并进一步证明如果增强假设条件，松弛问题的稳定点列收敛到MPCC的强稳定点。

NOTES

^*通讯作者。