均衡約束數(shù)學(xué)規(guī)劃問題的一種新的約束規(guī)格

童 毅,吳國民, 趙小科

(1. 武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖北 武漢 430072)

(2. 北京石油化工學(xué)院數(shù)理系,北京 102617)

均衡約束數(shù)學(xué)規(guī)劃問題的一種新的約束規(guī)格

童 毅1,吳國民2, 趙小科1

(1. 武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖北 武漢 430072)

(2. 北京石油化工學(xué)院數(shù)理系,北京 102617)

本文研究了均衡約束數(shù)學(xué)規(guī)劃 (MPEC) 問題.利用其弱穩(wěn)定點(diǎn), 獲得了一種新的約束規(guī)格 –MPEC 的偽正規(guī)約束規(guī)格. 用一種簡單的方式, 證明了該約束規(guī)格是介于 MPEC-MFCQ(即MPEC,Mangasarian-Fromowitz 約束規(guī)格) 與 MPEC-ACQ(即 MPEC,Abadie 約束規(guī)格) 之間的約束規(guī)格,因此該約束規(guī)格也可以導(dǎo)出 MPEC 問題的 M-穩(wěn)定點(diǎn).最后通過兩個(gè)例子,說明了該約束規(guī)格與 MPEC-MFCQ 以及與 MPEC-ACQ 之間是嚴(yán)格的強(qiáng)弱關(guān)系.

約束規(guī)格;偽正規(guī);均衡約束數(shù)學(xué)規(guī)劃;穩(wěn)定點(diǎn)

1引言

考慮如下均衡約束數(shù)學(xué)規(guī)劃 (MPEC) 問題

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

MPEC 問題是一類非常重要的優(yōu)化問題, 它有廣泛而重要的應(yīng)用[1]. 同時(shí) MPEC 是一類比較困難的問題,因?yàn)楹芏鄻?biāo)準(zhǔn)約束非線性規(guī)劃問題的約束規(guī)格,如 LICQ 和 MFCQ 約束規(guī) 格,對(duì)于這 一問題 是不成 立的.因此,通 常約 束 非線 性 規(guī)劃 的 K K T 條件并 不是其 必要條件.針對(duì)這種情況,人們提出了 MPEC 問題的各種穩(wěn)定點(diǎn)概念,如強(qiáng)穩(wěn)定點(diǎn)、M-穩(wěn)定點(diǎn)、C- 穩(wěn)定點(diǎn)和弱穩(wěn)定點(diǎn)等 等[2,3,4], 并給出了穩(wěn)定 點(diǎn) 成 立 的 充 分 性條件, 如 MPEC-LICQ, MPEC-MFCQ,MPEC-ACQ 和 MPEC-CRCQ 等.

眾 所 周 知, 強(qiáng) 穩(wěn) 定 點(diǎn) 條 件 等 價(jià) 于 MPEC 問 題 的 K K T 條 件[3], 同 時(shí) 也 是 各 種 穩(wěn) 定 點(diǎn)中最強(qiáng)的一種. 但是通常它是一種難以成立的最優(yōu)性條件,因此人們總是把 M-穩(wěn)定點(diǎn)作為 MPEC 問題的一階最優(yōu)性條件.并且由現(xiàn)有結(jié)果來看,當(dāng) MPEC 問題的約束規(guī)格,如MPEC-LICQ,MPEC-MFCQ,MPEC-ACQ 和 MPEC-CRCQ 等成立時(shí),M- 穩(wěn)定點(diǎn)都成立[5,6].

由于在一般約束優(yōu)化問題中,偽正規(guī)約束規(guī)格是介于 MFCQ 與 ACQ 之間的,并且,它是從否定的角度來定義的,這有別于一般的約束規(guī)格,對(duì)問題最優(yōu)性條件的研究具有重要意義.因此我們想在MPEC 中定義偽正規(guī),然后研究它與其他約束規(guī)格之間的關(guān)系.經(jīng)過理論分析,可以得到與一般約束優(yōu)化問題同樣的結(jié)論.

本文主要工作如下:首先在第二節(jié)介紹了一些背景知識(shí);其次在第三節(jié)給出了新定義的MPEC 問題約束規(guī)格,并且給出了該約束規(guī)格和其他約束規(guī)格之間的關(guān)系;第四節(jié)給出了兩個(gè)例子,說明新定義的約束規(guī)格與其他的約束規(guī)格之間是一種嚴(yán)格的強(qiáng)弱關(guān)系.

2預(yù)備知識(shí)

設(shè)x?是問題 MPEC 的一個(gè)可行點(diǎn),定義如下指標(biāo)集

同時(shí),把指標(biāo)集 β 劃分為 P(β)={(β1,β2)|β1∪ β2= β,β1∩ β2= ?}.

設(shè)x?是問題 MPEC 的一個(gè)可行點(diǎn),為了定義新的約束規(guī)格,介紹下面的優(yōu)化問題稱其為緊非線性規(guī)劃 (TNLP(x?)),顯然它是依賴于 x?的.TNLP(x?) 稱為緊的, 是因?yàn)槠淇尚杏蚴?MPEC 問題可行域的子集,因此如果 x?是 MPEC 的一個(gè)局部最優(yōu)解,那么也是TNLP(x?) 的一個(gè)局部最優(yōu)解. 通常用 TNLP(x?) 的約束規(guī)格來定義 MPEC 的約束規(guī)格.

定義2.1[1]稱 MPEC 在可行點(diǎn) x?處滿足 MPEC-LICQ 或 MPEC-MFCQ,如果與其相對(duì)應(yīng)的 TNLP(x?) 在同樣的點(diǎn) x?處滿足 LICQ 或 MFCQ.

定 義2.2稱 MPEC 的 可 行 點(diǎn) x?是 一 個(gè) 弱 穩(wěn) 定 點(diǎn), 如 果 存 在 Lagrange 乘 子 λ = (λg,λh,λG,λH) 使得下面條件成立

顯然,問題 TNLP(x?) 在點(diǎn) x?處的 KKT 條件等價(jià)于 MPEC 問題在 x?處的弱穩(wěn)定點(diǎn)條件.

給定(β1,β2)∈ P(β),定義另一個(gè)由 MPEC 問題導(dǎo)出的非線性規(guī)劃問題 NLP?(β1,β2)(x?)

由上述定義,易知問題 NLP?(β1,β2)(x?) 是依賴于 x?的. 由于問題 NLP?(β1,β2)(x?) 的可行域是 MPEC 問題可行域的一個(gè)子集,并且 x?對(duì)于問題 NLP?(β1,β2)(x?) 也是可行的.從而,若 x?是 MPEC 問題的一個(gè)局部最優(yōu)解,則 x?是問題 NLP?(β1,β2)(x?) 的一個(gè)局部最優(yōu)解.

考慮一般約束優(yōu)化問題 (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 在可行點(diǎn) x?處的偽正規(guī)成立, 如果不存在乘子 (λ,μ) 和序列{xk} 使得以下條件成立

定義2.4稱問題 CP 在可行點(diǎn) x?處的 ACQ 成立, 如果 TK(x?)=V(x?), 其中

3 MPEC 問題的一種新的約束規(guī)格

下面將從弱穩(wěn)定點(diǎn)的角度來定義MPEC 問題的偽正規(guī)約束規(guī)格.

定義3.1稱MPEC 問題在可行點(diǎn) x?處是偽正規(guī)的,如果不存在乘子 λ =(λg,λh,λG,λH)和序列 {xk} 使得以下條件成立

引理3.1[7]如果問題 CP 在點(diǎn) x?處的偽正規(guī)成立,那么其在點(diǎn) x?處的 ACQ 成立.

引理3.2[8]對(duì)任 意的 (β1,β2) ∈ P(β), 如果 問 題 N LP?(β1,β2)(x?) 的 ACQ 在 x?處成立,那么 MPEC 問題的 ACQ 在 x?處成立.

定理3.1如果 MPEC 問題在可行點(diǎn) x?處的偽正規(guī)成立,那么點(diǎn) x?處的 ACQ 成立.

證首先證明問 題 N LP?(β1,β2)(x?) 在 x?處 的 偽 正規(guī)成立. 假設(shè) N LP?(β1,β2)(x?) 在x?處偽正規(guī)不成立. 那么存在 λ =(λg,λh,λGα∪β1,λGγ∪β2,λHα∪β1,λHγ∪β2) 和序列 {xk} 使得

(i)

(ii)

(iii)

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

和序列 {xk} 滿足

由 (ii) 可得

因此 MPEC 問題的偽正規(guī)在點(diǎn) x?處不成立,從而矛盾,即問題 NLP?(β1,β2)(x?) 在 x?處的偽正規(guī)成立. 由引理 3.1 知 N LP?(β1,β2)(x?) 在 x?處的 ACQ 成立,再由 (β1,β2) 的任意性與引理 3.2 可以得到 MPEC 在 x?處 ACQ 成立.

若 MPEC 問題的一個(gè)局部最優(yōu)解 x?滿足 MPEC-ACQ,則 x?是一個(gè) M- 穩(wěn)定點(diǎn),故也可以得到以下推論.

推論3.1如果 MPEC 問題的一個(gè)局部最優(yōu)解 x?滿足 MPEC 問題的偽正規(guī),那么 x?是一個(gè)M-穩(wěn)定點(diǎn).

定理3.2如果 MPEC 問題中,g,h,G,H 是凹函數(shù),那么對(duì) MPEC 問題的所有可行點(diǎn)處偽正規(guī)均成立.

證假設(shè) MPEC 問題的偽正規(guī)在可行點(diǎn) x?處不成立,那么存在 λ =(λg,λh,λG,λH) 和序列 {xk} 使得以下條件成立

由于 g,h,G,H 都是凹函數(shù),故 ?y ∈ Rn,都有

從而 ?y ∈ Rn,

最后一個(gè)等式是由條件 (ii) 得到的, 再由條件 (i) 得

與條件 (iii) 矛盾, 定理得證.

推論3.2對(duì)于 MPEC 問題,如果 g,h,G,H 是線性的,那么 MPEC 問題的所有可行點(diǎn)處偽正規(guī)均成立.

利用 Motzkin 選擇理論[4], 可以得到 MPEC-MFCQ 等價(jià)形式如下: 不存在非零乘子λ =(λg,λh,λG,λH) 使得

顯然可以得到如下結(jié)論

推論3.3如果 MPEC 問題在可行點(diǎn) x?處 MPEC-MFCQ 成立,那么點(diǎn) x?處 MPEC 的偽正規(guī)成立.

4實(shí)例闡述

考慮如下兩個(gè) MPEC 問題, 例 4.1 說明 MPEC-MFCQ 是嚴(yán)格強(qiáng)于 MPEC 偽正規(guī)的, 例4.2 說明 MPEC-ACQ 是嚴(yán)格弱于 MPEC 偽正規(guī)的.

例4.1

顯然點(diǎn) x=(0,0) 是可行點(diǎn), 并 且 所有的約束都是積極約束. 令 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)} 線 性相 關(guān), 也 即 MPEC-MFCQ 不 成 立. 但 是, 因 為g(x),G(x),H(x) 都是線性的,所以 MPEC 問題的偽正規(guī)成立.

例4.2顯然點(diǎn) x=(0,0) 是可行點(diǎn),并且所有的約束都是積極約束,可算出該問題的切錐和 MPEC線 性 化 錐 是 相 等 的, 即 T(x)={(d1,d2)|d2≤ 0,d1+d2=0}=TlinMPEC(x). 從 而 該 問 題 的ACQ 成立.下面驗(yàn)證其偽正規(guī)不成立.

令

從而只要滿足 λg= λG= λH≥ 0,就可以得到偽正規(guī)的前兩條. 針對(duì) MPEC 問題的偽正規(guī)條件的 (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 問題的偽正規(guī)條件(i)–(iii) 成立, 則 MPEC 偽正規(guī)不成立.

[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] 杜文, 黃崇超. 求解二層規(guī)劃問題的遺傳算法 [J]. 數(shù)學(xué)雜志,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

國家自然科學(xué)基金資助 (71471140).

童毅 (1990–),男, 湖北漢川, 主要研究方向: 最優(yōu)化理論、算法及其應(yīng)用.