求不定二次规划全局最优解的新的线性化技术

求不定二次规划全局最优解的新的线性化技术

蔡剑

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

摘要：为了提高非线性约束的不定二次规划求解速度，提出了一种松弛线性规划的新算法.首先利用不定二次函数自身的特点，将其转化为凸二次函数；其次利用凸函数可以找到线性下界的特点，采用线性化技术建立不定二次规划的松弛线性规划；最后利用分支定界算法，通过对可行域的细分，缩小求解范围，最终求得最优值点.开展了实例计算，计算结果显示松弛线性规划算法能显著提升不定二次规划求全局最优解的速度.

关键词：不定二次规划;线性化技术;松弛线性规划;全局最优解

中图分类号：O221.2文献标志码：A

文章编号：1008-5564(2015)03-0005-04

收稿日期：2015-05-06

基金项目：国家自然科学

作者简介：谢梦燕(1994—)，女，浙江湖州人，湖州师范学院信息工程学院2012级计算机科学与技术专业学生，主要从事群智能优化研究；

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

不定二次规划广泛应用于经济、统计、金融、工程等领域，并且许多非线性规划问题都可以转化为这种形式，所以不定二次规划问题具有一定的理论价值和广泛的应用价值.在过去几年里，人们对不定二次规划已有一些研究，例如，文献[1-2]对带有线性约束的非凸规划提出了全局收敛算法，文献[3]对不等式约束优化问题提出了QP-free算法，文献[4]对非线性优化问题提出了近似算法，文献[5-8]对带有非线性约束的非凸规划提出了分支定界算法，均获得了很好的全局收敛性和数值结果.但这些全局优化算法更多的是考虑算法本身，本文从不定二次规划自身函数的特点出发，将目标函数和约束条件转化为凸二次函数，并利用凸函数可以找到线性下界的特点，将不定二次规划问题转化为松弛线性规划问题，再利用分支定界算法，并且从理论上也能证明算法是全局收敛的.

1新的线性化技术

(1)

其中Ai为n阶实对称矩阵，bi,x,l,u均为n维列向量，i=0,1,2,…,m.

定理1对任意不定二次规划，总可以表示成两个凸函数相加.

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

则

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

于是

利用凸函数的性质，给出了Ψi(x)的线性下界估计.

对于凸函数Φ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]

则构造出不定二次规划问题在Sk上的相应的松弛线性规划问题

(2)

2全局收敛算法

下面给出问题(2)的分支定界算法，主要是分支和定界两部分.分支采取双分规则，如下：

定界在下面的算法中有明确表出.令β(Sk)表示问题(2)在区间Sk上的最优解，xk=x(Sk)表示相应的最小值点.

步0，初始化.1)令k=0，所以活动结点的集合为Q0={S0}，上界α=，可行点的集合F=∅；2)给定参数ε>0，求解问题(2)在S0上的最值，得到其在x0=x(S0)处的最优目标值为β0=β(S0)，若x0对问题(1)是可行的，则更新F和α，F=F∪{x0}，α=f0(x0)，若αβ0+ε，则算法停止，x0是问题(1)的最优解，否则，执行步1；

步4，令Qk+1=Qk{S:α-β(S)ε,S∈Qk}，若Qk+1=∅，则算法停止，α为问题(1)的最优值，v为其最优解，否则令k=k+1，转入步5.

3算法的收敛性

定理2线性函数gi(x)在S0上与不定二次函数fi(x)严格一致.

证明1)由分支规则，对S0分支可得到一子矩形序列{Sk}k+1⊂Sk，问题(2)对每一个Sk求最优点，则可以得到相应的序列{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]，性质1和性质2成立.下面证明性质3.

对于算法的每一次迭代，k=0,1,…，假设

βk，

为真.很显然{βk}是一非下降序列，且有上界，因此{βk}存在极限

4数值例子

考虑不定二次规划问题

利用本文给出的线性化技术，先将之转化为松弛线性规划，然后利用C++编程，得到该问题的最优解为x*=(0.997 122 35,0.181 842 14,-0.980 343 21)T，运行时间为0.045秒，迭代次数为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]黄利国，孙莉，韩从英.并行求解约束优化问题的QP-free型算法[J].纯粹数学与应用数学，2011,27(1)：63-68.

[4]王若鹏，徐红敏.非线性l1问题的光滑近似算法[J].纯粹数学与应用数学，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—)，男，湖州师范学院信息工程学院讲师，博士，主要从事生物信息计算、群智能优化、并行分布式算法研究.