  A robust-to-dynamics optimization (RDO) problem is an optimization problem
specified by two pieces of input: (i) a mathematical program (an objective
function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ and a feasible set
$\Omega\subseteq\mathbb{R}^n$), and (ii) a dynamical system (a map
$g:\mathbb{R}^n\rightarrow\mathbb{R}^n$). Its goal is to minimize $f$ over the
set $\mathcal{S}\subseteq\Omega$ of initial conditions that forever remain in
$\Omega$ under $g$. The focus of this paper is on the case where the
mathematical program is a linear program and the dynamical system is either a
known linear map, or an uncertain linear map that can change over time. In both
cases, we study a converging sequence of polyhedral outer approximations and
(lifted) spectrahedral inner approximations to $\mathcal{S}$. Our inner
approximations are optimized with respect to the objective function $f$ and
their semidefinite characterization -- which has a semidefinite constraint of
fixed size -- is obtained by applying polar duality to convex sets that are
invariant under (multiple) linear maps. We characterize three barriers that can
stop convergence of the outer approximations from being finite. We prove that
once these barriers are removed, our inner and outer approximating procedures
find an optimal solution and a certificate of optimality for the RDO problem in
a finite number of steps. Moreover, in the case where the dynamics are linear,
we show that this phenomenon occurs in a number of steps that can be computed
in time polynomial in the bit size of the input data. Our analysis also leads
to a polynomial-time algorithm for RDO instances where the spectral radius of
the linear map is bounded above by any constant less than one. Finally, in our
concluding section, we propose a broader research agenda for studying
optimization problems with dynamical systems constraints, of which RDO is a
special case.
