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

蔡劍

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

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

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

中圖分類號：O221.2文獻標志碼：A

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

收稿日期：2015-05-06

基金項目：國家自然科學

作者簡介：謝夢燕(1994—)，女，浙江湖州人，湖州師范學院信息工程學院2012級計算機科學與技術(shù)專業(yè)學生，主要從事群智能優(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)濟、統(tǒng)計、金融、工程等領(lǐng)域，并且許多非線性規(guī)劃問題都可以轉(zhuǎn)化為這種形式，所以不定二次規(guī)劃問題具有一定的理論價值和廣泛的應(yīng)用價值.在過去幾年里，人們對不定二次規(guī)劃已有一些研究，例如，文獻[1-2]對帶有線性約束的非凸規(guī)劃提出了全局收斂算法，文獻[3]對不等式約束優(yōu)化問題提出了QP-free算法，文獻[4]對非線性優(yōu)化問題提出了近似算法，文獻[5-8]對帶有非線性約束的非凸規(guī)劃提出了分支定界算法，均獲得了很好的全局收斂性和數(shù)值結(jié)果.但這些全局優(yōu)化算法更多的是考慮算法本身，本文從不定二次規(guī)劃自身函數(shù)的特點出發(fā)，將目標函數(shù)和約束條件轉(zhuǎn)化為凸二次函數(shù)，并利用凸函數(shù)可以找到線性下界的特點，將不定二次規(guī)劃問題轉(zhuǎn)化為松弛線性規(guī)劃問題，再利用分支定界算法，并且從理論上也能證明算法是全局收斂的.

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

(1)

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

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

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

則

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

于是

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

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

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

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

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)的最小值點.

步0，初始化.1)令k=0，所以活動結(jié)點的集合為Q0={S0}，上界α=，可行點的集合F=?；2)給定參數(shù)ε>0，求解問題(2)在S0上的最值，得到其在x0=x(S0)處的最優(yōu)目標值為β0=β(S0)，若x0對問題(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)嚴格一致.

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

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

利用中值定理

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

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

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

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

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

βk，

為真.很顯然{βk}是一非下降序列，且有上界，因此{β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，運行時間為0.045秒，迭代次數(shù)為30次，說明算法可行，且運行速度非?？?

[參考文獻]

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

[4]王若鵬，徐紅敏.非線性l1問題的光滑近似算法[J].純粹數(shù)學與應(yīng)用數(shù)學，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.

[責任編輯王新奇]

Vol.18No.3Jul.2015

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