Minimizing Nonconvex Quadratic Functions Subject to Bound Constraints

nonconvex quadratic program;active-set;conjugate gradient;Lanczos;line search;negative curvature;optimality conditions;Applied Mathematics & Statistics

Mohy-ud-Din, HassanRobinson, Daniel P. ;

Johns Hopkins University

关键词: nonconvex quadratic program;    active-set;    conjugate gradient;    Lanczos;    line search;    negative curvature;    optimality conditions;    Applied Mathematics & Statistics;   

Others  :  https://jscholarship.library.jhu.edu/bitstream/handle/1774.2/37258/MOHY-UD-DIN-THESIS-2014.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: JOHNS HOPKINS DSpace Repository

【 摘 要 】

We present an active-set algorithm forfinding a local minimizer to a nonconvexbound-constrained quadratic problem. Our algorithm extends the ideas developed by Dost al and Sch oberl that is based on the linear conjugate gradient algorithm for (approximately) solving a linear system with a positive-de finite coefficientmatrix.This is achieved by making two key changes. First, we perform a line search along negative curvature directions when they are encountered in the linear conjugate gradient iteration. Second, we use Lanczos iterations to compute approximations to leftmost eigen-pairs, which is needed to promote convergence to points satisfying certain second-order optimality conditions. Preliminary numerical results show that ourmethod is e fficient and robust on nonconvex bound-constrained quadratic problems.