Accelerating MPGP-type Methods Through Preconditioning

Jakub Kružík, David Horák · 2025

Read Accelerating MPGP-type Methods Through Preconditioning by Jakub Kružík, David Horák (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00617.txt.

Introduction

Jakub Kružík and David Horák speed up a family of optimization methods by adding preconditioning. Their 2025 paper deals with quadratic programming, where a curved cost is minimized under constraints. The methods studied grow a set of free variables as they work. Preconditioning must act only on that free set, or the constraints would change. The standard trick recomputes an inner preconditioner each time the set changes.

The authors study a cheaper variant that computes it only once. They analyze the error this shortcut introduces. They also give a sharp bound on how well conditioned the resulting operator stays. Numerical tests show very large speedups are possible. The work aims to make these solvers practical on bigger problems, where recomputing at every step is costly.

Catalog record

CREATORJakub Kružík, David Horák
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00617

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerating MPGP-type Methods Through Preconditioning Jakub Kružík, David Horák Abstract Abstract This work investigates the acceleration of MPGP-type algorithms using preconditioning for the solution of quadratic programming problems. The preconditioning needs to be done only on the free set so as not to change the constraints. A variant of preconditioning restricted to the free set is the preconditioning in face. The inner preconditioner in preconditioning in face needs to be recomputed or updated every time the free set changes. Here, we investigate an approximate variant of preconditioning in face that computes the inner preconditioner only once. We analyze the error of the approximate variant and provide numerical experiments demonstrating that very large speedups can be achieved by the approximate variant. 1 Introduction This work investigates the acceleration of the MPGP-type [ 1 ] algorithms for the solution of quadratic programming (QP) problems \argmin_{\bm{x}}\frac{1}{2}\bm{x}^{T}\bm{A}\bm{x}-\bm{x}^{T}\bm{b}\quad\text{s.t.}\quad\bm{x}\in\Omega, where \bm{A}\in\mathbb{R}^{n\times n} is a symmetric positive semidefinite (SPS) matrix called the Hessian matrix, vector \bm{b}\in\mathbb{R}^{n} is known as the right-hand side, and \Omega is a set of constraints on the solution vector \bm{x}\in\mathbb{R}^{n} . The minimized quadratic function f(\bm{x})=\frac{1}{2}\bm{x}^{T}\bm{A}\bm{x}-\bm{x}^{T}\bm{b} is known as the cost function. The MPGP-type algorithms employ projections onto the feasible set \Omega . Therefore, the feasible set is typically assumed to be closed and convex so that the projection exists. In our case, we will restrict ourselves to \Omega consisting only of box constraints \Omega=\left\{\bm{x}\in\mathbb{R}^{n}\mid\bm{l}\leq\bm{x}\leq\bm{u}\right\}. The efficient solution of QP problems is important in a wide variety of fields, including economics, engineering, machine learning, and many others. Concrete applications where MPGP-type algorithms were used include contact mechanics in fractured rock [ 2 ] with applications to modeling deep geological repositories of radioactive waste [ 3 ] , machine learning for detecting wildfires from satellite images [ 4 ] or predicting compound bioactivity for the pharmaceutical industry [ 5 ] , and particle remapping for discrete element method modeling sea ice [ 6 ] . The restriction to the positive semidefinite Hessian allows us to use the conjugate gradient (CG) method for the unconstrained minimization part of the MPGP-type algorithm. The CG method is very successful for the solution of large systems of linear equations, and many aspects of its convergence are well understood [ 7 ] . Many problems solved by the CG method come from the discretization of PDEs with popular methods including finite elements/volumes, boundary elements, etc. In these cases, refining the discretization worsens the conditioning of the resulting systems of linear equations, i.e., the Hessian, which results in the slowdown of the CG convergence. The solution is to improve the spectrum of the Hessian using preconditioning. Our aim is to modify MPGP-type algorithms to be able to use preconditioning in the underlying CG method while not changing the constraints. This modification should not only lead to faster convergence in terms of the number of iterations but crucially in terms of time to solution. The paper is divided as follows. The following section briefly describes two MPGP-type algorithms - MPRGP and MPPCG. In section 3 , we discuss the difficulty with preconditioning QP problems and show how preconditioning is implemented into the MPGP-type method. Section 4 describes preconditioning in face, and section 5 describes its approximate variant, including the error between the two variants in specific settings. In section 6 , we have enough prerequisites to describe related works. Finally, we present numerical experiments in section 7 . 2 MPGP-type Algorithms QP problems with box constraints can be solved using the modified proportioning with reduced gradient projections (MPRGP) algorithm [ 8 , 1 ] . The simplification to the feasible set with only one of the bound constraints is straightforward. It is also possible to adapt the algorithm for various other constraints, such as elliptic and conical constraints [ 9 , 10 ] . As the name of the algorithm suggests, it utilizes gradient information for minimization, placing it among the first-order optimization methods. While MPRGP does not directly work with active and free sets, the information about active and free sets is hidden in the gradient splitting, which is described later. Consequently, MPRGP is considered an active set algorithm. The algorithm was developed from the Polyak algorithm [ 11 ] . A nice feature of the algorithm is that it has been proven to enjoy an R-linear rate of convergence given by the bound on the spectrum of the Hessian matrix [ 1 ] . In each iteration, MPRGP performs one of three types of steps: unconstrained minimization, expansion, or proportioning. Since our Hessian \bm{A} is SPS, the unconstrained minimization is performed by a step of the CG method. The active set is expanded by the expansion step , which consists of a maximal feasible unconstrained minimization, in our case a partial CG step to the box, followed by a fixed step length gradient projection. Finally, the proportioning step , designed to reduce the active set, consists of a step of the steepest descent method. To properly describe the algorithm, we first need to define the gradient splitting . Let \bm{g}=\bm{A}\bm{x}-\bm{b} be the gradient of the cost function f(\bm{x}) and let \mathcal{A}=\left\{i\;|\;\bm{x}_{i}=\bm{l}_{i}\quad\text{or}\quad\bm{x}_{i}=\bm{u}_{i}\right\},\qquad\mathcal{F}=\left\{i\;|\;\bm{l}_{i}<\bm{x}_{i}<\bm{u}_{i}\right\} be the active and free set , respectively. Then the gradient splitting is defined component-wise for i\in\{1,2,\dots,n\} and is computed after each gradient evaluation. The free gradient \bm{g}^{f} is defined as \displaystyle\bm{g}_{i}^{f}=\begin{cases}0\quad&\text{if}\quad i\in\mathcal{A},\\ \bm{g}_{i}\quad&\text{if}\quad i\in\mathcal{F}.\end{cases} (1) A step in the direction -\bm{g}^{f} may expand the active set but cannot reduce it. The chopped gradient \bm{g}^{c} is defined as \displaystyle\bm{g}_{i}^{c}=\begin{cases}0\quad&\text{if}\quad i\in\mathcal{F},\\ \min(\bm{g}_{i},0)\quad&\text{if}\quad\bm{x}_{i}=\bm{l}_{i},\\ \max(\bm{g}_{i},0)\quad&\text{if}\quad\bm{x}_{i}=\bm{u}_{i}.\end{cases} A step in the direction -\bm{g}^{c} may reduce the active set but cannot expand it. The next ingredient is the projection onto the feasible set \Omega , which in the case of box constraints can be computed cheaply as \left[P_{\Omega}(\bm{x})\right]_{i}=\min\left\{\bm{u}_{i},\max\left\{\bm{l}_{i},\bm{x}_{i}\right\}\right\},\quad i\in\{1,\dots,n\}. (2) Finally, the projected gradient is defined as \bm{g}^{P}=\bm{g}^{f}+\bm{g}^{c} . The decrease in its norm serves as the natural stopping criterion for the algorithm since \bm{g}^{P}=\bm{o} is equivalent to satisfying the Karush-Kuhn-Tucker conditions for a box-constrained QP problem. These are all the necessary ingredients to summarize MPRGP in Algorithm 1 . Input: \bm{A} , \bm{x}_{0}\in\Omega , \bm{b} , \Gamma>0 , \overline{\alpha}\in(0,2||\bm{A}||^{-1}) \bm{g}_{0}=\bm{A}\bm{x}_{0}-\bm{b} , \bm{p}_{0}=\bm{g}^{f}_{0} , k=0 1 while ||\bm{g}^{P}_{k}|| is not small : 2 if ||\bm{g}^{c}_{k}||^{2}\leq\Gamma^{2}||\bm{g}^{f}_{k}||^{2} : 3 \alpha^{feas}_{k}=\max\{\alpha\;|\;\bm{x}_{k}-\alpha\bm{p}_{k}\in\Omega\} 4 \alpha^{cg}_{k}=\bm{g}^{T}_{k}\bm{p}_{k}/\bm{p}^{T}_{k}\bm{A}\bm{p}_{k} 5 if \alpha^{cg}_{k}\leq\alpha^{feas}_{k} : 6 CG step - Algorithm 2 7 else: 8 Expansion step - Algorithm 3 ; else: 9 Proportioning step - Algorithm 4 ; k=k+1 10 Output: \bm{x}_{k} 11 Algorithm 1 MPRGP method \bm{x}_{k+1}=\bm{x}_{k}-\alpha^{cg}_{k}\bm{p}_{k} 1 \bm{g}_{k+1}=\bm{g}_{k}-\alpha^{cg}_{k}\bm{A}\bm{p}_{k} 2 \beta_{k}=\bm{p}^{T}_{k}\bm{A}\bm{g}^{f}_{k+1}/\bm{p}^{T}_{k}\bm{A}\bm{p}_{k} 3 \bm{p}_{k+1}=\bm{g}^{f}_{k+1}-\beta_{k}\bm{p}_{k} 4 Algorithm 2 CG step \bm{x}_{k+\frac{1}{2}}=\bm{x}_{k}-\alpha^{feas}_{k}\bm{p}_{k} 1 \bm{g}_{k+\frac{1}{2}}=\bm{g}_{k}-\alpha^{feas}_{k}\bm{A}\bm{p}_{k} 2 \bm{x}_{k+1}=P_{\Omega}(\bm{x}_{k+\frac{1}{2}}-\overline{\alpha}\bm{g}_{k}^{f}) 3 \bm{g}_{k+1}=\bm{A}\bm{x}_{k+1}-\bm{b} 4 \bm{p}_{k+1}=\bm{g}^{f}_{k+1} Algorithm 3 Expansion step \alpha^{sd}_{k}=\bm{g}^{T}_{k}\bm{g}^{c}_{k}/(\bm{g}^{c}_{k})^{T}\bm{A}\bm{g}^{c}_{k} 1 \alpha^{feas}_{k}=\max\{\alpha\;|\;\bm{x}_{k}-\alpha\bm{g}^{c}_{k}\in\Omega\} 2 if \alpha^{feas}_{k}<\alpha^{sd}_{k} : 3 \alpha^{sd}_{k}=\alpha^{feas}_{k} 4 \bm{x}_{k+1}=\bm{x}_{k}-\alpha^{sd}_{k}\bm{g}^{c}_{k} 5 \bm{g}_{k+1}=\bm{g}_{k}-\alpha^{sd}_{k}\bm{A}\bm{g}^{c}_{k} 6 \bm{p}_{k+1}=\bm{g}^{f}_{k+1} 7 Algorithm 4 Proportioning step The generalization to other constraints is in the way the maximal feasible step-length \alpha_{k}^{feas} is computed, the definition and ease of computing the projection onto the feasible set \Omega , and potentially restricting the constant step-length to the first half of the interval, i.e., \overline{\alpha}\in(0,||\bm{A}||^{-1}) , when the set \Omega is not subsymmetric [ 9 , 12 ] . The projections onto the feasible set \Omega often have closed forms that are easily evaluated, as in our case given by eq. 2 .

Read the complete text