4
$\begingroup$

I am curious of whether optimisation algorithms (whatever simplex, active-set quadratic programming, interior point sequential etc.) can fail due to numerical errors and how to avoid them. But I cannot find related literature online. It seems people mostly study the numerical stability of various matrix factorisation methods and solving partial differential equations. So my questions are, why there are not so many such research concerning iterative optimisation techniques? And would you please recommend some?

$\endgroup$
4
$\begingroup$

Most optimization algorithms are asked to converge to a tolerance that is far from machine precision, and a lot of them have a rate of convergence is slow enough that it is prohibitively expensive to ask for an answer correct to machine precision. So numerical roundoff just wouldn't affect them very much, compared to all the other sources of error.

Consider the difference with your other examples: numerical stability of various matrix factorizations is important because you want the answer correct to machine precision and you want the mathematical properties of the answer to be satisfied to machine precision too (e.g., after factorizing $A=LU$ you really would like to expect that $LU\approx A$). And so roundoff can seriously affect their usefulness when they are used as building blocks for other applications, such as numerical optimization.

Stability of methods for solving PDEs is not quite same sense of the word, it is more like the mathematical sense of not diverging exponentially due to perturbations, which may include roundoff errors, but includes just perturbations in general. (PDE methods also usually have rather coarse tolerances, not close to machine precision at all.) This isn't the same as for matrix factorizations: a numerically unstable method there could produce an inaccurate result due to accumulation of roundoff errors, even though there is a single answer that is not particularly sensitive to perturbations in the input data—such a method wouldn't even be backward stable.

$\endgroup$
  • $\begingroup$ Thanks for your answer! Would you please explain a bit more about "a lot of them have a rate of convergence is slow enough that it is prohibitively expensive to ask for an answer correct to machine precision."? $\endgroup$ – user112758 Sep 6 '17 at 0:22
  • 1
    $\begingroup$ @user112758 It depends on the method and the problem. If you think only of asymptotic rate of convergence of, say, Newton-type methods for a well-conditioned problem, then I think what I said is wrong and you can get to machine precision easily enough, but that's not the hard part for a reasonably nontrivial problem. And the challenge would have little to do with numerical stability. E.g., there is a collection of algorithms at ab-initio.mit.edu/wiki/index.php/NLopt_Algorithms. I'm a little unclear about what you're asking, do you have something specific in mind? $\endgroup$ – Kirill Sep 6 '17 at 1:03
  • $\begingroup$ @user112758 And it's somewhat uncommon to actually need the results to full machine precision, or have a sufficiently well-conditioned problem that getting such accuracy is at all feasible, so the extra effort might be wasted, so that depends on the problem too. $\endgroup$ – Kirill Sep 6 '17 at 1:09
  • $\begingroup$ thanks! I may need to investigate more on fully understand this. $\endgroup$ – user112758 Sep 12 '17 at 4:16
0
$\begingroup$

Let's take a look at the simplest case of optimizing a simple unconstrained convex quadratic function $\frac{1}{2} x^T H x - b^T x$. In this case, the optimization method is just a fancy word for solving the linear system of equations $H x = b$. It is well-known that solving such linear system of equation is not very stable if the condition number of the matrix $H$ blows up. And there is a lot of research on the stability of solving such linear system of equation.

This idea generalizes to the rest of the optimization methods that are fancier. The reason is that no matter how fancy the methods are, they are comprised of linear algebraic steps such as solving linear systems of equation. And therefore, they are as sensitive as those linear algebraic methods if not more.

If you want more rigorous results regarding the stability of the methods with respect to the errors in computing the iterates, you can look for the inexact version of those methods. For example, I just googled inexact interior point method and found this paper:https://link.springer.com/article/10.1023/A:1022663100715. You can do the same with other optimization methods of your choice. Note that the inexact method analysis usually assumes that you can find the iterates with a specific accuracy. But in practice, due to the linear algebraic problems, such as bad conditioning, that we talked about earlier, finding an iterate with a pre-specified accuracy might be challenging.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.