pith. sign in

arxiv: 2510.17465 · v2 · submitted 2025-10-20 · 🧮 math.OC · cs.SY· eess.SY

A condensing approach for linear-quadratic optimization with geometric constraints

Alberto De Marchi This is my paper

Pith reviewed 2026-05-18 06:19 UTC · model grok-4.3

classification 🧮 math.OC cs.SYeess.SY
keywords augmented Lagrangiancondensing techniquequadratic optimizationnonconvex constraintsgeometric constraintspolyhedral constraintsoptimization algorithms
0
0 comments X

The pith

A condensing technique in augmented Lagrangian methods speeds up linear-quadratic optimization with nonconvex geometric constraints.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops a method for solving optimization problems that have a convex quadratic objective and constraints that are mostly polyhedral but can include nonconvex geometric sets, such as those for cardinality or logical conditions. The approach relies on the augmented Lagrangian framework to ensure convergence to a solution, while introducing a condensing reformulation of the subproblems that exploits the structure to make solving them faster without needing a specific solver. This matters because such problems appear often in control, signal processing, and decision making, and the method makes handling the nonconvex parts feasible when projections onto those sets are computable. The key is that the condensing step reduces the subproblem complexity while preserving the overall guarantees.

Core claim

By integrating a solver-agnostic condensing technique with the augmented Lagrangian method, the approach reformulates the subproblems in a structure-exploiting way that leads to significant computational performance gains for linear-quadratic problems with polyhedral and nonconvex constraints, while convergence follows from the standard properties of the augmented Lagrangian framework.

What carries the argument

The condensing technique for structure-exploiting subproblem reformulation in the augmented Lagrangian framework.

If this is right

  • The method applies to problems including logical conditions and cardinality constraints.
  • Convergence guarantees are inherited from the augmented Lagrangian framework.
  • Significant improvements in computational performance are achieved through the condensing technique.
  • It is effective when projections onto the nonconvex constraint sets can be computed practically.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This could enable faster real-time optimization in automatic control applications.
  • The reformulation might be adaptable to other penalty or multiplier-based methods.
  • Testing on benchmark problems with cardinality constraints could reveal the extent of speedups.

Load-bearing premise

It is practical to compute projections onto this nonconvex set.

What would settle it

A numerical test on a quadratic program with cardinality constraints where the method shows no reduction in computation time or fails to converge compared to a standard solver.

Figures

Figures reproduced from arXiv: 2510.17465 by Alberto De Marchi.

Figure 1
Figure 1. Figure 1: Initial value problem (13): data (top) and performance (bottom) profiles for comparing different solver settings. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Obstacle problem (14): data (top) and performance (bottom) profiles for comparing different solver settings. Legend as in [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: AFTI-16 problem (13): data (top) and performance (bottom) profiles for comparing different solver settings. Legend as in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Closed-loop simulation of AFTI-16 behavior: outputs (top), inputs (middle) and solver run [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Scalability profiles for comparing different solver settings: initial value problem ( [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
read the original abstract

Optimization problems with convex quadratic cost and polyhedral constraints are ubiquitous in signal processing, automatic control and decision-making. We consider here an enlarged problem class that allows to encode logical conditions and cardinality constraints, among others. In particular, we cover also situations where parts of the constraints are nonconvex and possibly complicated, but it is practical to compute projections onto this nonconvex set. Our approach combines the augmented Lagrangian framework with a solver-agnostic structure-exploiting subproblem reformulation. While convergence guarantees follow from the former, the proposed condensing technique leads to significant improvements in computational performance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proposes a condensing approach for linear-quadratic optimization problems with geometric constraints, including nonconvex ones where projections are practical. It integrates this with the augmented Lagrangian framework via a solver-agnostic structure-exploiting subproblem reformulation, claiming that convergence follows from standard AL theory while the condensing technique yields significant computational performance improvements.

Significance. If the performance gains hold while keeping projections efficient, the method could advance practical solution of problems with cardinality or logical constraints in control and signal processing. Reliance on established AL convergence theory is a strength, providing a reliable foundation for the structural innovations.

major comments (2)
  1. Abstract: The central claim that the condensing technique leads to 'significant improvements in computational performance' lacks any quantitative evidence, timing data, or comparison to baseline AL methods. This assertion is load-bearing for the contribution, yet the abstract only states that projections onto the nonconvex set are 'practical' without analyzing whether condensing preserves this property when the set couples to the quadratic terms.
  2. Subproblem reformulation section (around the definition of the condensed quadratic program): The reformulation must ensure that repeated exact projections onto the nonconvex geometric set remain cheap after condensing. If the projection cost scales with the condensed dimension or requires iterative inner solvers, the claimed speedup over plain AL evaporates; the manuscript should provide a complexity argument or bound showing this does not occur.
minor comments (1)
  1. Abstract: The phrase 'enlarged problem class' would benefit from a brief parenthetical example of a logical or cardinality constraint to orient readers immediately.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report and the opportunity to clarify our contribution. We address the major comments point by point below, revising the manuscript where the feedback identifies opportunities for improvement.

read point-by-point responses

  1. Referee: Abstract: The central claim that the condensing technique leads to 'significant improvements in computational performance' lacks any quantitative evidence, timing data, or comparison to baseline AL methods. This assertion is load-bearing for the contribution, yet the abstract only states that projections onto the nonconvex set are 'practical' without analyzing whether condensing preserves this property when the set couples to the quadratic terms.

    Authors: We agree that the abstract would be strengthened by explicit reference to supporting evidence. The revised abstract now briefly notes the observed speedups from the numerical experiments in Section 5, which include timing comparisons against standard augmented-Lagrangian iterations without condensing. Regarding preservation of projection cost, the condensing step eliminates only the linear equality constraints arising from the dynamics while the geometric set remains unchanged and decoupled from the quadratic objective; the same projection operator is therefore applied at each iteration. A clarifying sentence has been added to the abstract and a short paragraph inserted in Section 3 to make this structural invariance explicit. revision: yes

  2. Referee: Subproblem reformulation section (around the definition of the condensed quadratic program): The reformulation must ensure that repeated exact projections onto the nonconvex geometric set remain cheap after condensing. If the projection cost scales with the condensed dimension or requires iterative inner solvers, the claimed speedup over plain AL evaporates; the manuscript should provide a complexity argument or bound showing this does not occur.

    Authors: The condensed quadratic program is obtained by eliminating the linear dynamics, yielding a smaller dense QP whose only non-polyhedral constraints are the original geometric set. Consequently the projection step is identical to the one used in the non-condensed formulation and its computational cost is independent of the condensed dimension. We have added a short complexity remark in the subproblem-reformulation section stating that each projection is performed in time linear in the size of the geometric set (a constant with respect to the overall problem dimension after condensing) and does not invoke inner iterative solvers. This bound, together with the reduction in QP size, underpins the reported performance gains. revision: yes

Circularity Check

0 steps flagged

No circularity; method builds on standard AL theory with independent condensing reformulation

full rationale

The paper attributes convergence guarantees directly to the established augmented Lagrangian framework and computational gains to a solver-agnostic condensing reformulation of subproblems. No derivation step reduces a claimed result or prediction to a fitted parameter, self-referential definition, or load-bearing self-citation by construction. The assumption that projections onto the nonconvex set remain practical is stated explicitly as a prerequisite rather than derived from the method itself, leaving the central claims self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on the abstract alone; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.0 · 5617 in / 992 out tokens · 36805 ms · 2026-05-18T06:19:33.794044+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Local Convergence Results for Sequential Quadratic Programming with Complementarity Constraints

    math.OC 2026-04 unverdicted novelty 7.0

    SQPCC converges locally to S-stationary points of MPCCs under weaker second-order sufficient conditions, without upper-level strict complementarity, and with active-set identification results.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    Armand and N

    P. Armand and N. N. Tran. An augmented Lagrangian method for equality constrained optimization with rapid infeasibility detection capabilities.Journal of Optimization Theory and Applications, 181(1):197–215, 2019. doi:10.1007/s10957-018-1401-7

    work page doi:10.1007/s10957-018-1401-7 2019

  2. [2]

    E. G. Birgin and J. M. Mart´ ınez.Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. doi:10.1137/1.9781611973365. 11

    work page doi:10.1137/1.9781611973365 2014

  3. [3]

    Cafieri, A

    S. Cafieri, A. R. Conn, and M. Mongeau. Mixed-integer nonlinear and continuous optimization formulations for aircraft conflict avoidance via heading and speed deviations.European Journal of Operational Research, 310(2):670–679, 2023. doi:10.1016/j.ejor.2023.03.002

    work page doi:10.1016/j.ejor.2023.03.002 2023

  4. [4]

    De Marchi

    A. De Marchi. Proximal gradient methods beyond monotony.Journal of Nonsmooth Analysis and Optimization, 4, 2023. doi:10.46298/jnsao-2023-10290

    work page doi:10.46298/jnsao-2023-10290 2023

  5. [5]

    De Marchi and A

    A. De Marchi and A. Themelis. Proximal gradient algorithms under local Lipschitz gradient conti- nuity.Journal of Optimization Theory and Applications, 194(3):771–794, 2022. doi:10.1007/s10957- 022-02048-5

    work page doi:10.1007/s10957- 2022

  6. [6]

    J. Hall, A. Nurkanovi´ c, F. Messerer, and M. Diehl. LCQPow: a solver for linear comple- mentarity quadratic programs.Mathematical Programming Computation, 17(1):81–109, 2025. doi:10.1007/s12532-024-00272-w

    work page doi:10.1007/s12532-024-00272-w 2025

  7. [7]

    Hoheisel, C

    T. Hoheisel, C. Kanzow, and A. Schwartz. Mathematical programs with vanishing constraints: a new regularization approach with strong convergence properties.Optimization, 61(6):619–636, 2012. doi:10.1080/02331934.2011.608164

    work page doi:10.1080/02331934.2011.608164 2012

  8. [8]

    X. Jia, C. Kanzow, P. Mehlitz, and G. Wachsmuth. An augmented Lagrangian method for optimiza- tion problems with structured geometric constraints.Mathematical Programming, 199(1):1365–1415,

    work page

  9. [9]

    doi:10.1007/s10107-022-01870-z

    work page doi:10.1007/s10107-022-01870-z

  10. [10]

    Trust -region algorithms for training responses: machine learning methods using indefinite Hessian approximations,

    C. Kanzow, P. Mehlitz, and D. Steck. Relaxation schemes for mathematical pro- grammes with switching constraints.Optimization Methods and Software, pages 1–36, 2019. doi:10.1080/10556788.2019.1663425

    work page doi:10.1080/10556788.2019.1663425 2019

  11. [11]

    Kapasouris, M

    P. Kapasouris, M. Athans, and G. Stein. Design of feedback control systems for unstable plants with saturating actuators. InProc. IFAC Symposium on Nonlinear Control System Design, pages 302–307. Pergamon Press, 1990

    work page 1990

  12. [12]

    Mahajan, S

    A. Mahajan, S. Leyffer, and C. Kirches. Solving mixed-integer nonlinear programs by QP-diving. Anl/mcs preprint p2071-0312, Argonne National Laboratory, 2012

    work page 2012

  13. [13]

    M´ enager, A

    E. M´ enager, A. Bambade, W. Jallet, A. De Marchi, and J. Carpentier. Contact-implicit inverse dynamics.IEEE Transactions on Robotics, 2025, hal-05201780. under review

    work page 2025

  14. [14]

    Nikitina, A

    V. Nikitina, A. De Marchi, and M. Gerdts. Hybrid optimal control with mixed-integer Lagrangian methods.IFAC-PapersOnLine, 2025, 2403.06842. 13th IFAC Symposium on Nonlinear Control Systems (NOLCOS)

    work page arXiv 2025

  15. [15]

    Palagachev and M

    K. Palagachev and M. Gerdts. Mathematical programs with blocks of vanishing constraints arising in discretized mixed-integer optimal control problems.Set-Valued and Variational Analysis, 23(1):149– 167, 2015. doi:10.1007/s11228-014-0297-0

    work page doi:10.1007/s11228-014-0297-0 2015

  16. [16]

    Robuschi, C

    N. Robuschi, C. Zeile, S. Sager, and F. Braghin. Multiphase mixed-integer nonlinear optimal control of hybrid electric vehicles.Automatica, 123:109325, 2021. doi:10.1016/j.automatica.2020.109325

    work page doi:10.1016/j.automatica.2020.109325 2021

  17. [17]

    D. E. Stewart and M. Anitescu. Optimal control of systems with discontinuous differential equations. Numerische Mathematik, 114(4):653–695, 2010. doi:10.1007/s00211-009-0262-2

    work page doi:10.1007/s00211-009-0262-2 2010

  18. [18]

    Zheng, T

    P. Zheng, T. Askham, S. L. Brunton, J. N. Kutz, and A. Y. Aravkin. A unified frame- work for sparse relaxed regularized regression: SR3.IEEE Access, 7:1404–1423, 2019. doi:10.1109/ACCESS.2018.2886528. 12 A Additional Material A.1 Globally Lipschitz gradient Let us denote∥X k∥the operator norm ofX k, which depends on the problem data as well as on paramete...

    work page doi:10.1109/access.2018.2886528 2019