Minimizing Nonconvex Quadratic Functions Subject to Bound Constraints
Embargo until
Date
2014-12-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Johns Hopkins University
Abstract
We present an active-set algorithm for finding a local minimizer to a nonconvex
bound-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 coefficient matrix.
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 our
method is e fficient and robust on nonconvex bound-constrained quadratic problems.
Description
Keywords
nonconvex quadratic program, active-set, conjugate gradient, Lanczos, line search, negative curvature, optimality conditions