Exact Verification of First-Order Methods via Mixed-Integer Linear Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914610053906432 |
|---|---|
| author | Ranjan, Vinit Park, Jisun Gualandi, Stefano Lodi, Andrea Stellato, Bartolomeo |
| author_facet | Ranjan, Vinit Park, Jisun Gualandi, Stefano Lodi, Andrea Stellato, Bartolomeo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11330 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact Verification of First-Order Methods via Mixed-Integer Linear Programming Ranjan, Vinit Park, Jisun Gualandi, Stefano Lodi, Andrea Stellato, Bartolomeo Optimization and Control 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. |
| title | Exact Verification of First-Order Methods via Mixed-Integer Linear Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.11330 |