求不定二次規(guī)劃全局最優(yōu)解的新的線性化技術(shù)

求不定二次規(guī)劃全局最優(yōu)解的新的線性化技術(shù)

蔡劍

(南京航空航天大學(xué) 金城學(xué)院，南京 211156)

摘要：為了提高非線性約束的不定二次規(guī)劃求解速度，提出了一種松弛線性規(guī)劃的新算法.首先利用不定二次函數(shù)自身的特點(diǎn)，將其轉(zhuǎn)化為凸二次函數(shù)；其次利用凸函數(shù)可以找到線性下界的特點(diǎn)，采用線性化技術(shù)建立不定二次規(guī)劃的松弛線性規(guī)劃；最后利用分支定界算法，通過對(duì)可行域的細(xì)分，縮小求解范圍，最終求得最優(yōu)值點(diǎn).開展了實(shí)例計(jì)算，計(jì)算結(jié)果顯示松弛線性規(guī)劃算法能顯著提升不定二次規(guī)劃求全局最優(yōu)解的速度.

關(guān)鍵詞：不定二次規(guī)劃;線性化技術(shù);松弛線性規(guī)劃;全局最優(yōu)解

中圖分類號(hào)：O221.2文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-5564(2015)03-0005-04

收稿日期：2015-05-06

基金項(xiàng)目：國(guó)家自然科學(xué)

作者簡(jiǎn)介：謝夢(mèng)燕(1994—)，女，浙江湖州人，湖州師范學(xué)院信息工程學(xué)院2012級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生，主要從事群智能優(yōu)化研究；

A New linear Relaxed Technology for Solving Global Optimal Solution ofIndefinite Quadratic Programming

CAI Jian

( Jincheng College, Nanjing University of Aeronautics and Astronautics, Nanjing 211156, China)

Abstract：In order to improve the solving speed of indefinite quadratic programming, a new relaxed linear programming algorithm was provided. Firstly, the function was turned into a convex quadratic function with its characteristics. Secondly, with the characteristics of the convex function has its linear lower bound, relaxed linear programming function was established by using of the linearization technology. Finally, by using of the branch and bound algorithm, the solving range was narrowed and the feasible region was subdivided, eventually the optimal value was obtained. Examples of calculation were carried out, and the calculation results show that the new algorithm of relaxed linear programming can significantly improve the solving speed of indefinite quadratic programming.

Key words：indefinite quadratic programming; linear technology; relaxed linear programming; global optimal solution

不定二次規(guī)劃廣泛應(yīng)用于經(jīng)濟(jì)、統(tǒng)計(jì)、金融、工程等領(lǐng)域，并且許多非線性規(guī)劃問題都可以轉(zhuǎn)化為這種形式，所以不定二次規(guī)劃問題具有一定的理論價(jià)值和廣泛的應(yīng)用價(jià)值.在過去幾年里，人們對(duì)不定二次規(guī)劃已有一些研究，例如，文獻(xiàn)[1-2]對(duì)帶有線性約束的非凸規(guī)劃提出了全局收斂算法，文獻(xiàn)[3]對(duì)不等式約束優(yōu)化問題提出了QP-free算法，文獻(xiàn)[4]對(duì)非線性優(yōu)化問題提出了近似算法，文獻(xiàn)[5-8]對(duì)帶有非線性約束的非凸規(guī)劃提出了分支定界算法，均獲得了很好的全局收斂性和數(shù)值結(jié)果.但這些全局優(yōu)化算法更多的是考慮算法本身，本文從不定二次規(guī)劃自身函數(shù)的特點(diǎn)出發(fā)，將目標(biāo)函數(shù)和約束條件轉(zhuǎn)化為凸二次函數(shù)，并利用凸函數(shù)可以找到線性下界的特點(diǎn)，將不定二次規(guī)劃問題轉(zhuǎn)化為松弛線性規(guī)劃問題，再利用分支定界算法，并且從理論上也能證明算法是全局收斂的.

1新的線性化技術(shù)

(1)

其中Ai為n階實(shí)對(duì)稱矩陣，bi,x,l,u均為n維列向量，i=0,1,2,…,m.

定理1對(duì)任意不定二次規(guī)劃，總可以表示成兩個(gè)凸函數(shù)相加.

L:yj=(ujk+ljk)xj-ujkljk，

則

-xj2≥yj=-(ujk+ljk)xj+ujkljk，

于是

利用凸函數(shù)的性質(zhì)，給出了Ψi(x)的線性下界估計(jì).

對(duì)于凸函數(shù)Φi(x)=xTBix，由次微分的定義，則有

Φi(x)≥Φ(x0)+(x-x0)TΦ(x0)，Φi(x)=?(x)，

從而得到了Φi(x)的線性下界估計(jì)，因此得到

fi(x) =Φi(x)+biTx+λiΨi(x)

biTx+λi[-(uk+lk)Tx+(uk)Tlk]

則構(gòu)造出不定二次規(guī)劃問題在Sk上的相應(yīng)的松弛線性規(guī)劃問題

(2)

2全局收斂算法

下面給出問題(2)的分支定界算法，主要是分支和定界兩部分.分支采取雙分規(guī)則，如下：

定界在下面的算法中有明確表出.令β(Sk)表示問題(2)在區(qū)間Sk上的最優(yōu)解，xk=x(Sk)表示相應(yīng)的最小值點(diǎn).

步0，初始化.1)令k=0，所以活動(dòng)結(jié)點(diǎn)的集合為Q0={S0}，上界α=，可行點(diǎn)的集合F=?；2)給定參數(shù)ε>0，求解問題(2)在S0上的最值，得到其在x0=x(S0)處的最優(yōu)目標(biāo)值為β0=β(S0)，若x0對(duì)問題(1)是可行的，則更新F和α，F(xiàn)=F∪{x0}，α=f0(x0)，若αβ0+ε，則算法停止，x0是問題(1)的最優(yōu)解，否則，執(zhí)行步1；

步4，令Qk+1=Qk{S:α-β(S)ε,S∈Qk}，若Qk+1=?，則算法停止，α為問題(1)的最優(yōu)值，v為其最優(yōu)解，否則令k=k+1，轉(zhuǎn)入步5.

3算法的收斂性

定理2線性函數(shù)gi(x)在S0上與不定二次函數(shù)fi(x)嚴(yán)格一致.

證明1)由分支規(guī)則，對(duì)S0分支可得到一子矩形序列{Sk}k+1?Sk，問題(2)對(duì)每一個(gè)Sk求最優(yōu)點(diǎn)，則可以得到相應(yīng)的序列{xk}，使得xk∈Sk=[lk,uk]，當(dāng)k→時(shí)，Sk→{x*}，即xk→x*.由于對(duì)Sk的上界和下界約束序列都是在緊空間上的，因此，存在收斂子序列Sq=[lq,uq]→[x*,x*]，則當(dāng)q→時(shí)，?xq∈Sq，xq→x*.

2)?Sq?S0，xq∈Sq，有

利用中值定理

‖2(Ai+λiI)‖‖uq-lq‖2+λ‖uq-lq‖2，

(1)算法第2步中分塊集的細(xì)分在S0上是窮舉的；

(2)在第2步中被選擇用來(lái)進(jìn)行分塊的集合的邊界在逐步得到改進(jìn)；

參考文獻(xiàn)證明由給定的算法及[9]，性質(zhì)1和性質(zhì)2成立.下面證明性質(zhì)3.

對(duì)于算法的每一次迭代，k=0,1,…，假設(shè)

βk，

為真.很顯然{βk}是一非下降序列，且有上界，因此{(lán)βk}存在極限

4數(shù)值例子

考慮不定二次規(guī)劃問題

利用本文給出的線性化技術(shù)，先將之轉(zhuǎn)化為松弛線性規(guī)劃，然后利用C++編程，得到該問題的最優(yōu)解為x*=(0.997 122 35,0.181 842 14,-0.980 343 21)T，運(yùn)行時(shí)間為0.045秒，迭代次數(shù)為30次，說(shuō)明算法可行，且運(yùn)行速度非?？?

[參考文獻(xiàn)]

[1]LIU G S,ZHANG J Z.A new branch and bound algorithm for solving quadratic programs with linear compleme Ntarity constraints[J].Journal of computational and Applied Mathematica,2002,146(1):77-87.

[2]BARRIENTOS O,CORREA R.An algorithm for globally minimization of linearly constrained quadratic functions[J].Joural of Global Optimization,2000,16:77-93.

[3]黃利國(guó)，孫莉，韓從英.并行求解約束優(yōu)化問題的QP-free型算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2011,27(1)：63-68.

[4]王若鵬，徐紅敏.非線性l1問題的光滑近似算法[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2013,29(1)：25-32.

[5]AUDET C,HANSEN P,JAUMARD B,et al.A branch and cut algorithm for nonconvex all quadratic programs[J].Journal of Global Optimization,1998,13:417-432.

[6]GAO Y L,SHANG Y L,ZHANG L S.A branch and reduce approach for solving nonconvex quadratic programming problems with quadratic constraints[J].Operations Research Transactions,2005,9(2):9-20.

[7]CAMBINIL R,SODINIL C.Decomposition methods for solving nonconvex quadratic programs via branch and bound[J].Journal of Global Optimization,2005,33(3):313-336.

[8]LINDEROTH J.A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs[J].Mathematical Programming,2005,103(2):251-282.

[9]AL-KHAYYAL,FAIZ A,VAN VOORHIS T.A relaxation method for nonconvex quadratically constrained quadratic programs[J].Jorunal of Global Optimization,1995,6:215-230.

[責(zé)任編輯王新奇]

Vol.18No.3Jul.2015

黃旭(1977—)，男，湖州師范學(xué)院信息工程學(xué)院講師，博士，主要從事生物信息計(jì)算、群智能優(yōu)化、并行分布式算法研究.