Convex Programming in FPTAS?

Question

Let us consider a very simple convex program of the form $$\mathsf{opt} = \inf_{\substack{Ax = b\\Cx\leq d}} f(x)$$ where $x\in\mathbb{R}^n$, $f$ is a (smooth enough) convex function, and $A$, $C$ are some constraint matrices and $b, d$ some vectors of appropriate dimensions, with rational entries (that way, they can be represented on a computer; we also assume $f$ can somehow be represented, e.g., if it is a convex quadratic function with rational coefficients etc). We also assume the problem is strictly feasible, so pretty much the best case scenario for interior-point methods (see Boyd & Vandenberghe, Chapter 11).

By construction, interior-point methods generate solutions that carry an additive error term, i.e., for $\delta > 0$ small enough they generate a point $x_{\delta}$ such that $$f(x_{\delta}) - \mathsf{opt} \leq \delta, \text{ such that } Ax_{\delta}=b \text{ and } \forall i, \; (Cx_{\delta})_i \leq d_i + \delta,$$ see also the summary on Wikipedia.

However, I am wondering whether such problems also admit an $\mathsf{FPTAS}$, as claimed on this post? For an algorithm $\verb|algo|$ to be a Fully Polynomial Time Approximation Scheme to $\mathsf{opt}$, it basically needs to satisfy $$\mathsf{opt} \leq \verb|algo| \leq (1+\varepsilon)\mathsf{opt}$$ for any $\varepsilon > 0$, where the runtime of $\verb|algo|$ must be polynomial w.r.t. the representation size of the instance, as well as $1/\varepsilon$.

Surely, this must be wrong, unless we assume that $\mathsf{opt} \geq 0$, since if the result is negative, the definition for $\mathsf{FPTAS}$ is ill-defined.

Did someone else already have to distinguish between a 'good enough in practice' additive error term, and an actual $\mathsf{FPTAS}$? Thank you very much in advance!

Answer 1

You are correct that the definition of FPTAS is ill-defined unless $\mathsf{opt} \geq 0$. Usually, when people are discussing an FPTAS it is in the context of a combinatorial problem where $\mathsf{opt} \geq 0$ either holds, or can be made to hold without loss of generality. If you have a lower bound for $f$ (at least on the feasible region), say L, then you can minimize the function $f(x) - L$. If you know that $\mathsf{opt} < 0$ then you can maximize the function $-f(x)$. Otherwise, you could ask that $|\mathsf{algo}-\mathsf{opt}| \leq \varepsilon|\mathsf{opt}|$ which aligns with the usual definition when $\mathsf{opt} \geq 0$.

Now let us address the distinction/connection between the additive error term seen in the analysis of interior-point methods, versus an FPTAS. First, I want to state for completeness that an algorithm with an additive error of $\varepsilon$ for any $\varepsilon > 0$ is stronger than an FPTAS (assuming the algorithm also has a running time that is polynomial in the input size and $1/\varepsilon$). Assuming $\mathsf{opt} \geq 1$, when given $\varepsilon > 0$ let $\delta = \varepsilon\mathsf{opt}$. Then find $x_\delta$ such that $f(x_\delta) - \mathsf{opt} \leq \delta = \varepsilon \mathsf{opt}$. Rearranging we get $f(x_\delta) \leq (1+\varepsilon) \mathsf{opt}$ as desired.

The reason I would not consider all convergent solvers to be FPTAS's (using the Wikipedia page's definition) is that the solutions returned by the solvers aren't necessarily feasible solutions. The constraints are allowed to be violated by $\varepsilon$. I imagine that under some "reasonable" assumptions, one could devise an algorithm to take the nearly feasible solution, and produce a feasible solution of similar cost. But I also suspect there are some pathological examples where you cannot.