Verification of Sequential Convex Programming for Parametric Non-convex Optimization

2025/11/13 by Rajiv Sambharya, Nikolai Matni, Sambharya, Rajiv +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Adversarial Robustness in Machine Learning #FOS: Mathematics #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2511.10622

openalex publication_date 2025/11/13 · openalex created_date 2025/11/15 · openalex updated_date 2026/07/28

Abstract

We introduce a verification framework to exactly verify the worst-case performance of sequential convex programming (SCP) algorithms for parametric non-convex optimization. The verification problem is formulated as an optimization problem that maximizes a performance metric (e.g., the suboptimality after a given number of iterations) over parameters constrained to be in a parameter set and iterate sequences consistent with the SCP update rules. Our framework is general, extending the notion of SCP to include both conventional variants such as trust-region, convex-concave, and prox-linear methods, and algorithms that combine convex subproblems with rounding steps, as in relaxing and rounding schemes. Unlike existing analyses that may only provide local guarantees under limited conditions, our framework delivers global worst-case guarantees--quantifying how well an SCP algorithm performs across all problem instances in the specified family. Applications in control, signal processing, and operations research demonstrate that our framework provides, for the first time, global worst-case guarantees for SCP algorithms in the parametric setting.

Citations

• Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
• Learning Acceleration Algorithms for Fast Parametric Convex Optimization with Certified Robustness
• Data-Driven Performance Guarantees for Parametric Optimization Problems
• Deep Distributed Optimization for Large-Scale Quadratic Programming
• Learning Algorithm Hyperparameters for Fast Parametric Convex Optimization
• Clarabel: An interior-point solver for conic programs with quadratic objectives
• Data-Driven Performance Guarantees for Classical and Learned Optimizers
• Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation
• Verification of First-Order Methods for Parametric Quadratic Optimization
• Learning to Warm-Start Fixed-Point Optimization Algorithms
• OMLT: Optimization & Machine Learning Toolkit
• Tutorial on amortized optimization
• CoCo: Online Mixed-Integer Control via Supervised Learning
• Accelerated Forward-Backward Optimization using Deep Learning
• Learning to Optimize: A Primer and A Benchmark
• Operator splitting for a homogeneous embedding of the linear\n complementarity problem
• Large Scale Model Predictive Control with Neural Networks and Primal Active Sets
• Online Mixed-Integer Optimization in Milliseconds
• Learning Warm-Start Points for AC Optimal Power Flow
• GuSTO: Guaranteed Sequential Trajectory Optimization via Sequential Convex Programming
• Machine Learning for Combinatorial Optimization: a Methodological Tour\n d'Horizon
• Machine learning for combinatorial optimization: A methodological tour d’horizon
• Strong mixed-integer programming formulations for trained neural networks
• Strong mixed-integer programming formulations for trained neural networks
• The proximal point method revisited
• A Review on Bilevel Optimization: From Classical to Evolutionary\n Approaches and Applications
• Efficiency of minimizing compositions of convex functions and smooth\n maps
• Disciplined Convex-Concave Programming
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic\n Programming
• Mixed Integer Linear Programming Formulation Techniques
• Выпуклая оптимизация
• A proximal method for composite minimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A branch-and-cut method for 0-1 mixed convex programming

Related

• Sequential Convex Programming for the Efficient Verification of Parametric MDPs
• Verification of First-Order Methods for Parametric Quadratic Optimization
• Sequential Convex Restriction and its Applications in Robust Optimization
• Exact Verification of First-Order Methods via Mixed-Integer Linear Programming
• Learning Acceleration Algorithms for Fast Parametric Convex Optimization with Certified Robustness