等式約束下凸二次規(guī)劃問題的改進擬Newton算法

1、 等式約束下凸二次規(guī)劃問題的改進擬 Newton 算法王建芳,楊曉光,宋偉大連海事大學應(yīng)用數(shù)學系,遼寧大連 (116026E-mail :摘 要:提出了擬 Newton 法求解凸二次規(guī)劃問題的改進擬 Newton 法,對于等式約束下凸 二次規(guī)劃問題利用增廣 Lagrange 函數(shù)將該約束問題轉(zhuǎn)化為無約束問題,采用 Wolf-Powell 線搜索確定步長,利用擬 Newton 算法求最優(yōu)解,并給出數(shù)值檢驗結(jié)果,表明算法是可行的 和有效的。關(guān)鍵詞:擬牛頓算法;凸二次規(guī)劃;等式約束; Wolf-Powell 線搜索 中圖分類號:O242.231. 引言二次規(guī)劃問題的求解是數(shù)學規(guī)劃和工業(yè)領(lǐng)域的重要課題

2、, 同時也是求解一般非線性規(guī)劃 問題的關(guān)鍵, 求解二次規(guī)劃問題的早期算法大都利用線性規(guī)劃的單純形法求二次規(guī)劃問題的 KKT 最優(yōu)性必要條件及其各種變形,包括 Wolf 算法 1和 Lemke 互補轉(zhuǎn)軸算法 2等;在二 次規(guī)劃問題的研究過程中, 20世紀 70年代出現(xiàn)了有效集算法 1; 20世紀 80年代出現(xiàn)了序 列二次規(guī)劃算法; 其中 Lagrange-Newton 算法是局部二次規(guī)劃算法 3。此外, 等式約束下二 次規(guī)劃算法常用方法有變量消去法、廣義消去法、 Lagrange 乘子法 4,文獻 1提出了利用 增廣 Lagrange 函數(shù)將該約束問題化為無約束問題,采用 Armijo 線搜索利

3、用擬 Newton 算法 進行求解,然而, Armijo 線搜索不能避免搜索步長過小的情況 , 而且,當 2( f x 不正定時, 算法不能保證 0Tk k y s >,此外擬 Newton 法修正原則 BFGS 法產(chǎn)生的 1k B +不一定對稱正定, 因而相應(yīng)的擬 Newton 方向可能不是 f 在 k x 的下降方向。為了克服這一缺陷本文改進了文獻 5的算法,采用 Wolf-Powell 線搜索確定步長,此線性搜索可以避免步長過小的情況,從而 減少迭代次數(shù)。2. 算法描述主要考慮以下等式約束凸二次規(guī)劃問題1min (2. TT f x x Qx c x s tAx b=+= (2.1

4、 式中, Q 為 n 階正定陣; A 為 m n ×階矩陣; , , m n nb R c R x R 。利用增廣 Lagrange 函數(shù)將該等式約束轉(zhuǎn)問題轉(zhuǎn)化為無約束問題,得到相應(yīng)的增廣 Lagrange 函數(shù)為:(, , ( ( ( ( 2T T x f x Ax b Ax b Ax b µµ=+式中 1(, , ; 0. Tm µ=>L 記 *x 為最優(yōu)解, *為最優(yōu)解 *x 處的增廣 Lagrange 乘子。 可以證明,在一定的條件下,當 µ固定 *時,有 *(, , x x x µ 見參考文獻 4。 于是問題(1可以轉(zhuǎn)

5、化為以下無約束最小值問題: 1min (, ( ( ( 22T T T T x x Qx c x Ax b Ax b Ax b µ=+ (2.2 其中, (, :nx R R 二階連續(xù)可微且有下界,記 (, k k k g x =, 1k k k y g g +=,1k k k s x x +=考慮迭代1k k k k x x d +=+ , 1k k k d B g =, 1( k k k Ax b µ+=其中 k 為乘子迭代公式中的乘子向量, k 為搜索步長, k B 是擬牛頓修正矩陣,他由 BFGS 修正公式(見文獻 31T T k k k k k kk k T Tk

6、 k k k ky y B s s B B B y s s B s +=+ (2.3 給出,由于 k k k k B s g =, k k k B d g =故上式可寫成1T T k k k kk k T Tk k k k kg g y y B B g d y d +=+ BFGS 校正公式是迄今最好的擬牛頓公式,它具有 DEP 校正所具有的各種性質(zhì),當采 取不精確線搜索時, BFGS 校正公式還具有總體收斂性。 (見參考文獻 3我們采用 Wolf-Powell 線搜索原則:給定常數(shù) 12, ,滿足 11201/2, 1<<<<取0k > 使之滿足下列不等式:12

7、( ( ( Tk k k k k k kT Tk k k k k kx d x g d x d d g d + (2.4 利用函數(shù) ( ( k k x d =+上式可等價下式:12( (0(0,( (0k k k +其中 k d 滿足線性方程組 0k k B d g +=, k B 為已知正定矩陣。 算法如下:步驟 1.若 1k =滿足(2.4則取 1k =否則轉(zhuǎn)下一步;步驟 2.給定常數(shù) 0>, 1, (0,1。令 (0k 是集合 , 0,1, 2, i i =L 中使得(2.4中第一個不等式成立的最大者,令 0i =;步驟 3. 若 (i k 滿足(2.4中的第二個不等式則終止計算,

8、并得到步長 (i k k =,否則令( 1( i i k k = 轉(zhuǎn)步 4;步驟 4.令 (1i k+是集合 ( ( (1(, 0,1, 2, i j i i k k k j +=L 中使(2.4中第一個不等式成立的最大者 , 令 :1i i =+, 轉(zhuǎn)步 3;其中第一個條件是 Armijo 型線搜索的條件,第二個條件的作用在于限制過小的步長, 一般地, 2值愈小線性搜索愈精確,不過 2值愈小工作量愈大,而不精確線搜索不要求過 小 2,的通常取 120.1, 0.4=。 綜上所述,利用擬 Newton 法解等式約束下凸二次規(guī)劃算法的步驟如下: 步 1給定初始點 1nx E ,乘子向量初始估計

9、1,參數(shù) µ,允許誤差 0>步 2置 1n B I =(單位矩陣計算在 1x 處的梯度 1111( TTg Qx c A A Ax b µ=+,置:1k =;步 3計算 1k k k d B g =;步 4沿方向 k d 通過 Wolf-Powell 線搜索原則確定步長 k 令 1k k k k x x d +=+; 步 5若 k g ,則停止迭代,得 *1k x x +=否則轉(zhuǎn)步 6 ; 步 6若 k n =,則令 11k x x +=返回步 2否則轉(zhuǎn)步 7 ;步 7 計算 1( k k k Ax b µ+=; 校正 k B :利用(2.3 產(chǎn)生 1k B

10、 +, 置 :1k k =+返回步 3 。 3. 算法收斂性線性搜索對算法的收斂性有影響,采用不同的線性搜索的擬 Newton 法的收斂性質(zhì)也不 相同。首先假設(shè):(1函數(shù)二次連續(xù)可微(2水平集是凸集,且函數(shù)在上是一致凸函數(shù),即存在正常數(shù),使得為了定理的證明,我們需要以下引理:引理 3.1(參考 4若假設(shè)成立,則 ( , 0k tr B ck k 2( (01, 01i ki i T i i i B S c k k S B S=+ 其中 ( tr A 表示矩陣 A 的跡, 0c >是常數(shù)。引理 3.2(參考 4 若假設(shè)成立, 點列 (k x 由 Wolf-Powell 型線搜索的 BFGS

11、 算法產(chǎn)生,則 存在常數(shù) 20c >,使得1( 2( cos k k k k d c f x ;其中, k 表示 kd 與 ( ( k f x 間的夾角。而且,存在常數(shù) 0>使得算法產(chǎn)生的步長 k 滿 足11, 0kk ii k +=。定理 1(參考 4若假設(shè)成立,則 Wolf-Powell 型線搜索的 BFGS 算法產(chǎn)生的點列 (k x 收 斂于問題的唯一極小值 *x 。4. 數(shù)值檢驗為了進一步驗證算法的實際計算效果, 我們對算法進行了一定的數(shù)值試驗 (以下算例中 均取參數(shù) 1122, 0.5, 0.6, 0.1, 0.4, 14e =如下:例 1 5 2221231231231

12、23min 22. 4 22x x x x x x s t x x x x x x +=+=例 2 522121212min 22. . 1x x x x s t x x +=計算結(jié)果見表 1、 2表 1 例 1的計算結(jié)果1Tx1µ0Tk x 1T k x 0k1k (1, 1, 1(1, 1, 1 (2, 2, 0.1 (1, 1 (1, 1 (1, 1 0.51 0.5(1.9061,1.9591,0.1376(1.9064,1.9519,0.1409 (1.9055,1.9539,0.1411 (1.9092,1.9541,0.1364 (1.9091,1.9545,0.136

13、3 (1.9090,1.9537,0.136345 72 4946 39 43表 2 例 2的計算結(jié)果1T x1µ0Tk x 1T k x 0k1k (1, 1 (1, 1 (0.5, 0.7 (1 (1 (1 2 1 1(0.3989,0.5997(0.3966,0.5999 (0.4011,0.5999 (0.4000, 0.6001 (0.4000,0.6000 (0.4000,0.600128 37 1319 29 16其中 0k 表示文獻 5中算法的迭代次數(shù), 1k 則表示本文改進算法的迭代次數(shù); 0Tk x 表示文 獻 5中算法的最優(yōu)解, 1Tk x 表示本文改進算法的最

14、優(yōu)解。數(shù)值計算結(jié)果表明優(yōu)于文獻 5中提 出的算法,而且對初始值和參數(shù)進行適當調(diào)整,發(fā)現(xiàn)計算結(jié)果并不敏感,精度較高,迭代次 數(shù)少。 參考文獻1 陳寶林 . 最優(yōu)化化理論與算法 M.北京:清華大學出版社 ,1989.2 席少林 . 非線性最優(yōu)化方法 M.北京:高等教育出版社 ,1992.3 袁亞湘 , 孫文瑜 . 最優(yōu)化理論與方法 . 北京:科學出版社, 2004.4 李董輝,童小嬌,萬中 . 數(shù)值最優(yōu)化 M.北京:科學出版社 ,2005.5 王朝平 , 趙天玉 , 陳忠 . 一個等式約束下凸二次規(guī)劃的擬牛頓算法 J.長江大學學報 ,2005,2(4 :109-110. A Class of Im

15、proved Quasi-Newton Methods on ConvexQuadratic ProblemsWang Jianfang, Yang Xiaoguang, Song WeiDepartment of Mathematics, Dalian Maritime University, Dalian, Liaoning (116026AbstractImproved Quasi-Newton Method presents a calss of improved quasi-Newton methods solving convex quadratic programming problem. We use augmented lagrange function to translate the constrained problem into unconstrained problem on the assumption that the linear search satiesfies Wolfe-Powell rules,then we use