  Convex optimization problems with staged structure appear in several
contexts, including optimal control, verification of deep neural networks, and
isotonic regression. Off-the-shelf solvers can solve these problems but may
scale poorly. We develop a nonconvex reformulation designed to exploit this
staged structure. Our reformulation has only simple bound constraints, enabling
solution via projected gradient methods and their accelerated variants. The
method automatically generates a sequence of primal and dual feasible solutions
to the original convex problem, making optimality certification easy. We
establish theoretical properties of the nonconvex formulation, showing that it
is (almost) free of spurious local minima and has the same global optimum as
the convex problem. We modify PGD to avoid spurious local minimizers so it
always converges to the global minimizer. For neural network verification, our
approach obtains small duality gaps in only a few gradient steps. Consequently,
it can quickly solve large-scale verification problems faster than both
off-the-shelf and specialized solvers.
