419. Accelerating Convergence of MPGP Algorithm
Invited abstract in session WC-3: Acceleration Methods in Optimization, stream Large scale optimization: methods and algorithms.
Wednesday, 14:00-16:00Room: B100/4011
Authors (first author is the speaker)
| 1. | Jakub Kruzik
|
| Czech Academy of Sciences, Institute of Geonics | |
| 2. | David Horak
|
| VSB - Technical University of Ostrava |
Abstract
Modified proportioning with gradient projections (MPGP) is an active set method that employs the conjugate gradient method to minimize a quadratic objective function on the free set, gradient projection to expand the active set, and proportioning to reduce the active set. Preconditioners are widely used to accelerate the solution of systems of linear equations. However, applying preconditioners in conjugate gradient-based algorithms for constrained quadratic programming is not straightforward. This is because preconditioning transforms variables, thereby converting constraints into more general forms, such as turning bound constraints into linear inequality constraints. Preconditioning applied to the submatrix of the Hessian corresponding to the free set (preconditioning in face) is a successful strategy that does not transform the constrained variables. However, a major drawback is that the preconditioner must be recomputed every time the free set changes. To overcome this limitation, we propose a new strategy for integrating preconditioning into MPGP. Our approach avoids both the transformation of constrained variables and the need to recompute the preconditioner based on the free set. This new preconditioning strategy is particularly effective when combined with alternative techniques for fast expansion of the active set. The speedup of the resulting algorithm will be demonstrated on a series of benchmarks using PERMON, an open-source library for quadratic programming.
Keywords
- First-order optimization
- Large-scale optimization
- Optimization software
Status: accepted
Back to the list of papers