  Nonconvex optimization problems with an L1-constraint are ubiquitous, and are
found in many application domains including: optimal control of hybrid systems,
machine learning and statistics, and operations research. This paper shows that
nonconvex optimization problems with an L1-constraint can be approximately
solved in polynomial time. We first show that nonlinear integer programs with
an L1-constraint can be solved in a number of oracle steps that is polynomial
in the dimension of the decision variable, for each fixed radius of the
L1-constraint. When specialized to polynomial integer programs, our result
shows that such problems have a time complexity that is polynomial in
simultaneously both the dimension of the decision variables and number of
constraints, for each fixed radius of the L1-constraint. We prove this result
using a geometric argument that leverages ideas from stochastic process theory
and from the theory of convex bodies in high-dimensional spaces. We conclude by
providing an additive polynomial time approximation scheme (PTAS) for
continuous optimization of Lipschitz functions subject to Lipschitz constraints
intersected with an L1-constraint, and we sketch a generalization to
mixed-integer optimization.
