On the Practical Implementation of a Sequential Quadratic Programming Algorithm for Nonconvex Sum-of-squares Problems
Pith reviewed 2026-05-16 08:10 UTC · model grok-4.3
The pith
A filter line search algorithm solves sequences of quadratic subproblems to handle nonconvex sum-of-squares optimization more efficiently.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper proposes a filter line search algorithm that solves a sequence of quadratic subproblems for nonconvex sum-of-squares optimization. Numerical benchmarks demonstrate that the algorithm can significantly reduce the number of iterations, resulting in a substantial decrease in computation time compared to established methods for nonconvex SOS programs.
What carries the argument
The filter line search algorithm applied to a transcribed sequence of quadratic subproblems.
If this is right
- Nonconvex SOS problems become solvable with substantially fewer iterations in the tested cases.
- Overall computation time for certifying polynomial nonnegativity drops compared with prior iterative solvers.
- Tractable solutions open for nonconvex instances in control engineering that previously exceeded practical limits.
- The method supplies a concrete implementation route for sequential quadratic programming on SOS constraints.
Where Pith is reading between the lines
- The same quadratic-subproblem structure might extend to other classes of nonconvex polynomial programs that admit SOS relaxations.
- Warm-starting the quadratic solves from previous iterates could produce further speed gains not explored in the benchmarks.
- Convergence radius might be characterized by examining how the filter parameters interact with the degree of the polynomials.
Load-bearing premise
The filter line search and quadratic subproblem sequence remain reliable and convergent for the full range of nonconvex SOS instances encountered in practice.
What would settle it
A standard nonconvex SOS benchmark from control theory on which the algorithm either diverges or requires more iterations and time than current solvers would falsify the performance claim.
read the original abstract
Sum-of-squares (SOS) optimization provides a computationally tractable framework for certifying polynomial nonnegativity. If the considered problem is convex, the SOS problem can be transcribed into and solved by semi-definite programs. However, in case of nonconvex problems iterative procedures are needed. Yet tractable and efficient solution methods are still lacking, limiting their application, for instance, in control engineering. To address this gap, we propose a filter line search algorithm that solves a sequence of quadratic subproblems. Numerical benchmarks demonstrate that the algorithm can significantly reduce the number of iterations, resulting in a substantial decrease in computation time compared to established methods for nonconvex SOS programs
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a filter line search SQP algorithm for nonconvex sum-of-squares (SOS) optimization problems. It formulates the nonconvex SOS task as a sequence of quadratic subproblems solved iteratively, with a filter mechanism to enforce progress and convergence. Numerical benchmarks are presented to claim that the method substantially reduces iteration counts and runtime relative to existing solvers for nonconvex SOS programs.
Significance. If the performance claims are substantiated across representative instances, the work could supply a practical, convergent solver for nonconvex SOS problems that arise in control synthesis and polynomial optimization, where current methods remain limited.
major comments (1)
- [§5 / abstract] Numerical benchmarks (abstract and §5): the central performance claim—that the filter line search SQP reduces iterations and computation time versus established methods—lacks any description of the test set (problem sizes, polynomial degrees, degree of nonconvexity), baseline solvers, or statistical controls (e.g., multiple random instances, failure rates). Without this information it is impossible to determine whether the observed speedups are general or artifacts of a narrow, specially structured test collection.
minor comments (1)
- [Abstract] The abstract would be strengthened by a single sentence indicating the classes of test problems (e.g., control Lyapunov functions of degree 4–6) used to obtain the reported speedups.
Simulated Author's Rebuttal
We thank the referee for the constructive comment on the numerical benchmarks. We address the concern below and will revise the manuscript to provide the requested details.
read point-by-point responses
-
Referee: [§5 / abstract] Numerical benchmarks (abstract and §5): the central performance claim—that the filter line search SQP reduces iterations and computation time versus established methods—lacks any description of the test set (problem sizes, polynomial degrees, degree of nonconvexity), baseline solvers, or statistical controls (e.g., multiple random instances, failure rates). Without this information it is impossible to determine whether the observed speedups are general or artifacts of a narrow, specially structured test collection.
Authors: We agree that the current presentation of the numerical results in Section 5 does not provide sufficient detail on the test problems to allow readers to fully assess the generality of the reported speedups. In the revised manuscript we will expand Section 5 to include: (i) explicit characterization of the test set by problem dimension (number of variables), polynomial degree, and degree of nonconvexity (e.g., number of nonconvex terms and/or the spectrum of the Hessian at the computed solution); (ii) precise identification of all baseline solvers employed for comparison; and (iii) statistical controls consisting of averages and standard deviations computed over multiple randomly generated instances together with observed failure rates. These additions will make clear that the performance improvements are not limited to a narrow or specially structured collection of instances. revision: yes
Circularity Check
No circularity: algorithmic proposal and empirical benchmarks are self-contained with no derivation chain reducing to inputs by construction.
full rationale
The paper proposes a filter line search SQP method for nonconvex sum-of-squares problems and supports its claims exclusively through numerical benchmarks comparing iteration counts and runtime against established solvers. No equations, derivations, fitted parameters, or self-citations appear in the abstract or described content that could create a self-definitional loop, a prediction forced by a prior fit, or an ansatz smuggled via citation. The central performance claims rest on external empirical evidence rather than any reduction of outputs to the algorithm's own inputs by construction. This is the expected honest outcome for an implementation-focused paper whose load-bearing steps are algorithmic description plus benchmarking, not mathematical derivation.
Axiom & Free-Parameter Ledger
Forward citations
Cited by 1 Pith paper
-
Data-driven discovery of polynomial ODEs with provably bounded solutions
SILAS jointly optimizes polynomial ODE vector fields and polynomial Lyapunov functions from data to produce models with provably bounded trajectories via compact absorbing sets.
Reference graph
Works this paper leans on
-
[1]
Parillo, Semidefinite programming relaxations for semialgebraic problems, Math
P.A. Parillo, Semidefinite programming relaxations for semialgebraic problems, Math. Program., Series B96(2), 293 (2003). DOI 10.1007/s10107-003-0387-5
-
[2]
G. Blekherman, P.A. Parrilo, R.R. Thomas (eds.),Semidefinite Optimization and Con- vex Algebraic Geometry. MOS-SIAM Series on Optimization (SIAM)
-
[3]
D. Bertsimas, D.A. Iancu, P.A. Parrilo, A Hierarchy of Near-Optimal Policies for Mul- tistage Adaptive Optimization,56(12), 2809. DOI 10.1109/TAC.2011.2162878
-
[4]
A. Magnani, S. Lall, S. Boyd, Tractable fitting with convex polynomials via sum-of- squares, inIEEE 44th Conf. Decis. Control. pp. 1672–1677. DOI 10.1109/CDC.2005. 1582399
-
[5]
B. Barak, J.A. Kelner, D. Steurer, Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method, inProc. 47th Annu. ACM Symp. Theory Comput.(As- sociation for Computing Machinery), STOC ’15, pp. 143–151. DOI 10.1145/2746539. 2746605
-
[7]
Z. Jarvis-Wloszek, R. Feeley, W. Tan, K. Sun, A. Packard, inPositive Polynomials in Control, ed. by D. Henrion, A. Garulli, Lect. Notes Control Inf. Sci. (Springer), pp. 3–22. DOI 10.1007/10997703 1
-
[8]
M. ApS. The mosek optimization toolbox for matlab. version 11.0.30 (2025). URL https://docs.mosek.com/latest/toolbox/index.html
work page 2025
-
[9]
arXiv preprint arXiv:2405.12762 (2 024)
P.J. Goulart, Y. Chen. Clarabel: An interior-point solver for conic programs with quadratic objectives (2024). URLhttps://arxiv.org/abs/2405.12762
-
[10]
B. O’Donoghue, E. Chu, N. Parikh, S. Boyd. SCS: Splitting conic solver, version 3.2.9. https://github.com/cvxgrp/scs(2023)
work page 2023
- [11]
- [12]
-
[13]
D. Papp, S. Yıldız, Alfonso: Matlab Package for Nonsymmetric Conic Optimization, INFORMS J. Comput.34(1), 11 (2022). DOI 10.1287/ijoc.2021.1058
-
[14]
A.A. Ahmadi, A. Majumdar, DSOS and SDSOS Optimization: More Tractable Alterna- tives to Sum of Squares and Semidefinite Optimization, SIAM J. Appl. Algebra Geom. 3(2), 193 (2019). DOI 10.1137/18M118935X
-
[15]
Parallelizing LQR computation through endpoint-explicit riccati recursion,
D. Driggs, H. Fawzi, Anysos: An anytime algorithm for sos programming, in2019 IEEE 58th Conf. Decis. Control(2019), pp. 3012–3017. DOI 10.1109/CDC40024.2019. 9029387
-
[16]
D. Jagt, S. Shivakumar, P. Seiler, M. Peet, Efficient Data Structures for Representation of Polynomial Optimization Problems: Implementation in SOSTOOLS, IEEE Control Syst. Lett.6, 3493 (2022). DOI 10.1109/LCSYS.2022.3183650 Sequential Quadratic Programming for Nonconvex Sum-of-squares Problems 29
- [17]
-
[18]
Cunis, Decomposed quasiconvex optimization with application to generalized cone problems, Opt
T. Cunis, Decomposed quasiconvex optimization with application to generalized cone problems, Opt. Let.19(2), 267 (2025). DOI 10.1007/s11590-024-02174-1
-
[19]
L¨ ofberg, Pre- and Post-Processing Sum-of-Squares Programs in Practice, IEEE Trans
J. L¨ ofberg, Pre- and Post-Processing Sum-of-Squares Programs in Practice, IEEE Trans. Autom. Control54(5), 1007 (2009). DOI 10.1109/TAC.2009.2017144
-
[20]
A.A. Ahmadi, G. Hall, A. Papachristodoulou, J. Saunderson, Y. Zheng, Improving Ef- ficiency and Scalability of Sum of Squares Optimization : Recent Advances and Lim- itations, in56th IEEE Conf. Decis. Control(Melbourne, 2017), pp. 453–462. DOI 10.1109/CDC.2017.8263706
-
[21]
A. Chakraborty, P. Seiler, G.J. Balas, Nonlinear region of attraction analysis for flight control verification and validation, Control Eng. Pract.19(4), 335 (2011). DOI 10.1016/ j.conengprac.2010.12.001
work page 2011
-
[22]
A. Chakraborty, P. Seiler, G.J. Balas, Susceptibility of F/A-18 Flight Controllers to the Falling-leaf Mode: Nonlinear Analysis, J. Guid. Control Dyn.34(2), 73 (2011). DOI 10.2514/1.50675
-
[23]
A. Iannelli, A. Marcos, P. Seiler, An equilibrium-independent region of attraction for- mulation for systems with uncertainty-dependent equilibria, in2018 IEEE Conf. Decis. Control(2018), pp. 725–730. DOI 10.1109/CDC.2018.8619153
-
[24]
P. Seiler, G.J. Balas, Quasiconvex sum-of-squares programming, in49th IEEE Conf. Decis. Control(Atlanta, US, 2010), pp. 3337–3342. DOI 10.1109/CDC.2010.5717672
-
[25]
H. Yin, A. Packard, M. Arcak, P. Seiler, Finite horizon backward reachability analy- sis and control synthesis for uncertain nonlinear systems, inProc. Am. Control Conf. (Philadelphia, US, 2019), pp. 5020–5026. DOI 10.23919/ACC.2019.8814444
-
[26]
H. Yin, P. Seiler, M. Arcak, Backward Reachability Using Integral Quadratic Con- straints for Uncertain Nonlinear Systems, IEEE Control Syst. Lett.5(2), 707 (2021). DOI 10.1109/LCSYS.2020.3005315
-
[27]
Z. Jarvis-Wloszek, R. Feeley, W. Tan, K. Sun, A. Packard, Some Controls Applications of Sum of Squares Programming, inProc. of the IEEE Conf. Decis. Control, vol. 5 (Maui, US, 2003), vol. 5, pp. 4676–4681. DOI 10.1109/CDC.2003.1272309
-
[28]
T. Cunis, I. Kolmanovsky, Viability, viscosity, and storage functions in model-predictive control with terminal constraints, Automatica131(109748) (2021). DOI 10.1016/j. automatica.2021.109748
work page doi:10.1016/j 2021
-
[29]
A. Majumdar, A.A. Ahmadi, R. Tedrake, Control Design Along Trajectories via Sum of Squares Optimization, in2013 IEEE Int. Conf. Robot. Autom.(Karlsruhe, 2013), pp. 4039–4046. DOI 10.1109/ICRA.2013.6631149
-
[30]
W. Lin, Z. Yang, Z. Ding, Reachable Set Estimation and Safety Verification of Nonlinear Systems via Iterative Sums of Squares Programming, J. Syst. Sci. Complex35(3), 1154 (2022). DOI 10.1007/s11424-022-1121-9
-
[31]
M. Newton, Z. Xiong, H. Wang, A. Papachristodoulou. On the Design of Rational Polynomial State Feedback Controllers (2025). DOI 10.48550/arXiv.2511.18988. URL http://arxiv.org/abs/2511.18988
-
[32]
A.D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, P. Tabuada, Control barrier functions: Theory and applications, in2019 18th Eur. Control Conf.(2019), pp. 3420–3431. DOI 10.23919/ECC.2019.8796030
-
[33]
A. Clark, Verification and Synthesis of Control Barrier Functions, in2021 60th IEEE Conf. Decis. and Control(2021), pp. 6105–6112. DOI 10.1109/CDC45484.2021.9683520
-
[34]
Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming
W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming. Ph.D. thesis, University of California, Berkeley, Berkeley, US (2006)
work page 2006
-
[35]
M. Schneeberger, F. D¨ orfler, S. Mastellone, SOS Construction of Compatible Control Lyapunov and Barrier Functions, IFAC-PapersOnLine56(2), 10428 (2023). DOI 10. 1016/j.ifacol.2023.10.1058
work page 2023
- [36]
-
[37]
PENLAB: A MATLAB solver for nonlinear semidefinite optimization
J. Fiala, M. Koˇ cvara, M. Stingl. PENLAB: A MATLAB solver for nonlinear semidefinite optimization (2013). DOI 10.48550/arXiv.1311.5240. URLhttp://arxiv.org/abs/ 1311.5240 30 Jan Olucak, Torbjørn Cunis
work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1311.5240 2013
-
[38]
T. Cunis, B. Legat, Sequential sum-of-squares programming for analysis of nonlinear systems, in2023 Am. Control Conf.(San Diego, CA, 2023). DOI 10.23919/ACC55779. 2023.10156153
-
[39]
S. Boyd, L. Vandenberghe,Convex Optimization, 7th edn. (Cambridge University Press, Cambridge, 2009)
work page 2009
-
[40]
Betts,Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, 2nd edn
J.T. Betts,Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, 2nd edn. (Society for Industrial and Applied Mathematics, 2010). DOI 10.1137/1.9780898718577
-
[41]
J. Nocedal, S.J. Wright,Numerical optimization, 2nd edn. Springer series in operations research (Springer, 2006)
work page 2006
-
[42]
L.T. Biegler,Nonlinear programming: concepts, algorithms, and applications to chem- ical processes(SIAM, 2010)
work page 2010
-
[43]
Nonlinear programming without a penalty function,
R. Fletcher, S. Leyffer, Nonlinear programming without a penalty function, Math. Prog. 91(2), 239 (2002). DOI 10.1007/s101070100244
-
[44]
A. W¨ achter, L.T. Biegler, Line search filter methods for nonlinear programming: Mo- tivation and global convergence, SIAM J. Optim.16(1), 1 (2005). DOI 10.1137/ S1052623403426556
work page 2005
-
[45]
A. W¨ achter, L.T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming106(1), 25 (2006). DOI 10.1007/s10107-004-0559-y
-
[46]
T. Cunis, J. Olucak, CaΣoS: A nonlinear sum-of-squares optimization suite, in2025 Am. Control Conf.(Denver, CO), pp. 1659–1666. DOI 10.23919/ACC63710.2025.11107794
-
[47]
Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM J
J.B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM J. Optim.11(3), 796 (2001)
work page 2001
-
[48]
C. Ebenbauer, F. Allg¨ ower, Analysis and design of polynomial control systems using dissipation inequalities and sum of squares, Computers and Chemical Engineering30, 1590 (2006). DOI 10.1016/j.compchemeng.2006.05.014
-
[49]
A.F. Izmailov, M.V. Solodov,Newton-Type Methods for Optimization and Varia- tional Problems(Springer International Publishing, Cham, 2014). DOI 10.1007/ 978-3-319-04247-3
work page 2014
-
[50]
S.P. Dokov, A.L. Dontchev, inOptimal Control: Theory, Algorithms, and Applications, ed. by W.H. Hager, P.M. Pardalos (Springer, New York, NY, 1998), pp. 116–129. DOI 10.1007/978-1-4757-6095-8{\ }6
-
[51]
A.L. Dontchev, R.T. Rockafellar, Convergence of inexact newton methods for gen- eralized equations, Mathematical Programming139(1-2), 115 (2013). DOI 10.1007/ s10107-013-0664-x
work page 2013
-
[52]
B.S. Mordukhovich, M.E. Sarabi, Generalized Newton Algorithms for Tilt-Stable Min- imizers in Nonsmooth Optimization, SIAM J. Optim.31(2), 1184 (2021). DOI 10.1137/20M1329937. URLhttps://epubs.siam.org/doi/10.1137/20M1329937
-
[53]
M.S. Louzeiro, G.N. Silva, J. Yuan, Inexact Newton Methods for Solving Generalized Equations on Riemannian Manifolds, pp. 1–34 (2023)
work page 2023
-
[54]
Q.T. Dinh, M. Diehl, inRecent Advances in Optimization and its Applications in En- gineering, ed. by M. Diehl, F. Glineur, E. Jarlebring, W. Michiels (Springer Berlin Hei- delberg, Berlin, Heidelberg, 2010), pp. 93–102. DOI 10.1007/978-3-642-12598-0{\ }9
-
[55]
Dontchev,Lectures on Variational Analysis
A.L. Dontchev,Lectures on Variational Analysis. No. 205 in Appl. Math. Sci. (Springer, Cham, 2021). DOI 10.1007/978-3-030-79911-3
-
[56]
CasADi – A software framework for nonlinear optimization and optimal con- trol
J.A.E. Andersson, J. Gillis, G. Horn, J.B. Rawlings, M. Diehl, CasADi: a software framework for nonlinear optimization and optimal control, Math. Program. Comput. 11(1), 1 (2019). DOI 10.1007/s12532-018-0139-4
-
[57]
A.A. Khan, C. Tammer, C. Z˘ alinescu,Set-valued Optimization(Springer, Berlin, 2015). DOI 10.1007/978-3-642-54265-7
-
[58]
J. Olucak, T. Cunis. Supplementary Material for the paper “On the Practical Imple- mentation of a Sequential Quadratic Programming Algorithm for Nonconvex Sum-of- squares Problems” (2026). DOI 10.18419/DARUS-5677. URLhttps://doi.org/10. 18419/DARUS-5677
-
[59]
M. Ulbrich, S. Ulbrich, L.N. Vicente, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Program., Ser. A100(2), 379 (2004). DOI 10.1007/s10107-003-0477-4 Sequential Quadratic Programming for Nonconvex Sum-of-squares Problems 31
-
[60]
R. Quirynen, B. Houska, M. Vallerio, D. Telen, F. Logist, J. Van Impe, M. Diehl, Symmetric algorithmic differentiation based exact hessian SQP method and software for economic MPC, in53rd IEEE Conf. Decis. Control(2014), pp. 2752–2757. DOI 10.1109/CDC.2014.7039811
-
[61]
Rauˇ ski, Limited memory BFGS method for sparse and large-scale nonlinear opti- mization
S. Rauˇ ski, Limited memory BFGS method for sparse and large-scale nonlinear opti- mization. Ph.d. dissertation, University of Bremen (2014)
work page 2014
-
[62]
T. Nikolayzik, Korrekturverfahren zur numerischen l¨ osung nichtlinearer opti- mierungsprobleme mittels methoden der parametrischen sensitivit¨ atsanalyse (german). Ph.d. dissertation, University of Bremen (2012)
work page 2012
-
[63]
G.S. Nurre, J.P. Sharkey, J.D. Nelson, A.J. Bradley, Preservicing mission - on-orbit modifications to hubble space telescope pointing control system, J. Guid. Control Dyn. 18(2), 222 (1995). DOI 10.2514/3.21373
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.