求解不等式約束極大極小值問題的罰函數方法

鄭芳英

（浙江理工大學理學院，杭州310018）

求解不等式約束極大極小值問題的罰函數方法

鄭芳英

（浙江理工大學理學院，杭州310018）

構造一個新的簡單精確光滑罰函數來求解含不等式約束極大極小值問題。首先通過添加一個變量，將含不等式約束的極大極小值問題轉化為與之等價的連續約束優化問題，然后利用新的簡單精確光滑罰函數，對等價的連續約束優化問題進行求解。在擴展的MF約束規范條件下，可以證明：當罰參數充分大時，無約束優化問題的局部極小點也是原極大極小值問題的局部極小點。算例結果表明，給出的罰函數方法可有效地求解含不等式約束的極大極小值問題。

約束優化問題；無約束優化問題；罰函數方法；極大極小值問題

0 引 言

極大極小值問題是優化問題的重要分支，工程優化設計、電子線路優化設計、經濟管理等許多實際問題都可以建模為極大極小值問題。本文研究如下含不等式約束的極大極小值問題：

其中fi：Rn→R（i=1，…，q），gi：Rn→R（i=q+1，…，m）為連續可微函數。

其中z∈R是新引進的變量。顯然問題（1）與問題（2）是等價的，從而可以利用已有的求解連續非線性規劃的算法求解問題（1）。

罰函數方法是求解連續約束優化問題的一種重要方法，其思想是將約束優化問題轉化為無約束或僅含簡單約束的優化問題來求解。但是傳統的罰函數要么簡單精確，但不是光滑的，如l1精確罰函數；要么光滑，但不是精確的，如二次罰函數；要么光滑精確的，但不是簡單的。這里的“簡單”是指罰函數中僅含目標函數及約束函數，而不含其梯度的信息。

2003年，Huyer等［4］通過增加一個變量，針對下式約束優化問題（3）給出了一個新的簡單精確罰函數。

其中［u，v］=｛x∈Rn：u≤x≤v｝為Rn中具有非空內部的箱子約束，f：D→R，Fj：D→R（?j∈E）連續可微函數，而D為含［u，v］的開集。固定ωj（?j∈E），考慮如下等價問題：

相應的罰問題為：

在一些常規的假設下，文獻［4］證明了罰問題（5）的局部極小點正好也是原問題（3）的局部極小點；同時證明，對于問題（5），當ε＞0時，對于充分大的σ，問題（5）不存在KKT點，而通常算法得到的點是KKT點。

Di Pillo等［5］考慮了無約束的極大極小值問題，首先將極大極小值問題轉化為一般連續約束優化問題，然后對轉化后的約束優化問題利用可微的罰函數方法進行求解；Ma等［6］借用了文獻［5］的方法，考慮了帶等式約束的極大極小值問題，利用一個新罰函數方法對轉化后的約束優化問題進行求解。

受到文獻［5-6］的啟發，本文在文獻［6］的研究基礎上，考慮含不等式約束的極大極小值問題，提出基于簡單精確光滑罰函數方法的求解問題（1）的一個新算法。

1 簡單精確光滑罰函數

定義集合：T=｛（x，z）∈Rn+1：fi（x）-z≤0，?i=1，…，q；gi（x）≤0，i=q+1，…，m｝，則問題（2）可以等價為下列優化問題：

其中ωi∈（0，1）（i=1，…，m）。類似地，定義集合Tε：

Tε=｛（x，z，ε）∈Rn+2：fi（x）-z≤εγωi，?i=1，…，q；gi（x）≤εγωi，i=q+1，…，m｝。

對于問題（6），定義罰函數如下：

其中α、β、γ、δ都是偶的正整數，且

相應的罰問題為：

下面來討論罰函數fσ（x，z，ε）的可微性和精確性。

定理1設（x，z）→（x*，z*）∈T，ε→ε*=0，且γ＞δ＞α＞0，2δ-α＞0，β＞1，

則有：lim fσ（x，z，ε）=fσ（x*，z*，0）=z*，

證明 當ε≠0，0＜1-cε-2δΔ（x，z，ε）＜1時，有0＜ε-2δΔ（x，z，ε）＜c1，即0＜Δ（x，z，ε）＜c1ε2δ，從

而有Δ（x，z，ε）=O（ε2δ），可得：

即

故

其中，

將Δ（x，z，ε）表達式代入式（10-12）以及由關系式（9），可得：

從而，罰函數fσ（x，z，ε）在Rn+2上是連續可微的。

引理1 在目標函數fσk（xk，zk，εk）為有限值且εk≠0條件下，如果（xk，zk，εk）∈L（Pσk），則（xk，zk，εk）?Tεk。其中L（Pσk）表示罰問題（Pσ）的局部極小點。

證明目標函數fσk（xk，zk，εk）為有限值且εk≠0，（xk，zk，εk）∈L（Pσk），所以，可以得到：

若（xk，zk，εk）∈Tεk，則βεβ-1σk≠0，矛盾。所以（xk，zk，εk）?Tεk。

定理2如果（xk，zk，εk）∈L（Pσk），在目標函數fσk（xk，zk，εk）為有限值，且εk≠0時，設（xk，zk，εk）（x*，z*，ε*）（x*）（i=q+1，…，m）在x*處滿足EMFCQ條件，則ε*=0，（x*，z*）∈T。

證明由εk≠0，（xk，zk，εk）∈L（Pσk）及關系式（10-12），可以得到：

由式（15），可以得到：

在式（16）兩端，令k→+∞，則式子的前三項都是有限值，而且

又由式（14）可以得到：

從而可得：

fi（x*）-z*-（ε*）γωi≤0，i=1，…，q，即fi（x*）-z*≤（ε*）γωi，?i=1，2，…，q。

由式（13）可得：

在x*處，定義如下指標集：

I0（x*）=｛i∈I：gi（x*）=0｝，

I+（x*）=｛i∈I：gi（x*）≥0｝，

I-（x*）=｛i∈I：gi（x*）＜0｝，

其中，I=｛i｜i=q+1，…，m｝。

由假設Δgi（x*）在x*處是滿足EMFCQ條件，即在x*處，?p∈Rn，使得：Δ

假設I+（x*）I0（x*）≠?，則至少存在某個i∈I+（x*）I0（x*），使得

所以有：

矛盾。所以I+（x*）I0（x*）=?，即I+（x*）=I0（x*）。而I=I+（x*）∪I0（x*）∪I-（x*）。所以gi（x*）≤0，i∈I。因此，

即（x*，z*）∈T0。

定理3如果（xk，zk，εk）∈L（Pσk），在目標函數fσk（xk，zk，εk）為有限值且εk≠0時，α、β、γ、δ滿足-α-β+2δ≥0，-α-β+δ+γ≥0，那么存在k0＞0，當k≥k0時，εk=0，（xk，zk）∈L（P）。

證明假設這個定理是不成立的。設存在一個子列｛（xnk，znk，εnk）｝?｛（xk，zk，εk）｝，對于任意的k0＞0k0＞0，當nk≥k0，εnk≠0時，由目標函數fσnk（xnk，znk，εnk）為有限值且εnk≠0，由引理1，有（xnk，znk，εnk）?Tεn，因此，由式（15）可得：

k

由定理2，有：εnk→ε*=0，（xnk，znk）→（x*，θ*）∈T。又由εnk≠0，0＜1-cεn-2δkΔ（xnk，znk，εnk）＜1，可以得到：

由題設：-α-β+2δ≥0，-α-β+δ+γ≥0，式（18）左邊不可能等于0，矛盾。因此，不可能存在這樣子列。所以，存在k0＞0，當k≥k0時，有：εk=0，（xk，zk，0）∈L（Pσk），此時xk和zk滿足：

因此，由（xk，zk，0）∈L（Pσk）知，存在點（xk，zk，0）某個鄰域U，對任意（x，z，0）∈U∩（T×｛0｝），有：zk=fσk（xk，zk，0）≤fσk（x，z，0）=z。所以，（xk，zk）∈L（P）。

在這部分，針對問題（2）給出了一個新的簡單精確光滑罰函數，通過證明，當罰參數σ足夠大時，罰問題的局部極小點也是原問題的局部極小點。

2 數值算例

為了驗證本文提出方法的有效性，下面給出兩個數值算例，且算例在Matlab 7.5.0編程環境下運行。

算例1［7］

其中f1（x）=+，f2（x）=（2-x1）2+（2-x2）2，f3（x）=2exp（-x1+x2）。在文獻［7］中，初始點設為x（0）=（0，0），最優解為x*=（1，1），對應最優目標函數值為2。利用本文提出的罰函數方法，取參數值分別為：α=2，β=6，δ=4，γ=6，ω=0.05，初始點為x（0）=（0，0），ε0=3，得到如表1數值結果。

表1 算例1的數值結果

算例2［7］

其中，f1（x）=（x1-2）2+（x2-1）2，f2（x）=（3x1+ x2-4）2。在文獻［7］中，取初始點為x（0）=（2，2），最優解x*=（1，1），最優目標函數值為1。利用本文提出的罰函數方法，取參數值分別為：α=2，β=6，δ=4，γ=6，ω=0.05，初始點為：x（0）=（2，2），ε0=2。

算例的數值結果見表2。

表2 算例2的數值結果

從以上兩個算例可以看到，通過適當的選取相關參數，當罰參數σ取的不是很大時，就可以得到原問題的最優解，從而說明本文給出的罰函數方法對于求解含約束的極大極小值問題是可行的。

3 結 論

本文在理論上給出了求解極大極小值問題的罰函數方法，并證明了該方法的可行性。文中給出的罰函數不同于傳統的罰函數，同時具有光滑性和精確性，而且不論原問題約束函數有多少個，罰問題與原問題比較，其變量僅增加了一維。因此，對于目標函數和約束函數都是連續的極大極小值問題，本文提供了光滑化的求解途徑。

本方法由于罰函數中用到的參數比較多，在算法設計時需要不斷地對參數進行調整，影響算法的效率。在之后的研究中，將考慮構造參數較少的精確光滑罰函數。

［1］Polak E，Mayne D H，Higgins J E.Superlinearly convergent algorithm for min-max problems［J］.Journal of Optimization Theory and Applications，1991，69（3）：407-439.

［2］Gaudioso M，Monaco M F.A buddle type approach to the unconstrained minimization of convex nonsmooth functions［J］.Mathmatical Programming，1982，23（1）：216-226.

［3］李興斯.解非線性極大極小值問題的凝聚函數法［J］.計算結構力學及其應用，1991，8（1）：86-92.

［4］Huyer W，Neumaier A.A new exact penalty function［J］.SIAM Journal of Optimization.2003，13（4）：1141-1158.

［5］Di Pillo G，Grippo L，Lucidi S.A smooth method for the finite minimax problem［J］.Mathematical Programming，1993，60：187-214.

［6］Ma C，Li X，Cedric Yiu K F，et al.New exact penalty function for solving constrained finite min-max problems［J］.Applied Mathematics and Mechanics，2012，33（2）：253-270.

［7］唐煥文，張立衛，王雪華.一類約束不可微優化問題的極大熵方法［J］.計算數學，1993，15（3）：268-275.

PenaIty Function Method for SoIving Finite Min-Max ProbIem IncIuding InequaIity Constraints

ZHENG Fang-ying
（School of Sciences，Zhejiang Sci-Tech University，Hangzhou 310018，China）

A new simple exact and smooth penalty function is constructed to solve min-max problem of inequality constraints.Firstly，through adding a variable，min-max problem including inequality constraints is transformed to equivalent continuous constraint optimization problem.Then，equivalent continuous constraint optimization problem is solved with new simple exact and smooth penalty function.Under extended-MF constraint standard conditions，it is proved that when the penalty parameter is sufficiently large，local minimum point of unconstrained optimization problem is also local minimum point of the original min-max problem.The calculation results show this penalty function method is an effective approach for solving min-max problem including inequality constraints.

constraint optimization problem；unconstrained optimization problem；penalty function method；min-max problem

O221.2

A

（責任編輯：康 鋒）

1673-3851（2014）05-0559-06

2014-03-31

國家自然科學基金（51075421）；浙江理工大學科研啟動基金（1206830-Y）

鄭芳英（1979-），女，浙江衢州人，博士，講師，主要從事非線性最優化理論研究。