鄭芳英， 張連生

(1.上海大學(xué)理學(xué)院，上海200444;2.浙江理工大學(xué)數(shù)學(xué)科學(xué)系，杭州310018)

本研究考慮如下的約束優(yōu)化問題：

式中，f，hj，gl∈C1，C1表示連續(xù)可微函數(shù)集，E，I分別表示等式約束函數(shù)以及不等式約束函數(shù)的指標(biāo)集，并且E={1，2，…，m}，I={1，2，…，k}，“L-min”表示所求的問題為局部極小問題.

到目前為止，有很多方法可用于求解一般約束優(yōu)化問題(P)，如序列二次規(guī)劃(sequential quadratic programming，SQP)方法、SQP信賴域法、慮子法［1］以及罰函數(shù)方法等，其中罰函數(shù)方法［2-8］是求解約束優(yōu)化問題的重要途徑之一.罰函數(shù)方法是通過罰函數(shù)將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題或僅含簡單約束的優(yōu)化問題，從而可以利用無約束優(yōu)化問題的求解算法來求解約束優(yōu)化問題.傳統(tǒng)的罰函數(shù)，要么是簡單精確，但非光滑的，如l1精確罰函數(shù)［9］;要么是簡單光滑，但非精確的，如二次罰函數(shù)［10］;要么是精確光滑，但非簡單的，如增廣拉格朗日罰函數(shù)［11-12］.這里的“簡單”是指罰函數(shù)的表達(dá)式中僅含目標(biāo)函數(shù)和約束函數(shù)，而不含其梯度信息.

通過增加一個變量，Huyer等［13］針對含箱子約束的等式約束優(yōu)化問題，給出了一個新的簡單精確罰函數(shù)fσ(x，ε)，并且得到了如下結(jié)論：當(dāng)σ＞0充分大及 ε＞0時，罰問題(Pσ)不存在 KKT(Karush-Kuhn-Tucher)點(diǎn).特別地，對于充分大的σ＞0，具有有限目標(biāo)函數(shù)值的罰問題(Pσ)的每個局部極小點(diǎn)(xσ，εσ)，都具有(xσ，0)形式，且xσ為原問題(P)的一個局部極小點(diǎn).但在實(shí)際計(jì)算中，當(dāng)ε＞0時，僅能計(jì)算罰問題的KKT點(diǎn).另一方面，文獻(xiàn)［13］中給出的罰函數(shù)在ε=0處是不可微的，這在實(shí)際計(jì)算中會受到很多的限制.

受到文獻(xiàn)［13］的啟發(fā)，本研究針對一般約束優(yōu)化問題(1)，給出了一個新的簡單精確光滑罰函數(shù).在較弱的約束品性的假設(shè)下，首先證明所給出的罰函數(shù)在ε=0處是連續(xù)可微的.對充分大的罰參數(shù)σ＞0，具有有限目標(biāo)函數(shù)值的罰問題(Pσ)的每個局部極小點(diǎn)(xσ，εσ)，都具有(xσ，0)形式，且xσ為原問題(P)的一個局部極小點(diǎn).針對新的罰函數(shù)，本研究給出了兩個數(shù)值算例及計(jì)算結(jié)果，并提出了一些未來需要解決的問題.

1 一個新的簡單精確光滑罰函數(shù)

對問題(1)，定義如下集合：

式中，wj，wl∈(0，1)，j∈E，l∈I.L(P)：問題(P)的局部極小點(diǎn)構(gòu)成的集合.顯然，S=Sε0，因此，下面的問題與問題(1)等價(jià)：

相應(yīng)地，罰函數(shù)fσ(x，ε)及罰問題(Pσ)如下：

下面討論所給出的罰函數(shù)fσ(x，ε)的光滑性和精確性.

定理1 當(dāng)參數(shù)α，β，γ，δ以及N滿足一定條件時，罰函數(shù)fσ(x，ε)在{(x，ε)∈Rn+1：ε=0，x∈S或者ε≠0，0＜1-cε-NδΔ(x，ε)≤1}上連續(xù)可微.

證明 記Δ(x，ε)fσ(x，ε)為fσ(x，ε)的梯度，則對任意的(x，ε)∈Rn+1，有

若ε=0，x∈S，則

若ε≠0，0＜1-cε-NδΔ(x，ε)≤1，則

當(dāng)ε≠0，0＜1-cε-NδΔ(x，ε)＜1，ε→ε*=0時，有Δ(x，ε)=O(εNδ)，從而有

整理得

當(dāng)x→x*∈S，ε→0時，有

事實(shí)上，滿足式(5)的α，β，γ，δ以及N是存在的，例如取N=2，γ＞1，δ＞α，β＞1時，式(5)成立.因此，函數(shù)fσ(x，ε)在{(x，ε)∈Rn+1：ε=0，x∈S或者ε≠0，0＜1-cε-NδΔ(x，ε)≤1}上連續(xù)可微.

下面討論罰函數(shù)fσ(x，ε)的精確性，即在一定條件下，證明存在σ0＞0，當(dāng)σ≥σ0時，罰函數(shù)的局部極小點(diǎn)具有(xσ，εσ)形式.這里εσ=0，且xσ為原問題的一個局部極小點(diǎn).

引理1 如果(x(k)，εk)∈L(Pσk)，其函數(shù)值fσk(x(k)，εk)為有限值，εk≠0，且參數(shù)α，β，γ，δ，N滿足式(5)，則(x(k)，εk)?Sεk.

顯然，當(dāng)εk≠0時，σkβ＞0，從而式(6)矛盾，故(x(k)，εk)?Sεk.

證明 由題設(shè)條件知

由式(8)可得

由式(7)可得

假設(shè)I+(x*，ε*)I0(x*，ε*)≠?，其I0(x*，ε*)={l：gl(x*)=ωl，l∈I}，則至少存在 l0∈I+(x*，ε*)I0(x*，ε*)，滿足gl0(x*)-ωl0＞0.根據(jù)題設(shè)，M-F約束品性在x*處成立，因此，存在p∈Rn，使得下式成立：

由式(12)，有

定理3 如果定理2的條件成立，并且參數(shù)α，β，γ，δ，N滿足相應(yīng)的條件，則存在k0＞0，使得當(dāng)k≥k0時，有εk=0，xk∈L(P).

即

另一方面，根據(jù) fσ(x，ε)的定義以及函數(shù)值fσk(x(k)，0)為有限值，可知x(k)∈S.因?yàn)?x(k)，0)∈L(Pσk)，即存在(x(k)，0)的一個鄰域 o((x(k)，0)，ρk)，ρk＞0，對任意的點(diǎn)(x，0)∈o((x(k)，0)，ρk)，x∈S，f(x(k))=fσk(x(k)，0)≤fσk(x，0)=f(x)都成立，即x(k)∈L(P)，所以定理成立.證畢.

2 數(shù)值算例

基于軟件Matlab 7.0的環(huán)境，利用Matlab的庫函數(shù)fmincon來求解罰問題(Pσ)，從而驗(yàn)證所給出的罰函數(shù)對于求解約束優(yōu)化問題是有效的.表1和表2分別為兩個算例的數(shù)值結(jié)果，其中分別列出了罰參數(shù)σk，最后得到的最優(yōu)解x(k)，εk以及相應(yīng)的目標(biāo)函數(shù)值f(x(k)).

(1)問題1.

該問題為一個二次規(guī)劃問題，存在18個局部極小值點(diǎn).在該算例中，我們?nèi)ˇ?β=2，δ=4，γ=10，ω= 0.005，N=4，選取初始點(diǎn)為x(0)=(0.000 0，0.000 0，0.000 0，0.000 0，0.000 0，0.000 0)，ε0=2，從而得到其中一個局部極小點(diǎn)為x*=(0.000 0，0.000 0，5.000 0，0.000 0，5.000 0，0.000 0)，極小值為f(x*)=-168.000 0，具體計(jì)算結(jié)果如表1所示.

(2)問題2.在該算例中，我們?nèi)ˇ?2，β=4，δ=2，γ=2，N=4，ω=0.05，選取初始點(diǎn) x(0)=(0.000 0，0.000 0，0.000 0)，ε0=2，從而得到問題2的極小點(diǎn)為x*= (1.000 0，-1.000 0，1.000 0)，對應(yīng)的極小值為f(x*)=-7.000 0，具體計(jì)算結(jié)果如表2所示.

表1 問題1的數(shù)值結(jié)果Table 1 Numerical results of Problem 1

表2 問題2的數(shù)值結(jié)果Table 2 Numerical results of Problem 2

3 結(jié)束語

本研究得到了求解約束優(yōu)化問題的一個新的方法——簡單光滑精確罰函數(shù)法.對于約束優(yōu)化問題是否存在具有二次可微的簡單精確罰函數(shù)，還需要進(jìn)一步的研究和探討.

［1］ FLETCHERR，LEYFFERS，TOINTP L.On the global convergence of a filter-SQP algorithm［J］.SIAM Journal on Optimization，2002，13(1)：44-59.

［2］ PILLOG D I.Exact penalty methods［M］.Netherlands：Kluwer Academic Publisher，1994：209-253.

［3］ PILLOG D I，GRIPPOL.Exact penalty functions in constrained optimization［J］.SIAM Journal on Control and Optimization，1989，27(6)：1333-1360.

［4］ PILLOG D I，GRIPPOL.An exact penalty function method with global convergence properties for nonlinear programming problems［J］.Mathematical Programming，1986，36：1-18.

［5］ PILLOG D I，LUCIDIS.An augmented Lagrangian function with improved exactness properties［J］.SIAM Journal on Optimization，2002，12(2)：376-406.

［6］ FLETCHERR.An exact penalty function for nonlinear programming with inequalities［J］. Mathematical Programming，1973，5：129-150.

［7］ FLETCHERR.Practical methods of optimization(2)：constrained optimization［M］.Wiley：John Wiley＆Sons，1981.

［8］ HANS P，MAGASARIANO L.Exact penalty functions in nonlinear programming［J］.Mathematical Programming，1979，17：251-269.

［9］ ZANGWILLW I.Nonlinear programming via penalty functions［J］.Management Science，1967，13：344-358.

［10］ FIACCOA V，MCCORMICKP.Nonlinear programming：sequential unconstrained minimization techniques［M］.Wiley：John Wiley＆Sons，1968.

［11］ HESTENESM R.Multiplier and gradient methods［J］.Journal of Optimization Theory and Applications，1969，4：303-320.

［12］ POWELLM J D.On the convergence of the variable metric algorithm ［J］.JournaloftheInstituteof Mathematics and Its Applications，1971，7：21-36.

［13］ HUYERW，NEUMAIERA.A new exact penalty function［J］.SIAM Journal on Optimization，2003，3(4)：1141-1158.