非線性優(yōu)化問題的光滑化序列二次規(guī)劃方法

宇振盛， 張麗娜， 秦 毅

（上海理工大學(xué) 理學(xué)院，上海 200093）

1 問題的提出

考慮非線性優(yōu)化問題

其中，x∈Rn，f：Rn→R，g：Rn→Rm是連續(xù)可微函數(shù).

此類問題廣泛應(yīng)用于隨機(jī)規(guī)劃、最優(yōu)控制以及半無限規(guī)劃和原始分解算法中［1－3］，在過去的幾十年里，人們已經(jīng)提出了許多數(shù)值方法來解決這一問題.其 中，序 列 二 次 規(guī) 劃 法（sequential quadratic programming，SQP）是使用最廣泛的方法之一，這類算法具有良好的全局收斂性，得到最優(yōu)解時需要的迭代次數(shù)也較少.該方法由Wilson［4］最早針對凸優(yōu)化問題提出，并由Biggs［5］，Han［6］和Powell［7－8］等推廣到一般問題，有關(guān)綜述報告可參見文獻(xiàn)［9］.

由與問題（1）相關(guān)的SQP 理論可知，可以通過迭代公式

來產(chǎn)生出收斂到問題（1）的Karush－Kuhn－Tucker（KKT）點(diǎn)的點(diǎn)列.其中，λk是由某些線搜索方法獲得的，用來降低評價函數(shù)的函數(shù)值的步長，dk是二次規(guī)劃問題

的解.Bk是目標(biāo)函數(shù)的拉格朗日函數(shù)的近似Hessen矩陣，通常由擬牛頓法獲得.

在SQP理論中，最常使用的評價函數(shù)是不可微精確罰函數(shù)

因為函數(shù)Ψ （x ，α） 的不可微性，從而給計算帶來一定的困難.為克服此困難，通常可用光滑的罰函數(shù)作為其評價函數(shù)［10］.本文使用逼近光滑罰函數(shù)［10－11］

來作為SQP算法的評價函數(shù).其中，Φ（x，α，μ）是逼近于Ψ （x ，α） 的，并且是連續(xù)可微的.文獻(xiàn)［11］中的數(shù)值試驗顯示，該光滑罰函數(shù)的性態(tài)良好.

2 光滑化SQP算法

使用逼近光滑罰函數(shù)

作為SQP算法的評價函數(shù).首先給出函數(shù)Φ（x，α，μ）的性質(zhì).

引理1 函數(shù)Φ（x，α，μ）的性質(zhì)［11］

a.對任意固定的μ，若f（x ） ，gi（x ）是k 階連續(xù)可微的，i＝1，2，…，m，則Φ（x，α，μ）也是k 階連續(xù)可微的.若f（x ），gi（x ）是 兩 階 連 續(xù) 可 微 的，則有

和

b.若f（x ） ，gi（x ）是凸的，i＝1，2，…，m，則Φ（x，α，μ）也是凸的.

c.Φ（x，α，μ）＞Ψ（x，α），?x∈Rn.

f.若μ1＜μ2，則Φ（x，α，μ1）＞Φ（x，α，μ2），?x∈Rn.

現(xiàn)在考慮SQP算法的迭代公式

其中，dk是下列二次子問題的解

式中，Bk是n×n 對稱正定矩陣.

本文中總是假定子問題（5）是可行的.在這種假設(shè)下，如果Bk是正定矩陣，那么，子問題（5）有唯一解dk，并且dk是子問題（5）的解當(dāng)且僅當(dāng)存在拉格朗日乘數(shù)ρk使得KTT條件成立

引理2［12］假設(shè)Bk是對稱正定矩陣，則點(diǎn)對是問題（1）的KTT點(diǎn)對當(dāng)且僅當(dāng)，）是子問題（5）的KTT點(diǎn)對.

下面敘述基于光滑化罰函數(shù)（4）的SQP算法.

算法1

步驟0 給定x1∈Rn，ρ1∈Rm，β∈（0，1），γ∈（0，1），ε≥0，B1∈Rn×n為 對 稱 正 定 矩 陣，μ0＞1，α0＞1，M ＞1，令k：＝1.

步驟1 求解子問題（6），得到dk和.若，則算法終止.

步驟3 若

其中

則令μk：＝μk－1，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟4.

步驟4 令μk－1：＝Mμk－1，轉(zhuǎn)步驟3.

步驟5 若

則令αk：＝αk－1，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟6.

步驟6 令αk－1：＝Mαk－1，轉(zhuǎn)步驟5.

步驟7 令λk為序列｛1，γ，γ2，… ｝中使下列不等式成立的最大值：

步 驟8 令xk＋1＝xk＋λkdk，ρk＋1＝ρk－，通 過BFGS 校 正 公 式 將Bk修 正 為Bk＋1，令k：＝k＋1，轉(zhuǎn)步驟1.

算法1中提到的BFGS校正公式如下［12］：

正.令

令

式中，參數(shù)θk定義為

于是，矩陣Bk的BFGS校正公式為

3 算法的全局收斂性

在分析算法1的全局收斂性之前，假設(shè)以下的條件成立.

假設(shè)A：

首先分析算法1的可行性.

引理3 算法1不會在步驟3和步驟4之間無限循環(huán).

證明

因為

和

引理3得證.

引理4 算法1不會在步驟5和步驟6之間無限循環(huán).

引理4得證.

引理5 當(dāng)算法1到達(dá)步驟7時，有

引理5的成立是顯然的.

定理1 由算法1所產(chǎn)生的序列x｛ ｝k 的任一聚點(diǎn)均為問題（1）的KTT點(diǎn).

證明 首先，證明

從算法1中可以得知，μ｛ ｝k 是單調(diào)非減序列.又由引理1和步驟7，可以知道

由式（8），Φ（xk，α，μk）－Φ（xk＋1，α，μk）→0.

又由步驟7可知

現(xiàn)證明λk→0不成立.反證，若λk→0，從算法1中可以得知，有

另一方面，

由式（10）和式（11），有

然而，由引理5，有

于是，導(dǎo)出矛盾.

由式（9）和λk→0不成立，有

又由式（13），假設(shè)A 的b和式（14），可以得到dk→0.

由文獻(xiàn)［13］中的定理3.2.1、定理4.3.3和本文中的引理3，可知定理1的結(jié)論成立

4 數(shù)值測試

在一臺CPU 1.70GHz，RAM 512MB 的PC 上利用Mathematica 7.0.1編程實現(xiàn)了算法1.測試函數(shù)取自文獻(xiàn)［14－16］，計算結(jié)果如表1所示，其中，HS（i）表示文獻(xiàn)［14］中的第i個算例，S（i）表示文獻(xiàn)［15］中的第i個算例.在算法中，各參數(shù)分別取為β＝0.5，γ＝0.5，M ＝2，μ0＝2，α0＝2，ρ1＝0m×1，B1＝In，ε＝10－6.表1的算例說明，對于測試的問題，本文的算法在很短的時間和較少的迭代次數(shù)內(nèi)可求得問題較為滿意的解.

表1 數(shù)值測試結(jié)果Fig.1 Numerical test results

5 結(jié)束語

結(jié)合一類雙曲余弦型光滑化罰函數(shù)，給出了求解等式約束優(yōu)化問題的SQP算法，獲得了算法的全局收斂性，并驗證了算法的有效性.對于該類函數(shù)如何結(jié)合一般的非光滑問題［17］及其它有效算法，如信賴域算法［18］，值得進(jìn)一步研究.

［1］Qi L Q.Superlinearly convergent approximate Newton methods for LC1optimization problems［J］.Mathematical Programming，1994，64（1／2／3）：277－294.

［2］Rockafellar R T.Computational for large－scale problems in extended linear－quadratic programming［J］.Mathematical Programming，1990，48（1／2／3）：447－474.

［3］Rockafellar R T，Wets R J B.Generalized linearquadratic problems of deterministic and stochastic optimal control in discrete time［J］.SIAM Journal on Control and Optimization，1990，28（4）：810－922.

［4］Wilson R B.A simplicial method for convex programming［D］.Boston：Harvard University，1963.

［5］Biggs M S.Constrained minimization using recursive equality quadratic programming in numerical methods for nonlinear optimization［M］∥Lootsma F A，ed.Numerical Methods for Nonlinear Optimization.London，New York：Academic Press，1972：411－428.

［6］Han S P.A globally convergent method for nonlinear programming［J］.Journal of Optimization Theory and Applications，1977，22（3）：297－309.

［7］Powell M J D.A fast algorithm for nonlinearly constrained optimization calculations.Lecture Notes in Mathematics［M］∥Waston G A.Lecture Notes in Mathematics.Berlin：Springer Verlag，1978，630：144－157.

［8］Powell M J D.The convergence of variable metric methods for nonlinearly constrained optimization calculations［M］∥Nonlinear Programming.New York：Academic Press，1978：27－63.

［9］Gould N I M，Toint P L.SQP methods for large－scale nonlinear programming［C］∥IFIP—the International Federation for Information Processing，2000，46：149－178.

［10］Zhang J L，Zhang X S.An SQP method based on smoothing penalty function for nonlinear optimizations with inequality constraint［J］.Journal of Systems Science and Complexity，2001，14（2）：212－217.

［11］Herty M，Klar A，Singh A K，et al.Smoothed penalty algorithms for optimization of nonlinear models［J］.Computation Optimization and Application，2007，37（2）：157－176.

［12］黃紅選，韓繼業(yè).數(shù)學(xué)規(guī)劃［M］.北京：清華大學(xué)出版社，2006.

［13］Bank B，Guddatt J，Klatle D，et al.Nonlinear parametric optimization.Birkh?uesr［M］.Berlin：Akademie－Verlag，1982.

［14］Hock W，Schittkowski K.Test examples for nonlinear programming codes［M］∥Lecture Notes in Economics and Mathematical Systems.Berlin：Springer－Verlag，1981，187.

［15］Schittkowski K.More test examples for nonlinear programming codes［M］∥Lecture Notes in Economics and Mathematical Systems.Berlin：Springer－Verlag，1981，282.

［16］Andrei N.An unconstrained optimization test functions collection［J］.Advanced Modeling and Optimization，2008，10（1）：147－161

［17］劉晶，高巖.求解一類無限維非光滑算子方程的光滑化牛 頓 法［J］.上 海 理 工 大 學(xué) 學(xué) 報，2008，30（2）：167－170.

［18］王安琪，宇振盛，曹倩倩.線性約束優(yōu)化的一個自適應(yīng)非單調(diào)信賴域算法［J］.上海理工大學(xué)學(xué)報，2010，32（6）：545－548.