Motivating example
This question concerns continuous convex minimization. However, the motivating example is the classic binary knapsack problem $$\text{maximize}\quad v^T x \qquad \text{subject to}\quad w^T x \leq W, ~~x_i \in \{0, 1\}.$$ There is a well-known dynamic program that solves this problem in $O(Wn)$-time. This is called pseudopolynomial time, because it depends on the parameter $W$. The existence of this algorithm does not imply that knapsack is in P, because there is no reason to assume that $W$ is $O(p(n))$.[1]
There is also a well-known fully polynomial-time approximation scheme (FPTAS) for knapsack, which produces a $(1 - \varepsilon)$-optimal solution in $O(n / \varepsilon)$ time (I think). For a given $\varepsilon$, this algorithm's runtime is $O(p(n))$, but because the runtime is also polynomial in $1 / \varepsilon$, this algorithm does not amount to a proof that knapsack is in P.[2]
In general, we can prove that a problem is in P by providing a polynomial-time solution algorithm. But the examples above show us two common pitfalls in this approach:
The runtime cannot depend on the parameters of the problem.
→ If it does, then you have a pseudopolynomial-time algorithm.
The solution must be exact.
→ If the solution is $(1 - \varepsilon)$-optimal and the runtime is polynomial in $n$ and $1 /\varepsilon$, then you have an FPTAS.
Putative polynomial-time algorithms for convex minimization
Now, a common statement in convex optimization courses it that "convex optimization problems can be solved in polynomial time." But I think this statement needs to be qualified.
For linear programs (which are a type of convex optimization problem), the simplex method is known to be worst-case exponential time. Interior-point methods such as the ellipsoid method and Newton's method are often claimed to be polynomial time. But examining a convergence proof[3] reveals that the runtime depends on the permissible complementarity error $\varepsilon$. Therefore, it appears that these interior-point methods are actually FPTASes for linear programming.
Likewise, for convex minimization problems, even if we assume strong convexity, linearly independent constraint gradients, and Slater's regularity condition, the runtime of Newton's method depends on the condition number and Lipschitz constant of the objective Hessian.[4] So, if this convergence analysis is accurate, the Newton's method for convex minimization is actually psuedopolynomial-time because it depends on the function parameters.
My question
Are there any truly polynomial-time algorithms for convex minimization?
- That is, that produce an exact solution in runtime polynomial in the number of variables and constraints with no dependence on the condition number?
- If so, what regularity conditions do they require?
- I am interested in the theoretical properties of the algorithms rather than their practical efficacy.
There was a similar question on CS Theory SE but it doesn't consider the specific categories of pseudopolynomial-time algorithms and FPTASes.
References:
- Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1976
- Vazirani, Approximation Algorithms, 2004
- Nocedal and Wright, Numerical Optimization, 2006, section 14.2
- Boyd and Vanderberge, Convex Optimization, 2004, section 9.5