betaFeedback

WorksMathematics

Continuous-time analysis and algorithms for linear and convex quadratic programs via exactly solvable differential inclusions

Abstract

Linear and convex quadratic programs are fundamental problems in optimization. While many methods have been developed for solving these programs in large-scale applications, to our knowledge none have attempted to solve their continuous-time gradient flow, a differential inclusion, in full generality without assumptions beyond feasibility. Recent work solved the gradient flows in two special cases, basis pursuit and the lasso, and obtained competitive algorithms. Motivated by these results, we solve the general case exactly. Using the minimal selection principle for monotone differential inclusions, we show that the trajectory of the gradient flow consists of finitely many pieces, each obtained from one nonnegative least-squares problem. Its final piece yields an optimal solution or a certificate of unboundedness. This analysis leads to two algorithms. The first algorithm is exact, terminates after finitely many steps, and applies to linear programs and projections onto polyhedra. The second algorithm, which we call minimal selection descent, discretizes the gradient flow for general convex quadratic programs. Its iterates converge to an optimal solution when one exists and otherwise certify unboundedness. We apply both algorithms to a positivity-preserving limiter for a discontinuous Galerkin scheme and to optimal control problems for the Poisson and heat equations. In the limiter, the first algorithm conserves the total mass more accurately than the state-of-the-art Douglas–Rachford splitting method. On the control problems, minimal selection descent reaches the optimal value to machine precision and is competitive in time with commercial and open-source solvers.

Introduction

Linear and convex quadratic programs [1, 2] are fundamental optimization problems used in many fields, including operations research, economics, robotics, machine learning, and scientific computing [3, 4, 5, 6, 7, 8]. These problems can be expressed as

min⁡x∈Rn{12⟨x,Qx⟩+⟨c,x⟩} subject to Ax≤b,(1)\min_{x\in\mathbb{R}^{n}} \left\{ \frac{1}{2}\langle x,Qx\rangle+ \langle c,x\rangle\right\}\ \text{subject to } Ax\le b, \tag*{(1)}

where Q∈Rn×nQ\in\mathbb{R}^{n\times n} is symmetric positive semidefinite (SPSD), A∈Rm×nA\in\mathbb{R}^{m\times n}, c∈Rnc\in\mathbb{R}^{n}, and b∈Rmb\in\mathbb{R}^{m}. Problem (1) is a linear program when Q=0Q=0 and a quadratic program otherwise. The study of algorithms for these problems began in the 1940s and 1950s, and much of modern optimization theory originates in it [9, 10, 11]. In current applications, the dimensions mm and nn are often large, and researchers have developed many new methods to solve problem (1) at that scale [12, 13].

We consider here the continuous-time optimization of problem (1) via a differential inclusion [14, 15]. Let C={x∈Rn:Ax≤b}C=\{x\in\mathbb{R}^{n}:Ax\le b\} and assume that CC is nonempty. The (nonsmooth) gradient flow of problem (1) is the differential inclusion

x˙(τ)∈−Qx(τ)−c−NC(x(τ)),x(0)=x0∈C,(2)\dot{x}(\tau)\in-Qx(\tau)-c-N_C(x(\tau)),\qquad x(0)=x_0\in C, \tag*{(2)}

where NC(x(τ))N_C(x(\tau)) denotes the normal cone of CC at x(τ)x(\tau) (see Table 1 in § 2). At each time τ\tau, the velocity x˙(τ)\dot{x}(\tau) is an element of the nonempty set on the right-hand side of (2). This differential inclusion has a unique solution, which converges to an optimal solution of problem (1) whenever one exists [14, 15].

NotationMeaning
[m][m]The indices i∈{1,2,…,m}i \in\{1,2,\ldots,m\};
pEp_{\mathcal{E}}The ∣E∣|\mathcal{E}|-dimensional subvector of p∈Rmp \in\mathbb{R}^{m} indexed by E⊂[m]\mathcal{E} \subset[m];
⟨x1,x2⟩\langle x_1,x_2\rangleThe Euclidean scalar product of two vectors x1,x2∈Rnx_1,x_2 \in\mathbb{R}^{n};
int⁡C\operatorname{int} CInterior of a nonempty subset CC;
ri⁡C\operatorname{ri} CRelative interior of a nonempty subset CC;
χC\chi_CThe characteristic function of a set CC: χC(x):={0if x∈C,+∞otherwise.\chi_C(x) := \begin{cases} 0 & \text{if } x \in C, \\ +\infty& \text{otherwise.} \end{cases}
dom⁡f\operatorname{dom} fThe domain of a function ff: dom⁡f:={x∈Rn:f(x)<+∞}\operatorname{dom} f := \{x \in\mathbb{R}^{n}: f(x) < +\infty\};
NC(x)N_C(x)The normal cone of a closed convex set CC at x∈Cx \in C: NC(x):={s∈Rn:⟨s,y−x⟩≤0 for every y∈C}N_C(x) := \{s \in\mathbb{R}^{n}: \langle s,y-x\rangle\le0 \text{ for every } y \in C\};
TC(x)T_C(x)The tangent cone of a closed convex set CC at x∈Cx \in C: TC(x):={d∈Rn:⟨s,d⟩≤0 for every s∈NC(x)}T_C(x) := \{d \in\mathbb{R}^{n}: \langle s,d\rangle\le0 \text{ for every } s \in N_C(x)\};
proj⁡C(x)\operatorname{proj}_C(x)Projection of x∈Rnx \in\mathbb{R}^{n} onto a closed convex set C⊂RnC \subset\mathbb{R}^{n}: proj⁡C(x):=arg⁡min⁡y∈C ∥x−y∥2\operatorname{proj}_C(x) := \underset{y\in C}{\arg\min}\ \lVert x-y\rVert^2

Table 1. Some notation and definitions used in this work.

Solutions of differential inclusions, however, have rarely been computed exactly, except in simple examples [16, 17] and for certain linear complementarity systems describing mechanical systems and electrical networks [18]. Most research has instead focused on the theory of differential inclusions and on the numerical approximation of their solutions in, e.g., nonsmooth analysis, control theory, and optimization [14, 15, 19, 20, 21, 22, 23]. Exact solutions have recently been computed for the differential inclusions of basis pursuit and the lasso [5, 24] by Tendero et al. [25] and Langlois and Darbon [26]. Both papers used these solutions to analyze the dynamics and to derive algorithms that are exact (numerically up to machine precision) and competitive with established methods, such as the simplex method and coordinate descent.

Motivated by these results, we solve exactly the differential inclusion (2) characterizing linear and convex quadratic programs. We use the minimal selection principle (§ 2.2), which states that at each time, the solution moves along the element of minimal norm in the set on the right-hand side of (2). Our analysis yields two algorithms. Algorithm 1 computes the solution exactly when Q=tIn×nQ=tI_{n\times n} with t≥0t\ge0, that is, for linear programs (t=0t=0) and projections onto polyhedra (t>0t>0), and terminates after finitely many iterations. Algorithm 2, which we call minimal selection descent (MSD), discretizes (2) by the explicit Euler method and applies to every SPSD QQ.

Contributions of this paper: (i) We compute the solution of the differential inclusion (2) exactly. Each piece of the solution is an explicit function of time given by one nonnegative least-squares problem, and each breakpoint is the first zero of an explicit analytic function. (ii) We prove that the solution has finitely many pieces for every SPSD QQ, and its final piece yields either an optimal solution of problem (1) or a certificate of unboundedness. When Q=tIn×nQ=tI_{n\times n} with t≥0t\ge0, every piece lies on a straight line with a closed-form breakpoint and no active set occurs twice, so Algorithm 1 terminates after finitely many iterations. (iii) For general SPSD QQ, each step of MSD preserves feasibility and solves one nonnegative least-squares problem over the active constraints.

Algorithm 1: Computing an optimal solution of problem (1) with Q=tIn×nQ=tI_{n\times n}, or certifying unboundedness.

Input: A matrix A∈Rm×nA\in\mathbb{R}^{m\times n}, vectors b∈Rmb\in\mathbb{R}^{m}, c∈Rnc\in\mathbb{R}^{n}, a scalar t≥0t\ge0, and a feasible initial point x(0)∈Cx^{(0)}\in C.

Output: An optimal solution xsx^{s} of (1) with dual variable psp^{s}, or a direction dsd^{s} certifying unboundedness (Ads≤0Ad^{s}\le0 and ⟨c,ds⟩<0\langle c,d^{s}\rangle<0).

  1. for k=0,1,2,…k=0,1,2,\ldots do

  2. Compute E(k)={i∈{1,…,m}:[Ax(k)]i=bi}\mathcal{E}^{(k)}=\{i\in\{1,\ldots,m\}:[Ax^{(k)}]_{i}=b_{i}\};

  3. Compute p(k)∈arg min⁡pi≥0, i∈E(k)pi=0, i∉E(k)12∥ATp+tx(k)+c∥22p^{(k)}\in\underset{\substack{p_i\ge0,\ i\in\mathcal{E}^{(k)}\\p_i=0,\ i\notin\mathcal{E}^{(k)}}}{\operatorname{arg\,min}}\frac{1}{2}\left\|A^{\mathsf{T}}p+tx^{(k)}+c\right\|_{2}^{2} and set d(k)=−ATp(k)−tx(k)−cd^{(k)}=-A^{\mathsf{T}}p^{(k)}-tx^{(k)}-c;

  4. Compute the stepsize Δ(k)=min⁡i∉E(k)bi−[Ax(k)]imax⁡(0,[Ad(k)]i)\Delta^{(k)}=\min_{i\notin\mathcal{E}^{(k)}}\frac{b_i-[Ax^{(k)}]_i}{\max(0,[Ad^{(k)}]_i)}.

  5. if t>0t>0 and tΔ(k)≥1t\Delta^{(k)}\ge1 then

  6. Set xs=x(k)+1td(k)x^{s}=x^{(k)}+\frac{1}{t}d^{(k)} and ps=p(k)p^{s}=p^{(k)};

  7. return (xs,ps)(x^{s},p^{s}); // Optimal

  8. else if t=0t=0 and Δ(k)=+∞\Delta^{(k)}=+\infty then

  9. if ∥d(k)∥2=0\|d^{(k)}\|_{2}=0 then return (x(k),p(k))(x^{(k)},p^{(k)}), an optimal pair;

  10. else return ds=d(k)d^{s}=d^{(k)}, certifying unboundedness;

  11. Update x(k+1)=x(k)+Δ(k)d(k)x^{(k+1)}=x^{(k)}+\Delta^{(k)}d^{(k)};

  12. end

Algorithm 2: Minimal selection descent for problem (1) with SPSD matrix QQ.

References

  1. [1]H. Markowitz. The optimization of a quadratic function subject to linear constraints. Nav. Res. Logist. Q., 3(1-2):111–133, 1956.DOI
  2. [2]P. Wolfe. The simplex method for quadratic programming. Econometrica, 27(3):382–398, 1959.
  3. [3]A. Charnes and W. W. Cooper. Management models and industrial applications of linear programming. Manage. Sci., 4(1):38–91, 1957.
  4. [4]Y. Tassa, N. Mansard, and E. Todorov. Control-limited differential dynamic programming. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 1168–1175. IEEE, 2014.DOI
  5. [5]R. Tibshirani. Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B. Stat. Methodol., 58(1):267–288, 1996.
  6. [6]A. Chambolle and T. Pock. An introduction to continuous optimization for imaging. Acta Numer., 25:161–319, 2016.DOI
  7. [7]J. W. Pearson and J. Gondzio. Fast interior point solution of quadratic programming problems arising from PDE-constrained optimization. Numer. Math., 137(4):959–999, 2017. doi: 10.1007/s00211-017-0892-8.DOI
  8. [8]Chen Liu, Jingwei Hu, William T. Taitano, and Xiangxiong Zhang. An optimization-based positivity-preserving limiter in semi-implicit discontinuous Galerkin schemes solving Fokker–Planck equations. Comput. Math. Appl., 192:54–71, 2025. doi: 10.1016/j.camwa.2025.05.008.DOI
  9. [9]G. B. Dantzig. Maximization of a linear function of variables subject to linear inequalities. In T. C. Koopmans, editor, Activity Analysis of Production and Allocation, pages 339–347. John Wiley & Sons, New York, 1951.
  10. [10]R. W. Cottle and G. Infanger. Harry Markowitz and the early history of quadratic programming. In Handbook of Portfolio Construction, pages 179–211. Springer, 2010.DOI
  11. [11]M. J. Todd. The many facets of linear programming. Math. Program., 91(3):417–436, 2002.DOI
  12. [12]S. J. Wright. Optimization in theory and practice. arXiv preprint arXiv:2510.15734, 2025.arxiv.org/abs/2510.15734
  13. [13]V. N. Dinh. Real-time QP solvers: a concise review and practical guide towards legged robots. arXiv preprint arXiv:2510.21773, 2025.arxiv.org/abs/2510.21773
  14. [14]J.-P. Aubin and A. Cellina. Differential inclusions: Set-valued Maps and Viability Theory, volume 264. Springer Science & Business Media, 2012.
  15. [15]H. Brezis. Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North-Holland Mathematics Studies, No. 5. North-Holland Publishing Company, Amsterdam, 1973.
  16. [16]J.-B. Hiriart-Urruty and C. Lemaréchal. Convex analysis and minimization algorithms I: Fundamentals, volume 305 of Grundlehren Text Editions. Springer Science & Business Media, 1996.
  17. [17]Rafal K Goebel. Set-valued, convex, and nonsmooth analysis in dynamics and control: An introduction. SIAM, 2024.DOI
  18. [18]W. P. M. H. Heemels, J. M. Schumacher, and S. Weiland. Linear complementarity systems. SIAM J. Appl. Math., 60(4):1234–1269, 2000.DOI
  19. [19]P. Dupuis and H. Ishii. On Lipschitz continuity of the solution mapping to the Skorokhod problem, with applications. Stochastics, 35(1):31–62, 1991.DOI
  20. [20]Paul Dupuis and Anna Nagurney. Dynamical systems and variational inequalities. Annals of Operations Research, 44(1):7–42, 1993.DOI
  21. [21]J.-B. Hiriart-Urruty and C. Lemaréchal. Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods, volume 306 of Grundlehren Text Editions. Springer Science & Business Media, 1996.
  22. [22]H. Attouch, G. Buttazzo, and G. Michaille. Variational analysis in Sobolev and BV spaces: applications to PDEs and optimization. SIAM, 2014.
  23. [23]Asen Dontchev and Frank Lempio. Difference methods for differential inclusions: A survey. SIAM review, 34(2):263–294, 1992.DOI
  24. [24]SS Chen, DL Donoho, and MA Saunders. Atomic decomposition by basis pursuit. SIAM Rev., 43(1):129–159, 2001.
  25. [25]Y. Tendero, I. Ciril, J. Darbon, and S. Serna. An algorithm solving compressive sensing problem based on maximal monotone operators. SIAM J. Sci. Comput., 43(6):A4067–A4094, 2021.DOI
  26. [26]G. P. Langlois and J. Darbon. A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions. arXiv preprint arXiv:2507.05562, 2025.arxiv.org/abs/2507.05562
  27. [27]G. W. Brown and T. C. Koopmans. Computational suggestions for maximizing a linear function subject to linear inequalities. In T. C. Koopmans, editor, Activity Analysis of Production and Allocation, pages 377–380. John Wiley & Sons, New York, 1951.
  28. [28]G. Zoutendijk. Methods of feasible directions, volume 960. Elsevier, Amsterdam, 1960.
  29. [29]J. B. Rosen. The gradient projection method for nonlinear programming. Part I. Linear constraints. J. Soc. Indust. Appl. Math., 8(1):181–217, 1960.DOI
  30. [30]C. E. Lemke. The constrained gradient method of linear programming. J. Soc. Indust. Appl. Math., 9(1):1–17, 1961.DOI
  31. [31]S. Y. Chang and K. G. Murty. The steepest descent gravitational method for linear programming. Discrete Appl. Math., 25(3):211–239, 1989.
  32. [32]J. Nocedal and S. J. Wright. Numerical optimization. Springer, 2006.
  33. [33]B. Brogliato, A. Daniilidis, C. Lemárechal, and V. Acary. On the equivalence between complementarity systems, projected systems and differential inclusions. Systems & Control Letters, 55(1):45–51, 2006.
  34. [34]R. T. Rockafellar and R. J.-B. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
  35. [35]J. J. Moreau. Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires. C. R. Acad. Sci. Paris, 255:238–240, 1962.
  36. [36]R. T. Rockafellar. Convex analysis, volume 11. Princeton University Press, 1997.
  37. [37]C. L. Lawson and R. J. Hanson. Solving least squares problems, volume 15 of Classics in Applied Mathematics. SIAM, 1995.
  38. [38]M. C. Meyer. A simple new algorithm for quadratic programming with applications in statistics. Comm. Statist. Simulation Comput., 42(5):1126–1139, 2013.DOI
  39. [39]M. Dimiccoli. Fundamentals of cone regression. Technical report, Institute of Robotics and Industrial Informatics (CSIC-UPС), 2016.arxiv.org/abs/1507.06496
  40. [40]MOSEK ApS. MOSEK optimization toolbox for MATLAB. User’s Guide and Reference Manual, Version, 4(1):116, 2019.
  41. [41]Gurobi Optimization, LLC. Gurobi Optimizer reference manual. https://www.gurobi.com, 2026.
  42. [42]Q. Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method. Math. Program. Comput., 10(1):119–142, 2018.arxiv.org/abs/1503.01889
  43. [43]Xiangxiong Zhang and Chi-Wang Shu. Maximum-principle-satisfying and positivity-preserving high-order schemes for conservation laws: survey and new developments. Proceedings: Mathematical, Physical and Engineering Sciences, pages 2752–2776, 2011.DOI
  44. [44]Xiangxiong Zhang and Chi-Wang Shu. On maximum-principle-satisfying high order schemes for scalar conservation laws. J. Comput. Phys., 229(9):3091–3120, 2010.DOI
  45. [45]Xiangxiong Zhang and Chi-Wang Shu. On positivity-preserving high order discontinuous Galerkin schemes for compressible Euler equations on rectangular meshes. J. Comput. Phys., 229(23):8918–8934, 2010.DOI
  46. [46]Chen Liu, Beatrice Riviere, Jie Shen, and Xiangxiong Zhang. A simple and efficient convex optimization based bound-preserving high order accurate limiter for Cahn–Hilliard–Navier–Stokes system. SIAM J. Sci. Comput., 46(3):A1923–A1948, 2024. doi: 10.1137/23M1587853.DOI
  47. [47]Chen Liu, Gregory T. Buzzard, and Xiangxiong Zhang. An optimization based limiter for enforcing positivity in a semi-implicit discontinuous Galerkin scheme for compressible Navier–Stokes equations. J. Comput. Phys., 519:113440, 2024. doi: 10.1016/j.jcp.2024.113440.DOI
  48. [48]P. Benner, A. Onwunta, and M. Stoll. Block-diagonal preconditioning for optimal control problems constrained by PDEs with uncertain inputs. SIAM Journal on Matrix Analysis and Applications, 37(2):491–518, 2016.DOI
  49. [49]Peter Benner, Sergey Dolgov, Akwum Onwunta, and Martin Stoll. Low-rank solvers for un-steady Stokes–Brinkman optimal control problem with random data. Computer Methods in Applied Mechanics and Engineering, 304:26–54, 2016. ISSN 0045-7825. doi: https://doi.org/10.1016/j.cma.2016.02.004. URL https://www.sciencedirect.com/science/article/pii/S0045782516300263.
  50. [50]Peter Benner, Sergey Dolgov, Akwum Onwunta, and Martin Stoll. Low-rank solution of an optimal control problem constrained by random Navier-Stokes equations. International Journal on Numerical Methods for Fluids, 92:1653–1678, 2020.DOI
  51. [51]Harbir Antil, Sergey Dolgov, and Akwum Onwunta. TTRISK: Tensor train decomposition algorithm for risk-averse optimization. Numerical Linear Algebra with Applications, 3(3):e2481, 2023. URL https://doi.org/10.1002/nla.2481.12.
  52. [52]Harbir Antil, Sergey Dolgov, and Akwum Onwunta. Smoothed Moreau-Yosida tensor-train approximation of state-constrained optimization problems under uncertainty. Numerical Linear Algebra with Applications, page 32:e70028, 2025. URL https://doi.org/10.1002/nla.70028.
  53. [53]Harbir Antil, Sergey Dolgov, and Akwum Onwunta. Tensor train solution to uncertain optimization problems with shared sparsity penalty. Optimization and Engineering, 2025. URL https://doi.org/10.1007/s11081-025-10036-7.
  54. [54]Stéphane Caron, Akram Zaki, Pavel Otta, Daniel Armström, Justin Carpentier, Fengyu Yang, Pierre-Alexandre Lez iart, and João Sousa Pinto. qpbenchmark: Benchmark for quadratic programming solvers available in Python, 2026. URL https://github.com/qpsolvers/qpbenchmark. Version 2.7.1.
  55. [55]Howard Elman, Alison Ramage, and David Silvester. IFISS: A computational laboratory for investigating incompressible flow problems. SIAM Review, 56:261–273, 2014.DOI
  56. [56]M. Stoll and A. Wathen. All-at-once solution of time-dependent PDE-constrained optimization problems. Technical Report NA-10/13, Mathematical Institute, University of Oxford, nov 2010. URL https://ora.ox.ac.uk/objects/uuid:c94b530e-5a3d-4fb1-9c11-8d50302b9cb3.
  57. [57]J. W. Pearson, M. Stoll, and A. J. Wathen. Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl., 33(4):1126–1152, 2012. doi: 10.1137/110847949.DOI
  58. [58]Weijie Su, Stephen Boyd, and Emmanuel J. Candes. A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1–43, 2016.
  59. [59]Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2):95–110, 1956.DOI
  60. [60]Alan J. Hoffman. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952.

Paper details

vlnc:W_zsdf78m6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Code

View statement
Looking for related papers…
Contents