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?

  • 2
    $\begingroup$ 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). $\endgroup$ – Gamow Sep 7 '19 at 18:13
  • $\begingroup$ 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. $\endgroup$ – gradstudent Sep 7 '19 at 19:14
  • 1
    $\begingroup$ 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. $\endgroup$ – Kristoffer Arnsfelt Hansen Sep 9 '19 at 10:39
  • $\begingroup$ Yes. This is why this is my "Case 2" where I called LPs to be "exact" solvers. $\endgroup$ – gradstudent Sep 15 '19 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.