A Hybrid Perspective on Suboptimal Mixed-Integer Quadratic Programming

Luke Fina, Christopher Petersen · 2025

Read A Hybrid Perspective on Suboptimal Mixed-Integer Quadratic Programming by Luke Fina, Christopher Petersen (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-02772.txt.

Introduction

Luke Fina and Christopher Petersen build controllers that solve hard mixed-integer optimization problems only approximately, on purpose, and still keep systems stable. Their 2025 paper works on mixed-integer quadratic programs, which arise when control decisions mix continuous dials with on-off switches. Solving them exactly at every step is often too slow for live feedback.

The framework treats the solver's shortcuts as bounded disturbances from the true optimal answer. Parametric optimization plus hybrid systems theory then models the controller and the plant as one system. Stability is proved for that combined loop rather than assumed. Simulations of model predictive control with several solver settings bear the theory out. The authors argue engineers can tune solver effort for speed without flying blind on safety.

Catalog record

CREATORLuke Fina, Christopher Petersen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

A Hybrid Perspective on Suboptimal Mixed-Integer Quadratic Programming Luke Fina, Christopher Petersen Abstract This work solves suboptimal mixed-integer quadratic programs recursively for feedback control of dynamical systems. The proposed framework leverages parametric mixed-integer quadratic programming (MIQP) and hybrid systems theory to model a recursive MIQP feedback controller and a feedback controlled dynamical system. The proposed hybrid framework theoretically encodes the suboptimal part via solver parameters as bounded perturbations from the optimal solution set. The stability of the proposed hybrid framework is theoretically guaranteed and validated through MIQP model predictive control simulations with multiple solver parameters. I Introduction Optimization-based feedback control is dependent on recursive optimization algorithms updating as new information from a dynamical system arrives, like position and disturbances updates. Approximation error is well known to occur for feedback control and classically is viewed as uncertainty in the plant model [ 1 ] . In recent years, researchers have begun to analyze approximation error bounds in the controller due to optimization algorithm performance in optimization-based feedback control [ 2 ] . This work extends this approximation error bound analysis to the field of recursive mixed-integer optimization and analyzes the asymptotic behavior of the mixed-integer feedback control of a dynamical system, where the term mixed-integer means there are discrete and continuous decision variables. An optimization-based feedback controller with algorithm-based approximation error analysis can be viewed as a discrete-time dynamical system [ 2 ] . For example, treating a continuous optimization algorithm as a discrete-time dynamical system recently provided new insights into algorithm phenomena that have previously eluded theoretical understanding for the accelerated Nestrov method [ 3 ] . Treating mixed-integer algorithms as discrete-time dynamical systems is less explored [ 2 ] . One work that explores this perspective, solves integer optimization as a collection of coupled oscillators [ 4 ] . Aside from this work, the discrete-time dynamical systems perspective for mixed-integer algorithms has seldom been explored to the author’s knowledge. One important distinction to make is that recursive continuous optimization algorithms have analytical convergence rates that allow for strong theoretical discrete-time dynamics analysis [ 5 ] , while mixed-integer optimization algorithms do not have theoretically derivable convergence rates [ 6 ] . However, modern mixed-integer solvers combine a collection of heuristics, branch-and-bound, and cuts to achieve fast solutions in practice [ 7 , 6 ] . To that end, this work abstracts mixed-integer algorithms to a black box solver, introduces relevant black box solver terms, and analyzes the asymptotic behavior of the mixed-integer solver and feedback controlled dynamical system. Quadratic programs (QPs) are prevalent in recursive continuous optimization for feedback control, e.g. model predictive control and control barrier functions [ 8 , 9 ] . Due to the prevalence of quadratic programming in feedback control, our work focuses on the mixed-integer version of quadratic programming, mixed-integer quadratic programming (MIQP). MIQPs can model control scenarios that QPs cannot, e.g. when the control is integer in model predictive control [ 10 ] or signal temporal logic [ 11 ] . This work focuses on recursive MIQPs, but the theory can be easily extended to recursive mixed-integer linear programming and recursive indefinite quadratic programming. To be precise, this work leverages the theory of parametric MIQP for recursive MIQPs to prove the MIQP solver feedback controller and feedback controlled dynamical system with sufficient regularity conditions is a hybrid system. A blend of continuous time and discrete time systems can be theoretically described by hybrid systems [ 12 , 13 ] . The MIQP solver operating on hardware is modeled over discrete time and the feedback controlled dynamical system is modeled over continuous time. Recently, continuous optimization algorithm works have explored a hybrid system framework [ 14 , 15 ] . Finally, this work explores specific MIQP solver parameters useful for practitioners. To summarize, the main contributions of this paper are the following: • A novel hybrid systems framework for recursive MIQPs is proposed, and the framework generalizes to recursive mixed-integer linear programs and recursive indefinite quadratic programs by leveraging parametric MIQPs. • Sufficient regularity conditions are presented for the recursive MIQP and feedback controlled dynamical system to satisfy the basic hybrid conditions (Theorem 1 ). • Stability conditions are derived for solutions to the proposed hybrid system with suboptimal solver parameters (Theorem 2 ). • Useful suboptimal solver parameters are explored by solving MIQP model predictive control in simulation. The rest of the paper is organized as follows. Section II presents preliminaries for the recursive MIQP and the hybrid system formulation. Section III defines solver processes and solver parameters. Section IV presents stability guarantees for the proposed hybrid framework. Section V explores suboptimal solver parameters for MIQP model predictive control and the impact on hybrid solutions. Section VI concludes. Section VII includes technical details necessary for the proofs in this work. Notation and Terminology: In this work, parametric optimization is leveraged to theoretically analyze recursive optimization. Parametric optimization is based on point set mappings. Point to set mappings are used within the optimization literature and are denoted as the power set 2^{\mathbb{R}^{p}}, which is the family of all sets [ 16 ] . Set value mappings by definition are mappings from an arbitrary set X to the power set. This work treats point to set mappings as the more general set value mappings throughout this work [ 17 ] [Ch 5]. A set valued map M from S\subseteq\mathbb{R}^{p} to the power set of some Euclidean space \mathbb{R}^{p} is denoted by M:S\rightrightarrows\mathbb{R}^{p}. The domain \text{dom}M of a set value map is defined as \text{dom}M=\{x\in\mathbb{R}^{p}|M(x)\neq\emptyset\}. Set value mappings are also the fundamental mathematical tool for differential inclusions. Discrete time variants of differential inclusions are termed difference inclusions and are used for explicitly modeling the optimization problem in the proposed hybrid systems framework. A function \alpha:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} is a class \mathcal{K}_{\infty} function if \alpha is zero at zero, continuous, strictly increasing, and unbounded. A function \beta:\mathbb{R}_{\geq 0}\times\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0} is a class \mathcal{KL} function if it is non-decreasing in its first argument, non-increasing in its second arguments, i.e, \lim_{r\to 0^{+}}\beta(r,s)=0 for each s\in\mathbb{R}_{\geq 0}, and \lim_{s\to\infty}\beta(r,s)=0 for each r\in\mathbb{R}_{\geq 0}. The notation |\cdot|_{\mathcal{A}} denotes the Euclidean norm for a point \cdot to the set \mathcal{A}. This work denotes the real numbers as \mathbb{R}, the rational numbers as \mathbb{Q}, and x+\mathbb{B} denotes a closed Euclidean unit ball center at x. II Preliminaries and Problem Statement This section connects notions of regularity from a parametric MIQP and hybrid systems context, then formulates a hybrid systems framework for parametric MIQPs with sampled continuous dynamics changing over time. Section IV derives stability conditions for the proposed hybrid system. II-A Parametric MIQPs Preliminaries MIQPs in feedback control are solved recursively, we leverage the theoretical framework of parametric optimization to theoretically analyze the recursive MIQP. Varying information can be constructed in a constraint or objective term at every sample time k . In this work, the parametric MIQP focuses on information varying in a linear objective term and affine constraints, where the parameter is a sampled state from a continuous dynamical system. The connection between parametric optimization and time-varying convex optimization literature inspires the connection between recursive MIQPs and parametric optimization in this work [ 18 ] . This work studies a

Read the complete text