Source-linked AI summary
Successive Convexification of Non-Convex Optimal Control Problems and Its Convergence Properties
Yuanqi Mao, Michael Szmuk, Behcet Acikmese
TL;DR
The paper addresses non-convex optimal control caused by nonlinear dynamics, under convexified state and control constraints. It proposes successive linearization with safeguarding mechanisms and proves continuous-time convergence, supported by an illustrative numerical example.
Problem
Non-convex optimal control problems are difficult for general nonlinear programming because computational effort lacks known bounds and poor initial guesses can cause divergence.
Method
SCvx successively linearizes nonlinear dynamics, solves convex subproblems, and uses virtual control and trust regions to safeguard the iterations.
Results
For an infinite convergent sequence, every limit point is a constrained stationary point satisfying the optimality condition for the original non-convex optimal control problem.
Takeaways & Limitations
The algorithm provides a systematic convex-subproblem framework for solving non-convex optimal control problems while retaining a continuous-time convergence guarantee.
Abstract
from arXiv · showhide
This paper presents an algorithm to solve non-convex optimal control problems, where non-convexity can arise from nonlinear dynamics, and non-convex state and control constraints. This paper assumes that the state and control constraints are already convex or convexified, the proposed algorithm convexifies the nonlinear dynamics, via a linearization, in a successive manner. Thus at each succession, a convex optimal control subproblem is solved. Since the dynamics are linearized and other constraints are convex, after a discretization, the subproblem can be expressed as a finite dimensional convex programming subproblem. Since convex optimization problems can be solved very efficiently, especially with custom solvers, this subproblem can be solved in time-critical applications, such as real-time path planning for autonomous vehicles. Several safe-guarding techniques are incorporated into the algorithm, namely virtual control and trust regions, which add another layer of algorithmic robustness. A convergence analysis is presented in continuous- time setting. By doing so, our convergence results will be independent from any numerical schemes used for discretization. Numerical simulations are performed for an illustrative trajectory optimization example.
I. INTRODUCTION
The paper targets non-convex optimal control problems by retaining convexified constraints and addressing nonlinear dynamics through successive convexification. It motivates this approach with the need for reliable, computationally efficient methods and establishes continuous-time convergence guarantees.
- Motivation: Non-convex optimal control problems arise from nonlinear dynamics, non-convex constraints, and applications such as planetary landing, autonomous path planning, and spacecraft rendezvous.The paper assumes state and control constraints have already been convexified for its main formulation.
- Motivation: General nonlinear programming methods offer limited computational guarantees and can diverge from poor initial guesses, hindering automated and real-time applications.These concerns motivate reformulation within a convex programming framework.
- Motivation: Convex programming can provide polynomial-time solutions to global optimality and support real-time execution with generic or customized SOCP solvers.The paper uses these properties as motivation for convexifying the remaining nonlinear dynamics.
- Contributions: The proposed SCvx method successively linearizes nonlinear dynamics and solves a sequence of convex subproblems, while virtual control and trust regions safeguard convergence.The paper presents a continuous-time convergence analysis and identifies a systematic algorithmic framework.
B. Algorithm Description
SCvx forms each iteration by linearizing the dynamics around the previous trajectory and control, then solving the resulting convex subproblem successively until convergence.
- B. Algorithm Description: SCvx linearizes the dynamics around the trajectory and control obtained at the previous succession.The successive procedure is repeated until convergence.
- B. Algorithm Description: The successive linearization is designed to recover at least first-order optimality for the original nonlinear problem.A single convexified problem need not have the same solution as the original non-convex problem.
1) Linearization:
Linearization converts the nonlinear dynamics into a linear system in deviation state and control variables, yielding convexity but introducing feasibility and approximation concerns.
- 1) Linearization:: The first-order Taylor expansion is taken around the previous trajectory and control, using d(t) and w(t) as the new state and control.These deviation variables are defined relative to the preceding succession's solution.
- 1) Linearization:: The resulting linear system provides convexity but introduces artificial infeasibility and approximation error.The paper addresses these issues with virtual control and trust regions in subsequent subsections.
2) Virtual Control:
Virtual control prevents linearization-induced infeasibility by restoring reachability, while a penalty term discourages its use in the optimized solution.
- 2) Virtual Control:: Linearization can make a feasible original problem artificially infeasible, blocking iterations and preventing convergence.The issue occurs at some points in the solution space.
- 2) Virtual Control:: An unconstrained virtual control can make any state in the feasible region reachable in finite time when the augmented pair is controllable.For autonomous vehicles, it can be interpreted as synthetic acceleration.
- 2) Virtual Control:: The algorithm heavily penalizes virtual control through an additional λγ(Ev) cost term so it is used only as needed.The penalty function uses the L1 norm.
- 2) Virtual Control:: The penalized objective is defined after linearization and has an analogous formulation before linearization.This preserves the virtual-control safeguard within the successive optimization procedure.
3) Trust Regions:
Trust regions limit each linearized trajectory’s deviation from the previous nominal trajectory, reducing risks from inaccurate or unbounded linear approximations. Together with virtual control, they support convergence toward feasibility.
- Trust-region motivation: Linearization can make a feasible nonlinear problem artificially infeasible or can render the convexified problem unbounded.These risks arise when the linearized model departs substantially from the nonlinear problem.
- Trust-region motivation: Trust regions restrict the new trajectory’s deviation from the previous nominal trajectory because the linear approximation is trusted only locally.The trust-region radius is adjusted during iteration.
- Trust-region behavior: The trust-region radius is adjusted iteratively; in the illustrative example, restricting x to [0.5,1.5] and changing the radius eventually converges to x = 0.The figure depicts a typical two-dimensional convergence process.
- Trust-region behavior: The algorithm can start from virtually anywhere and converge to a feasible point, while virtual control allows early trajectories to deviate from the constraint.The early deviation is shown as part of the safeguarded convergence process.
4) The SCvx Algorithm:
SCvx repeatedly solves a convex optimal control subproblem with virtual control and trust regions, then accepts, rejects, and sizes steps using actual-versus-predicted cost reduction. Solving each subproblem to full optimality is intended to reduce the number of successions.
- Subproblem: At each succession, SCvx solves a convex optimal control problem for the control increment and state increment under linearized constraints and safeguarding terms.The subproblem minimizes L(d,w) subject to the specified convexified constraints.
- Algorithmic distinction: Unlike conventional trust-region line searches, SCvx solves each convex subproblem to full optimality, potentially reducing the number of successions through larger cost reductions.The paper notes that computational effort per succession may slightly increase.
- Step evaluation: SCvx computes the ratio r_k = ΔJ_k/ΔL_k to assess how accurately the linear approximation predicts penalized-cost reduction.Ratios near 1 indicate agreement between actual and predicted reduction.
- Trust-region update: If r_k < ρ_0, the algorithm rejects the step and contracts the trust-region radius.Rejected steps return to the subproblem solve with a smaller radius.
- Trust-region update: Accepted steps update the state and control, while the radius contracts, stays fixed, or expands according to thresholds ρ_1, ρ_2 and factor α.The radius is also bounded below by Δ_l.
III. CONVERGENCE ANALYSIS
The convergence analysis reformulates the continuous-time control problem as an infinite-dimensional optimization problem in Banach space. States and controls are treated as independent variables, with dynamics represented as algebraic equality constraints.
- Continuous-time formulation: The analysis is conducted in continuous time, making the convergence results independent of numerical discretization schemes.The paper uses this setting to simplify the convergence analysis.
- Continuous-time formulation: States and controls are treated as independent variables, and their pair is denoted by x in the Banach-space formulation.This redefines the variable space X for the analysis.
- Problem reformulation: The original dynamics are represented as algebraic equations, while state and control constraints are represented as inequalities.These constraints define the feasible set F.
- Problem reformulation: The original objective functional becomes Ψ(x), which is stated to be Fréchet differentiable.Problem 3 minimizes Ψ(x) subject to the reformulated constraints.
- Penalty formulation: The penalty formulation introduces J(x,λ) for the equality-constrained problem, producing Problem 4 with the original constraints retained.The penalized cost is defined after rewriting the dynamics as g(x) = 0.
A. Exactness of Penalty Function γ(g(x))
The penalty analysis establishes when penalizing the dynamics preserves stationarity, using generalized derivatives and constraint qualifications. Under the stated multiplier-based penalty condition, stationary points of the penalty problem correspond to constrained stationary points of the original problem.
- Penalty exactness: An exact penalty function uses a finite λ such that the penalized and unpenalized problems have equivalent optimality conditions.The paper studies exactness despite nonsmoothness in the penalty term.
- Stationarity conditions: Under LICQ, a local solution of Problem 3 admits multipliers satisfying the first-order stationarity conditions.LICQ requires linear independence of the active constraint gradients.
- Stationarity conditions: The generalized directional derivative and generalized differential provide the nonsmooth optimality tools used to analyze the penalized cost.The paper introduces these objects before deriving the penalty problem’s conditions.
- Exactness theorem: If the penalty weight satisfies the theorem’s multiplier-based condition, a stationary point of Problem 3 is a constrained stationary point of Problem 4.The result places the point in the set S of constrained stationary points.
- Exactness theorem: Conversely, a feasible constrained stationary point of Problem 3 is stationary for the penalty problem.This converse is used in the subsequent convergence analysis.
- Exactness theorem: The theorem does not provide a constructive way to select λ; implementations instead use a sufficiently large fixed penalty weight.The paper reports that this works well for most applications numerically.
B. Convergence Analysis
The convergence analysis establishes stationarity properties for SCvx, covering both finite termination and infinite sequences. It also shows that sufficiently small trust regions make the actual-to-predicted reduction ratio acceptable, despite nondifferentiable penalty terms.
- Finite convergence: The predicted cost changes are nonnegative, and zero predicted change implies that the current iterate is stationary for the penalty problem.
- Infinite sequences: The infinite-sequence analysis is complicated by the nondifferentiable penalty function γ(·), although the Taylor remainder o(∥d∥) is independent of x.
- Trust-region behavior: As the trust-region radius approaches zero, the actual-to-predicted reduction ratio r(x,∆) approaches 1.Therefore, for any c < 1, sufficiently small ∆ ensures r(x,∆) ≥ c.
- Trust-region behavior: Rejected trial steps cannot continue forever because repeated trust-region reductions eventually make rk exceed the acceptance threshold ρ0.
- Infinite sequences: If SCvx generates an infinite sequence, it has limit points, and every limit point is a constrained stationary point of Problem 4.The proof uses convex compactness of the feasible region together with the trust-region acceptance result.
IV. NUMERICAL SIMULATIONS
The numerical example applies SCvx to double-integrator dynamics with nonlinear aerodynamic drag and a bounded thrust input. After an initial straight-line linearization, the method reaches desirable convergence after the first 10 accepted successions and produces a drag-dependent thrust profile.
- Problem setup: The example uses double-integrator dynamics with nonlinear aerodynamic drag and thrust limited to a maximum magnitude Tmax.
- Problem setup: The first succession is linearized about a constant-velocity straight-line trajectory connecting the initial and final positions.
- Convergence behavior: The convergence history shows desirable convergence after the first 10 accepted successions.
- Thrust profile: With aerodynamic drag, thrust decreases at the beginning and remains nonzero in the middle to counter energy loss.
- Thrust profile: The drag case has less area under its thrust curve than the no-drag case, indicating reduced optimal cost when nonlinear dynamics include drag.
- Algorithm behavior: The trust-region mechanism rejects steps when rk falls below ρ0 and adjusts ∆k according to rk relative to ρ0, ρ1, and ρ2.After rejection, decreasing ∆k raises rk above ρ0.
V. CONCLUSIONS
The paper proposes SCvx for nonlinear optimal control and analyzes its convergence. In the infinite convergent case, every limit point satisfies the original problem’s optimality condition.
- SCvx successively convexifies nonlinear dynamics to solve non-convex optimal control problems through convex subproblems.
- The paper provides a relatively thorough description and analysis of the proposed algorithm, supported by an illustrative numerical example.
- For the infinite convergent case, every limit point satisfies the optimality condition for the original non-convex optimal control problem.
- The authors identify integrating SCvx with other convexification techniques as a next step toward handling a broader class of non-convexities.