非線性優化問題的光滑化序列二次規劃方法

宇振盛， 張麗娜， 秦 毅

（上海理工大學 理學院，上海 200093）

1 問題的提出

考慮非線性優化問題

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

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

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

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

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

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

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

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

2 光滑化SQP算法

使用逼近光滑罰函數

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

引理1 函數Φ（x，α，μ）的性質［11］

a.對任意固定的μ，若f（x ） ，gi（x ）是k 階連續可微的，i＝1，2，…，m，則Φ（x，α，μ）也是k 階連續可微的.若f（x ），gi（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.

現在考慮SQP算法的迭代公式

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

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

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

引理2［12］假設Bk是對稱正定矩陣，則點對是問題（1）的KTT點對當且僅當，）是子問題（5）的KTT點對.

下面敘述基于光滑化罰函數（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，轉步驟5；否則，轉步驟4.

步驟4 令μk－1：＝Mμk－1，轉步驟3.

步驟5 若

則令αk：＝αk－1，轉步驟7；否則，轉步驟6.

步驟6 令αk－1：＝Mαk－1，轉步驟5.

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

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

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

正.令

令

式中，參數θk定義為

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

3 算法的全局收斂性

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

假設A：

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

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

證明

因為

和

引理3得證.

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

引理4得證.

引理5 當算法1到達步驟7時，有

引理5的成立是顯然的.

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

證明 首先，證明

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

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

又由步驟7可知

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

另一方面，

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

然而，由引理5，有

于是，導出矛盾.

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

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

由文獻［13］中的定理3.2.1、定理4.3.3和本文中的引理3，可知定理1的結論成立

4 數值測試

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

表1 數值測試結果Fig.1 Numerical test results

5 結束語

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

［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］黃紅選，韓繼業.數學規劃［M］.北京：清華大學出版社，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］.上 海 理 工 大 學 學 報，2008，30（2）：167－170.

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