Reformulations of Quadratic Programs for Lipschitz Continuity

Devansh R. Agrawal, Haejoon Lee, Dimitra Panagou · 2025

Read Reformulations of Quadratic Programs for Lipschitz Continuity by Devansh R. Agrawal, Haejoon Lee, Dimitra Panagou (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-2508-18530.txt.

Introduction

Devansh Agrawal, Haejoon Lee, and Dimitra Panagou rework quadratic programs for smoother controllers in a 2025 paper. Controllers based on optimization can jump sharply between answers. Many constraints make that jumpiness worse. Smooth response to inputs is a must for well-posed control.

Their method converts the quadratic program into a cone problem. The new problem is proven Lipschitz continuous. This holds no matter the shape of the constraints. Independence of constraint gradients is not assumed. A closed-form answer exists for the new problem. General quadratic programs with many constraints lack one. Closed form means faster work in the loop. Strict analysis backs each claimed trait. Examples show the new form in action. Control theorists gain regularity without giving up ease of use. Safety-critical optimization gains most. The approach is general, not tuned to one use.

Catalog record

CREATORDevansh R. Agrawal, Haejoon Lee, Dimitra Panagou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18530

Browse the full library · About the Tower of Babel

Full text

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

Reformulations of Quadratic Programs for Lipschitz Continuity Devansh R. Agrawal, Haejoon Lee, Dimitra Panagou Abstract Optimization-based controllers often lack regularity guarantees, such as Lipschitz continuity, when multiple constraints are present. When used to control a dynamical system, these conditions are essential to ensure the existence and uniqueness of the system’s trajectory. Here we propose a general method to convert a QP ( QP ) into a SOCP ( SOCP ), which is shown to be Lipschitz continuous. Key features of our approach are that (i) the regularity of the resulting formulation does not depend on the structural properties of the constraints, such as the linear independence of their gradients; and (ii) it admits a closed-form solution, which is not available for general QP with multiple constraints, enabling faster computation. We support our method with rigorous analysis and examples. [Code] 1 1 1 Code: https://github.com/joonlee16/Lipschitz-controllers I Introduction This paper investigates the Lipschitz continuity of parametric QP ( QP ) of the form \displaystyle\min_{u\in\mathbb{R}^{m}}\ \displaystyle\left\|u-\pi_{\rm des}(x)\right\|^{2} (1a) \displaystyle\operatorname*{s.t.}\ \displaystyle u\in K(x), (1b) where x\in\mathcal{X}\subset\mathbb{R}^{n} is a parameter, and \displaystyle K(x)=\left\{u\in\mathbb{R}^{m}:A(x)u\leq b(x)\right\} (2) is a convex polyhedral set with A:\mathcal{X}\to\mathbb{R}^{p\times m} , b:\mathcal{X}\to\mathbb{R}^{p} , and \pi_{\rm des}:\mathcal{X}\to\mathbb{R}^{m} . We assume throughout that K(x) is nonempty at each x\in\mathcal{X} . The set of minimizers of ( 1 ) is denoted by \displaystyle\Pi(x)=\operatorname*{argmin}_{\begin{subarray}{c}u\in K(x)\end{subarray}}\left\|u-\pi_{\rm des}(x)\right\|^{2}, (3) where \Pi:\mathcal{X}\rightrightarrows\mathbb{R}^{m} is a set-valued map. Since K is always nonempty and the objective function is strongly convex, \Pi(x) contains exactly one element at each x\in\mathcal{X} . This unique minimizer is denoted by \pi:\mathcal{X}\to\mathbb{R}^{m} . Lipschitz continuity of \pi , the (unique) minimizer of parametric problems such as ( 3 ), is of fundamental importance. For example, consider a nonlinear dynamical system \displaystyle\dot{x}=f(x,u)=f(x,\pi(x))=f_{\rm cl}(x), (4) where the control input determined by ( 3 ), that is, u=\pi(x) . When \pi is Lipschitz continuous, its sensitivity to changes in x is bounded. That is, small perturbations in the state (induced by noise, numerical inaccuracies, etc.) result in bounded deviations in the control input, thereby preventing instability or chattering behavior of the system. Moreover, the Lipschitz continuity of \pi induces Lipschitz continuity of the closed-loop dynamics f_{\rm{cl}} . In turn, this ensures that the system ( 4 ) admits a unique solution for all time [ 1 ] , guaranteeing that the system trajectories are unique. Fig. 1: A depiction of the main problem and our proposed solution approach. In parametric QP , the solution \pi_{\rm qp}(x) may be non-Lipschitz or even discontinuous with respect to x . This paper defines a subset \Phi(x) of the constraint set K(x) that is always feasible and Lipschitz continuous on \mathbb{R}^{m} (defined in 2 ) such that the modified solution \pi(x) is Lipschitz continuous. This is done by identifying a Lipschitz continuous function \pi_{\rm f}(x) that is always feasible, and constructing a set \Phi(x) around it such that \pi_{\rm socp}(x) is Lipschitz wrt x . However, it is well known that in the absence of certain constraint qualifications (e.g., LICQ ( LICQ )), \pi can be non-Lipschitz or even discontinuous [ 2 , 3 , 4 ] . This is true even when A,b,\pi_{\rm des} are continuously differentiable with respect to x (see Example 1 ), or SC ( SC ) is satisfied (see Example 2 ). Example 1 . Let x\in\mathcal{X}=\mathbb{R} . Consider the QP \displaystyle\pi_{\rm qp}(x)=\operatorname*{argmin}_{\begin{subarray}{c}u\in\mathbb{R}^{2}\end{subarray}}\ \displaystyle\left\|u-\begin{bmatrix}-2\\ 0\end{bmatrix}\right\|^{2} (5a) \displaystyle\operatorname*{s.t.}\ \displaystyle\begin{bmatrix}1&0\\ -1&-x\end{bmatrix}u\leq\begin{bmatrix}1\\ -(1+x)\end{bmatrix}. (5b) The solution of ( 5 ) can be derived analytically, and is plotted in Figure 2 (c). Even though A,b are continuously differentiable, notice that there exists a discontinuity of solution at x=0 . Fig. 2: Fig. (a) and (b) depict the feasible spaces and solutions of the original QP ( 5 ) and of our proposed SOCP reformulation in the form of ( 16 ) at x=-2 and x=2 , respectively. Note at x=0 , K(x) shrinks to \{u\in\mathbb{R}^{2}:u_{1}=1\} , a set with no interior. This causes \pi_{\rm qp} to jump, as depicted in Fig. (c). In contrast, the SOCP reformulation introduces a smoothly varying feasible space \Phi(x) centered at \pi_{\rm f}(x) , ensuring that the solution \pi_{\rm socp}(x) transitions without jumps, as depicted in Fig. (d). Animations are available in our supplementary repository . Since discontinuous solutions may not be preferable in practice, e.g., due to chattering phenomena, the focus of this paper is to reformulate ( 1 ) into a problem of the form \displaystyle\min_{u\in\mathbb{R}^{m}}\ \displaystyle\left\|u-\pi_{\rm des}(x)\right\|^{2} (6a) \displaystyle\operatorname*{s.t.}\ \displaystyle u\in\Phi(x)\subset K(x), (6b) whose minimizer is both unique and Lipschitz continuous with respect to x . To this end, we propose a suitable definition for \Phi:\mathcal{X}\rightrightarrows\mathbb{R}^{m} and demonstrate that, by construction, its properties ensure the Lipschitz continuity of the minimizer of ( 6 ). Figure 1 depicts this pictorially. Literature Review: Parametric optimization — both convex and nonconvex — has been extensively studied [ 5 , 6 , 7 , 8 ] , with a central focus on establishing conditions under which the solution map exhibits regularity [ 9 , 10 , 11 , 3 , 2 ] . Under constraint qualifications such as LICQ , MFCQ ( MFCQ ), and SC , solutions to QP can be differentiable, Lipschitz, or Hölder continuous, depending on the setting. See [ 8 , 11 ] for detailed summary. To apply these results, one must verify constraint qualifications hold. Although feasible in some cases [ 12 , 13 , 14 ] , this is generally difficult. One alterative approach is to combine multiple constraints into a unified constraint [ 15 , 16 , 17 ] , where LICQ holds trivially. However, this may render the problem infeasible even if K(x) is non-empty. Another line of work analyzes regularity of the feasible set map K:\mathcal{X}\rightrightarrows\mathbb{R}^{m} , treating it as a set-valued mapping [ 18 , 7 , 19 ] . This literature studies whether K is Lipschitz continuous and when Lipschitz selections of K exist. Contributions: In this paper, we take a fundamentally different approach. Instead of focusing on the structural conditions of the QP like constraint qualifications, we • propose a method to reformulate the QP ( 3 ) into a SOCP ( SOCP ) ( 6 ) that is guaranteed to admit a unique Lipschitz continuous solution under mild assumptions, • show that our SOCP admits a closed-form solution, • illustrate the challenges and ideas through examples, • provide a conjecture to expand the set of feasible solutions and reduce conservatism. The core theoretical insight is that by carefully tightening the constraint set, we ensure Lipschitz continuity while preserving uniqueness. A key source of non-Lipschitz behavior in ( 3 ) is when two active constraints become linearly dependent, as shown in Example 1 . Small perturbations in this case can drastically alter the feasible set and solution. Our formulation defines \Phi to avoid such degeneracies. II PRELIMINARIES Let \mathbb{R} denote the set of reals. Let C^{k} denote the set of functions with k continuous derivatives. Definition 1 ( [ 8 , Def 9.1] ) . Let X,Y be normed spaces. A function f:X\to Y is Lipschitz continuous on X if there exists a L\geq 0 such that \displaystyle\left\|f(x_{1})-f(x_{2})\right\|\leq L\left\|x_{1}-x_{2}\right\|,\ \forall x_{1},x_{2}\in X. (7) f is locally Lipschitz at x\in X if there exists a neighborhood \mathcal{B}\subset X

Read the complete text