考虑如下均衡约束数学规划(MPEC)问题

$ \begin{split} &\qquad \quad \min_{x\in\mathbb{R}^n} \, \, f(x), \\ &\rm{s.t.} \left\{\begin{array}{ll} g_i(x)\leq0, &\quad i=1, \cdots, p, \\ h_i(x)=0, &\quad i=1, \cdots, q, \\ G_i(x)\geq0, H_i(x)\geq0, G_i(x)H_i(x)=0, &\quad i=1, \cdots, m, \\ \end{array}\right. \end{split} $

(1.1)

其中$f: R^n\rightarrow R; g_i: R^n\rightarrow R, i=1, \cdots, p; h_i: R^n\rightarrow R, i=1, \cdots, q$; 且$G_i, H_i: R^n\rightarrow R, i=1, \cdots, m$.

MPEC问题是一类非常重要的优化问题, 它有广泛而重要的应用^[1].同时MPEC是一类比较困难的问题, 因为很多标准约束非线性规划问题的约束规格, 如LICQ和MFCQ约束规格, 对于这一问题是不成立的.因此, 通常约束非线性规划的$KKT$条件并不是其必要条件.针对这种情况, 人们提出了MPEC问题的各种稳定点概念, 如强稳定点、$M$-稳定点、$C$-稳定点和弱稳定点等等^{[2, 3, 4]}, 并给出了稳定点成立的充分性条件, 如$\rm{MPEC-LICQ, MPEC-MFCQ, MPEC-ACQ和MPEC-CRCQ}$等.

众所周知, 强稳定点条件等价于MPEC问题的$KKT$条件^[3], 同时也是各种稳定点中最强的一种.但是通常它是一种难以成立的最优性条件, 因此人们总是把$M$-稳定点作为MPEC问题的一阶最优性条件.并且由现有结果来看, 当MPEC问题的约束规格, 如：$\rm{MPEC-LICQ, MPEC-MFCQ, MPEC-ACQ和MPEC-CRCQ}$等成立时, $M$-稳定点都成立^{[5, 6]}.

由于在一般约束优化问题中, 伪正规约束规格是介于MFCQ与ACQ之间的, 并且, 它是从否定的角度来定义的, 这有别于一般的约束规格, 对问题最优性条件的研究具有重要意义.因此, 我们想在MPEC中定义伪正规, 然后研究它与其他约束规格之间的关系.经过理论分析, 可以得到与一般约束优化问题同样的结论.

本文主要工作如下:首先我们在第二节介绍了一些背景知识; 其次在第三节给出了新定义的MPEC问题约束规格, 并且给出了该约束规格和其他约束规格之间的关系; 第四节给出了两个例子, 说明新定义的约束规格与其他的约束规格之间是一种严格的强弱关系.

设$x^*$是问题MPEC的一个可行点, 我们定义如下指标集

$ \left\{\begin{array}{lll} I_g:=I_g(x^*)=\{i|g(x^*)=0\}, \\ \alpha:=\alpha(x^*)=\{i|G_i(x^*)=0, H_i(x^*)>0\}, \\ \beta:=\beta(x^*)=\{i|G_i(x^*)=0, H_i(x^*)=0\}, \\ \gamma:=\gamma(x^*)=\{i|G_i(x^*)>0, H_i(x^*)=0\}. \\ \end{array}\right. $

(2.1)

同时, 把指标集$\beta$划分为$P(\beta)=\{(\beta_1, \beta_2)|\beta_1\cup\beta_2=\beta, \beta_1\cap\beta_2=\emptyset\}$.

设$x^*$是问题MPEC的一个可行点, 为了定义新的约束规格, 我们介绍下面的优化问题

$ \begin{split} &\qquad \quad \min_{x\in\mathbb{R}^n} \, \, f(x), \\ &\rm{s.t.} \left\{\begin{array}{ll} g_i(x)\leq0, &\quad i=1, \cdots, p, \\ h_i(x)=0, &\quad i=1, \cdots, q, \\ G_{\alpha\cup\beta}(x)=0, G_\gamma(x)\geq0, &\\ H_\alpha(x)\geq0, H_{\gamma\cup\beta}(x)=0, &\\ \end{array}\right. \end{split} $

(2.2)

称其为紧非线性规划(TNLP$(x^*)$), 显然它是依赖于$x^*$的. TNLP$(x^*)$称为紧的, 是因为其可行域是MPEC问题可行域的子集, 因此如果$x^*$是MPEC的一个局部最优解, 那么也是TNLP$(x^*)$的一个局部最优解.我们通常用TNLP$(x^*)$的约束规格来定义MPEC的约束规格.

定义2.1^[1]  称MPEC在可行点$x^*$处满足$\rm{MPEC-LICQ}$或MPEC-MFCQ, 如果与其相对应的TNLP$(x^*)$在同样的点$x^*$处满足LICQ或MFCQ.

定义2.2  称MPEC的可行点$x^*$是一个弱稳定点, 如果存在Lagrange乘子$\lambda=(\lambda^g, \lambda^h, \lambda^G, \lambda^H)$使得下面条件成立

$ \begin{array}{cl} (ⅰ)&0=\nabla f(x^*)+\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^G\nabla H_i(x^*)]; \\ (ⅱ)&\lambda^g\geq 0; \lambda_i^g=0, \forall i\not\in I_g; \\ (ⅲ)&\lambda_\alpha^H=0, \lambda_\gamma^G=0. \\ \end{array} $

显然, 问题TNLP$(x^*)$在点$x^*$处的KKT条件等价于MPEC问题在$x^*$处的弱稳定点条件.

给定$(\beta_1, \beta_2)\in P(\beta)$, 定义另一个由MPEC问题导出的非线性规划问题NLP$_*(\beta_1, \beta_2)(x^*)$

$ \begin{split} &\qquad \quad \min_{x\in\mathbb{R}^n} \, \, f(x),\\ &\rm{s.t.} \left\{\begin{array}{ll} g_i(x)\leq0, &\quad i=1, \cdots, p, \\ h_i(x)=0, &\quad i=1, \cdots, q, \\ G_{\alpha\cup\beta_1}(x)=0, G_{\gamma\cup\beta_2}(x)\geq0, &\\ H_{\alpha\cup\beta_1}(x)\geq0, H_{\gamma\cup\beta_2}(x)=0. &\\ \end{array}\right. \end{split} $

(2.3)

由上述定义, 易知, 问题${\rm{NLP}}_*(\beta_1, \beta_2)(x^*)$是依赖于$x^*$的.由于问题${\rm{NLP}}_*(\beta_1, \beta_2)(x^*)$的可行域是MPEC问题可行域的一个子集, 并且$x^*$对于问题${\rm{NLP}}_*(\beta_1, \beta_2)(x^*)$也是可行的.从而, 若$x^*$是MPEC问题的一个局部最优解, 则$x^*$是问题${\rm{NLP}}_*(\beta_1, \beta_2)(x^*)$的一个局部最优解.

考虑一般约束优化问题$(\rm{CP})$

$ \begin{split} &\qquad \quad \min_{x\in\mathbb{R}^n} \, \, f(x),\\ &\rm{s.t.} \left\{\begin{array}{ll} g_i(x)\leq0, &\quad i=1, \cdots, p, \\ h_i(x)=0, &\quad i=1, \cdots, q, \\ \end{array}\right. \end{split} $

(2.4)

其中$f: R^n\rightarrow R; g_i: R^n\rightarrow R, i=1, \cdots, p; h_i: R^n\rightarrow R, i=1, \cdots, q$.且令$K=\{x|g_i(x)\leq0, i=1, \cdots, p; h_i(x)=0, i=1, \cdots, q\}$.

定义2.3^[7] 称问题CP在可行点$x^*$处的伪正规成立, 如果不存在乘子$(\lambda, \mu)$和序列$\{x^k\}$使得以下条件成立

$ \begin{array}{cl} (ⅰ)&\sum\limits_{i = 1}^p\lambda_i\nabla g_i(x^*)+\sum\limits_{i = 1}^q\mu_i\nabla h_i(x^*)=0; \\ (ⅱ)&\lambda\geq 0; \lambda_i=0, \forall i\not\in I_g=\{i|g_i(x^*)=0\}; \\ (ⅲ)&\{x^k\}\rightarrow x^*, \sum\limits_{i = 1}^p\lambda_i g_i(x^k)+\sum\limits_{i = 1}^q\mu_i h_i(x^k)>0. \\ \end{array} $

定义2.4 称问题CP在可行点$x^*$处的ACQ成立, 如果$T_K(x^*)=V(x^*)$, 其中

$ V(x^*)=\{y|\nabla h_i(x^*)^Ty=0, i=1, \cdots, p; \nabla g_i(x^*)^Ty=0, i=1, \cdots, q\}, \\ T_K(x^*)=\{d|\exists\{x^k\}\in K, \exists\{t^k\}\searrow 0: x^k\rightarrow x^*, [(x^k-x^*)/ t^k]\rightarrow d\}. $

下面将从弱稳定点的角度来定义MPEC问题的伪正规约束规格.

定义3.1 称MPEC问题在可行点$x^*$处是伪正规的, 如果不存在乘子$\lambda=(\lambda^g, \lambda^h, \lambda^G, \lambda^H)$和序列$\{x^k\}$使得以下条件成立

$ \begin{array}{cl} (ⅰ)&\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^H\nabla H_i(x^*)]=0; \\ (ⅱ)&\lambda^g\geq 0; \lambda_i^g=0, \forall i\not\in I_g; \lambda_\alpha ^H=0, \lambda_\gamma^G=0; \\ (ⅲ)&\{x^k\}\rightarrow x^*, \sum\limits_{i = 1}^p\lambda_i^g g_i(x^k)+\sum\limits_{i = 1}^q\lambda_i^h h_i(x^k)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(x^k)+\lambda_i^G H_i(x^k)]>0. \\ \end{array} $

引理3.1^[7] 如果问题CP在点$x^*$处的伪正规成立, 那么其在点$x^*$处的ACQ成立.

引理3.2^[8] 对任意的$(\beta_1, \beta_2)\in P(\beta)$, 如果问题$NLP_*(\beta_1, \beta_2)(x^*)$的ACQ在$x^*$处成立, 那么MPEC问题的ACQ在$x^*$处成立.

定理3.1  如果MPEC问题在可行点$x^*$处的伪正规成立, 那么点$x^*$处的ACQ成立.

证 首先证明问题$NLP_*(\beta_1, \beta_2)(x^*)$在$x^*$处的伪正规成立.假设$NLP_*(\beta_1, \beta_2)(x^*)$在$x^*$处伪正规不成立.那么存在$\lambda=(\lambda^g, \lambda^h, \lambda_{\alpha\cup\beta_1}^G, \lambda_{\gamma\cup\beta_2}^G, \lambda_{\alpha\cup\beta_1}^H, \lambda_{\gamma\cup\beta_2}^H)$和序列$\{x^k\}$使得

(ⅰ)

$ \sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)+\sum\limits_{i = 1}^{N(\alpha\cup\beta_1)}\lambda_{(\alpha\cup\beta_1)_i}^G\nabla G_i(x^*)-\sum\limits_{i = 1}^{N(\gamma\cup\beta_2)}\lambda_{(\gamma\cup\beta_2)_i}^G\nabla G_i(x^*)\\ -\sum\limits_{i = 1}^{N(\alpha\cup\beta_1)}\lambda_{(\alpha\cup\beta_1)_i}^H\nabla H_i(x^*)+\sum\limits_{i = 1}^{N(\gamma\cup\beta_2)}\lambda_{(\gamma\cup\beta_2)_i}^H\nabla H_i(x^*)=0; $

(ⅱ)

$ \lambda^g\geq 0; \lambda_i^g=0, \forall i\not\in I_g; \lambda_{\alpha\cup\beta_1}^H\geq0; \lambda_{(\alpha\cup\beta_1)_i}^H=0, \forall i\in\alpha;\\ \lambda_{\gamma\cup\beta_2}^G\geq0; \lambda_{(\gamma\cup\beta_2)_i}^G=0, \forall i\in\gamma; $

(ⅲ)

$ \{x^k\}\rightarrow x^*, \sum\limits_{i = 1}^p\lambda_i^g g_i(x^k)+\sum\limits_{i = 1}^q\lambda_i^h h_i(x^k)+\sum\limits_{i = 1}^{N(\alpha\cup\beta_1)}\lambda_{(\alpha\cup\beta_1)_i}^G G_i(x^k)\\ -\sum\limits_{i = 1}^{N(\gamma\cup\beta_2)}\lambda_{(\gamma\cup\beta_2)_i}^G G_i(x^k)-\sum\limits_{i = 1}^{N(\alpha\cup\beta_1)}\lambda_{(\alpha\cup\beta_1)_i}^H H_i(x^k)+\sum\limits_{i = 1}^{N(\gamma\cup\beta_2)}\lambda_{(\gamma\cup\beta_2)_i}^H H_i(x^k)>0. $

由于$N(\alpha\cup\beta_1)+N(\gamma\cup\beta_2)=m$, 于是存在乘子

$ \lambda=(\lambda^g, \lambda^h, \lambda^G, \lambda^H)=(\lambda^g, \lambda^h, (-\lambda_{\alpha\cup\beta_1}^G, \lambda_{\gamma\cup\beta_2}^G), (\lambda_{\alpha\cup\beta_1}^H, -\lambda_{\gamma\cup\beta_2}^H)) $

和序列$\{x^k\}$满足

$ \begin{array}{cl} &\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^H\nabla H_i(x^*)]=0; \\ &\{x^k\}\rightarrow x^*, \ \ \sum\limits_{i = 1}^p\lambda_i^g g_i(x^k)+\sum\limits_{i = 1}^q\lambda_i^h h_i(x^k)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(x^k)+\lambda_i^H H_i(x^k)]>0. \\ \end{array} $

由(ⅱ)可得

$ \lambda^g\geq 0; \lambda_i^g=0, \forall i\not\in I_g; \lambda_\alpha ^H=0, \lambda_\gamma^G=0. $

因此MPEC问题的伪正规在点$x^*$处不成立, 从而矛盾, 即问题${\rm{NLP}}_*(\beta_1, \beta_2)(x^*)$在$x^*$处的伪正规成立.由引理3.1知$NLP_*(\beta_1, \beta_2)(x^*)$在$x^*$处的ACQ成立, 再由$(\beta_1, \beta_2)$的任意性与引理3.2可以得到MPEC在$x^*$处ACQ成立.

若MPEC问题的一个局部最优解$x^*$满足MPEC-ACQ, 则$x^*$是一个$M$-稳定点, 故也可以得到以下推论.

推论3.1 如果MPEC问题的一个局部最优解$x^*$满足MPEC问题的伪正规, 那么$x^*$是一个$M$-稳定点.

定理3.2 如果MPEC问题中, $g, h, G, H$是凹函数, 那么对MPEC问题的所有可行点处伪正规均成立.

证 假设MPEC问题的伪正规在可行点$x^*$处不成立, 那么存在$\lambda=(\lambda^g, \lambda^h, \lambda^G, \lambda^H)$和序列$\{x^k\}$使得以下条件成立

$ \begin{array}{cl} (ⅰ)&\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^H\nabla H_i(x^*)]=0; \\ (ⅱ)&\lambda^g\geq 0; \lambda_i^g=0, \forall i\not\in I_g; \lambda_\alpha ^H=0, \lambda_\gamma^G=0; \\ (ⅲ)&\{x^k\}\rightarrow x^*, \sum\limits_{i = 1}^p\lambda_i^g g_i(x^k)+\sum\limits_{i = 1}^q\lambda_i^h h_i(x^k)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(x^k)+\lambda_i^H H_i(x^k)]>0. \\ \end{array} $

由于$g, h, G, H$都是凹函数, 故$\forall y\in R^n$, 都有

$ \begin{array}{cl} h_i(y)\leq h_i(x^*)+\nabla h_i^T(y-x^*)\quad i=1, \cdots, p, \\ g_i(y)\leq g_i(x^*)+\nabla g_i^T(y-x^*)\quad i=1, \cdots, q, \\ G_i(y)\leq G_i(x^*)+\nabla G_i^T(y-x^*)\quad i=1, \cdots, m, \\ H_i(y)\leq H_i(x^*)+\nabla H_i^T(y-x^*)\quad i=1, \cdots, m, \\ \end{array} $

从而$\forall y\in R^n$

$ \begin{array}{ll} \ \ \ \sum\limits_{i = 1}^p\lambda_i^g g_i(y)+\sum\limits_{i = 1}^q\lambda_i^h h_i(y)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(y)+\lambda_i^H H_i(y)]\\ \leq\sum\limits_{i = 1}^p\lambda_i^g g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(x^*)+\lambda_i^H H_i(x^*)]\\ \ \ \ +\{\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^H\nabla H_i(x^*)]\}^T(y-x^*)\\ =\{\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^H\nabla H_i(x^*)]\}^T(y-x^*). \end{array} $

最后一个等式是由条件(ⅱ)得到的, 再由条件(ⅰ)得

$ \sum\limits_{i = 1}^p\lambda_i^g g_i(y)+\sum\limits_{i = 1}^q\lambda_i^h h_i(y)-\sum\limits_{i = 1}^m[\lambda_i^G G_i(y)+\lambda_i^G H_i(y)]\leq0, $

与条件(ⅲ)矛盾, 定理得证.

推论3.2 对于MPEC问题, 如果$g, h, G, H$是线性的, 那么MPEC问题的所有可行点处伪正规均成立.

利用Motzkin选择理论^[4] 我们可以得到MPEC-MFCQ等价形式如下:不存在非零乘子$\lambda=(\lambda^g, \lambda^h, \lambda^G, \lambda^H)$使得

$ \begin{array}{cl} (ⅰ)&\sum\limits_{i = 1}^p\lambda_i^g\nabla g_i(x^*)+\sum\limits_{i = 1}^q\lambda_i^h\nabla h_i(x^*)-\sum\limits_{i = 1}^m[\lambda_i^G\nabla G_i(x^*)+\lambda_i^G\nabla H_i(x^*)]=0; \\ (ⅱ)&\lambda^g\geq 0; \lambda_i^g=0, \forall i\in I_g; \lambda_\alpha ^H=0, \lambda_\gamma^G=0. \\ \end{array} $

显然可以得到如下结论：

推论3.3 如果MPEC问题在可行点$x^*$处MPEC-MFCQ成立, 那么点$x^*$处MPEC的伪正规成立.

考虑如下两个MPEC问题, 例4.1说明MPEC-MFCQ是严格强于MPEC伪正规的, 例4.2说明MPEC-ACQ是严格弱于MPEC伪正规的.

例4.1

$ \begin{split} &\qquad \quad \min \, \, f(x),\\ &\rm{s.t.} \left\{\begin{array}{ll} g(x)=x_1+x_2\leq0, \\ G(x)=x_1\geq0, H(x)=x_2\geq0, \\ G(x)H(x)=x_1x_2=0. \\ \end{array}\right. \end{split} $

(4.1)

显然点$x=(0, 0)$是可行点, 并且所有的约束都是积极约束.令$a\nabla g(x)-b\nabla G(x)-c\nabla H(x)=0$, 即$a(1, 1)^T-b(1, 0)^T-c(0, 1)^T=0$, 可得$a=b=c$.从而只要$a=b=c\neq0$, 就可得$\{\nabla g(x), \nabla G(x), \nabla H(x)\}$线性相关, 也即MPEC-MFCQ不成立.但是, 因为$g(x), G(x), H(x)$都是线性的, 所以MPEC问题的伪正规成立.

例4.2

$ \begin{split} &\qquad \quad \min \, \, f(x),\\ &\rm{s.t.} \left\{\begin{array}{ll} g(x)=x_2\leq0, \\ h(x)=x_1^2-x_2^2=0, \\ G(x)=x_1\geq0, H(x)=x_1+x_2\geq0, \\ G(x)H(x)=x_1(x_1+x_2)=0. \\ \end{array}\right. \end{split} $

(4.2)

显然点$x=(0, 0)$是可行点, 并且所有的约束都是积极约束, 可算出该问题的切锥和MPEC线性化锥是相等的, 即$T(x)=\{(d_1, d_2)|d_2\leq0, d_1+d_2=0\}=T_{\rm{{MPEC}}}^{\rm{{lin}}}(x)$.从而该问题的ACQ成立.下面验证其伪正规不成立.

令

$ \lambda^g\nabla g(x)+\lambda^h\nabla h(x)-\lambda^G\nabla G(x)-\lambda^H\nabla H(x)\\ =\lambda^g(0, 1)^T+\lambda^h(0, 0)^T-\lambda^G(1, 0)^T-\lambda^H(1, 1)^T=0. $

从而只要满足$\lambda^g=\lambda^G=\lambda^H\geq0$, 就可以得到伪正规的前两条.针对MPEC问题的伪正规条件的(ⅲ), 令$\lambda^g g(x^k)+\lambda^h h(x^k)-\lambda^G G(x^k)-\lambda^H H(x^k)=\lambda^h((x_1^k)^2-(x_2^k)^2)>0$.这样, 只要满足$\lambda^g=\lambda^G=\lambda^H\geq0, \lambda^h=0, \{x^k\}\rightarrow x, (x_1^k)^2>(x_2^k)^2$, 就有MPEC问题的伪正规条件(ⅰ)-(ⅲ)成立, 则MPEC伪正规不成立.