An efficient nonconvex reformulation of stagewise convex optimization problems
This work addresses scalability challenges for researchers and practitioners in fields like optimal control and neural network verification, though it is incremental as it builds on existing convex optimization methods.
The authors tackled the scalability issue of solving convex optimization problems with staged structure by developing a nonconvex reformulation with simple bound constraints, enabling efficient solution via projected gradient methods and achieving faster performance on large-scale neural network verification problems compared to existing solvers.
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.