A condensing approach for linear-quadratic optimization with geometric constraints

1. Problem Statement

The paper addresses finite-dimensional optimization problems of the form:
$$\begin{aligned} & \underset{x}{\text{minimize}} & & f(x) := \frac{1}{2}\langle x, Qx \rangle + \langle q, x \rangle \\ & \text{subject to} & & Ax \in C \end{aligned}$$
where:

• $f(x)$ is a convex quadratic cost function ($Q \succeq 0$).
• $A \in \mathbb{R}^{m \times n}$ is a linear operator.
• $C \subset \mathbb{R}^m$ is a nonempty, closed, but potentially nonconvex set.

Significance of the Problem Class:
While classical Linear-Quadratic (LQ) problems usually assume convex constraints (e.g., polyhedral sets), this formulation allows $C$ to be nonconvex. This enables the encoding of:

• Logical conditions: Such as "either-or" constraints.
• Complementarity constraints: Modeling contact mechanics or switching dynamics.
• Cardinality constraints: Promoting sparsity.
• Vanishing constraints: Common in mixed-integer optimal control.

The key assumption is that while $C$ may be nonconvex and complex, the projection operator $\text{proj}_C$ is computationally tractable (a "projection oracle").

2. Methodology

The proposed approach combines the Augmented Lagrangian (AL) framework with a condensing technique that exploits the specific linear-quadratic structure of the problem.

A. Augmented Lagrangian Framework

The problem is reformulated using an auxiliary variable $z$:
$$\min_{x, z} f(x) + \mathcal{I}_C(z) \quad \text{s.t.} \quad Ax - z = 0$$
where $\mathcal{I}_C$ is the indicator function of set $C$. The method solves a sequence of subproblems minimizing the Augmented Lagrangian function:
$$\mathcal{L}_\sigma(x, z, \hat{x}, \hat{y}) = \mu f(x) + \frac{1}{2}\|Ax - z + \hat{y}\|^2 + \frac{\rho}{2}\|x - \hat{x}\|^2$$
subject to $z \in C$.

• Convergence: The algorithm inherits rigorous convergence guarantees from the AL framework (e.g., [8]), ensuring that feasible limit points are KKT points and infeasible limit points are stationary for the constraint violation.
• Safeguarding: A safeguarding scheme projects dual estimates onto a compact set to ensure global convergence.

B. The Condensing Approach (Core Contribution)

Standard AL methods solve for both $x$ and $z$ simultaneously, which can be computationally expensive and ill-conditioned. The author proposes a condensing strategy:

1. Partial Minimization: For a fixed $z \in C$, the subproblem with respect to $x$ is an unconstrained strictly convex quadratic program.
2. Analytical Solution: The optimal $x$ can be expressed as a linear mapping of $z$, denoted $x = X_k(z)$. This is obtained by solving a linear system (or a KKT system if "safe" equality constraints exist).
3. Marginal Function: The problem is reduced to a lower-dimensional optimization over $z$ only:
   $$\min_{z \in C} M_k(z) := \mathcal{L}_\sigma(X_k(z), z, \hat{x}, \hat{y})$$
4. Benefits:
   • Dimensionality Reduction: The subproblem size reduces from $n+m$ variables to $m$ variables.
   • Conditioning: The reduced problem is better conditioned.
   • Gradient Availability: The gradient of the marginal function $M_k(z)$ is cheap to compute: $\nabla M_k(z) = z - A X_k(z) - \hat{y}$.
   • Handling "Safe" Constraints: Linear equality constraints (e.g., dynamics $A_{eq}x = b_{eq}$) can be treated as hard constraints within the inner solve, further preserving sparsity and structure without relaxation.

C. Numerical Solver

The inner subproblems (both the extended and condensed versions) are solved using first-order methods suitable for nonconvex sets, specifically:

• Projected Gradient variants (e.g., nmpg with spectral steps).
• Quasi-Newton methods (e.g., panoc+ with extrapolation).
• Both utilize nonmonotone linesearch for globalization.

3. Key Contributions

1. Generalized Framework: Extends the generic projection-based AL approach (previously limited to general nonlinear settings) to specifically exploit linear-quadratic structure.
2. Condensing Technique: Introduces a method to analytically eliminate the primal variable $x$ from the subproblem, reducing the dimensionality and improving conditioning.
3. Handling Safe Constraints: Demonstrates how to treat linear equality constraints (like system dynamics) as hard constraints within the inner solver, avoiding the need to penalize them in the AL function.
4. Solver Agnosticism: The approach works with any subsolver capable of handling the reduced problem, provided it can evaluate projections onto $C$.

4. Numerical Results

The method was tested on three benchmarks using MATLAB on a standard laptop, comparing six configurations (Extended vs. Condensed; Soft vs. Hard constraints; nmpg vs. panoc+).

• Initial Value Problem (Discontinuous Dynamics):
  • The condensed formulation with "hard" equality constraints significantly outperformed the extended formulation.
  • Performance was comparable to specialized solvers for complementarity constraints, despite using a generic approach.
• Obstacle Problem:
  • The method successfully solved discretized problems with $N=256$ (an increase from previous literature's $N=64$).
  • The condensed approach reduced inner iterations from millions to thousands, maintaining reasonable runtimes.
• AFTI-16 Aircraft Tracking:
  • A control task with "either-or" constraints on control inputs.
  • The condensed formulation with hard constraints showed the greatest advantage.
  • The solver demonstrated robustness in closed-loop simulations, quickly finding control sequences to steer the system despite nonconvex constraints and disturbances.

General Findings:

• Speed-up: The condensing approach consistently provided faster convergence and better scalability.
• Robustness: The method handled redundant constraints and nonconvex feasible sets effectively.
• Subsolver Impact: While panoc+ generally outperformed nmpg, the structural improvements (condensing) had a more significant impact on performance than the choice of subsolver.

5. Significance

This paper bridges the gap between theoretical rigor (guaranteed convergence for nonconvex sets) and computational efficiency (exploiting LQ structure).

• It provides a practical tool for optimal control problems involving logical constraints, switching dynamics, and contact mechanics, which are notoriously difficult for standard Nonlinear Programming (NLP) solvers due to constraint qualification failures.
• By reducing the problem size and improving conditioning, it enables the solution of larger-scale discretized control problems that were previously computationally prohibitive using generic projection-based methods.
• The approach is highly flexible, requiring only a projection oracle for the constraint set, making it applicable to a wide range of engineering and decision-making problems.