一种基于LVI求解二次规划问题的数值算法(英文)  

An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems

作　　者：张雨浓[1,2] 李学忠[3] 张智军[1] 李钧[1] 

机构地区：[1]中山大学信息科学与技术学院,广州510006 [2]中山大学深圳研究院,深圳518057 [3]中山大学软件学院,广州510006

出　　处：《运筹学学报》2012年第1期21-30,共10页Operations Research Transactions

基　　金：supported by The National Natural Science Foundation of China(No61075121, 60935001);by the Fundamental Research Funds for the Central Universities of China(No3162460)

摘　　要：给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题.这类带约束的二次规划问题首先被转换为线性变分不等式问题,该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式,从而得到QP问题的最优解.进一步给出了94LVI算法的全局收敛性证明.94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.This paper presents and investigates a numerical algorithm （termed as 94LVI algorithm） for solving quadratic programming （QP） problems with linear equality and bound constraints. To do this, the constrained QP problems are firstly converted into linear variational inequalities （LVI）, which are then converted into equivalent piecewise- linear projection equations （PLPE）. After that, the resultant PLPE is solved by the presented 94LVI algorithm. The optimal numerical solutions to the QP problems are thus obtained. Furthermore, the theoretical proof of the global convergence of the 94LVI algorithm is presented. The numerical comparison results between the 94LVI algorithm and the active set algorithm are provided as well, which further demonstrates the efficacy and superiority of the presented algorithm for solving such QP problems.

关 键 词：数值算法 二次规划 94LVI算法 全局收敛性 

分 类 号：O221.2[理学—运筹学与控制论]