A Perspective-Based Convex Relaxation for Switched-Affine Optimal Control

Systems and Control Letters, 86:34–40, December 2015.

• Final paper

• Code

We consider the switched-affine optimal control problem, i.e., the problem of selecting a sequence of affine dynamics from a finite set in order to minimize a sum of convex functions of the system state. We develop a new reduction of this problem to a mixed-integer convex program (MICP), based on perspective functions. Relaxing the integer constraints of this MICP results in a convex optimization problem, whose optimal value is a lower bound on the original problem value. We show that this bound is at least as tight as a similar bound obtained from another well-known MICP reformulation (via conversion to a mixed logical dynamical system); our numerical study indicates it is often substantially tighter. Using simple integer-rounding techniques, we can also use our formulation to obtain an upper bound (and corresponding sequence of control inputs). In our numerical study, this bound was typically within a few percent of the optimal value, making it attractive as a standalone heuristic, or as a subroutine in a global algorithm such as branch and bound. We conclude with some extensions of our reformulation to problems with switching costs and piecewise-affine dynamics.