帶3-分片NCP函數(shù)的無罰函數(shù)和濾子的SQP算法

周 敏，尚有林

（河南科技大學數(shù)學與統(tǒng)計學院，河南 洛陽 471023）

帶3-分片NCP函數(shù)的無罰函數(shù)和濾子的SQP算法

周 敏，尚有林

（河南科技大學數(shù)學與統(tǒng)計學院，河南 洛陽 471023）

對于非線性約束優(yōu)化問題，提出了一種新的無罰函數(shù)和濾子的SQP算法。根據(jù)優(yōu)化問題的一階KKT條件，利用乘子和3-分片NCP函數(shù)，得到非光滑方程以致簡化優(yōu)化問題。在線搜索的過程中，采用無罰函數(shù)和濾子的方法。同時證明了該SQP算法是可行的，并具有全局收斂性。

濾子；SQP算法；收斂；NCP函數(shù)

0 引言

考慮如下的約束非線性規(guī)劃問題（NLP）：

其中，x∈?n，f：?n→?，Ci：?n→?，都是二次連續(xù)可微函數(shù)。

非線性規(guī)劃問題（NLP）的拉格朗日函數(shù)為：

其中，λ＝（λ1，…，λm）T∈?m是乘子向量。

問題（2）是一種非線性互補問題（NCP）。由于NCP函數(shù)的各種性質(zhì)引起了廣泛的關注，一個解決非線性互補問題（2）的方法是構建一個可求解的非線性方程：Φ（x，λ）＝0。為了避免實際問題中懲罰參數(shù)的設置，F(xiàn)letcher第一次提出了關于求解約束非線性優(yōu)化問題的濾子方法［1］，同時定義了約束違反度函數(shù)

Gould和Toint提出了一種新的無罰函數(shù)和濾子的方法，這個方法被證明是全局收斂性的，并用于SQP方法或信賴域SQP方法關于非線性等式約束問題的求解［2－6］。

本文對于非線性約束優(yōu)化問題，提出了一種新的無罰函數(shù)和濾子的SQP算法。根據(jù)優(yōu)化問題的一階KKT條件，利用乘子和3-分片NCP函數(shù)，得到非光滑方程以致簡化優(yōu)化問題。在線搜索的過程中，采用無罰函數(shù)和濾子的方法。對給出的新的SQP算法，證明了該算法是可實現(xiàn)的，并進一步討論了該算法的收斂性。

1 預備知識

定義1函數(shù)φ：?2→?，如果有

則稱φ為一個NCP函數(shù)。

較為常用的NCP函數(shù)有F-B NCP函數(shù)、極小化NCP函數(shù)、3-分片線性NCP函數(shù)等，對于其他的NCP函數(shù)及其性質(zhì)，見文獻［7－8］。

本文采用3-分片線性NCP函數(shù)來求解，形式如下：

式中，φ是除原點外處處可微函數(shù)，但是在原點處是強半光滑。

為了充分利用NCP函數(shù)與KKT條件間的關系和NCP函數(shù)幾乎處處可微的性質(zhì)，本文改造濾子中的度量，將約束違反度函數(shù)p（x）修正為：

對于一個給定的迭代點xk∈?n，即問題（NLP）的局部最優(yōu)解xk的當前估計，解如下問題QP（xk，d）得dk（同時可以得到問題QP（xk，d）對應的乘子λk），

其中，Hk是拉格朗日函數(shù)的近似Hessian陣表示歐幾里得范數(shù)。

函數(shù)f（xk）的真實下降量

f（xk）的預測下降量

f（xk）的充分下降條件表示為：

其中，τ是某一個常數(shù)。

選擇xk＋1為下一個迭代點，則xk＋1滿足

需要指出的是，若xk＋dk不滿足式（7）～式（9），但是卻很接近最優(yōu)解，即出現(xiàn)了所謂的Maratos效應，為了克服此現(xiàn)象，計算二階校正步（SOC），即解決如下子問題

2 新的SQP算法

2.1 S0：初始化

2.2 S1：計算QP（xk，△k）

S1.1 如果QP（xk，△k）是不可行的，進入恢復性階段，找到一個點xk＋1，直至使QP（xk＋1，△k＋1）可行，返回S1；

S1.2 如果QP（xk，△k）是可行的，得到dk，置xk＋1＝xk＋dk，進入S2。

2.3 S2：判斷終止條件

S2.1 如果dk＝0，停止，得到KKT點xk；

S2.2 如果dk≠0，計算拉格朗日乘子λk，同時計算△f和△q，進入S3。

2.4 S3：無罰函數(shù)和濾子的線搜索

S3.1 如果（xk＋1，λk）滿足式（7）～式（9），進入S4；

S3.2 如果（xk＋1，λk）不滿足式（7）～式（9），計算SOC（QPs（xk，△k）），得到，記，進入S3.3；

S3.3 如果（xk＋1，λk）不滿足式（7）～式（9），減小信賴域半徑△k＋1和計算QP，返回S1。

2.5 S4：判斷充分下降條件

S4.1 如果xk＋1不滿足式（4）～式（6），減小信賴域半徑△k和計算QP，返回S1；

S4.2 如果xk＋1滿足式（4）～式（6），更新信賴域半徑△k和Bk＋1。如果xk＋1滿足式（7）而xk不滿足，則，否則。如果式（7）滿足，則，否則置rk＋1＝rk。置k＝ k＋1返回S1。

在算法中，當問題不相容或者信賴域半徑小于事先給定的下界時，算法將會進入到恢復階段?；謴碗A段具體算法可以參見文獻［1］。

3 收斂性分析

在下面的分析中，需要如下假設：

A1 目標函數(shù)f和約束函數(shù)ci（x）都是二次連續(xù)可微的。

A2 算法產(chǎn)生的所有迭代點均位于一個有界緊凸集S中。

A3 存在正常數(shù)a、b，使得Hessian陣Hk滿足，?k和d∈?n成立。

A4 子問題QP（xk，△k）的KKT乘子λk一致有界，QPs（xk，△k）的KKT乘子k一致有界。

證明根據(jù)S2～S4，得到是單調(diào)遞減并且

由于k≥k1時，｛fk｝是單調(diào)遞減的，同時式（11）表明當k→∞時，有f（xk）→－∞，這與假設矛盾。

故引理得證。

算法有3個不成功（即xk＋1＝xk）的循環(huán)

循環(huán)1 S1.2-S2.2-S3.1-S4.1-S1；

循環(huán)2 S1.2-S2.2-S3.1-S4.2-S1；

循環(huán)3 S1.2-S2.2-S3.2-S3.3-S1。

為了說明算法是有效的，迭代是成功的，即上述的3個循環(huán)是有限終止的，給出以下3個引理：

引理2算法中循環(huán)1是有限終止的。

引理3算法中循環(huán)2是有限終止的。

引理4算法中循環(huán)3是有限終止的。

在第2部分新的SQP算法的迭代過程中，xk＋1＝xk＋dk或者xk＋1＝xk＋dk＋k成立，因此，可以看出引理2～引理4是成立的，即第2部分給出的新的SQP算法是可執(zhí)行的。

由A1～A4是成立的，給出算法的全局收斂性定理。

定理1由算法產(chǎn)生的序列有如下情況：

（Ⅰ）迭代到問題（NLP）的KKT點；

（Ⅱ）至少存在一個聚點是問題（NLP）的KKT點。

該算法的證明類同于文獻［9］。

4 結束語

綜上所述，本文提出了一種新的無罰函數(shù)和濾子的SQP算法，其中該算法是基于3-分片NCP函數(shù)。由此類推也可將本文中的方法用于4-分片NCP函數(shù)或者其他的NCP函數(shù)，繼而可得到相似的結論。

［1］ Fletcher R，Leyffer S.Nonlinear Programming Without a Penalty Function［J］.Math Programming，2002，91（2）：239－269.

［2］ Fletcher R，Leyffer S，Toint P.On the Global Convergence of a Filter-SQP Algorithm［J］.SIAM J Optim，2002，12：44－59.

［3］ Panier E R，Tits A L，Herskovits J N.A QP-free，Globally，Locally Superlinear Convergent Method for the Inequality Constrained Optimization Problems［J］.SIAM J Control Optim，1988，36：788－811.

［4］ Pu D，Li K，Xue W.Convergence of QP-free Infeasible Methods for Inequality Optimization Problems［J］.J of Tongji University，2005，33：525－529.

［5］ Liu X，Yuan Y.A Sequential Quqdratic Programming Method a Penalty Function and a Filter for Equality Constrained Nonlinear Programming［J］.SIAM J on Optimization，2011，91：545－571.

［6］ Ulbrich M，Ulbrich S.Non-monotone Trust Region Methods for Nonlinear Equality Constrained Optizization Without a Penalty Function［J］.Math Program，2003，95：103－135.

［7］ Galantai A.Properties and Construction of NCP Functions［J］.Comput Optim Appl，2012，52（3）：805－824.

［8］ Pu D，Zhou Y.Piecewise Linear NCP Function for QP-free Feasible Method［J］.Applied Mathematics，2006，21：289－301.

［9］ Su K.Trust-region Filter Method with NCP Function［J］.Math，2008，28（12）：1525－1534.

O224

A

1672－6871（2014）04－0082－04

國家自然科學基金項目（10971053）；河南省自然科學基金項目（094300510050）

周 敏（1987－），女，河南三門峽人，碩士生；尚有林（1963－），男，河南洛陽人，教授，博士，博士生導師，主要研究方向為非線性規(guī)劃.

2013－10－29