Successive Convexification: A Superlinearly Convergent Algorithm for Non-convex Optimal Control Problems

Abstract

This paper presents the SCvx algorithm, a successive convexification algorithm designed to solve non-convex constrained optimal control problems with global convergence and superlinear convergence-rate guarantees. The proposed algorithm can handle nonlinear dynamics and non-convex state and control constraints. It solves the original problem to optimality by successively linearizing non-convex dynamics and constraints about the solution of the previous iteration. The resulting convex subproblems are numerically tractable, and can be computed quickly and reliably using convex optimization solvers, making the SCvx algorithm well suited for real-time applications. Analysis is presented to show that the algorithm converges both globally and superlinearly, guaranteeing i) local optimality recovery: if the converged solution is feasible with respect to the original problem, then it is also a local optimum; ii) strong convergence: if the Kurdyka-Lojasiewicz (KL) inequality holds at the converged solution, then the solution is unique. The superlinear rate of convergence is obtained by exploiting the structure of optimal control problems, showcasing that faster rate of convergence can be achieved by leveraging specific problem properties when compared to generic nonlinear programming methods. Numerical simulations are performed for a non-convex quad-rotor motion planning problem, and corresponding results obtained using Sequential Quadratic Programming (SQP) and general purpose Interior Point Method (IPM) solvers are provided for comparison. The results show that the convergence rate of the SCvx algorithm is indeed superlinear, and that SCvx outperforms the other two methods by converging in less number of iterations.

arXiv comment35 pages, 7 figures, manuscript submitted to SIAM Journal on Control and Optimization (SICON)

Cited by in corpus (18)

• Dual Quaternion Based Powered Descent Guidance with State-Triggered Constraints
• A Survey on Convex Optimization for Guidance and Control of Vehicular Systems
• Collision Avoidance Maneuver Optimization with a Multiple-Impulse Convex Formulation
• Flatness-based Quadcopter Trajectory Planning and Tracking with Continuous-time Safety Guarantees
• Contact-Implicit Trajectory Optimization Based on a Variable Smooth Contact Model and Successive Convexification
• End-to-end Neural Network Based Quadcopter control
• Variable-Horizon Guidance for Autonomous Rendezvous and Docking to a Tumbling Target
• Autonomous parafoil precision landing using convex real-time optimized guidance and control
• Successive Convexification with Feasibility Guarantee via Augmented Lagrangian for Non-Convex Optimal Control Problems
• Formal Methods for Autonomous Systems
• Sequential sum-of-squares programming for analysis of nonlinear systems
• Lossless convexification of non-convex optimal control problems with disjoint semi-continuous inputs
• Convex Optimization for Trajectory Generation
• Attitude Trajectory Optimization for Agile Satellites in Autonomous Remote Sensing Constellation
• Ignition Point Reachability for Aerodynamically-Controlled Reusable Launch Vehicles
• Iterative Best Response for Multi-Body Asset-Guarding Games
• Proportional-Integral Projected Gradient Method for Model Predictive Control
• Distributed Experiment Design and Control for Multi-agent Systems with Gaussian Processes