Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?

Question

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:

1. Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1976
2. Vazirani, Approximation Algorithms, 2004
3. Nocedal and Wright, Numerical Optimization, 2006, section 14.2
4. Boyd and Vanderberge, Convex Optimization, 2004, section 9.5

Answer 1

(I will take a shot at answering my own question.)

I believe the answer to the question posed in the title is, basically,

Yes.

When people say that convex programs are "polynomially solvable," they mean they are solvable in the sense that an FPTAS exists.

Linear programming

Even for "simple" convex programs such as linear programming, the existence of an exact, polynomial-time algorithm is still open, as described on Wikipedia. In particular,

• Simplex methods are exact (up to floating-point error), but all simplex methods so far have worst-case exponential runtime. (It is an open question whether a polynomial-time set of pivot rules exists.)
• Interior-point methods are, technically speaking, FPTASes. However, for reasons that appear to have more to do with convention than theory, it is not common to refer to them as such.

Wikipedia also names

Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?

as an important open problem.

Convex programming

Similar statements can be made about convex programming in general: Wikipedia says that

Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

The phrases "many classes" is doing a lot of work here; if we consider the minimization a convex function over convex inequality constraints (which is only a subset of convex programming problems, which also include conic constraints and other ways of characterizing convex sets) subject to regularity constraints, then we can show that (for example) gradient descent converges at a certain guaranteed rate. That is, these problems admit FPTASes. Again, the fact that we call these solutions "polynomial-time" algorithms is a bit sloppy, but it seems to capture the difference in difficulty between convex minimization and general nonlinear programming in a legible way.

Convex programs that are "truly" in P

Finally,

Are there any truly polynomial-time algorithms for convex minimization?

Yes, for some problems. Consider the least-squares problem

$$ \begin{align} \text{minimize}\quad & ||Ax - b||_2^2 \\ \text{subject to}\quad & Cx = d. \end{align} $$ The KKT conditions can be written as $$ \begin{bmatrix} A^T A & C^T \\ C & 0 \\ \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} = \begin{bmatrix} A^T b \\ d \end{bmatrix} $$ Assuming that $C$ has full row rank and $A$ has full column rank, the minimum is unique and can be obtained by solving this linear system using your favorite algorithm. Algorithms for solving linear systems have worst-case polynomial runtime in the matrix dimensions, and they produce a solution that is exact up to floating-point error.

Obviously, the set of convex programs that can be written in this form is very small relative to the set of convex programs overall.

Answer 2

There is an upper bound about some complexity of some kind interior-point method given by cvxbook in P589 Eq. (11.26), (11.27), where the tolerance appears in a constant \begin{equation} c = \log_2\log_2(1/\epsilon_{\mathrm{nt}}) \end{equation} It grows extremely slow with $\epsilon_{\mathrm{nt}}$ decreasing. This is known as quadratic convergence of Newton method afaik. My teacher of convex optimization told us many times like "six steps, six steps" on convex optimization classes. And Boyd has also made a joke about it: One time he was giving a talk about Newton method. He purposely replace the constant $c$ by digit $5$. An audience asked a question that where the $\epsilon$ goes at the last line. He answered that the digit $5$ is a symbol for $\log_2\log_2(1/\epsilon_{\mathrm{nt}})$. In my opinion it is an FPTAS, but the complexity grows so slowly about $\epsilon$ that pratically the effect of $\epsilon$ is omitted.