Exact Verification of First-Order Methods via Mixed-Integer Linear Programming
Vinit Ranjan, Jisun Park, Stefano Gualandi, Andrea Lodi, Bartolomeo Stellato · 2024
Read Exact Verification of First-Order Methods via Mixed-Integer Linear Programming by Vinit Ranjan, Jisun Park, Stefano Gualandi, Andrea Lodi, Bartolomeo Stellato (2024) 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-2412-11330.txt.
Introduction
Vinit Ranjan and four co-authors present an exact check in 2024 for the worst-case behavior of fast solving methods. Such methods tackle math problems step by step and drive tools from networks to control systems. Proving how badly they can lag, rather than guessing, is hard.
The team casts the check as a mixed-integer linear program. Its goal is to push the leftover error as high as it can go after a set number of steps. Tight shapes for each step keep the math exact, and a custom tightening step speeds the search. Tests on network, coding, and control problems cut the worst-case bounds by orders of size.
Catalog record
| CREATOR | Vinit Ranjan, Jisun Park, Stefano Gualandi, Andrea Lodi, Bartolomeo Stellato |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11330
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact Verification of First-Order Methods via Mixed-Integer Linear Programming Vinit Ranjan, Jisun Park, Stefano Gualandi, Andrea Lodi, Bartolomeo Stellato Abstract We present exact mixed-integer linear programming formulations for verifying the performance of first-order methods for parametric quadratic optimization. We formulate the verification problem as a mixed-integer linear program where the objective is to maximize the infinity norm of the fixed-point residual after a given number of iterations. Our approach captures a wide range of gradient, projection, proximal iterations through affine or piecewise affine constraints. We derive tight polyhedral convex hull formulations of the constraints representing the algorithm iterations. To improve the scalability, we develop a custom bound tightening technique combining interval propagation, operator theory, and optimization-based bound tightening. Numerical examples, including linear and quadratic programs from network optimization, sparse coding using Lasso, and optimal control, show that our method provides several orders of magnitude reductions in the worst-case fixed-point residuals, closely matching the true worst-case performance. 1 Introduction Convex Quadratic Programming (QP) is a fundamental class of optimization problems in applied mathematics, operations research, engineering, and computer science [ 18 ] with several applications from finance [ 17 , 57 ] and machine learning [ 20 , 30 , 49 , 80 ] , to signal processing [ 23 , 58 ] and model predictive control [ 15 ] . A particularly important subclass of QP is Linear Programming (LP) [ 31 ] , which is widely used in scheduling [ 46 ] , network optimization [ 12 ] , chip design [ 53 ] , and resource allocation [ 13 ] . In many such applications, solving the optimization problem is part of a wider system, imposing strict computational requirements on the algorithm used. In particular, these algorithms consist of repeated iterations, generating a sequence of points that converge to an optimal solution, if the problem is solvable. Depending on the operational speed of each application, the time available to solve each optimization problem may vary from minutes to milliseconds, which, in turn, sets an exact limit on the number of allowed iterations. Therefore, to safely deploy optimization algorithms, we must ensure that they always converge within the prescribed iteration limit, i.e. , in real-time. First-order optimization algorithms have attracted an increasing interest over the last decade due to their low per-iteration cost and memory requirements, and their warm-start capabilities. These properties are particularly useful, on the one hand, in large-scale optimization problems arising in data-science and machine learning, and, on the other hand, in embedded optimization problems arising in engineering and optimal control. First-order methods date back to the 1950s and were first applied to QPs for the development of the Frank-Wolfe algorithm [ 36 ] . Recently, several general-purpose solvers based on first-order methods have appeared, including PDLP [ 2 , 3 ] for LP, OSQP [ 75 ] and QPALM [ 47 ] for QP, and SCS [ 62 , 60 ] and COSMO [ 37 ] for conic optimization. These methods feature several algorithmic enhancements that make them generally reliable, including acceleration [ 62 ] , and restarts [ 2 , 3 ] , which guarantee worst-case linear convergence rates. However, their exact non-asymptotic empirical behavior for a fixed budget of iterations is not clearly understood. In particular, their practical convergence behavior can be very different, and sometimes significantly better, than the worst-case bounds that do not account for any application-specific problem structure and warm-starts used. In this paper, we introduce an exact and scalable Mixed-Integer Linear Programming (MILP) formulation of the problem of analyzing the performance of first-order methods in LP and QP. 1.1 The problem We are interested in solving QPs of the form \begin{array}[]{ll}\text{minimize}&(1/2)z^{T}Pz+q(x)^{T}z\\ \text{subject to}&Az+r=b(x)\\ &r\in C_{1}\times C_{2}\times\dots\times C_{L},\end{array} (1) with variables z\in{\mbox{\bf R}}^{n} and r\in{\mbox{\bf R}}^{m} , and instance parameters x\in X\subseteq{\mbox{\bf R}}^{p} , where X is a polyhedron. The sets C_{i}\subseteq{\mbox{\bf R}}^{n_{i}} come from a selected list: the zero set \{0\}^{n_{i}} to model equality constraints, the nonnegative orthant {\mbox{\bf R}}_{+}^{n_{i}} to model one-sided inequality constraints, and the box [\ell,u]\subseteq{\mbox{\bf R}}^{n_{i}} to model double-sided inequality constraints. We denote the objective as f(z,x)=(1/2)z^{T}Pz+q(x)^{T}z with positive semidefinite matrix P\in{\mbox{\bf S}}_{+}^{n} and affine function q(x)\in{\mbox{\bf R}}^{n} . The constraints are defined by matrix A\in{\mbox{\bf R}}^{m\times n} , and affine function b(x)\in{\mbox{\bf R}}^{m} . If P=0 , problem ( 1 ) becomes an LP. We focus on settings where we solve several instances of problem ( 1 ) with varying instance parameters x . We assume problem ( 1 ) to be solvable for any x\in X and we denote the optimal solutions as z^{\star}(x) . Problems where q(x) and b(x) change arise in a wide range of settings, including sparse coding using Lasso [ 80 ] ( x being the input signal), model predictive control [ 15 ] ( x being the state of a linear dynamical system), and network flow problems [ 12 , Ch. 1] ( x being the node supplies). Our goal is to solve problem ( 1 ) using first-order methods of the form s^{k+1}=T(s^{k},x),\quad k=0,1,\dots, (2) where T is a fixed-point operator that maps the (primal-dual) iterate s^{k}\in{\mbox{\bf R}}^{d} to s^{k+1}\in{\mbox{\bf R}}^{d} depending on the instance parameter x . For prescribed iteration-dependent schedules, we also allow s^{k+1}=T_{k}(s^{k},x) and interpret T^{K} below as T_{K-1}\circ\cdots\circ T_{0} at fixed x . For any convergent first-order method and instance x , T can be constructed such that the fixed-points of T correspond to the optimal solution of the given instance. We assume the operator to be L -Lipschitz in its first argument with L>0 and, therefore, single-valued [ 70 , Sec. 2.1] . Operators of this form encode a wide range of algorithms, including gradient descent, proximal gradient descent, and operator splitting algorithms [ 70 ] . We denote the initial iterate set as the polyhedron S\subset{\mbox{\bf R}}^{d} . For cold-started algorithms, we have {S=\{0\}} . For a given x , fixed-points s^{\star}=T(s^{\star},x) correspond to the (primal-dual) optimal solutions of problem ( 1 ) ( i.e. , we can compute z^{\star} from s^{\star} ). We define the fixed-point residual at iterate s^{k} for parameter x as T(s^{k},x)-s^{k} . As k\to\infty , the fixed-point residual converges to 0 for common cases of operators ( e.g. , averaged or contractive [ 7 , Corollary 5.8, Theorem 1.50] , [ 70 , Theorem 1] ). Furthermore, it is often the case that the fixed-point residual with proper scaling can model the optimality conditions of ( 1 ). In Section 4 , we provide algorithm-specific scaling matrices H such that H(s^{K}-s^{K-1}) recovers the optimality conditions of the specific problem. Therefore, the fixed-point residual is an easily computable measure of suboptimality and infeasibility. It is worth noting that in some cases, the fixed-point residual may not monotonically decrease; it may even increase for some iterations. However, for any convergent first-order method, the residual will still converge to 0 as k\to\infty . We are interested in numerically verifying that the worst-case magnitude of the fixed-point residual after K iterations is at most an accepted tolerance \epsilon>0 . Specifically, we would like to verify the following condition: \|H(T^{K}(s^{0},x)-T^{K-1}(s^{0},x))\|_{\infty}\leq\epsilon,\quad\forall x\in X,\;s^{0}\in S, (3) where T^{K}(s^{0},x) denotes the K -times composition of T with parameter x , starting from iterate s^{0}