# When can convex optimization be considered to be exactly solvable?

If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $$\epsilon >0$$ where $$\epsilon$$ measures the accuracy of the solution. Here apart from the error coming due to the finiteness of the run-time we are also getting an error from the machine precision.

But I guess this is not the situation when say one is using an LP solver to solve a LP which we can consider to be giving us an exact" answer in polynomial time. Such solvers would typically use some pivoting rule based simplex method. Here the only source of $$\epsilon$$ is I guess the machine precision and not algorithmic.

• What is the mathematically rigorous way to distinguish between the above two situations?

• If we were to say use gradient descent to solve a LP then can there be a sense in which we could say that it might work "faster" than calling a LP solver?

• As soon as you move away from linear functions, you may run into optima with irrational coordinates and hence need the $\epsilon$. Consider for instance the problem of minimizing $f(x)=x^2-2$ subject to the constraint $f(x)\ge0$ (where $x$ is a real variable). – Gamow Sep 7 '19 at 18:13
• Yes. And since this is not a LP this is like my case 1 where the error has 2 different sources, the finite precision arithmetic and the finiteness of the run-time. So this is conceptually different from LP's error - and I do not know how to say this rigorously. – gradstudent Sep 7 '19 at 19:14
• When using interior point algorithms for solving LPs, it it well-known that once a sufficiently good approximation to an optimal solution has been computed, one may "round" the approximation to an optimal basic feasible solution. – Kristoffer Arnsfelt Hansen Sep 9 '19 at 10:39
• Yes. This is why this is my "Case 2" where I called LPs to be "exact" solvers. – gradstudent Sep 15 '19 at 20:01