Geometric Conditions for Lossless Convexification in Linear Optimal Control with Discrete-Valued Inputs

1. Problem Statement

The paper addresses the challenge of solving Optimal Control Problems (OCPs) for linear systems where the control inputs are discrete-valued (e.g., on-off actuators or thrusters with fixed magnitude levels).

• Core Difficulty: Discrete inputs introduce mixed-integer constraints, transforming the problem into a Mixed-Integer Program (MIP). MIPs are computationally intractable for real-time, safety-critical applications (like spacecraft control) due to exponential growth in runtime and a lack of convergence guarantees.
• Specific Application: The authors focus on fuel-optimal control for spacecraft rendezvous. Fuel optimality is typically modeled using the $L_1$-norm of the control input (proportional to total propellant usage), which is a Lagrange-form cost function.
• Goal: To reformulate the non-convex, mixed-integer problem into a convex program (CP) that can be solved efficiently in real-time, without losing the optimality of the solution (i.e., "lossless" convexification).

2. Methodology

The proposed methodology extends existing lossless convexification techniques (previously limited to Mayer-form problems) to Lagrange-form problems with discrete inputs. The approach involves three main steps:

A. Epigraph Transformation (Lagrange to Mayer)

The authors transform the original Lagrange-form problem (minimizing the integral of a cost function) into an equivalent Mayer-form problem (minimizing a terminal state).

• They introduce an auxiliary cost state variable $x_c(t)$ with dynamics $\dot{x}_c(t) = \mu(t)$, where $\mu(t)$ represents the instantaneous cost.
• The original cost function $\psi(u)$ (e.g., $L_1$-norm) is incorporated into the dynamics via an epigraph transformation. The input set is augmented to $\tilde{U}_e = \text{conv}(U) \times [\bar{u}, \bar{u}] \cap \text{epi}(\psi(u))$.
• This converts the integral cost minimization into a terminal state minimization ($x_c(t_f)$).

B. Geometric Conditions and System Normality

The core theoretical contribution lies in establishing conditions under which the relaxed convex problem yields a solution that naturally satisfies the original discrete constraints.

• Assumption (A1): The vertices (extreme points) of the augmented set $\tilde{U}_e$ must correspond exactly to the original discrete input set $U$ paired with their cost values. This is a geometric condition on the input set and the cost function.
• System Normality: The authors prove that if the original linear system $(A, B)$ is strongly normal with respect to the convex hull of the input set, then the augmented system $(\hat{A}, \hat{B})$ is also strongly normal with respect to the augmented set $\tilde{U}_e$.
• Extreme-Point Relaxation: Under strong normality, the optimal control for the relaxed convex problem is guaranteed to lie on the extreme points (vertices) of the input polytope. Due to Assumption (A1), these vertices correspond exactly to the original discrete values.

C. Theoretical Result

Theorem 1 formalizes that if the system is strongly normal and the geometric condition (A1) holds, the solution to the relaxed convex problem (Problem 3) is identical to the solution of the original mixed-integer problem (Problem 1). This validates the "lossless" nature of the convexification.

3. Key Contributions

1. Extension to Lagrange-Form: The paper extends lossless convexification from Mayer-form problems to Lagrange-form problems (specifically fuel-optimal control) by proving that system normality is preserved under the epigraph transformation.
2. Geometric Characterization: It identifies specific geometric conditions on the input set and cost function (Assumption A1) that guarantee the relaxed solution remains discrete-valued.
3. Real-Time Feasibility: By converting a difficult Mixed-Integer Program into a standard Convex Program, the method enables the use of efficient solvers (like interior-point methods) suitable for real-time embedded systems.
4. Validation on Spacecraft Rendezvous: The approach is validated on a realistic low-Earth orbit (LEO) rendezvous scenario using Yamanaka-Ankersen equations for relative motion.

4. Numerical Results

The authors validated the framework using Monte Carlo simulations on a spacecraft rendezvous maneuver with cold-gas thrusters (discrete inputs: $\{-u_{max}, 0, u_{max}\}$).

• Discreteness of Solution:
  • In a high-resolution simulation ($N=1000$ grid points), the average distance of the control inputs to the discrete set was $\bar{d}(u) \approx 0.002$, confirming the control trajectory was effectively discrete-valued.
  • Visual inspection of the control inputs showed they snapped exactly to the admissible discrete values ($\pm u_{max}$ or $0$).
• Computational Performance:
  • Solver Time: Using a MacBook Air (M1 chip), the solver time was approximately 0.29 seconds for a 200-second horizon.
  • Real-Time Benchmark: In a Monte Carlo simulation of 1,000 random initial conditions with a 400-second horizon and $N=400$ grid points:
    • Mean solver time: 0.083 seconds.
    • Median solver time: 0.069 seconds.
    • All solver times were well below the 1-second target required by NASA's SPLICE project for real-time guidance updates.
• Grid Resolution Trade-off: Reducing grid points decreased computation time linearly while only slightly increasing the quantization error, which can be compensated via feedback control.

5. Significance

This work bridges a critical gap between theoretical optimal control and practical implementation for safety-critical systems:

• Eliminates MIP Complexity: It removes the need for computationally expensive Mixed-Integer solvers, which are often too slow for real-time autonomous vehicle or spacecraft control.
• Fuel Efficiency: It enables true fuel-optimal control (minimizing $L_1$-norm) for systems with discrete actuators, a capability previously difficult to achieve in real-time. Standard quadratic controllers often waste fuel because they do not directly minimize propellant usage.
• Safety-Critical Applications: The demonstrated sub-second computation times make this approach viable for autonomous rendezvous, docking, and landing missions where rapid re-planning is necessary.

In conclusion, the paper provides a rigorous mathematical framework and empirical evidence that lossless convexification is a viable, real-time solution for optimal control of linear systems with discrete inputs, provided specific geometric and normality conditions are met.