A regularized active-set method for sparse convex quadratic programming
Abstract/Contents
- Abstract
- An active-set algorithm is developed for solving convex quadratic programs (QPs). The algorithm employs primal regularization within a bound-constrained augmented Lagrangian method. This leads to a sequence of QP subproblems that are feasible and strictly convex, and whose KKT systems are guaranteed to be nonsingular for any active set. A simplified, single-phase algorithm becomes possible for each QP subproblem. There is no need to control the inertia of the KKT system defining each search direction, and a simple step-length procedure may be used without risk of cycling in the presence of degeneracy. Since all KKT systems are nonsingular, they can be factored with a variety of sparse direct linear solvers. Block-LU updates of the KKT factors allow for active-set changes. The principal benefit of primal and dual regularization is that warm starts are possible from any given active set. This is vital inside sequential quadratic programming (SQP) methods for nonlinear optimization, such as the SNOPT solver. The method provides a reliable approach to solving sparse generalized least-squares problems. Ordinary least-squares problems with Tikhonov regularization and bounds can be solved as a single QP subproblem. The algorithm is implemented as the QPBLUR solver (Matlab and Fortran 95 versions) and the Fortran version has been integrated into SNOPT. The performance of QPBLUR is evaluated on a test set of large convex QPs, and on the sequences of QPs arising from SNOPT's SQP method.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2011 |
| Publication date | 2010, c2011; 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Maes, Christopher Mario |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Saunders, Michael A |
| Thesis advisor | Saunders, Michael A |
| Thesis advisor | Gill, Philip E |
| Thesis advisor | Murray, Walter |
| Advisor | Gill, Philip E |
| Advisor | Murray, Walter |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Christopher M. Maes. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Christopher Mario Maes
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...