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

Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (1): 21-30.

• Original Articles • Previous Articles Next Articles

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

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

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.

References

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]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[2]	LV Wei, WANG Weiping. An identification method to estimate the thickness of sea ice [J]. Operations Research Transactions, 2018, 22(4): 117-126.
[3]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[4]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[5]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[6]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[7]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[8]	ZHANG Yanli, MA Xinshun. A class recourse stochastic programs algorithm with MaxEMin evaluation [J]. Operations Research Transactions, 2016, 20(4): 52-60.
[9]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[10]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.
[11]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[12]	CHENG Cong, ZHANG Liwei. Newton methods for inverse problems of quadratic programming [J]. Operations Research Transactions, 2014, 18(3): 60-70.
[13]	LU Yue, ZHANG Jihong, ZHANG Liwei. An alternating direction numerical method for a type of inverse quadratic programming problem [J]. Operations Research Transactions, 2014, 18(2): 1-16.
[14]	SUN Xiaoling, LI Duan. Recent advances in integer programming [J]. Operations Research Transactions, 2014, 18(1): 39-68.
[15]	DU Shouqiang. Global convergence of the Levenberg-Marquardt method with Goldstein line search [J]. Operations Research Transactions, 2012, 16(4): 105-111.

An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments