]*>","")" /> 边界约束二次规划问题的分解方法

• 论文 • 上一篇    下一篇

边界约束二次规划问题的分解方法

卢战杰,魏紫銮   

  1. 中科院计算数学与科学工程计算研究所,中科院计算数学与科学工程计算研究所
  • 出版日期:1999-04-14 发布日期:1999-04-14

卢战杰,魏紫銮. 边界约束二次规划问题的分解方法[J]. 计算数学, 1999, 21(4): 475-482.

DECOMPOSITION METHOD FOR QUADRATIC PROGRAMMING PROBLEM WITH BOX CONSTRAINTS

  1. Lu Zanjie; Wei Ziluan(Institute of COmputational Mathematics and Setentific/Engineering Computing,Chinese Academy of Sciences, Beijing)
  • Online:1999-04-14 Published:1999-04-14
A Decomposition method for solving quadratic programming (QP) with boxconstraints is presented in this paper. It is similar to the iterative method forsolving linear system of equations. The main ideas of the algorithm are to splitthe Hessian matrix Q of the oP problem into the sum of two matrices N and Hsuch that Q = N + H and (N - H) is symmetric positive definite matrix ((N, H)is called a regular splitting of Q)[5]. A new quadratic programming problem withHessian matrix N to replace the original Q is easier to solve than the originalproblem in each iteration. The convergence of the algorithm is proved under certainassumptions, and the sequence generated by the algorithm converges to optimalsolution and has a linear rate of R-convergence if the matrix Q is positive definite,or a stationary point for the general indefinite matrix Q, and the numerical resultsare also given.
()

[1] D.P. Bertsekas, Projected Newton method for optimization problems with simple constraints, SIAM J. Control and Optimization, 20 (1982), 221-246.
[2] T.F. Coleman, L.A. Hulbert, A direct active set algorithm for large sparse quadratic pro-gram with simple bounds, Mathematical Programming, 45 (1989), 373-406.
[3] A. Miedlander, J.M. Martinez, On the maximization of a concave quadratic function withbox constraints, SIAM J. Optimization, 4 (1994), 177-192.
[4] C.G. Han, P.M. Pardalos, Y. Ye, Computational aspects of an interior point algorithmfor quadratic programming problem with box constraints, in Large Scale Numerical OPtimization, T.Coleman and Y.Ye, eds., Society for industrial and Applied Mathematics,Philadephia, PA, 1990.
[5] Z.L. Wei, Subspace search method for quadratic programming with box constraints, JCM,21 (1999), 307-314.
[6] Wu Li, Differentiable piecewise quadratic penaty function for quadratic programming withsimple bound constraint, SIAM J. Optimization, 6 (1996), 299-315.
[7] H.B. Keller, On the solution of singular and semidefinite linear systems by iteration, SIAMJ. Numer. Anal., 2 (1965), 281-290.
[8] Z.Q. Luo, P. Tseng, On the convergence of a matrix splitting algorithm for the symmetricmonotone linear comlemeatarity problem, SIAM J. Control and Optimization, 29 (1991),1037-1060.
[9] Z.Q. Luo, P. Tseng, Error bound and convergence analysis of matrix splitting algorithmfor the affine variational inequality problem, SIAM J. OPtimization, 2 (1992), 43-54.
[10] Y. Yuan, Numerical Methods for Nonlinear Programming, Shanghai Scientific and Technical Publishers, 1993 (in Chinese).
No related articles found!
阅读次数
全文


摘要