王祝君，朱德通

（1.湖南工程學(xué)院 理學(xué)院，湘潭 411104；2.上海師范大學(xué) 數(shù)理學(xué)院，上海 200234）

本文討論下面的非線性等式和有界約束優(yōu)化問題：

嚴(yán)格內(nèi)部用int（Ω）：｛x∈Rn：c（x）＝0，a＜x＜b｝表示.假設(shè)函數(shù)f（x）和c（x）在Ω的開鄰域上二次連續(xù)可微.我們采用Coleman和Li的仿射內(nèi)點(diǎn)牛頓方法，結(jié)合利用Fletcher罰函數(shù)的過濾法解這種非線性等式和有界約束優(yōu)化問題.

文獻(xiàn)［1］中證明了Coleman－Li的方法在合適的假設(shè)下，是局部超線性收斂的，其中包括了嚴(yán)格互補(bǔ)性假設(shè)，即對(duì)所有的i∈｛1，……，n｝，有x（i）＊∈｛a（i），b（i）｝?［▽f（x＊）（i）］≠0，其中x＊是只帶簡單有界約束最優(yōu)化問題的解.

過濾方法會(huì)遭遇 Maratos效應(yīng)［3］.Maratos效應(yīng)之所以出現(xiàn)是由于用來判別迭代點(diǎn)好壞的價(jià)值函數(shù)是非光滑的，如果價(jià)值函數(shù)是光滑函數(shù)，就可避免Maratos效應(yīng).我們利用Fletcher罰函數(shù)作為價(jià)值函數(shù)，與之相結(jié)合的過濾方法既可以保持算法的總體收斂性，也避免了使用二階校正步.

本文中第1節(jié)給出完整的算法，包含了計(jì)算搜索方向的仿射內(nèi)點(diǎn)牛頓法和確定步長的過濾線搜索方法.第2節(jié)匯報(bào)了數(shù)值結(jié)果.

1 算法

設(shè)問題（1）的Lagrange函數(shù)為L（x，λ，υ，μ）：＝l（x，λ）－υT（x－a）－μY（b－x），其中l(wèi)（x，λ）＝f（x）＋λTc（x），λ∈Rm，0≤∈Rn，0≤μ∈Rn是 Lagrange乘子.假設(shè)可行性滿足，x是問題的局部極小點(diǎn)，則一階KKT必要條件是存在三個(gè)向量λ，υ，μ使得

其中▽xl（x，λ）＝g（x）＋A（x）λ，g（x）是f（x）的梯度，A（x）表示約束函數(shù)c（x）的梯度.忽略原始和對(duì)偶可行性，一階必要條件可寫成

本文中，設(shè)v（i）表示向量v的第i個(gè)分量.

如果對(duì)每個(gè)i，由（▽xl）（i）＝0可得a（i）＜x（i）＜b（i），則稱點(diǎn)x∈Ω是非退化的.如果上面的條件對(duì)每個(gè)x∈Ω滿足，則稱問題（1）是非退化的.

受Coleman和Li在［1］中用仿射內(nèi)點(diǎn)算法解有界約束優(yōu)化問題的啟示，定義對(duì)角矩陣D（x），其對(duì)角元為

可得問題（1）的一階必要條件：當(dāng)且僅當(dāng)存在λ∈Rm使得

而（2）牛頓步（s，sλ）滿足

試驗(yàn)步長αk，t是可接受的，如果相應(yīng)的試驗(yàn)點(diǎn)xk（αk，t）：＝xk＋αk，tsk提供了Fletcher罰函數(shù)Fρ（x，的充分下降，其中λ（x）是相應(yīng)于等式約束的乘子估計(jì)，ρ是罰參數(shù).若λ（x＊）是相應(yīng)于等式約束優(yōu)化問題

的嚴(yán)格局部解x＊的乘子向量，則存在罰參數(shù)ρ＞0，使得x＊是Fρ（x，λ（x＊））嚴(yán)格局部解.

過濾方法基本思想是把（4）當(dāng)做一個(gè)雙目標(biāo)問題：最小化約束違反和最小化函數(shù)l（x，λ（x））＝f（x）＋λ（x）Tc（x），定義λk（αk，t）＝如果它在當(dāng)前迭代中使上面兩個(gè)目標(biāo)中任一個(gè)的充分下降，即若

對(duì)常數(shù)γh，γl∈（0，1）滿足，就稱試驗(yàn)點(diǎn)xk（αk，t）＝xk＋αk，tsk是可接受的.為避免收斂到可行點(diǎn)而不是最優(yōu)點(diǎn)，我們要求試驗(yàn)點(diǎn)滿足所謂的l－型切換條件

算法用到一個(gè)含（h，l）對(duì)的過濾集Fk?｛（h，l）∈R2：h≥0｝.若（h（xk（αk，t）），l（xk（αk，t）））∈Fk，就說試驗(yàn)點(diǎn)不被當(dāng)前過濾集接受.初始過濾集定義為F0：＝｛（h，l）∈R2：h≥hmax｝，其中hmax＞h（x0）.在迭代過程中，過濾集用校正公式

進(jìn)行擴(kuò)張.當(dāng)被接受的步長或者不滿足l型切換條件（7），或者不滿足 Armijo條件（8）時(shí)，就用（9）擴(kuò)張過濾集.若被接受的步長既滿足（7），又滿足（8），過濾集保持不變.這種方式保證了算法不會(huì)發(fā)生循環(huán).

在試驗(yàn)步不滿足上面所有準(zhǔn)則的情況下，我們用所涉及函數(shù)的線性模型逼近一個(gè)最小步長αmink.當(dāng)αk，t比αmink更小時(shí)，算法轉(zhuǎn)向可行性恢復(fù)階段.可行性恢復(fù)階段的目的是當(dāng)回代線搜索程序不能使目標(biāo)函數(shù)充分下降，步長太小時(shí)，通過減少不可行性，產(chǎn)生一個(gè)擴(kuò)張的過濾集Fk＋1接受的新迭代.

把第一個(gè)等式代入（5），可知若步長滿足αk，t≤，則（5）不成立.同樣，在ωk＜0的情況下，若（6）可能不滿足.

另一方面，因?yàn)樵趩栴}（1）的最優(yōu)點(diǎn)處，a≤x≤b，而且這個(gè)性質(zhì)對(duì)所有的迭代保持.假設(shè)sk∈Rn，αk，t表示沿sk到邊界的步長

考慮｛xk｝的一個(gè)極限點(diǎn).因?yàn)棣羕，t＞0（xk∈int（Ω））且sk的符號(hào)與－▽xl（xk，λk）的符號(hào)相同，容易證明

（2）中的第一個(gè)方程表明了

故由 （13）可得

其中κ2和κ1是與k無關(guān)的正常數(shù).

綜上所述，可概括出下面的最小試驗(yàn)步長

下面是用仿射內(nèi)點(diǎn)過濾線搜索方法解問題（1）的算法.

算法

給定（x0，λ0），其中x0∈int（Ω）?Rn，εtol，0＜τ1），γl∈（0，1），sh＞1，sl≥2sh.

步1.初始過濾集Fk：＝｛（h，l）∈R2：h≥hmax｝，迭代計(jì)數(shù)k←0.

步2.計(jì)算仿射矩陣D（xk）和E（xk）.

步3.檢驗(yàn)收斂性.若‖Dk▽xlk‖＋‖ck‖1≤εtol，停止，否則，轉(zhuǎn)下一步.

步4.從（3）計(jì)算搜索方向（sk，sλk）.

若線性系統(tǒng)是病態(tài)的，轉(zhuǎn)可行性恢復(fù)階段.

步5.回代線搜索.

步5.1.初始化線搜索.設(shè)αk，0且t←0.

步5.2.計(jì)算新的試驗(yàn)點(diǎn).若

αk，t＜由（16）給出，轉(zhuǎn)第9步可行性恢復(fù)階段.否則，計(jì)算試驗(yàn)點(diǎn)xk（αk，t）＝xk＋αk，tsk，λk（αk，t）＝λk＋

步5.3.若xk（αk，t）∈Fk，拒絕試驗(yàn)步長，轉(zhuǎn)第5.5步.

步5.4.檢驗(yàn)當(dāng)前迭代的充分下降性.

步5.4.1情況I：（7）滿足：若 Armijo條件（8）滿足，且a≤xk（αk，t）≤b，接受試驗(yàn)步，轉(zhuǎn)第6步，否則轉(zhuǎn)第5.5步.

步5.4.2情況II：（7）不滿足：若（5）或（6）滿足，且a≤xk（αk，t）≤b，接受試驗(yàn)步，轉(zhuǎn)第6步，否則轉(zhuǎn)第5.5步.

步5.5.設(shè)αk，t＋1＝τ·αk，t，t←t＋1，回到第5.2步.

步6.接受試驗(yàn)點(diǎn).設(shè)

步7.如果k不是l－型迭代，用（9）擴(kuò)張過濾集.否則，設(shè)Fk＋1∶＝Fk.

步8.設(shè)k＝k＋1，回到第2步.

步9.可行性恢復(fù)階段.通過下降不可行度量h計(jì)算新的迭代xk＋1，使得xk＋1滿足（5）－（6），從而可被過濾集接受.用（9）擴(kuò)張過濾集，從第8步繼續(xù)迭代.

2 數(shù)值結(jié)果

本文中所有的程序都用Matlab 7.0編寫，并在帶配置為1.7Ghz celeron和512DDRAM的PC微機(jī)上運(yùn)行.測試題取自文獻(xiàn)［2］，問題自變量的維數(shù)從2到5，約束的個(gè)數(shù)從1到3.初始點(diǎn)取文獻(xiàn)［2］中問題提供的初始點(diǎn)，常數(shù)值分別為λ0＝1，εtol＝10－6，τ＝0.5，hmax＝104max｛1，h（x0）｝，ηl＝0.3 ，δ＝1 ，γh＝0.01，γl＝0.01，sh＝1.5，sl＝3.2.Lagrange函數(shù)的Hessian陣用有限差分近似.算法都取得了文獻(xiàn)［2］中給出的參考最優(yōu)函數(shù)值.詳細(xì)的數(shù)值結(jié)果在表2中列出，其表頭中字母的意思列在表1中.數(shù)值結(jié)果表明所提的算法是有效的.

表1 表2中字母的意義

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

［1］T.F.Coleman and Y.Li.An Interior Trust Region Approach for Nonlinear Minimization Subject to Bounds［J］.SIAM J.Optim.，1996，6：418－445.

［2］W.Hock，K.Schittkowski，Test Examples for Nonlinear Programming Codes［M］.Springer－Verlag，Berlin，1981.

［3］A.Wachter and L.Biegler.Line Search Filter Methods for Nonlinear Programming：Local Convergence［J］.SIAM J.Optim.，2005，16：32－48.

［4］A.Wachter and L.Biegler.Line Search Filter Methods for Nonlinear Programming：Motivation and Global Convergence［J］.SIAM J.Comput.，2005，16：1－31.