求解混合約束極大極小問題的精確光滑罰函數(shù)法

姜合峰,高 娟,張 瑞,王福勝

（太原師范學(xué)院數(shù)學(xué)系,山西晉中030619）

求解混合約束極大極小問題的精確光滑罰函數(shù)法

姜合峰,高 娟,張 瑞,王福勝

（太原師范學(xué)院數(shù)學(xué)系,山西晉中030619）

提出一個新的精確光滑罰函數(shù)法求解混合約束極大極小問題,通過引入一個新變量,將帶混合約束的極大極小問題轉(zhuǎn)化為等價的無約束優(yōu)化問題,證明在合理的假設(shè)條件下,罰問題的極小點就是原問題的極小點,數(shù)值實驗表明新算法是求解帶混合約束的極大極小問題的一種有效算法.

混合約束的極大極小問題；無約束優(yōu)化問題；精確罰函數(shù)

0 引言

極大極小問題是一類有廣泛應(yīng)用背景的優(yōu)化問題,例如：大量的金融、工程管理、經(jīng)濟(jì)問題都是轉(zhuǎn)化成極大極小問題模型來求解的.

本文研究如下帶混合約束的極大極小問題：

其中,fi：Rn→R,i∈Q,Fi：Rn→R,i∈Igi：Rn→R,i∈K,（Q＝｛1,…,q｝,I＝｛q＋1,…,m｝,

K＝｛m＋1,…,k｝）是連續(xù)可微的函數(shù).由于極大函數(shù)是不可微的,所以問題（P）是典型的不可微優(yōu)化問題,求解極大極小問題有一定的難度.

目前已有多種不同的算法來求解混合約束極大極小問題,如文獻(xiàn)［1］結(jié)合罰函數(shù)和非單調(diào)線性搜索技術(shù),并利用SQP方法求解混合約束極大極小問題；文獻(xiàn)［2］主要研究混合約束的極大極小問題,它是文獻(xiàn)［3］的推廣,但通過求解線性方程組獲得高階修正方向；文獻(xiàn)［4］將光滑優(yōu)化問題的積極集約束識別技術(shù)推廣應(yīng)用于非光滑的帶約束極大極小問題.

近來,在文獻(xiàn)［5］和［6］中,分別對于帶等式約束和不等式約束的極大極小問題,通過引入一個新的變量,提出了一種新的精確罰函數(shù)來求解約束優(yōu)化問題.受到文獻(xiàn)［5,6］的啟發(fā),本文考慮帶混合約束的極大極小問題,提出了一種新的求解問題（P）的精確罰函數(shù)方法.

1 簡單精確光滑罰函數(shù)

我們引進(jìn)參量z,則原問題（P）可轉(zhuǎn)化為連續(xù)非線性規(guī)劃問題：

也就是說,求解帶混合約束極大極小問題（P）相當(dāng)于求解問題（ˉp）.

定義集合：S＝｛（x,z）∈Rn＋1：fi（x）－z≤0,?i∈Q；Fi（x）＝0,?i∈I；gi（x）≤0,?i∈｝K,

則非線性規(guī)劃問題（ˉp）等價于下面的優(yōu)化問題：

其中,ωi∈（0,1）,i＝1,2,…k.類似地,定義集合Sε：Sε＝｛（x,z,ε）∈Rn＋2：

下面討論罰函數(shù)fσ（x,z,ε）的連續(xù)可微性.

2 算法

步2利用BFGS算法求解問題（Pσ）,將其解記作（xσ,zσ,εσ）.

步3若｜εσ｜≤ε～,‖▽（x,z,ε）fσ（x,z,ε）‖≤η,則停止,否則,令σ＝σ＋ρ,轉(zhuǎn)步2.

下面討論在弱的條件下,此算法中罰問題的極小點就是混合約束極大極小問題的極小點.

引理1 設(shè)（xk,zk,εk）∈L（Pσk）,且目標(biāo)函數(shù)值fσk（xk,zk,εk）有限和εk≠0,則有（xk,zk,εk）?Sσk.

定理2 設(shè)（xk,zk,εk）∈L（Pσk）且目標(biāo)函數(shù)值fσk（xk,zk,εk）有限和εk≠0,（xk,zk,εk）→

（x＊,z＊,ε＊）,且▽Fi（x＊）,i∈I是線性獨立的,約束優(yōu)化問題（1）在點x＊處滿足EMFCQ約束規(guī)格,那么ε＊＝0,（x＊,z＊）∈S.

1）證明ε＊＝0.由εk≠0和引理1得,（xk,zk,εk）?Sε.再由（xk,zk,εk）∈L（Pσk）,可得

3 數(shù)值實驗

為了驗證算法的可實施性和有效性,本節(jié)選取下面兩個問題進(jìn)行數(shù)值實驗,所有實驗均在Matlab R2014a軟件編程下運(yùn)行.

例1［7］minmax｛fi（x）：i＝1,2,3｝,s.t.f4（x）＝x1＋x2－2＝0,f5（x）＝－x21－x22＋2.25≤0其中f（x）：f1（x）＝x21＋x22,f2（x）＝（2－x1）2＋（2－x2）2,f3（x）＝2exp（－x1＋x2）.取初始點為x0＝［3,2］,最優(yōu)解為x＊＝（1.353 6,0.646 4）,最優(yōu)值為2.250 0.參數(shù)設(shè)置為

表1 例1的數(shù)值結(jié)果

4 結(jié)論

本文針對帶混合約束的極大極小規(guī)劃問題,提供了一種新的求解非光滑的極大極小問題的罰函數(shù)法,此罰函數(shù)中參數(shù)比較多,在算法設(shè)計時需對參數(shù)進(jìn)行調(diào)整,數(shù)值結(jié)果表明,不要求很大的罰參數(shù)就可以獲得問題的最優(yōu)值點,驗證了本文設(shè)計的罰函數(shù)運(yùn)算效果良好.

［1］YU Y H,GAO L,Nonmonotone line search for monstrainedminimax problems［J］.Journal of Optimization Theory and Application,2002,115（2）：419－446

［2］JIAN J B,ZHANG X L,MA R Q.Generalized monotone line search SQP algorithm for constrained minimax problems［J］.Optimization,2009,58（1）：101－131

［3］JIAN J B,MA R Q,ZHANG X L.Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints［J］.Journal of Computational and Applied Mathematics,2007,205：406－429

［4］D.L.Han,J.B.Jian,J.Li,On the accurate identification of active set for constrained minimax problems［J］.Nonlinear Analysis：Theoty,Methods and Application,2011,74：3022－3032

［5］馬 騁,李 訊,姚家暉,等.一種新的求解帶約束的有限極大極小問題的精確罰函數(shù)［J］.應(yīng)用數(shù)學(xué)和力學(xué),2012,33（2）：251－264

［6］鄭芳英.求解不等式約束極大極小值問題的罰函數(shù)方法［J］.浙江理工大學(xué)學(xué)報,2014,31（5）：560－564

［7］唐煥文,張立衛(wèi),王云誠.一般約束極大極小問題的一個有效的近似解法［J］.經(jīng)濟(jì)數(shù)學(xué),1995,12（1）：10－16

［8］簡金寶,光滑約束優(yōu)化快速算法——理論分析與數(shù)值實驗［M］.北京：科學(xué)出版社,2010

A Exact and Smooth Penalty Function for Solving Mixed Constrained Min－Max Problems

JIANG Hefeng,GAO Juan,ZHANG Rui,WANG Fusheng
（Department of Mathematics,Taiyuan Normal University,Jinzhong 030619,China）

A new exact and smooth penalty function was introduced to solve min－max problem of equality and inequality constraints.Though adding a new variable,the mixed constraints min－max problem is transformed to equivalent unconstrained optimization problem.It is proved that,under certain reasonable assumptions,the minimum point of unconstrained optimization problem was equivalent to the minimum point of the original constrained one.The numerical results demonstrate that the new method is an effective approach for solving mixed constrained min－max problems.

mixed constrained min－max problem；unconstrained optimization problem；exact penalty function

1672－2027（2016）04－0041－04

O221.2

A

2016－06－08

姜合峰（1973－）,男,山西夏縣人,碩士,太原師范學(xué)院數(shù)學(xué)系副教授,主要從事最優(yōu)化理論與方法.