Polynomial-Time Approximation for Nonconvex Optimization Problems with an L1-Constraint

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.

complexity. Lenstra (and refinements by subsequent authors) [3,9,10,13,18] showed that the integer linear program (ILP) given by min{c ′ x | Ax ≤ b, x ∈ Z n } with c ∈ Q n , b ∈ Z m , and A ∈ Z m×n can be: (1) solved in polynomial time in the number of constraints m when the dimension n is fixed, and (2) solved in polynomial time in dimension n when the number of constraints m is fixed. A related result [20] shows the ILP given by min{c ′ x | Ax = b, x ∈ Z n + } with c ∈ Q n , b ∈ Z m , and A ∈ Z m×n can be solved in psuedopolynomial time when the number of constraints m is fixed. More recently, it has been shown that integer polynomial optimization min{p(x) | Ax ≤ b, x ∈ Z n }, where p(x) is a polynomial satisfying certain properties, can be approximately [6,12] or exactly [7] solved in polynomial time for fixed dimension n.
However, little is known about which other classes of integer programs can be solved in fixed-parameter polynomial time. This paper proves that nonlinear integer programs of the form can be solved in polynomial-time oracle complexity for fixed values of λ ∈ R + , where · 1 is the usual ℓ 1 -norm. Such constraints are common in integer programs: For instance, capacity constraints like {x : x ≥ 0, ∑ i x i ≤ λ } are equivalent to {x : If the functions f , g can be computed in polynomial time, such as linear or (possibly non-convex) quadratic functions, then our result implies (1) can be solved in polynomial (in simultaneously both the dimension n and number of constraints) time for fixed λ . This is in contrast to past algorithms [3,6,7,9,10,12,13,18] that only apply to integer programs with polynomial objective and linear constraints and (depending on the algorithm) are polynomial in either dimension (for fixed number of constraints) or number of constraints (for fixed dimension). Section 2 covers preliminaries, and Section 3 develops our algorithm to solve (1). We prove the number of integer-valued vectors in the scaled ℓ 1 -ball is upper-bounded by a polynomial in n using stochastic process theory, and this new result is used to show that our algorithm has polynomial complexity when applied to problems with (weighted) L1-constraints. Next, Section 4 gives an algorithm to compute a polynomial or exponential in n upper bound on the number of oracle operations required to solve a given integer program min{ f (x) | g(x) ≤ 0, x ∈ Z n } for when: g is a convex function that can be optimized in polynomial time, and the continuous relaxation of the feasible set {x : g(x) ≤ 0} is bounded. Section 5 presents a side result in which we provide an additive polynomial time approximation schemes (PTAS) for optimizing where f , g are Lipschitz: for all i and some κ ∈ R + . This generalizes results that give a PTAS for optimization of Lipschitz functions [4] or polynomials [5,15] over the continuous unit simplex.

Preliminaries
Let R n , Q n , Z n , and N n be the set of n-dimensional real-, rational-, integer-, and natural number-valued vectors, respectively, where the natural numbers are N = {0, 1, . . .}. Recall the usual inner product g, x = ∑ j g j x j , and let • be the Hadamard or elementwise product operator, such that z = x • y ⇐⇒ z i = x i · y i , ∀i ∈ [n]. We use the ℓ p norm notation: to be the unit ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls centered at the origin, respectively. For any λ ∈ R + and set K ⊂ R n , the scaled set is λ K : If K, D ⊂ R n are convex sets, then the covering number of K by copies of D is defined as the quantity where #V is the cardinality of the set V , and ⊕ denotes the Minkowski summation operator defined as A related value is the packing number of K by copies of D, which is defined as the quantity A basic inequality [2] relating these two quantities is P(K, 2D) ≤ N(K, D) ≤ P(K, D).

Polynomial-Time Solvability with a Bounded L1-Constraint
This section shows (1) can be solved in polynomial time for fixed λ . We use stochastic process theory and the theory of convex bodies in high-dimensional spaces to characterize the complexity of scaled ℓ p -balls, which we then use to upper bound the number of integers within scaled ℓ p -balls centered at the origin. Surprisingly, we find that the number of integers in the scaled ℓ 1 -ball is polynomial in dimension when the radius of the ball is fixed, which is in sharp contrast to the number of integers within the scaled ℓ ∞ -ball. We use this result to design an algorithm to solve (1), and we prove its polynomial-time complexity. Our algorithm is then generalized to integer programs with a weighted L1-constraint.

Characterizing the Integer Complexity of Lp-Balls
Covering numbers provide one useful measure of the complexity of a set in Euclidean space. Exactly determining covering numbers is difficult, but fortunately stochastic process theory provides several approaches for bounding the covering number. One approach is Sudakov's minoration [17,22,24], which relates the covering number of a symmetric convex set K to its Gaussian mean width:

Proposition 1 (Sudakov's Minoration [22])
Let K ⊂ R n be a symmetric convex set, and recall that N(K, rB 2 ) is the covering number of K by ℓ 2 -balls with radius r. We have the bound where g ∈ R n is a vector whose entries are iid Gaussian random variables with zero mean and unit variance.
Another useful approach is a basic volume-based inequality [24] for bounding the covering number; however, these bounds can be loose.

Proposition 2 (Volume Estimate of Covering Number [24])
For any symmetric convex sets K, D ⊂ R n we have .
When K/λ = D/r, this simplifies to ( λ r ) n ≤ N(λ K, rK) ≤ (2 + λ r ) n . The above approaches for bounding the covering number of a symmetric convex set can be used to derive bounds for the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls. Asymptotic bounds are found in [24], but we need non-asymptotic bounds for our purposes.

Proposition 3
Recall that λ B 1 , λ B 2 , and λ B ∞ are the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls centered at the origin and with radius λ . If r ≤ λ , then we have The upper bounds hold unconditionally, that is for all λ ≥ 0.
Proof Since λ B 1 is symmetric and convex, we can upper bound its covering number using the Sudakov minoration. The first step is to compute the Gaussian mean width, which is achieved by noting that Hölder's inequality and the symmetry of λ B 1 give where we have used the elementary bound max j |g j | ≤ √ 2 log n. Combining this with Sudakov's minoration (5) gives which simplifies to N(λ B 1 , rB 2 ) ≤ n (λ / √ 2r) 2 . The upper bound follows by noting The lower bound is given in [24], and the argument is that one copy of rB 2 is needed for each vertex of λ B 1 .
Bounds for the covering number of λ B ∞ follow from the simplified expression in Proposition 2 for the situation where An upper bound for the covering number of λ B 2 follows by noting

and a lower bound follows by noting
This says the number of ℓ ∞ -balls we need to cover an ℓ 1 -ball is polynomial in n for fixed λ /r. This is significant because in general (e.g., the ℓ ∞ -balls) covering an n-dimensional convex body requires an exponential in n number of balls.
The reason for our interest in covering numbers is that they can be used to count the number of integers within a convex set. In particular, we have the bounds: Proof The upper bound follows if we can show that two integer-valued vectors cannot lie within the same 1 2+δ B ∞ covering-ball. To prove this, suppose the opposite is true. Then there exists some point o such that u, v are two integer-valued vectors with The above result can be used to bound the number of integer-valued vectors within the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls.

Remark 3
The relevant outcome for our purposes is that #(λ B 1 ∩ Z n ) is polynomial in n when λ is fixed. As is well known, the above result says that #(λ B ∞ ∩ Z n ) is exponential in n. Our bounds for the ℓ 2 -ball are ambiguous, though we conjecture that #(λ B 2 ∩ Z n ) is exponential in n.
Remark 4 A simplified set of bounds for λ ≥ 1 implied by the above theorem are Algorithm 1 Solve L1-constrained integer programs To show ϕ is bijective, observe that it can be written as ϕ(u) = Mu − e 1 where M is a lower bidiagonal (square) matrix with 1 on the main diagonal and −1 on the diagonal below, and e 1 is a vector whose first entry is 1 and the remaining entries are 0. The matrix M can be seen to have full rank, and so ϕ must be bijective. The computational complexity follows because we perform one subtraction operation per entry of the result vector, which has dimension k. ⊓ ⊔ Theorem 2 Algorithm 1 solves (1) in O(n ((2+δ )⌊λ ⌋) 2 /2+1 ) oracle steps, for any δ ∈ (0, 1) and where computing f , g comprises a single oracle step.
Proof Recall that #(λ B 1 ∩ Z n ) ≤ n ((2+δ )⌊λ ⌋) 2 /2 by Corollary 1, the sets M ⌊λ ⌋+1 n , SignPerm(h) are of finite cardinality and such that each single combination can be computed in O(1) oracle time [16,23], and computing v requires O(n) oracle time by Lemma 1. Hence it suffices to show that Algorithm 1 will enumerate over every point x ∈ λ B 1 ∩ Z n exactly once. Let A be the set of points that are enumerated by Algorithm 1. Suppose x ∈ A then by the second inner loop this must mean that |x| ∈ A. Since |x| = ϕ(u) for some u ∈ M ⌊λ ⌋+1 n this means by Lemma 1 that ∑ n i=1 |x| i ≤ λ . Hence x ∈ λ B 1 ∩ Z n and A ⊆ λ B 1 ∩ Z n . Now suppose x ∈ λ B 1 ∩ Z n , then |x| ∈ λ B 1 ∩ N n . By Lemma 1, ϕ is bijective: Therefore, there exists a unique u ∈ M ⌊λ ⌋+1 n such that u = ϕ −1 0 (|x|). Since Algorithm 1 iterates over all u ∈ M ⌊λ ⌋+1 n , |x| must be generated by some iteration of the second inner loop. Hence λ B 1 ∩ Z n ⊆ A, and so A = λ B 1 ∩ Z n since we have shown both set inclusions. Note that since ϕ is a bijection and each permutation vector in SignPerm is distinct, this means each point cannot be enumerated more then once.
⊓ ⊔ Remark 5 A simplified result implied by the above theorem is that the oracle complexity is O(n 4λ 2 +1 ).

(Non-convex) Integer Quadratically-Constrained Quadratic Program (IQCQP):
If Proof Using the result of Theorem 2 it suffices to compute the time complexity of the oracle for f , g to determine the overall time complexity of each instance, which will result in the form O((P(n, m, s) + ns) · n ((2+δ )⌊λ ⌋) 2 /2 ), where P is a polynomial of n, m, s and O(ns) is the arithmetic complexity for generating each iteration by Lemma 1 and [16,23]. For ILP, since the dot product of two vectors in Q n can be computed in O(s 2 n) time and g is comprised of m constraints this means that the complexity f , g is of order O(s 2 mn) and hence the resulting complexity bound. For IQP, since resolving quadratic forms of matrices in Q n×n requires time complexity of O(s 2 n 2 ) we obtain that the complexity of evaluating f , g is of order O(s 2 mn 2 ). Likewise, for IQCQP the time complexity of resolving the quadratic constraints dominates the complexity of evaluating the objective function, hence the time complexity of resolving this oracle is O(s 2 mn 2 ). ⊓ ⊔ Remark 6 A simplified result from the above corollary is that the arithmetic complexity is: O(s 2 mn 4λ 2 +1 ) for ILP, and O(s 2 mn 4λ 2 +2 ) for IQP and IQCQP.

Algorithm for Solving Weighted L1-Constrained Integer Programs
The algorithm and analysis in the previous section easily generalize to the case of an integer program with a weighted L1-constraint: If we define the effective dimension n = ∑ i 1(w i ≤ λ ), the effective radius µ = λ /(min i w i ), and the effective decision variable y ∈ Z n with a bijection between the components of y and the non-zero components of x (i.e., x i such that w i ≤ λ ); then we can rewrite this problem as where M gives the bijection (i.e., x = My). We can then solve this problem by applying Algorithm 1, and similar results to Theorem 2 and Corollary 2 can be shown but with n and µ taking the place of n and λ .

Bounding the Running Time of a Given Integer Program
Here, we provide a polyomial-time algorithm to generate upper bounds on the number of oracle operations required to solve an integer program with a bounded feasible region and convex constraints g(x) that can be optimized in polynomial time. Let C = {x : g(x) ≤ 0} be the continuous relaxation for the feasible region of (16). Our algorithm is deterministic and provides bounds that are polynomial or exponential in dimension n. The trivial bound on complexity for when the feasible region lies within λ B ∞ is (1 + 2⌊λ ⌋) n (see Corollary 1), and our algorithm can potentially provide polynomial in n bounds for specific problem instances. Algorithm 2 describes our procedure. The intuition is that the algorithm finds a radius ρ such that ρB 1 covers C, and then bounds the oracle complexity using Theorem 2. When the feasible set C is nonnegative (i.e., C ⊂ R n + ), the minimum radius is readily computed by solving max x ∑ i x i g(x i ) ≤ 0 . When C is general (i.e., C ⊂ R n ), directly finding the minimum radius is difficult in this case. So the algorithm takes a different approach: It performs a change of variables x = u − v where u, v ≥ 0, computes bounds on u, v, and converts (16) into another instance of (16) with a nonnegative feasible region. The correctness and polynomial-time complexity of Algorithm 2 is given by the following result: Theorem 3 Suppose C ⊂ R n is bounded, and that g(x) can be optimized in polynomial time. Then Algorithm 2 runs in polynomial time, and the value bnd computed by the algorithm is an upper bound on the oracle complexity for solving (16).
Proof This algorithm runs in polynomial time because it consists of solving 2n + 1 convex optimization problems with at most 2n variables, each of which can be solved in polynomial time by assumption on g and the linearity of the objective functions. Next we prove that the value bnd provides an upper bound on the oracle complexity.
where the last equality holds since s,t ≥ 0. And l, u are constructed so that for all x ∈ C: if s = max{x, 0} and t = max{−x, 0}, then we have x = s − t with 0 ≤ s ≤ u and 0 ≤ t ≤ l. Hence we have max Thus C ∩ Z n ⊆ ρB 1 ∩ Z n for ρ as defined in the algorithm. This means we can solve (16) by using Algorithm 1 to solve (1) with ρ ≡ λ , and so the oracle complexity for solving (16) is bounded by the rate given in Theorem 2. ⊓ ⊔ Remark 7 When C lies in a single orthant, the value ρ is tight in the sense that Remark 8 Algorithm 2 can be modified to return simplified bounds by changing the last statement of the algorithm to "bnd := n 4ρ 2 +1 ".
The next proposition shows that our algorithm returns non-trivial bounds. More specifically, it returns polynomial bounds for some instances of (16) and exponential bounds for other instances of (16).
y − x ∞ ≤ ε/κ. Thus the set of all points x generated by the algorithm are the centers of (ε/κ)B ∞ copies that form a covering of λ B 1 .
⊓ ⊔ Remark 11 A simplified result implied by the above theorem for ε > 0 is that the oracle complexity is O(n 4(λ κ/ε) 2 +1 ) Remark 12 Algorithm 3 can be suitably modified, as in Section 3.3, to solve minimization problems with weighted L1-constraints.

Conclusion
Using a geometric argument based on stochastic process theory and the theory of convex bodies in high-dimensional spaces, we showed the number of integers within a scaled ℓ 1 -ball is polynomial in dimension when the radius of the ball is fixed. This result was used to develop an algorithm that solves L1-constrained integer programs and has oracle complexity that is polynomial in dimension when the radius of the L1-constraint is fixed. Our result implies polynomial (in both the dimension of the decision variables and constraints) arithmetic time complexity for instances of integer programming with fixed radius L1-constraints and polynomial-time computable objective function and constraints (e.g., problems where the objective and constraints are linear or quadratic). Next we used these results to develop a polynomial-time algorithm that generates polynomial or exponential in dimension bounds on the oracle complexity for solving integer programs with convex constraints, and an additive PTAS for continuous optimization of problems with Lipschitz objective and Lipschitz constraints intersected with an L1-constraint.