<p>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 <span class="math-container">$\epsilon &gt;0$</span> where <span class="math-container">$\epsilon$</span> 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. </p>

<p>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 <span class="math-container">$\epsilon$</span> is I guess the machine precision and not algorithmic. </p>

<ul>
<li><p>What is the mathematically rigorous way to distinguish between the above two situations? </p></li>
<li><p>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? </p></li>
</ul>

CC BY-SA 4.0
2019-09-07T18:13:31.723Z
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
CC BY-SA 4.0
2019-09-07T19:14:21.693Z
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
CC BY-SA 4.0
2019-09-09T10:39:30.103Z
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
CC BY-SA 4.0
2019-09-15T20:01:23.603Z
Yes. This is why this is my "Case 2" where I called LPs to be "exact" solvers.
gradstudent
<time-complexity><polynomial-time><convex-optimization>
When can convex optimization be considered to be exactly solvable?
gradstudent
# When can convex optimization be considered to be exactly solvable?

(Asked by: username_0 on 2019-09-07)

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?

**Tags:** time-complexity, polynomial-time, convex-optimization
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: Yes. This is why this is my "Case 2" where I called LPs to be "exact" solvers.  

---

## 0 answers

