MPCC问题的M稳定性的序列最优性条件研究

The Sequential Optimality Condition for M-Stationarity for MPCC

摘要: 带有互补约束的数学规划(MPCC)问题是一类难于求解的优化问题，其在许多领域都有着重要的应用。针对互补约束的特殊结构，人们提出了多种方法求解MPCC问题。近年来，非线性优化问题的序列最优性条件受到了广泛的关注。基于序列最优性条件，算法的收敛性结果得到了显著改进。但是，非线性优化问题的序列最优性条件不能直接用于研究MPCC问题。因此，本文基于非线性优化问题(NLP)的CAKKT条件，提出了MPCC问题关于M稳定性的序列最优性条件，即MPCC-CAKKT条件。MPCC-CAKKT条件是比现有的MPCC-AKKT条件更强的序列最优性条件。此外，还给出了与之相关的保证M稳定性的较弱的约束规范，即MPCC-CAKKT正则性。

Abstract: Mathematical program with complementarity constraints (MPCC) is a difficult class of optimization problems, which plays an important role in many fields. Due to the special structure of the complementarity constraints, several methods have been suggested in order to deal with the MPCC. Recently, the sequential optimality conditions for nonlinear optimization problems (NLP) have been drawn concerns widely. Convergence analysis of these methods for NLP has been dramatically improved by using the sequential optimality conditions. However, the established sequential optimality conditions for NLP are not suitable for MPCC. In this paper, based on the CAKKT condition for NLP, we present a sequential optimality condition for MPCC, namely MPCC-CAKKT condition, which is stronger than the MPCC-AKKT condition. Furthermore, we present a weaker constraint qualification for M stationarity which is closely related to MPCC-CAKKT.

1. 引言

本文主要研究带有互补约束的数学规划(Mathematical program with complementarity constraints，简称MPCC)问题，其优化模型如下

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)\le 0,\\ h\left(x\right)=0,\\ 0\le H\left(x\right)\perp G\left(x\right)\ge 0.\end{array}$ (1.1)

其中，$f:R^n\to R,g:R^n\to R^p,h:R^n\to R^q,H,G:R^n\to R^m$ 是连续可微的，$0\le u\perp v\ge 0$ 表示$u\ge 0,v\ge 0$ ，$u^{\text{T}}v=0$ 。

MPCC问题在工程设计、机器学习和交通科学等许多领域都有着广泛的应用，因此研究MPCC问题具有重要的理论价值和实际意义。由于互补约束的特殊结构，NLP问题的许多约束规范并不适用于MPCC问题，因此KKT条件在局部最优解处往往不成立。近年来，为了更好的研究MPCC问题，提出了MPCC的几种稳定性概念，如S稳定性，M稳定性，C稳定性和W稳定性。

由于序列最优性条件与算法的停止准则密切相关，并且可以改进算法的收敛性结果。因此，非线性优化问题的序列最优性条件受到了人们的广泛关注，如AKKT条件，AGP条件，DCAKKT条件和WCAKKT条件等。DCAKKT条件是一个比AGP条件更强的序列最优性条件，WCAKKT条件强于AKKT条件，这些序列最优性条件被广泛应用于改进算法的收敛性结果[1] [2]。但是，非线性优化问题的序列最优性条件不能直接用于研究MPCC问题[3]。因此，Andreani [4]等人基于MPCC的W-，C，M-稳定性，提出了MPCC问题的AW-，AC，AM-稳定性，并提出了与之相关的约束规范，讨论了与现有约束规范之间的强弱关系。2021年，Ramos [5]基于NLP问题中的AKKT条件，提出了MPCC-AKKT及其相关的约束规范MPCC-CCP，并讨论了其与MPCC常用的约束规范之间的关系，如MPCC-RCPLD，MPCC-quasinormality和MPCC-pseudonormality等。

本文在MPCC-AKKT条件的基础上，建立了比MPCC-AKKT条件更强的序列最优性条件，即MPCC-CAKKT条件。然后，提出了与之相关的约束规范，即MPCC-CAKKT正则性条件。证明了MPCC问题的局部最优解在MPCC-CAKKT条件下是M稳定点，这说明了MPCC-CAKKT正则性是一个能够保证M稳定性的约束规范。

本文结构如下：第二节介绍了需要的基本知识。第三节提出了MPCC问题新的序列最优性条件，即MPCC-CAKKT条件，并证明MPCC-CAKKT条件是一个合理的序列最优性条件。第四节提出了MPCC问题的一个新的约束规范，即MPCC-CAKKT正则性，并证明了MPCC-CAKKT正则性是能够保证M稳定性的约束规范。第五节给出总结。

2. 基础知识

本节给出文章中需要用到的一些基本概念。

定义2.1 [6] (外极限)设$S:R^n\rightrightarrows R^m$ 是一集值映射，S在$x^{\ast }$ 处的外极限为

$\underset{x\to x^{\ast }}{\lim \sup }S\left(x\right)=\left\{u|\exists x^k\to x^{\ast },\exists u^k\in S\left(x^k\right),u^k\to u\right\}.$

定义2.2 [6] (外半连续)称集值映射$S:R^n\rightrightarrows R^m$ 在点$x^{\ast }$ 点处是外半连续的，如果

$\underset{x\to x^{\ast }}{\lim \sup }S\left(x\right)\subset S\left(x^{\ast }\right).$

定义2.3 [6] (极锥)对于任意一个锥$\mathcal{K}\in R^s$ ，它的极锥为${\mathcal{K}}^{\circ }:=\left\{v\in R^s|\langle v,k\rangle \le 0,�于任意的k\in \mathcal{K}\right\}$ 。

定义2.4 [6] (法锥与正则法锥)设$S\subset X$ ，X为有限维Hilbert空间，$x\in S,v\in X$ 称为S在点x处的正则法向量，如果$\langle v,x^{\prime }-x\rangle \le o\left(\Vert x^{\prime }-x\Vert \right),x^{\prime }\in S$ 。所有正则法向量的集合记为${\widehat{N}}_s\left(x\right)$ 称为正则法锥，即

${\widehat{N}}_s\left(x\right)=\left\{v\in X|\langle v,x^{\prime }-x\rangle \le \circ \left(\Vert x^{\prime }-x\Vert \right),x^{\prime }\in S\right\}.$

向量$v\in X$ 称为S在点x处的法向量，如果存在序列$x^k\to x$ ，存在$v^k\in {\widehat{N}}_s\left(x^k\right)$ 满足$v^k\to v$ ，所有法向量的集合称为法锥，记为$N_s\left(x\right)$ ，即

$N_s\left(x\right)=\left\{v\in X|\exists x^k\to x,v^k\in {\widehat{N}}_s\left(x^k\right)\text{s}\text{.t}.v^k\to v\right\}.$

设

$\mathcal{C}:=\left\{\left(c_1,c_2\right)\in R^2:0\le -c_1\perp -c_2\ge 0\right\}.$

显然，$\left(\left(-H_1\left(x\right),-G_1\left(x\right)\right),\cdots ,\left(-H_m\left(x\right),-G_m\left(x\right)\right)\right)\in {\mathcal{C}}^m$ 等价于互补约束$0\le H\left(x\right)\perp G\left(x\right)\ge 0$ 。

命题2.1 [4] (1) 令$\left(c_1,c_2\right)\in \mathcal{C}$ ，则在$\left(c_1,c_2\right)$ 处的切锥为

$T_C\left(\left(c_1,c_2\right)\right)=\{d=\left(d_1,d_2\right):\begin{array}{l}{d}_1=0,d_2\in R\text{ if}{c}_1=0,c_2<0\\ d_1\in R,d_2=0\text{ if}{c}_1<0,c_2=0\\ \left(d_1,d_2\right)\in C\text{ if}{c}_1=0,c_2=0\end{array}\};$

(2) 令$\left(c_1,c_2\right)\in \mathcal{C}$ ，则在$\left(c_1,c_2\right)$ 处的正则法锥为

${\widehat{N}}_C\left(\left(c_1,c_2\right)\right)=\{d=\left(d_1,d_2\right):\begin{array}{l}{d}_1\in R,d_2=\text{0 }\text{if}{c}_1=0,c_2<0\\ d_1=0,d_2\in R\text{ if}{c}_1<0,c_2=0\\ d_1\ge 0,d_2\ge 0\text{ if}{c}_1=0,c_2=0\end{array}\};$

(3) 令$\left(c_1,c_2\right)\in \mathcal{C}$ ，则在$\left(c_1,c_2\right)$ 处的极限法锥为

$N_C\left(\left(c_1,c_2\right)\right)=\{d=\left(d_1,d_2\right):\begin{array}{l}{d}_1\in R,d_2=\text{0 if}{c}_1=0,c_2<0\\ d_1=0,d_2\in R\text{ if}{c}_1<0,c_2=0\\ \text{either }{d}_1\ge 0,d_2\ge 0\text{ if}{c}_1=0,c_2=0\\ \text{or }{d}_1>0,d_2>0\end{array}\}.$

MPCC问题等价于以下带有几何约束形式的问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }F\left(x\right)\in \Lambda \end{array}$ (2.1)

其中，

$\begin{array}{l}F\left(x\right)=\left(g\left(x\right),h\left(x\right),\Psi \left(x\right)\right),\Lambda :=R_{-}^p\times {\left\{0\right\}}^q\times {\mathcal{C}}^m,\\ \Psi \left(x\right):=\left(\left(-H_1\left(x\right),-G_1\left(x\right)\right),\cdots ,\left(-H_m\left(x\right),-G_m\left(x\right)\right)\right).\end{array}$

定义$\Omega =\left\{x\in R^n|F\left(x\right)\in \Lambda \right\}$ 是MPCC问题(2.1)的可行域。为了简便表述，对于某些$p,q,m\in N$ 考虑集合$\Lambda =R_{-}^p\times {\left\{0\right\}}^q\times {\mathcal{C}}^m$ 。对于集合$\Lambda =R_{-}^p\times {\left\{0\right\}}^q\times {\mathcal{C}}^m$ 中任意一点$z:=\left(a,b,-\left(c_{11},c_{21}\right),\cdots ,-\left(c_{1m},c_{2m}\right)\right)$ ，做如下定义：

$\begin{array}{l}I\left(z,\Lambda \right):=\left\{i\in \left\{1,\cdots ,m\right\}:c_{1i}=0,c_{2i}>0\right\},\\ J\left(z,\Lambda \right):=\left\{i\in \left\{1,\cdots ,m\right\}:c_{1i}=0,c_{2i}=0\right\},\\ K\left(z,\Lambda \right):=\left\{i\in \left\{1,\cdots ,m\right\}:c_{1i}>0,c_{2i}=0\right\}.\end{array}$

由于$\Lambda$ 在文章中并不容易混淆，因此我们用$I\left(z\right),J\left(z\right),K\left(z\right)$ 来代替$I\left(z,\Lambda \right),J\left(z,\Lambda \right),K\left(z,\Lambda \right)$ 。

对于$x^{\ast }\in \Omega$ 定义如下指标集：

$\begin{array}{l}A\left(x^{\ast },\Omega \right):=\left\{j\in \left\{1,\cdots ,p\right\}:g_j\left(x^{\ast }\right)=0\right\},\\ I\left(x^{\ast },\Omega \right):=I\left(F\left(x^{\ast }\right),\Lambda \right)=\left\{i\in \left\{1,\cdots ,m\right\}:H_i\left(x^{\ast }\right)=0,G_i\left(x^{\ast }\right)>0\right\},\\ J\left(x^{\ast },\Omega \right):=J\left(F\left(x^{\ast }\right),\Lambda \right)=\left\{i\in \left\{1,\cdots ,m\right\}:H_i\left(x^{\ast }\right)=0,G_i\left(x^{\ast }\right)=0\right\},\\ K\left(x^{\ast },\Omega \right):=K\left(F\left(x^{\ast }\right),\Lambda \right)=\left\{i\in \left\{1,\cdots ,m\right\}:H_i\left(x^{\ast }\right)>0,G_i\left(x^{\ast }\right)=0\right\}.\end{array}$

由于$\Omega$ 在上下文中有明确的定义，故我们用$A\left(x^{\ast }\right),I\left(x^{\ast }\right),J\left(x^{\ast }\right),K\left(x^{\ast }\right)$ 来代替$A\left(x^{\ast },\Omega \right),I\left(x^{\ast },\Omega \right),J\left(x^{\ast },\Omega \right),K\left(x^{\ast },\Omega \right)$ 。

定义2.5 [5] (M稳定点)称可行点$x^{\ast }$ 是MPCC问题的M稳定点，若存在$\lambda$ ，其中，$\lambda =\left({\lambda }^g,{\lambda }^h,{\lambda }^G,{\lambda }^H\right)\in R_{+}^p\times R^{q+2m}$ ，使得$x^{\ast }$ 满足

$\begin{array}{l}{\nabla }_{x}L\left(x,\lambda \right)=0,\\ {\lambda }_{\left\{1,\cdots ,p\right\}\backslash A\left(x^{\ast }\right)}^g=0,{\lambda }_{I\left(x^{\ast }\right)}^G=0,{\lambda }_{K\left(x^{\ast }\right)}^H=0,\\ {\lambda }_i^G{\lambda }_i^H=0\text{or}{\lambda }_i^G>0,{\lambda }_i^H>0,\forall i\in J\left(x^{\ast }\right).\end{array}$

命题2.2 [5]令$x^{\ast }$ 是MPEC问题的可行点，则有$x^{\ast }$ 为M稳定点当且仅当

$0\in \nabla f\left(x^{\ast }\right)+\nabla F{\left(x^{\ast }\right)}^{\text{T}}{N}_{\Lambda }\left(F\left(x^{\ast }\right)\right).$

引理2.1 [5]令$\Lambda :=R_{-}^p\times {\left\{0\right\}}^q\times {\mathcal{C}}^m$ ，任意一点$z:=\left(a,b,\left(c_1^1,c_2^1\right),\cdots ,\left(c_1^m,c_2^m\right)\right)\in \Lambda$ 。那么有

$N_{\Lambda }\left(z\right)={\displaystyle \prod _{j=1}^p{N}_{R_{-}}\left(a_j\right)}\times {\displaystyle \prod _{j=1}^q{N}_{\left\{0\right\}}\left(b_j\right)}\times {\displaystyle \prod _{i=1}^m{N}_{\mathcal{C}}}\left(\left(c_1^i,c_2^i\right)\right).$

3. 关于M稳定性的新序列最优性条件

本节给出了关于MPCC问题M稳定性的CAKKT条件的定义，并证明了MPCC-CAKKT条件是一个合理的序列最优性条件。显然，由于MPCC-CAKKT条件与MPCC算法的停止准则相关，故有利于算法的数值实现。

定义3.1 (MPCC-CAKKT条件) MPCC问题的可行点$x^{\ast }$ 是MPCC-CAKKT点，如果存在序列$\left\{x^k\right\}$ ，$\left\{z^k\right\}$ 和$\left\{{\lambda }^k\right\}$ 使得

$x^k\to x^{\ast }$ , $z^k\to F\left(x^{\ast }\right)$ , $z^k\in \Lambda$ .

$\nabla f\left(x^k\right)+\nabla F{\left(x^k\right)}^{\text{T}}{\lambda }^k\to 0.$

其中${\lambda }^k\in N_{\Lambda }\left(z^k\right)$ ，且满足$\underset{k\to \infty }{\lim }{\lambda }_i^{h,k}{h}_i\left(x^k\right)=0$ ,$i=1,\cdots ,q$ 。

若${\lambda }^k=\left({\lambda }^{g,k},{\lambda }^{h,k},{\lambda }^{G,k},{\lambda }^{H,k}\right)\in R_{+}^p\times R^q\times R^m\times R^m$ ，对于足够大的k，有

$\left\{\nabla f\left(x^k\right)+{\displaystyle \sum _{i=1}^p{\lambda }_i^{g,k}\nabla g_i\left(x^k\right)}+{\displaystyle \sum _{i=1}^q{\lambda }_i^{h,k}\nabla h_i\left(x^k\right)}-{\displaystyle \sum _{i=1}^m{\lambda }_i^{G,k}\nabla G_i\left(x^k\right)}-{\displaystyle \sum _{i=1}^m{\lambda }_i^{H,k}\nabla H_i\left(x^k\right)}\right\}\to 0.$

$\left\{{\displaystyle \sum _{i=1}^p\left|{\lambda }_i^{g,k}{g}_i\left(x^k\right)\right|}+{\displaystyle \sum _{i=1}^q\left|{\lambda }_i^{h,k}{h}_i\left(x^k\right)\right|}+{\displaystyle \sum _{i=1}^m\left|{\lambda }_i^{G,k}{G}_i\left(x^k\right)\right|}+{\displaystyle \sum _{i=1}^m\left|{\lambda }_i^{H,k}{H}_i\left(x^k\right)\right|}\right\}\to 0.$

其中，${\lambda }_i^{G,k}{\lambda }_i^{H,k}=0$ 或${\lambda }_i^{G,k}>0$ ，${\lambda }_i^{H,k}>0$ ，对于每个$i\in J\left(z^k\right)$ 。

定理3.2 假设$x^{\ast }$ 是MPCC问题的局部最优解，则$x^{\ast }$ 满足MPCC-CAKKT条件。

证明：假设$x^{\ast }$ 是MPCC问题的局部最优解，取$\delta >0$ ，使得$f\left(x^{\ast }\right)\le f\left(x\right)$ 。对于每个$x\in B\left(x^{\ast },\delta \right)\cap \Omega$ 和任意序列$\left\{{\rho }_k\right\}\subseteq R_{+}$ ，使得${\rho }_k\to \infty$ 。则对于每个$k\in N$ ，考虑问题

$\begin{array}{l}\min f\left(x\right)+\frac{1}{2}{\Vert \left(x-x^{\ast },z-F\left(x^{\ast }\right)\right)\Vert }^2+\frac{1}{2}{\rho }_k{\Vert F\left(x\right)-z\Vert }^2\\ \text{s}\text{.t}\text{. }\left(x,z\right)\in U,\end{array}$ (3.1)

其中，$U:=\left\{\left(x,z\right)\in R^n\times \Lambda :\Vert \left(x,z\right)-\left(x^{\ast },F\left(x^{\ast }\right)\right)\Vert \le \delta \right\}.$

由于U的紧致性和函数的连续性可知，问题(3.1)的全局最优解存在。令$\left(x^k,z^k\right)$ 为问题(3.1)的全局最优解。下证$\left\{\left(x^k,z^k\right)\right\}$ 收敛于$\left(x^{\ast },F\left(x^{\ast }\right)\right)$ 。由于$\left(x^{\ast },F\left(x^{\ast }\right)\right)$ 的定义，我们可以得到

$f\left(x^k\right)+\frac{1}{2}{\Vert \left(x^k-x^{\ast },z^k-F\left(x^{\ast }\right)\right)\Vert }^2+\frac{1}{2}{\rho }_k{\Vert F\left(x^k\right)-z^k\Vert }^2\le f\left(x^{\ast }\right).$ (3.2)

再根据外部罚函数的收敛性理论，不失一般性，假设$\left(\widehat{x},\widehat{z}\right)$ 为$\left\{\left(x^k,z^k\right)\right\}$ 的极限。下证$\left(\widehat{x},\widehat{z}\right)=\left(x^{\ast },F\left(x^{\ast }\right)\right)$ 。由(3.2)可知，$\Vert F\left(x^k\right)-z^k\Vert \to 0$ 。因此，对于足够大的k，取极限得：$F\left(\widehat{x}\right)=\widehat{z}$ 。另外，根据式(3.2)，不等号两边同时取极限，我们还可以得到

${\Vert \left(\widehat{x}-x^{\ast },\widehat{z}-F\left(x^{\ast }\right)\right)\Vert }^2\le 2\left(f\left(x^{\ast }\right)-f\left(\widehat{x}\right)\right)$ .

由于$f\left(x^{\ast }\right)\le f\left(\widehat{x}\right)$ ，因此

$0\le {\Vert \left(\widehat{x}-x^{\ast },\widehat{z}-F\left(x^{\ast }\right)\right)\Vert }^2\le 0$ .

故可得$\widehat{x}=x^{\ast }$ 和$F\left(\widehat{x}\right)=F\left(x^{\ast }\right)$ 。因此，对于足够大的k，有

$\Vert \left(x^k,z^k\right)-\left(x^{\ast },F\left(x^{\ast }\right)\right)\Vert <\delta$ .

由于$\left(x^k,z^k\right)$ 的定义，由(3.2)可得

$0=y^k+\nabla f\left(x^k\right)+\nabla F{\left(x^k\right)}^{\text{T}}{\lambda }^k,{\lambda }^k\in N_{\Lambda }\left(z^k\right).$ (3.3)

其中，$y^k:=-\nabla F{\left(x^k\right)}^{\text{T}}\left(F\left(x^{\ast }\right)-z^k\right)+\left(x^k-x^{\ast }\right)$ ，${\lambda }^k:={\rho }_k\left(F\left(x^k\right)-z^k\right)+\left(F\left(x^{\ast }\right)-z^k\right)$ 。

由于$y^k\to 0$ 。故从(3.3)式可得出结论，$x^{\ast }$ 满足

$\nabla f\left(x^k\right)+\nabla F{\left(x^k\right)}^{\text{T}}{\lambda }^k\to 0,{\lambda }^k\in N_{\Lambda }\left(z^k\right).$ (3.4)

下证，$\underset{k\to \infty }{\lim }{\lambda }_i^{h,k}{h}_i\left(x^k\right)=0,i=1,\cdots ,q$ 。由(3.2)式可知

$\frac{1}{2}{\rho }_k{\Vert F\left(x^k\right)-z^k\Vert }^2\to 0.$ (3.5)

对(3.5)式展开有

$\frac{1}{2}{\rho }_k\left({\displaystyle \sum _{i=1}^p{\left(g_i\left(x^k\right)-z_i^{g,k}\right)}^2}+{\displaystyle \sum _{i=1}^q{\left(h_i\left(x^k\right)-z_i^{h,k}\right)}^2}+{\displaystyle \sum _{i=1}^m{\left(G_i\left(x^k\right)-z_i^{G,k}\right)}^2}+{\displaystyle \sum _{i=1}^m{\left(H_i\left(x^k\right)-z_i^{H,k}\right)}^2}\right)\to 0.$ (3.6)

由(3.4)式可知

$\frac{1}{2}{\rho }_k{\left(g_i\left(x^k\right)-z_i^{g,k}\right)}^2\to 0,i=1,\cdots ,p$ , $\frac{1}{2}{\rho }_k{\left(G_i\left(x^k\right)-z_i^{G,k}\right)}^2\to 0,i=1,\cdots ,m$ ,

$\frac{1}{2}{\rho }_k{\left(H_i\left(x^k\right)-z_i^{H,k}\right)}^2\to 0,i=1,\cdots ,m.$

故有

$\frac{1}{2}{\rho }_k{\left(h_i\left(x^k\right)-z_i^{h,k}\right)}^2\to 0,i=1,\cdots ,q.$ (3.7)

(3.7)式两端对x求梯度得：${\rho }_k\left(h_i\left(x^k\right)-z_i^{h,k}\right)\nabla h_i\left(x^k\right)\to 0,i=1,\cdots ,q.$

定义，

${\lambda }_i{}^{h,k}={\rho }_k\left(h_i\left(x^k\right)-z_i^{h,k}\right),i=1,\cdots ,q.$ (3.8)

则有

$\begin{array}{c}{\lambda }_i^{h,k}{h}_i\left(x^k\right)={\rho }_k\left(h_i\left(x^k\right)-z_i^{h,k}\right)\cdot h_i\left(x^k\right)\\ ={\rho }_k\left(h_i\left(x^k\right)-z_i^{h,k}\right)\cdot \left(h_i\left(x^k\right)-z_i^{h,k}+z_i^{h,k}\right)\\ ={\rho }_k{\left(h_i\left(x^k\right)-z_i^{h,k}\right)}^2+{\rho }_k\left(h_i\left(x^k\right)-z_i^{h,k}\right)\cdot z_i^{h,k}\\ ={\rho }_k{\left(h_i\left(x^k\right)-z_i^{h,k}\right)}^2+{\lambda }_i^{h,k}{z}_i^{h,k}\end{array}$ (3.9)

由于$z_i^{h,k}\in \Lambda$ ，故$z_i^{h,k}=0$ 。又由(3.8)式知${\rho }_k{\left(h_i\left(x^k\right)-z_i^{h,k}\right)}^2\to 0,i=1,\cdots ,q$ ，故当k足够大时，式(3.9)趋于0，即$\underset{k\to \infty }{\lim }{\lambda }_i^{h,k}{h}_i\left(x^k\right)=0,i=1,\cdots ,q$ 得证。综上可得结论，即$x^{\ast }$ 为MPEC-CAKKT点。$\square$

4. 保证M稳定性的新的约束规范

本节中首先提出了与MPCC-CAKKT相关的约束规范，即MPCC-CAKKT正则性，然后证明了MPCC-CAKKT正则性是能保证M稳定性的约束规范。

定义4.1 对于所有$x\in R^n$ ，$z\in \Lambda$ 和$r\in R_{+}$ ，我们定义$\mathcal{K}\left(\left(x,z\right),r\right)$ 为

$\mathcal{K}\left(\left(x,z\right),r\right):=\left\{\lambda =\left({\lambda }^g,{\lambda }^h,{\lambda }^G,{\lambda }^H\right):{\displaystyle \sum _{i=1}^q\left|{\lambda }_i^h{h}_i\left(x\right)\right|}\le r,\lambda \in N_{\Lambda }\left(z\right)\right\}.$

定义4.2 (MPCC-CAKKT正则性)称MPCC问题在可行点$x^{\ast }$ 处满足MPCC-CAKKT正则性，如果集值映射在点$\left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right)$ 处外半连续，即

$\underset{\left(\left(x^k,z^k\right),r^k\right)\to \left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right)}{\lim \sup }\nabla F{\left(x^k\right)}^{\text{T}}\mathcal{K}\left(\left(x^k,z^k\right),r^k\right)\subset \nabla F{\left(x^{\ast }\right)}^{\text{T}}\mathcal{K}\left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right).$

定理4.3 假设$x^{\ast }$ 是MPCC问题的一个MPCC-CAKKT点，若MPCC-CAKKT正则性在$x^{\ast }$ 处成立，那么$x^{\ast }$ 是M稳定点。

证明：对于任意连续可微的目标函数f，若$x^{\ast }$ 满足MPCC-CAKKT条件，则存在序列$\left\{x^k\right\}\to x^{\ast }$ ，$z^k\to F\left(x^{\ast }\right)$ ，$r^k\searrow$ ，$\left\{{\lambda }^k\right\}\in \mathcal{K}\left(\left(x^k,z^k\right),r^k\right)$ ，使得

$y^k=\nabla f\left(x^k\right)+\nabla F{\left(x^k\right)}^{\text{T}}{\lambda }^k\to 0.$

令${\omega }^k=\nabla F{\left(x^k\right)}^{\text{T}}{\lambda }^k$ ，则有${\omega }^k\in \nabla F{\left(x^k\right)}^{\text{T}}\mathcal{K}\left(\left(x^k,z^k\right),r^k\right)$ ，${\omega }^k=y^k-\nabla f\left(x^k\right)$ 。由定义2.1和${\omega }^k\to {\omega }^{\ast }$ ，可得

${\omega }^{\ast }\in \underset{\left(\left(x^k,z^k\right),r^k\right)\to \left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right)}{\lim \sup }\nabla F{\left(x^k\right)}^{\text{T}}\mathcal{K}\left(\left(x^k,z^k\right),r^k\right)$ .

由于$\nabla f\left(x\right)$ 连续性，MPCC-CAKKT正则性和$y^k\to 0$ 可以得到

$\begin{array}{c}-\nabla f\left(x^{\ast }\right)=\underset{k}{\lim }{\omega }^k={\omega }^{\ast }\in \underset{\left(\left(x^k,z^k\right),r^k\right)\to \left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right)}{\lim \sup }\nabla F{\left(x^k\right)}^{\text{T}}\mathcal{K}\left(\left(x^k,z^k\right),r^k\right)\\ \subset \nabla F{\left(x^{\ast }\right)}^{\text{T}}\mathcal{K}\left(\left(x^{\ast },F\left(x^{\ast }\right)\right),0\right)\subset \nabla F{\left(x^{\ast }\right)}^{\text{T}}{N}_{\Lambda }\left(F\left(x^{\ast }\right)\right).\end{array}$

故$x^{\ast }$ 为M稳定点。$\square$

推论4.4 假设$x^{\ast }$ 是MPCC问题的一个局部最优解，若MPCC-CAKKT正则性在$x^{\ast }$ 处成立，则$x^{\ast }$ 是M稳定点。

由定理3.2和定理4.3可知：若$x^{\ast }$ 是MPCC问题的一个局部最优解，且$x^{\ast }$ 满足MPCC-CAKKT正则性条件，那么$x^{\ast }$ 是M稳定点。该结果意味着MPCC-CAKKT正则性是关于M稳定性的约束规范。

5. 总结

本文主要研究了MPCC问题的序列最优性条件，介绍了与MPCC问题M稳定性相关的序列最优性条件(MPCC-CAKKT条件)，证明了MPCC-CAKKT条件是MPCC问题的一个合理的序列最优性条件。同时，提出了MPCC-CAKKT正则性，并证明了在MPCC-CAKKT正则性的条件下，MPCC问题的局部最优解是M稳定点。因此，MPCC-CAKKT正则性是MPCC问题的约束规范。

基金项目

辽宁师范大学教师指导本科生科研训练项目(项目编号：CX202302012)。