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

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 21-30.

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

张雨浓^1,2, 李学忠³, 张智军¹, 李钧¹

1. 中山大学信息科学与技术学院, 广州 510006； 2. 中山大学深圳研究院，深圳 518057； 3. 中山大学软件学院，广州 510006

收稿日期:2011-05-12 修回日期:2011-11-14 出版日期:2012-03-15 发布日期:2012-03-15
通讯作者: 张雨浓 E-mail:zhynong@mail.sysu.edu.cn

An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems

ZHANG Yu-Nong^1,2, LI Xue-Zhong³, ZHANG Zhi-Jun¹, LI Jun¹

1. School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006; 2. Research Institute of Sun Yat-sen University in Shenzhen, Shenzhen 518057; 3. School of Software, Sun Yat-sen University, Guangzhou 510006

Received:2011-05-12 Revised:2011-11-14 Online:2012-03-15 Published:2012-03-15
Contact: Yunong ZHANG E-mail:zhynong@mail.sysu.edu.cn
Supported by:
This work is supported by The National Natural Science Foundation of China (No. 61075121, 60935001), and also by the Fundamental Research Funds for the Central Universities of China (No. 3162460).

摘要/Abstract

摘要： 给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题. 这类带约束的二次规划问题首先被转换为线性变分不等式问题，该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式，从而得到QP问题的最优解. 进一步给出了94LVI算法的全局收敛性证明. 94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.

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

Abstract: 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.

Key words: numerical algorithm, quadratic programming, 94LVI algorithm, global convergence

张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.

ZHANG Yu-Nong, LI Xue-Zhong, ZHANG Zhi-Jun, LI Jun. An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems[J]. Operations Research Transactions, 2012, 16(1): 21-30.

参考文献

Johansen T A, Fossen T I, Berge S P. Constrained nonlinear control allocation with singularity avoidance using sequential quadratic programming[J]. IEEE Transactions on Control Systems Technology, 2004, 12(1): 211-216.
Grudinin N. Reactive power optimization using successive quadratic programming method[J]. IEEE Transactions on Power Systems, 1998, 13(4): 1219-1225.
Wang J, Zhang Y N. Recurrent neural network for real-time computation of inverse kinematics of redundant manipulators[M]. Machine Intelligence: Quo-Vadis? (eds: P. Sincak, J. Vascak, and K. Hirota), World Scientific, Singapore, 2004, 299-319.
Leithead W E, Zhang Y N. O(N^2)-operation approximation of covariance matrix inverse in gaussian process regression based on Quasi-Newton BFGS method[J]. Communications in Statistics -- Simulation and Computation, 2007, 36(2): 367-380.
Zhang Y N. Towards piecewise-linear primal neural networks for optimization and redundant robotics[C]//MengChu Zhou, Proceedings of IEEE International Conference on Networking, Sensing and Control, Florida: IEEE Press, 2006, 374-379.
Zhang Y N, Ge S S, Lee T H. A unified quadratic programming based dynamical system approach to joint torque optimization of physically constrained redundant manipulators[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2004, 34(5): 2126-2132.
Zhang Y N, Wang J. A dual neural network for constrainted torque optimization of kinematically redundant manipulators[J]. IEEE Transactions on Systems, Man and Cybernetics, Part B, 2002, 32(5): 654-662.
Zhang Y N, Wang J. Obstacle avoidance of kinematically redundant manipulators using a dual neural network[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2004, 34(1): 752-759.
Powell M J D. A method for nonlinear constraints in minimization problems[M]. Optimization (ed: R. Fletcher), Academic Press, London, 1969.
Hestens M R. Multiplier and Gradient Methods[J]. Journal of optimization theory and applicatuins, 1969, 4(5): 303-320.
Fletcher R. A general quadratic programming algorithm[J]. IMA Journal of Applied Mathematics, 1971, 7(1): 76-91.
Jin Z J, Bai Y Q, Han B S. A weighted-path-following interior-point algorithm for convex quadratic optimization[J]. Operations Research Transactions, 2010, 14(1): 55-65.
Zhao S F, Fei P S, Li J. A projection and contraction method for convex quadratic programming[J]. Journal of Wuhan University, 2001, 47(1): 22-24.
He B S. A new method for a class of linear variational inequalities[J]. Mathematical Programming, 1994, 66(1-3): 137-144.
Zhang Y N. On the LVI-based primal-dual neural network for solving online linear and quadratic programming problems[C]//Suhada Jayasuriya, Proceedings of American Control Conference, Portland: IEEE Press, 2005, 1351-1356.

Zhang Y N, Cai B H, Zhang L, Li K N. Bi-criteria velocity minimization of robot manipulators using a linear variational inequalityes-based primal-dual neural network and PUMA560 example[J]. Advanced Robotics, 2008, 22(13-14): 1479-1496.
He B S. Solving a class of linear projection equations[J]. Numerische Mathematik, 1994, 68(1): 71-80.
He B S. A projection and contraction method for a class of linear complementarity problem and its application in convex quadratic programming[J]. Applied Mathematics and Optimization, 1992, 25(3): 247-262.

[1]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[2]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[3]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[4]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[5]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[6]	张艳丽, 马新顺. 一类带有MaxEMin评判的补偿型随机规划算法[J]. 运筹学学报, 2016, 20(4): 52-60.
[7]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[8]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[9]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.
[10]	卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.
[11]	孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.
[12]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[13]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.
[14]	王华. 解非线性互补问题的非单调可行SQP方法[J]. 运筹学学报, 2011, 15(2): 85-94.