Sequential Convex Programming

Definition

Sequential convex programming (SCP) solves a nonconvex optimal-control / trajectory-planning
problem by repeatedly solving a convex approximation of it: at each iteration the nonlinear
dynamics and nonconvex constraints are linearized about the previous iterate, the resulting convex
subproblem (here a quadratic program with linear constraints) is solved over a trust region that
keeps the linearization valid, and the solution seeds the next iterate until the cost change falls
below a tolerance (Misra & Bai 2017). It converges to a local KKT point of the original problem,
not a global optimum. In the cited work the technique plans point-to-point arm trajectories for a
free-flying space manipulator (Misra: an attitude-controlled, redundant 8-DOF arm whose base
translates passively and must be compensated; Virgili-Llop: a fully thrust-and-momentum-actuated
base) — distinct from the free-floating regime where base motion is uncontrolled and folded into a
generalized Jacobian.

Key Equations

Symbols per notation.md.

Each iteration $q$ linearizes a nonlinear constraint $g(x)$ about the current iterate $x^q$ to an
affine constraint (Misra Eq. 15):

$\hat{g}(x)=g(x^q)+\nabla g(x^q{)}^{\top }(x-x^q).$

With manipulator state ${\zeta }_k=[{\theta }_k;{\dot{\theta }}_k]$, control $u_k={\ddot{\theta }}_k$, and discrete
dynamics ${\zeta }_{k+1}=A_{\Delta t}{\zeta }_k+B_{\Delta t}{u}_k$, each SCP iteration is the convex QP
(Misra Eqs. 22–24, with the affine constraints $E_k^q+F_k^q{\zeta }_k=0$ and $C_k^q{\zeta }_k\le D_k^q$):

\quad\text{s.t.}\quad \zeta_{k+1}=A_{\Delta t}\zeta_k+B_{\Delta t}u_k,\ \ E_k^q+F_k^q\zeta_k=0,\ \ C_k^q\zeta_k\le D_k^q,\ \ \|\zeta-\zeta^q\|\le\rho.$$ Hard terminal/obstacle constraints are softened with an exact $\ell_1$ penalty $\lambda\,\|g(\zeta)\|_1$ (Misra Eqs. 25–26), valid for $\lambda>\lambda^{\*}=\|\mu_i^{\*}\|_\infty$; the trust-region radius $\rho$ expands/contracts per iteration on the ratio of actual to predicted cost change. > _Notation note._ Misra writes the augmented objective with $\hat\Gamma,\tilde\Gamma$; this clashes > with the load-bearing coordinate-transform matrix $\boldsymbol{\Gamma}$ in > [notation.md](../notation.md), so those symbols are **not** reused here. $\rho$ (trust-region > radius), $\lambda$ (penalty weight), $A_{\Delta t},B_{\Delta t}$, $\zeta,u$ are local to this page > and not yet in the registry. ## Source Support - [misra2017optimal](../sources/misra2017optimal.md) — primary; formulates redundant free-flying-arm point-to-point planning as SCP, with the affine pose/obstacle linearization, the QP subproblem, the $\ell_1$-penalty reformulation, and the trust-region update law (Algorithm 1). - [virgili-llop2019convex](../sources/virgili-llop2019convex.md) — supporting; uses SCP in a capture guidance scheme split into a **convergence-guaranteed** SCP for system-wide translation (proven to reach a KKT point against convexified keep-out zones) and a **trust-region-heuristic** SCP for internal reconfiguration (no recursive-feasibility guarantee); HIL-validated for real-time use. ## Related Topics - [trajectory_optimization](trajectory_optimization.md) — SCP is one numerical method for solving the nonconvex trajectory-optimization problem. - [optimal_control_bvp](optimal_control_bvp.md) — the underlying object is a constrained nonconvex optimal-control problem; SCP transcribes and discretizes it rather than solving the continuous BVP. - [model_predictive_control](model_predictive_control.md) — Virgili-Llop's deterministic-convergence, real-time-capable (HIL-validated) SCP is *suitable* for onboard recompute; the paper re-solves the problem from the hold position to pick the optimal maneuver start time, but does not itself run a receding-horizon loop during execution. - [motion_planning](motion_planning.md) — both sources apply SCP to collision-free point-to-point motion planning with obstacle/keep-out constraints. - Misra plans on a redundant (n > 6) arm and seeds the SCP loop with a [damped_least_squares](damped_least_squares.md) inverse-kinematics guess, touching [redundancy_resolution](redundancy_resolution.md). (Virgili-Llop instead seeds with a constant-acceleration joint-space interpolation and a line-of-sight attitude guess — no IK seed.) ## Open Questions - [ ] Misra's "free-flying" base is **attitude-controlled but translation-passive** (the SCP *compensates* for, rather than commands, base translation). How does the formulation change for our **fully-actuated** 6-DOF base, where base force/torque are decision variables? - [ ] Virgili-Llop guarantees convergence only for the *translation* sub-maneuver; the reconfiguration SCP relies on trust-region heuristics with no recursive-feasibility guarantee. Can a convergence certificate be recovered when the full coupled inertia $\boldsymbol{M},\boldsymbol{C}$ is retained? - [ ] SCP returns a *local* KKT point dependent on the inverse-kinematics seed. How sensitive is the planned trajectory to seed choice near a [kinematic_singularity](kinematic_singularity.md)?