期刊
MATHEMATICAL PROGRAMMING COMPUTATION
卷 7, 期 1, 页码 71-112出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s12532-014-0075-x
关键词
Large-scale quadratic programming; Active-set methods; Convex and nonconvex quadratic programming; KKT systems; Schur-complement method; Variable-reduction method
类别
资金
- National Science Foundation [DMS-0915220, DMS-1318480]
- Department of Energy [DE-SC0002349]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1318480] Funding Source: National Science Foundation
Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is the solution of an equality-constrained subproblem involving a working set of linearly independent constraints. The method is a reformulation of a method for general QP first proposed by Fletcher, and modified subsequently by Gould. The reformulation facilitates a simpler analysis and has the benefit that the algorithm reduces to a variant of the simplex method when the QP is a linear program. The search direction is computed from a KKT system formed from the QP Hessian and the gradients of the working-set constraints. It is shown that, under certain circumstances, the solution of this KKT system may be updated using a simple recurrence relation, thereby giving a significant reduction in the number of KKT systems that need to be solved. The second part of the paper focuses on the solution of QP problems with constraints in so-called standard form. We describe how the constituent KKT systems are solved, and discuss how an initial basis is defined. Numerical results are presented for all QPs in the CUTEst test collection.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据