均衡约束数学规划问题的一种新的约束规格

童 毅,吴国民, 赵小科

(1. 武汉大学数学与统计学院,湖北 武汉 430072)

(2. 北京石油化工学院数理系,北京 102617)

均衡约束数学规划问题的一种新的约束规格

童 毅1,吴国民2, 赵小科1

(1. 武汉大学数学与统计学院,湖北 武汉 430072)

(2. 北京石油化工学院数理系,北京 102617)

本文研究了均衡约束数学规划 (MPEC) 问题.利用其弱稳定点, 获得了一种新的约束规格 –MPEC 的伪正规约束规格. 用一种简单的方式, 证明了该约束规格是介于 MPEC-MFCQ(即MPEC,Mangasarian-Fromowitz 约束规格) 与 MPEC-ACQ(即 MPEC,Abadie 约束规格) 之间的约束规格,因此该约束规格也可以导出 MPEC 问题的 M-稳定点.最后通过两个例子,说明了该约束规格与 MPEC-MFCQ 以及与 MPEC-ACQ 之间是严格的强弱关系.

约束规格;伪正规;均衡约束数学规划;稳定点

1引言

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

其中 f:Rn→ R;gi:Rn→ R,i=1,···,p;hi:Rn→ R,i=1,···,q; 且 Gi,Hi:Rn→R,i=1,···,m.

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

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

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

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

2预备知识

设x∗是问题 MPEC 的一个可行点,定义如下指标集

同时,把指标集 β 划分为 P(β)={(β1,β2)|β1∪ β2= β,β1∩ β2= ∅}.

设x∗是问题 MPEC 的一个可行点,为了定义新的约束规格,介绍下面的优化问题称其为紧非线性规划 (TNLP(x∗)),显然它是依赖于 x∗的.TNLP(x∗) 称为紧的, 是因为其可行域是 MPEC 问题可行域的子集,因此如果 x∗是 MPEC 的一个局部最优解,那么也是TNLP(x∗) 的一个局部最优解. 通常用 TNLP(x∗) 的约束规格来定义 MPEC 的约束规格.

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

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

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

给定(β1,β2)∈ P(β),定义另一个由 MPEC 问题导出的非线性规划问题 NLP∗(β1,β2)(x∗)

由上述定义,易知问题 NLP∗(β1,β2)(x∗) 是依赖于 x∗的. 由于问题 NLP∗(β1,β2)(x∗) 的可行域是 MPEC 问题可行域的一个子集,并且 x∗对于问题 NLP∗(β1,β2)(x∗) 也是可行的.从而,若 x∗是 MPEC 问题的一个局部最优解,则 x∗是问题 NLP∗(β1,β2)(x∗) 的一个局部最优解.

考虑一般约束优化问题 (CP)

其中 f:Rn→ R;gi:Rn→ R,i=1,···,p;hi:Rn→ R,i=1,···,q. 且令 K={x|gi(x) ≤0,i=1,···,p;hi(x)=0,i=1,···,q}.

定义2.3[7]称问题 CP 在可行点 x∗处的伪正规成立, 如果不存在乘子 (λ,µ) 和序列{xk} 使得以下条件成立

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

3 MPEC 问题的一种新的约束规格

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

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

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

引理3.2[8]对任 意的 (β1,β2) ∈ P(β), 如果 问 题 N LP∗(β1,β2)(x∗) 的 ACQ 在 x∗处成立,那么 MPEC 问题的 ACQ 在 x∗处成立.

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

证首先证明问 题 N LP∗(β1,β2)(x∗) 在 x∗处 的 伪 正规成立. 假设 N LP∗(β1,β2)(x∗) 在x∗处伪正规不成立. 那么存在 λ =(λg,λh,λGα∪β1,λGγ∪β2,λHα∪β1,λHγ∪β2) 和序列 {xk} 使得

(i)

(ii)

(iii)

由于 N(α ∪ β1)+N(γ ∪ β2)=m,于是存在乘子

和序列 {xk} 满足

由 (ii) 可得

因此 MPEC 问题的伪正规在点 x∗处不成立,从而矛盾,即问题 NLP∗(β1,β2)(x∗) 在 x∗处的伪正规成立. 由引理 3.1 知 N LP∗(β1,β2)(x∗) 在 x∗处的 ACQ 成立,再由 (β1,β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∗处不成立,那么存在 λ =(λg,λh,λG,λH) 和序列 {xk} 使得以下条件成立

由于 g,h,G,H 都是凹函数,故 ∀y ∈ Rn,都有

从而 ∀y ∈ Rn,

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

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

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

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

显然可以得到如下结论

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

4实例阐述

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

例4.1

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

例4.2显然点 x=(0,0) 是可行点,并且所有的约束都是积极约束,可算出该问题的切锥和 MPEC线 性 化 锥 是 相 等 的, 即 T(x)={(d1,d2)|d2≤ 0,d1+d2=0}=TlinMPEC(x). 从 而 该 问 题 的ACQ 成立.下面验证其伪正规不成立.

令

从而只要满足 λg= λG= λH≥ 0,就可以得到伪正规的前两条. 针对 MPEC 问题的伪正规条件的 (iii), 令 λgg(xk)+ λhh(xk) − λGG(xk) − λHH(xk)= λh((xk1)2− (xk2)2) ＞ 0. 这样, 只要满足 λg= λG= λH≥ 0,λh=0,{xk} → x,(xk1)2＞ (xk2)2, 就有 MPEC 问题的伪正规条件(i)–(iii) 成立, 则 MPEC 伪正规不成立.

[1]Luo Z Q,Pang J S,Ralph D.Mathematical programs with equilibrium constraints[M].Cambridge: Cambridge University Press,1996.

[2]Outrata J V.Optimality conditions for a class of mathematical programs with equilibrium constraints[J].Math.Ope.Res.,1999,24(3):627–644.

[3]Outrata J V.A generalized mathematical program with equilibrium constraints[J].SIAM J.Control Optim.,2000,38(5):1623–1638.

[4]Scheel H,Scholtes.Mathematical programs with complementarity constraints:stationarity,optimality,and sensitivity[J].Math.Oper.Res.,2000,25(1):1–22.

[5]Flegel M L,Kanzow C.On M-stationary points for mathematical programs with equilibrium constraint[J].J.Math.Anal.Appl.,2005,310(1):286-302.

[6]Ye J.Necessary and suffi cient optimality conditions for mathematical programs with equilibrium constraint[J].J.Math.Anal.Appl.,2005,307(1):350–369.

[7]Flegel M L,Kanzow C.Abadie-type constraint qualifi cation for mathematical programs with equilibrium constraints[J].J.Optim.Theory Appl.,2005,124(3):595–614.

[8]Flegel M L,Kanzow C.On the Guignard constraint qualifi cation for mathematical programs with equilibrium constraints[J].Optim.,2005,54(6):517-534.

[9]Bertsekas D P,Nedic A,Ozdaglar A E.Convexity,duality,and lagrange multipliers[M].Cambridge: Massachusett Institute of Techenology,Spring,2001.

[10]Mangasarian O L.Nonlinear programming[M].Philadelphia:Classics Appl Math.10,SIAM,1994.

[11]Ye J J.Constraint qualifi cations and necessary optimality conditions for optimization problems with variational inequality constraints[J].SIAM J.Optim.,2000,10(4):943–962.

[12]Ye J J,Zhang J.Enhanced Karush-Kuhn-Tucker condition and weaker constraint qualifi cations[J]. Math.Program,2013,10(1):353–381.

[13] 杜文, 黄崇超. 求解二层规划问题的遗传算法 [J]. 数学杂志,2005,25(2):167–170.

A NEW CONSTRAINT QUALIFICATION FOR MATHEMATICAL PROGRAMS WITH EQUILIBRIUM CONSTRAINTS

TONG Yi1,WU Guo-min2,ZHAO Xiao-ke1
(1.School of Mathematics and Statistics,WuHan University,Wuhan 430072,China)
(2.Department of Mathematics and Physics,Beijing Institute of Petrochemical Technology, Beijing 102617,China)

This paper considers mathematical programs with equilibrium constraints (MPEC).A new constraint qualification called MPEC-pseudonormality is proposed by weakly stationary.According to a simple way,we prove that MPEC-pseudonormality is between MPEC Mangasarian-Fromovitz constraint qualifi cation(MPEC-MFCQ)and MPEC Abadies constant qulifi cation(MPEC-ACQ).So MPEC-pseudonormality can also derive M-stationary of MPEC. Finally,we state that the relationships among MPEC-pseudonormality,MPEC-MFCQ and MPEC-ACQ are strict.

constraint qualification;pseudonormality;mathematical programs with equilibrium constraints;stationary

tion:90C33

0C33

O221.2

A

0255-7797(2017)02-0376-07

2014-11-10 接收日期:2015-05-06

国家自然科学基金资助 (71471140).

童毅 (1990–),男, 湖北汉川, 主要研究方向: 最优化理论、算法及其应用.