We propose primal-dual active-set (PDAS) methods for solving large-scale instances of an important class of convex quadratic optimization problems (QPs). The iterates of the algorithms are partitions of the index set of variables, where corresponding to each partition there exist unique primal-dual variables that can be obtained by solving a (reduced) linear system. Algorithms of this type have recently received attention when solving certain QPs and linear complementarity problems since, with rapid changes in the active set estimate, they often converge in few iterations. Indeed, as discussed in this paper, convergence in a finite number of iterations is guaranteed when a basic PDAS method is employed to solve certain QPs for which a reduced Hessian of the objective function is (a perturbation of) an M-matrix. We propose three PDAS algorithms. The novelty of the algorithms is that they allow inexactness in the (reduced) linear system solves at all partitions except optimal ones. Such a feature is particularly important in large-scale settings when one employs iterative Krylov subspace methods to solve these systems. Our first algorithm is convergent when solving problems for which properties of the Hessian can be exploited to derive explicit bounds to be enforced on the (reduced) linear system residuals, whereas our second and third algorithms employ dynamic parameters to obviate the need of such explicit bounds. We prove that when applied to solve an important class of convex QPs, our algorithms converge from any initial partition. We also illustrate their practical behavior by providing the results of numerical experiments on a set of discretized optimal control problems, some of which are explicitly formulated to exhibit degeneracy.
Citation
F. E. Curtis and Z. Han. Globally Convergent Primal-Dual Active-Set Methods with Inexact Subproblem Solves. SIAM Journal on Optimization, 26(4):2261-2283, 2016.