💻 computer science

A Fast Convergent Algorithm for Solving Non-convex Partially-Decoupled Generalized Nash Equilibrium Problems

This paper introduces FALCON, a fast convergent algorithm that utilizes sequential convex programming and potential game reformulation to solve non-convex, partially-decoupled generalized Nash equilibrium problems in multi-agent optimal control with guaranteed global convergence to an open-loop Nash equilibrium.

Original authors: Bennet Outland, Vishala Arya

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bennet Outland, Vishala Arya

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a high-stakes game of tag played not just by people, but by autonomous robots, self-driving cars, or spacecraft. In these scenarios, everyone is trying to win (or survive) based on their own goals, but their movements are tightly linked. If one car swerves, it changes the options available to everyone else. In the world of mathematics, this is called a Non-Convex Differential Game.

The problem is that these games are incredibly hard to solve. It's like trying to find the lowest point in a landscape filled with deep valleys, sharp cliffs, and hidden holes (non-convexity). Most existing algorithms are like hikers who get stuck in a small valley, thinking it's the bottom, when a much deeper one exists nearby. Or, they might try to take a shortcut that leads them off a cliff (violating safety rules).

This paper introduces a new algorithm called FALCON (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria). Think of FALCON as a super-smart, cautious guide that helps a group of players find the best possible strategy for everyone, even in the most chaotic and dangerous environments.

Here is how FALCON works, broken down into simple concepts:

1. The "Partially-Untangled" Game

First, the authors make a reasonable assumption: while the players affect each other's goals and safety rules, they don't directly control each other's engines.

The Analogy: Imagine a group of cyclists racing. Cyclist A's pedaling doesn't physically push Cyclist B's bike. However, if Cyclist A blocks the path, Cyclist B has to change their route to avoid crashing. FALCON assumes the "physics" of each player is independent, but the "rules of the road" (constraints) connect them. This simplifies the math without losing the essence of the problem.

2. The "Smoothie" Trick (Convexification)

The core difficulty is that the game landscape is bumpy and jagged. FALCON uses a technique called Sequential Convex Programming.

The Analogy: Imagine you are trying to roll a ball to the bottom of a crumpled piece of paper. It's impossible to predict the path. FALCON takes a small, flat piece of paper (a "trust region") and places it over the crumpled area. On this small, flat piece, the path is a straight line (convex). The algorithm solves the easy problem on the flat paper, takes a step, then moves the flat paper to the new location and repeats.
The Safety Net: To make sure the players don't wander off the paper into the "cliffs" (where the math breaks), FALCON uses a Trust Region. It says, "You can only move as far as this small circle allows." If the step looks good, the circle gets bigger; if it looks bad, the circle shrinks.

3. The "Continuous Safety" Belt

A common problem with these algorithms is that they check safety rules only at specific moments (like checking a car's speed only once every second). But what if the car swerved dangerously between those checks?

The Analogy: FALCON doesn't just check the speed at the start and end of a second; it adds a "safety belt" that monitors the car continuously. It creates a virtual variable that accumulates any tiny violation of the rules between the checks. If the car ever drifts even slightly out of bounds, this belt tightens and forces the algorithm to correct the path. This ensures the solution is safe at every instant, not just at the checkpoints.

4. The "Team Negotiator" (Augmented Lagrangian)

Since the players have shared constraints (like "don't crash into each other"), they need a way to negotiate.

The Analogy: FALCON uses a mathematical "negotiator" (Lagrange multipliers). If Player A gets too close to Player B, the negotiator raises a "penalty price." Player A then adjusts their path to lower the price. The algorithm keeps adjusting these prices until everyone finds a balance where no one wants to change their strategy because it would only make things worse for them. This balance is called a Nash Equilibrium.

5. The Results: Racing, Hallways, and Space

The authors tested FALCON on three difficult scenarios to prove it works:

The F1 Racing Game: Two cars racing around a sharp corner.
- The Result: FALCON was faster and more reliable than previous methods. While other algorithms got stuck or failed to find a solution in tricky starting positions, FALCON found the winning strategy 100% of the time. It successfully figured out how the cars should jockey for position to cut off the opponent without crashing.
The Narrowing Hallways: Three robots trying to squeeze through a hallway with two narrow choke points.
- The Result: The robots had to coordinate perfectly. They couldn't just rush; they had to take turns. FALCON allowed them to "emerge" with a smart behavior where they naturally lined up and passed through the narrow spots one by one while staying in communication range.
The Space Game (Lady, Bandit, Guard): A high-value satellite ("Lady") is being chased by an attacker ("Bandit") while a protector ("Guard") tries to block the attacker.
- The Result: This is a complex 3D dance in space. FALCON calculated the trajectories where the Guard successfully intercepted the Bandit to let the Lady escape, or where the Bandit managed to get close despite the Guard's efforts. It handled the complex physics and collision avoidance simultaneously.

The Bottom Line

FALCON is a new, fast, and reliable way to solve complex multi-agent games. It guarantees that if a solution exists, the algorithm will find it (global convergence). It ensures that the solution is safe at every single moment in time, not just at the checkpoints. By turning a jagged, impossible-to-solve puzzle into a series of small, manageable, flat puzzles, FALCON allows autonomous systems to make smart, safe, and cooperative decisions in the real world.

Technical Summary: FALCON for Non-Convex Partially-Decoupled Generalized Nash Equilibrium Problems

Problem Formulation

The paper addresses the challenge of solving multi-agent optimal control problems in aerospace and robotics, specifically modeling them as non-convex differential games. The authors focus on a specific subclass of Generalized Nash Equilibrium Problems (GNEPs) termed Partially-Decoupled Generalized Nash Equilibrium Problems (PDGNEPs).

In this formulation, $N$ agents seek to minimize individual cost functions $J_i$ subject to:

Separable Dynamics: Each agent $i$ evolves according to its own dynamics $\dot{x}_i(t) = f(x_i(t), u_i(t))$ , independent of other agents' controls or states.
Coupled Constraints: Agents are coupled through shared equality and inequality constraints $C(X, \Upsilon) \leq 0$ , which may depend on the trajectories of all agents.
Objective: Finding an Open-Loop Nash Equilibrium, defined as a set of strategies where no agent can unilaterally improve their cost by deviating, given the strategies of others.

Existing methods face limitations: Iterative LQ Games (iLQGames) lack native handling of constraints; Augmented Lagrangian Games (ALGAMES) show improved performance but struggle with tight non-convexities; and Differential Games Sequential Quadratic Programming (DG-SQP) offers convergence guarantees but often suffers from high computational costs and numerical instability in highly non-convex scenarios.

Methodology: The FALCON Algorithm

The authors propose FALCON (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria), an algorithm that combines Sequential Convex Programming (SCP) with an Augmented Lagrangian framework. The core methodology proceeds as follows:

1. Continuous-Time Constraint Enforcement

To address the issue of inter-sample constraint violations common in discretized SCP solvers, the authors reformulate constraints using an exterior-penalty approach.

A continuous-time measure of constraint violation, $\Lambda_i(t)$ , is defined using a cubic penalty function $q(z) = [z]_+^3$ (chosen for $C^2$ smoothness).
An augmented state variable $y_i(t)$ accumulates this violation over time.
Constraints are enforced not just at discretization nodes but throughout the continuous horizon by bounding the accumulation of $y_i$ between nodes, ensuring pointwise constraint satisfaction within a theoretical bound $\delta(\varepsilon)$ .

2. Augmented Lagrangian and Epigraph Reformulation

To handle non-convex objectives and constraints:

Epigraph Form: The non-convex cost function $J_i$ is shifted into the constraints via an epigraph variable $\tau_i$ , minimizing $\tau_i$ subject to $J_i \leq \tau_i$ . This allows the objective to be linearized while keeping the non-convexity in the constraints.
Augmented Lagrangian: An augmented Lagrangian function $L_i$ is constructed, incorporating Lagrange multipliers ( $\lambda, \mu$ ) and penalty weights ( $\omega$ ) for both dynamics and coupling constraints.

3. Sequential Convexification (SCvx*)

The non-convex game is approximated iteratively by solving a sequence of convex sub-problems:

Linearization: Dynamics and constraints are linearized around a reference trajectory $\bar{z}$ .
Relaxation: Virtual control ( $\xi$ ) and virtual buffer ( $\zeta$ ) variables are introduced to mitigate artificial infeasibility caused by linearization.
Trust Region: A trust region constraint $\|z - \bar{z}\|_\infty \leq r$ ensures the approximation remains valid.
Potential Game Reformulation: The resulting convex sub-problem is structured as a Variational Generalized Nash Equilibrium (v-GNE). By constructing a strongly convex potential function $\Phi_k$ (sum of individual penalized objectives), the sub-problem is solved efficiently as a Second-Order Cone Program (SOCP).

4. Algorithmic Loop

The algorithm iterates through:

Successive Linearization: Creating the convex sub-problem.
Step Acceptance: Evaluating the "quality" of the step using a joint-potential ratio $\rho_k$ (comparing actual cost reduction vs. predicted reduction). Steps are accepted if $\rho_k$ exceeds a threshold.
Multiplier Updates: Lagrange multipliers and penalty weights are updated based on constraint violations and a user-defined tolerance $\delta_k$ .
Trust Region Adjustment: The trust region radius $r$ is dynamically adjusted (contracted or expanded) based on the acceptance ratio.

Key Contributions

Algorithm Development: Introduction of FALCON, a novel algorithm that solves non-convex PDGNEPs by combining sequential convexification with augmented Lagrangian techniques.
Theoretical Guarantees: Proof of global convergence to an open-loop Nash equilibrium under mild assumptions (bounded acceleration, Lipschitz continuity, $C^2$ smoothness). The solution is guaranteed to be dynamically feasible and approximately coupling-feasible in a continuous-time sense.
Continuous-Time Safety: A rigorous formulation for enforcing constraints continuously between discretization nodes, preventing safety violations in inter-sample intervals.
Efficiency: Demonstration that the convexified sub-problem can be solved as a potential game using efficient SOCP solvers, avoiding the computational bottlenecks of previous DG-SQP methods.

Numerical Results

The authors validate FALCON on three distinct non-convex differential game scenarios:

F1 Austin Racing (2 Players):
- Scenario: Two cars racing on a sharp corner of the F1 Austin track.
- Performance: FALCON achieved a 100% convergence rate across various initial conditions, whereas DG-SQP converged only 72% of the time.
- Speed: FALCON was significantly faster, with an average computation time of 0.873 seconds compared to DG-SQP's 50.021 seconds. ALGAMES failed to converge on this difficult case under the same standards.
Narrowing Hallways (3 Players):
- Scenario: Three unicycle agents navigating a hallway with two choke-points while maintaining collision avoidance and communication range constraints.
- Observation: The algorithm successfully handled the non-convex environment, demonstrating emergent cooperative behaviors (e.g., agents sequencing their passage through choke-points) while strictly adhering to continuous-time constraints.
Spacecraft Lady-Bandit-Guard (3 Players):
- Scenario: A heterogeneous game in $R^6$ (Clohessy-Wiltshire-Hill dynamics) involving a "Lady" (high-value asset), a "Bandit" (attacker), and a "Guard" (defender).
- Observation: FALCON solved the complex pursuit-evasion-defense game, successfully simulating scenarios where the guard blocked the bandit to allow the lady to escape, handling the non-convexities of the engagement geometry.

Significance and Claims

The paper claims that FALCON represents a significant advancement in solving multi-agent differential games by bridging the gap between computational efficiency and theoretical convergence guarantees.

Differentiation: Unlike iLQGames, FALCON natively handles state and control constraints. Unlike DG-SQP, it offers superior numerical performance and robustness in highly non-convex settings without sacrificing convergence guarantees.
Safety: The continuous-time constraint formulation is highlighted as a critical feature for safety-critical aerospace applications where inter-sample violations are unacceptable.
Scalability: By reducing the inner loop to a potential game solvable via SOCP, the method offers a scalable approach for complex multi-agent systems.

The authors conclude that FALCON provides a robust, fast, and theoretically grounded framework for solving non-convex differential games, making it suitable for complex aerospace operations such as pursuit-evasion, contested space operations, and cooperative guidance.