Brendan Gould

Brendan Gould, Akash Harapanahalli, Samuel Coogan

We present linrax, the first simplex based linear program (LP) solver compatible with the JAX ecosystem. In many control algorithms, LPs are often automatically generated and frequently solved either offline or online in the control loop. This motivates the design of linrax, which is especially suited for compilation into a complex JAX-based pipeline as a subroutine. We discuss the challenges associated with implementing a general purpose LP solver under strict design requirements from JAX. Notably, we can solve general problems which may include dependent constraints-something not possible with existing JAX-compatible LP solvers that use first-order techniques and may fail to converge. We demonstrate the utility of linrax through several examples, including a robust control synthesis pipeline for a nonlinear vehicle model using automatic differentiation through a LP-based reachable set framework.

Brendan Gould, Chih-Yuan Chiu, Antoine P. Leeman et al.

We study the set of solutions to a parameterized, strongly convex optimization problem whose cost depends on uncertain, bounded parameters. We compute a certified outer approximation of the corresponding set of optimizers, using convergence properties of the projected gradient descent (PGD) algorithm for convex programs. Concretely, by treating the cost parameter as constant but unknown, we interpret the PGD iterates as an uncertain dynamical system and analyze its forward reachable sets. Since PGD converges exponentially to the unique optimizer for each fixed parameter, these reachable sets provide outer approximations of the optimizer set, with an explicit error bound that decays exponentially with the iteration count. We apply system-level synthesis (SLS) on the PGD dynamics to optimize the step-size sequence and obtain reachable-set over-approximations. Our method outperforms existing baselines in over-approximating, with low conservativeness, the minimizer sets of convex programs with uncertain costs and high-dimensional decision variables.