On the Practical Implementation of a Sequential Quadratic Programming Algorithm for Nonconvex Sum-of-squares Problems

This paper proposes a filter line search algorithm that solves a sequence of quadratic subproblems to efficiently address nonconvex sum-of-squares optimization challenges, demonstrating through benchmarks that it significantly reduces iteration counts and computation time compared to established methods.

The Gist

The Big Picture: Finding the "Perfect" Shape in a Messy World

Imagine you are an engineer trying to design a robot arm, a self-driving car, or a satellite. You need to prove that your design is safe and stable. In the world of math, this often comes down to a specific question: "Is this complicated formula always positive?" (i.e., does it never dip below zero?)

If the formula is simple and "bowl-shaped" (convex), mathematicians have a magic tool called Sum-of-Squares (SOS) optimization. It's like having a GPS that instantly tells you the shortest, safest route. You can plug the problem into a computer, and it solves it perfectly.

But here's the catch: Real life is messy. Most real-world problems (like a robot arm swinging wildly or a plane flying through turbulence) are non-convex. They are shaped like a mountain range with many peaks and valleys, not a smooth bowl. The "magic GPS" breaks down here. The old methods for solving these messy problems are like trying to climb a mountain by taking one tiny step at a time, checking your compass, and hoping you don't fall off a cliff. They are slow, they get stuck, and they often need you to start at the very top of the mountain (a perfect guess) to work at all.

The Solution: A Smart Hiker with a Filter

The authors of this paper, Jan Olucak and Torbjørn Cunis, have built a new, smarter way to climb these messy mountains. They call their method Sequential Quadratic Programming with a Filter Line Search.

Let's break that down using an analogy:

1. The "Sequential Quadratic" Part: The Local Map

Instead of trying to see the whole mountain at once (which is impossible), the hiker looks at the ground right under their feet.

• Old Method: Takes tiny, cautious steps in one direction, then stops to check.
• New Method: The hiker looks at the immediate slope and assumes the ground is a smooth, curved hill (a "quadratic" shape). They calculate the best path down that specific curve. It's a much better guess than just walking in a straight line. Then, they take a big step, look at the new ground, draw a new map, and repeat. This is much faster.

2. The "Filter" Part: The Two-Goal Compass

Usually, when you try to optimize something, you have two conflicting goals:

1. Make the cost lower (Get to the bottom of the valley).
2. Stay within the rules (Don't fall off the cliff or walk into a forbidden zone).

Old methods use a "Penalty Score." If you break a rule, you get a huge penalty added to your score. But if you pick the wrong penalty number, the math gets confused and crashes.

The authors use a Filter. Imagine a filter as a checklist of "Bad Spots" you've already visited.

• If you find a spot that is better than any spot on the list (either lower cost or fewer rule violations), you are allowed to go there.
• If you find a spot that is worse in both ways, you are rejected.
• Why it's cool: You don't need to guess a penalty number. The filter simply says, "Hey, you made progress on something important, so you're allowed to move." This makes the algorithm much more robust and less likely to crash.

3. The "Feasibility Restoration" Part: The Rescue Rope

Sometimes, the hiker takes a step and realizes, "Oh no, I'm in a hole I can't climb out of!" (The problem is temporarily infeasible).

• Old methods: Usually just give up and say, "The problem is broken."
• New Method: The algorithm has a Rescue Rope. It pauses the main goal and says, "Forget about finding the bottom of the valley for a second. Let's just climb out of this hole." Once you are back on solid ground (feasible), it resumes the main climb. This allows the algorithm to start from a "bad" guess and still find a solution.

Why This Matters (The Results)

The authors tested this new "Smart Hiker" against the old "Tiny Step" method (called Coordinate Descent) using real-world engineering problems, like:

• F/A-18 Fighter Jets: Calculating how much turbulence a jet can handle before it becomes unstable.
• Robot Arms: Figuring out the safe working area for a multi-jointed robot.
• Satellites: Designing control laws to keep a satellite stable while spinning.

The Results:

• Speed: The new method was often 50% to 90% faster.
• Reliability: The old method often got stuck or failed if the starting guess wasn't perfect. The new method could start from a "bad" guess and still find the solution.
• Complexity: It could solve problems that the old method simply couldn't touch (like systems where the controls don't behave in a straight line).

The Takeaway

This paper is about giving engineers a better toolbox. For decades, we've had great tools for simple, smooth problems, but real life is bumpy and messy. The authors have built a smart, adaptive algorithm that can navigate the bumps, ignore the "penalty traps," and even pull itself out of holes when it gets stuck.

They even made the code open-source (free for everyone to use), so engineers can start using this "Smart Hiker" to design safer planes, robots, and satellites right now. It's a significant step toward making complex mathematical safety checks practical for everyday engineering.

Technical Summary

1. Problem Statement

The paper addresses the challenge of solving nonconvex Sum-of-Squares (SOS) optimization problems.

• Context: SOS optimization is a powerful framework for certifying polynomial nonnegativity, widely used in control engineering (e.g., stability analysis, region-of-attraction estimation, control synthesis).
• The Gap: While convex SOS problems can be efficiently solved via Semi-Definite Programs (SDPs), many practical control problems (involving local stability, invariance, or non-affine dynamics) result in nonconvex SOS formulations.
• Limitations of Current Methods: Existing state-of-the-art methods for nonconvex SOS rely on Coordinate Descent (CD) or hybrid bisection approaches. These methods:
  • Require a feasible initial guess (which is often hard to find).
  • Lack convergence guarantees for general nonconvex problems.
  • Often require splitting the problem into many smaller convex subproblems, leading to unpredictable performance and high iteration counts.
  • Struggle with non-affine system dynamics (where control inputs enter nonlinearly).

2. Methodology

The authors propose a Sequential Quadratic Programming (SQP) algorithm tailored for SOS problems, integrated with a Filter Line Search globalization strategy.

A. Sequential Quadratic SOS Programming

Instead of linearizing the problem (as in previous Sequential Linear SOS work), the authors formulate a sequence of local quadratic subproblems:

• At each iteration $k$, given a candidate solution $\xi_k$, they solve a convex SOS problem to find a search direction $\omega_k$.
• The subproblem minimizes a quadratic approximation of the Lagrangian subject to linearized SOS constraints.
• This approach leverages the KKT conditions of the original nonconvex problem, utilizing a Hessian approximation ($H_k$) to achieve faster local convergence (potentially superlinear or quadratic).

B. Filter Line Search (Globalization)

To ensure robustness from arbitrary starting points and handle constraint violations without penalty parameters, the authors employ a Filter Line Search:

• Decoupling: Unlike merit functions that combine cost and constraint violation into a single scalar (requiring penalty parameter tuning), the filter treats them as a bi-objective problem.
• Acceptance Criteria: A trial point is accepted if it improves either the objective function or reduces the constraint violation relative to previous iterates stored in the filter.
• Feasibility Restoration: If the algorithm stalls or cannot find a feasible step, a dedicated Feasibility Restoration Phase is invoked. This phase minimizes constraint violation (using a signed-distance metric) while keeping the solution close to the current iterate via regularization.
• Second-Order Correction (SOC): To mitigate the "Maratos effect" (slow convergence due to inaccurate linear approximations), a second-order correction step is applied to adjust the search direction and reduce constraint violations further.

C. Practical Implementation Details

• Constraint Violation Check: Since projecting onto the SOS cone analytically is impossible, the authors compare three methods: SOS Projection (via SDP), Signed Distance (via SDP), and Sampling. They select the Signed Distance method as it offers the best balance between accuracy and computational efficiency.
• Software: The algorithm is implemented in the open-source MATLAB-based toolbox CaΣoS (Control and Sum-of-Squares), which features efficient symbolic polynomial handling and parameterized solvers.

3. Key Contributions

1. Algorithmic Proposal: Introduction of a filter line search SQP algorithm specifically designed for nonconvex SOS problems, moving beyond the limitations of coordinate descent.
2. Convergence Analysis: A proof of local convergence (linear, superlinear, or quadratic depending on the Hessian approximation quality) for the sequential SOS algorithm.
3. Design Aspects: Development of SOS-specific components, including:
   • An efficient signed-distance metric for constraint violation estimation.
   • A robust feasibility restoration phase with regularization to handle infeasible starting points.
4. Open-Source Implementation: Release of the algorithm within the CaΣoS toolbox, accompanied by comprehensive numerical benchmarks.

4. Results and Benchmarks

The proposed method was benchmarked against the state-of-the-art Coordinate Descent (CD) method across several control engineering applications:

• Region-of-Attraction (ROA) Estimation:
  • F/A-18 Flight Control: The SQP method converged in 19 iterations (52.5s total time), while CD failed to converge within 100 iterations (277s).
  • N-link Robot Arm: For systems with up to 24 states, SQP required 60% fewer iterations and 54% less computation time than CD.
  • Robustness: When initialized with a clearly infeasible guess (negative polynomials), CD failed immediately. SQP successfully recovered via the feasibility restoration phase, converging to a feasible solution.
• Control Synthesis:
  • Nonlinear Aircraft Dynamics: The problem involved non-affine control inputs, which CD cannot solve directly without complex reformulations. SQP solved it in ~13 seconds.
  • Spacecraft Attitude Control: SQP solved the problem in ~1 minute, whereas CD failed after 6 iterations.
• Reachability Analysis: SQP significantly reduced iterations and total time compared to CD, particularly for higher-dimensional systems (4 states).
• CBF-CLF Synthesis: A complex problem with 1756 constraints was solved in 53 iterations, demonstrating the scalability of the approach.

Key Performance Metrics:

• Iteration Count: Significantly reduced compared to CD.
• Computation Time: Substantial reduction (often by factors of 2x to 10x) due to fewer iterations and efficient subproblem solving.
• Robustness: Ability to start from infeasible points, a major advantage over CD.

5. Significance

This paper represents a significant step forward in the practical application of SOS optimization for nonlinear control systems.

• Overcoming Nonconvexity: It provides a tractable, efficient, and robust method for solving nonconvex SOS problems that were previously difficult or impossible to solve with standard SDP-based tools.
• Control Engineering Impact: It enables the direct synthesis of controllers and stability certificates for systems with non-affine dynamics and local constraints, which are common in real-world robotics and aerospace applications.
• Theoretical and Practical Bridge: By combining rigorous local convergence theory with a practical globalization strategy (filter line search) and open-source software, the authors make advanced nonlinear control synthesis more accessible to engineers.

In summary, the proposed Sequential Quadratic SOS algorithm with Filter Line Search outperforms existing coordinate descent methods in speed, iteration count, and robustness, particularly for complex, nonconvex control problems.