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

鄭芳英

（浙江理工大學(xué)理學(xué)院，杭州310018）

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

鄭芳英

（浙江理工大學(xué)理學(xué)院，杭州310018）

構(gòu)造一個(gè)新的簡(jiǎn)單精確光滑罰函數(shù)來求解含不等式約束極大極小值問題。首先通過添加一個(gè)變量，將含不等式約束的極大極小值問題轉(zhuǎn)化為與之等價(jià)的連續(xù)約束優(yōu)化問題，然后利用新的簡(jiǎn)單精確光滑罰函數(shù)，對(duì)等價(jià)的連續(xù)約束優(yōu)化問題進(jìn)行求解。在擴(kuò)展的MF約束規(guī)范條件下，可以證明：當(dāng)罰參數(shù)充分大時(shí)，無約束優(yōu)化問題的局部極小點(diǎn)也是原極大極小值問題的局部極小點(diǎn)。算例結(jié)果表明，給出的罰函數(shù)方法可有效地求解含不等式約束的極大極小值問題。

約束優(yōu)化問題；無約束優(yōu)化問題；罰函數(shù)方法；極大極小值問題

0 引 言

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

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

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

罰函數(shù)方法是求解連續(xù)約束優(yōu)化問題的一種重要方法，其思想是將約束優(yōu)化問題轉(zhuǎn)化為無約束或僅含簡(jiǎn)單約束的優(yōu)化問題來求解。但是傳統(tǒng)的罰函數(shù)要么簡(jiǎn)單精確，但不是光滑的，如l1精確罰函數(shù)；要么光滑，但不是精確的，如二次罰函數(shù)；要么光滑精確的，但不是簡(jiǎn)單的。這里的“簡(jiǎn)單”是指罰函數(shù)中僅含目標(biāo)函數(shù)及約束函數(shù)，而不含其梯度的信息。

2003年，Huyer等［4］通過增加一個(gè)變量，針對(duì)下式約束優(yōu)化問題（3）給出了一個(gè)新的簡(jiǎn)單精確罰函數(shù)。

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

相應(yīng)的罰問題為：

在一些常規(guī)的假設(shè)下，文獻(xiàn)［4］證明了罰問題（5）的局部極小點(diǎn)正好也是原問題（3）的局部極小點(diǎn)；同時(shí)證明，對(duì)于問題（5），當(dāng)ε＞0時(shí)，對(duì)于充分大的σ，問題（5）不存在KKT點(diǎn)，而通常算法得到的點(diǎn)是KKT點(diǎn)。

Di Pillo等［5］考慮了無約束的極大極小值問題，首先將極大極小值問題轉(zhuǎn)化為一般連續(xù)約束優(yōu)化問題，然后對(duì)轉(zhuǎn)化后的約束優(yōu)化問題利用可微的罰函數(shù)方法進(jìn)行求解；Ma等［6］借用了文獻(xiàn)［5］的方法，考慮了帶等式約束的極大極小值問題，利用一個(gè)新罰函數(shù)方法對(duì)轉(zhuǎn)化后的約束優(yōu)化問題進(jìn)行求解。

受到文獻(xiàn)［5-6］的啟發(fā)，本文在文獻(xiàn)［6］的研究基礎(chǔ)上，考慮含不等式約束的極大極小值問題，提出基于簡(jiǎn)單精確光滑罰函數(shù)方法的求解問題（1）的一個(gè)新算法。

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

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

其中ω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｝。

對(duì)于問題（6），定義罰函數(shù)如下：

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

相應(yīng)的罰問題為：

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

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

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

證明 當(dāng)ε≠0，0＜1-cε-2δΔ（x，z，ε）＜1時(shí)，有0＜ε-2δΔ（x，z，ε）＜c1，即0＜Δ（x，z，ε）＜c1ε2δ，從

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

即

故

其中，

將Δ（x，z，ε）表達(dá)式代入式（10-12）以及由關(guān)系式（9），可得：

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

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

證明目標(biāo)函數(shù)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），在目標(biāo)函數(shù)fσk（xk，zk，εk）為有限值，且εk≠0時(shí)，設(shè)（xk，zk，εk）（x*，z*，ε*）（x*）（i=q+1，…，m）在x*處滿足EMFCQ條件，則ε*=0，（x*，z*）∈T。

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

由式（15），可以得到：

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

又由式（14）可以得到：

從而可得：

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

由式（13）可得：

在x*處，定義如下指標(biāo)集：

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｝。

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

假設(shè)I+（x*）I0（x*）≠?，則至少存在某個(gè)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），在目標(biāo)函數(shù)fσk（xk，zk，εk）為有限值且εk≠0時(shí)，α、β、γ、δ滿足-α-β+2δ≥0，-α-β+δ+γ≥0，那么存在k0＞0，當(dāng)k≥k0時(shí)，εk=0，（xk，zk）∈L（P）。

證明假設(shè)這個(gè)定理是不成立的。設(shè)存在一個(gè)子列｛（xnk，znk，εnk）｝?｛（xk，zk，εk）｝，對(duì)于任意的k0＞0k0＞0，當(dāng)nk≥k0，εnk≠0時(shí)，由目標(biāo)函數(shù)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，可以得到：

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

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

在這部分，針對(duì)問題（2）給出了一個(gè)新的簡(jiǎn)單精確光滑罰函數(shù)，通過證明，當(dāng)罰參數(shù)σ足夠大時(shí)，罰問題的局部極小點(diǎn)也是原問題的局部極小點(diǎn)。

2 數(shù)值算例

為了驗(yàn)證本文提出方法的有效性，下面給出兩個(gè)數(shù)值算例，且算例在Matlab 7.5.0編程環(huán)境下運(yùn)行。

算例1［7］

其中f1（x）=+，f2（x）=（2-x1）2+（2-x2）2，f3（x）=2exp（-x1+x2）。在文獻(xiàn)［7］中，初始點(diǎn)設(shè)為x（0）=（0，0），最優(yōu)解為x*=（1，1），對(duì)應(yīng)最優(yōu)目標(biāo)函數(shù)值為2。利用本文提出的罰函數(shù)方法，取參數(shù)值分別為：α=2，β=6，δ=4，γ=6，ω=0.05，初始點(diǎn)為x（0）=（0，0），ε0=3，得到如表1數(shù)值結(jié)果。

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

算例2［7］

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

算例的數(shù)值結(jié)果見表2。

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

從以上兩個(gè)算例可以看到，通過適當(dāng)?shù)倪x取相關(guān)參數(shù)，當(dāng)罰參數(shù)σ取的不是很大時(shí)，就可以得到原問題的最優(yōu)解，從而說明本文給出的罰函數(shù)方法對(duì)于求解含約束的極大極小值問題是可行的。

3 結(jié) 論

本文在理論上給出了求解極大極小值問題的罰函數(shù)方法，并證明了該方法的可行性。文中給出的罰函數(shù)不同于傳統(tǒng)的罰函數(shù)，同時(shí)具有光滑性和精確性，而且不論原問題約束函數(shù)有多少個(gè)，罰問題與原問題比較，其變量?jī)H增加了一維。因此，對(duì)于目標(biāo)函數(shù)和約束函數(shù)都是連續(xù)的極大極小值問題，本文提供了光滑化的求解途徑。

本方法由于罰函數(shù)中用到的參數(shù)比較多，在算法設(shè)計(jì)時(shí)需要不斷地對(duì)參數(shù)進(jìn)行調(diào)整，影響算法的效率。在之后的研究中，將考慮構(gòu)造參數(shù)較少的精確光滑罰函數(shù)。

［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］李興斯.解非線性極大極小值問題的凝聚函數(shù)法［J］.計(jì)算結(jié)構(gòu)力學(xué)及其應(yīng)用，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］唐煥文，張立衛(wèi)，王雪華.一類約束不可微優(yōu)化問題的極大熵方法［J］.計(jì)算數(shù)學(xué)，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

（責(zé)任編輯：康 鋒）

1673-3851（2014）05-0559-06

2014-03-31

國(guó)家自然科學(xué)基金（51075421）；浙江理工大學(xué)科研啟動(dòng)基金（1206830-Y）

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