12
$\begingroup$

I asked for clarification about a recent question about minpack, and got the following comment:

Any system of equations is equivalent to an optimization problem, which is why Newton-based methods in optimization look a lot like Newton-based methods for solving systems of nonlinear equations.

What confuses me about this comment (and related negative opinions about specialized nonlinear least squares solvers like minpack) might be best explained on the example of the conjugate gradient method. This method is applicable to systems $Ax=b$ with a symmetric positive definite matrix $A$. It could also be used to solve the general least square problem $\operatorname{min}_x||Ax-b||^2$ for an arbitrary matrix $A$, but doing so is not recommended. One explanation why we shouldn't do this is that the condition number of the system would increase significantly.

But if turning a systems of equations into an optimization problem is considered problematic even for the linear case, why should it be less problematic for the general case? It seems to be somehow related to using a state of the art optimization algorithm, instead of using a slightly aged nonlinear least squares solver. But aren't the problems related to throwing away information and increasing the condition number of the system relatively independent of the actually used optimization algorithm?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

Since one of my answers has been cited, I'll try to clarify why I suggested using IPOPT instead of MINPACK.

My objections to using MINPACK have nothing to do with the algorithms that MINPACK uses and everything to do with their implementation. My main objection is that the software dates back to 1980, and was last updated in 1999. Jorge Moré is retired; I doubt he or any of the other authors of the software keep tabs on it anymore, and there's no team of people actively supporting it. The only documentation I can find on the software is the original, 1980 Argonne technical report written by Jorge Moré and the other MINPACK authors. (Chapters 1-3 can be found here, and Chapter 4 can be found here.) After searching the MINPACK source code and perusing the documentation (the PDFs are scanned images, and can't be searched), I don't see any options to accommodate constraints. Since the original poster of the nonlinear least-squares problem wanted to solve a constrained nonlinear least-squares problem, MINPACK won't even solve that problem.

If you look at the IPOPT mailing list, some users indicate that performance of the package on nonlinear least squares (NLS) problems is mixed relative to Levenberg-Marquardt algorithms and more specialized NLS algorithms (see here, here, and here). The performance of IPOPT relative to NLS algorithms, is, of course, problem dependent. Given that user feedback, IPOPT seems like a reasonable recommendation relative to NLS algorithms.

However, you make a good point that NLS algorithms should be investigated. I agree. I just think that a package more modern than MINPACK should be used because I believe it will perform better, be more usable, and be supported. Ceres seems like an interesting candidate package, but it can't handle constrained problems right now. TAO would work on box-constrained least-squares problems, although it doesn't implement the classic Levenberg-Marquardt, but instead implements a derivative-free algorithm. A derivative-free algorithm would probably work well for large-scale problems, but I wouldn't use it for small-scale problems. I couldn't find any other packages that inspired a great deal of confidence in their software engineering. For instance, GALAHAD doesn't seem to use version control or any automated testing, at first glance. MINPACK doesn't seem to do those things either. If you have experience with MINPACK or recommendations regarding better software, I'm all ears.

With all of that in mind, getting back to the quote of my comment:

Any system of equations is equivalent to an optimization problem, which is why Newton-based methods in optimization look a lot like Newton-based methods for solving systems of nonlinear equations.

A better comment is probably something to the effect of:

When we want to solve a system of $n$ equations with $n$ unknowns $g(x) = 0$, we can formulate this as a least squares optimization problem. (Paraphrase of last paragraph of p.102 of Nonlinear Programming, 2nd edition, by Dmitri Bertsekas.)

This statement holds even for solving systems of equations under constraints. I don't know of any algorithms that are considered "equation solvers" for the case where there are constraints on the variables. The common approach I know of, perhaps jaundiced by several semesters of optimization courses and research in an optimization lab, is to incorporate the constraints on the system of equations into an optimization formulation. If you were to try to use the constraints in a Newton-Raphson-like scheme for equation solving, you'd probably end up with a projected gradient or projected trust-region method, much like methods used in constrained optimization.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I do have experience with MINPACK. It's good enough as a local method. I like that it's stopping criteria work well without tweaking. I know that the thing with the constraints can be annoying, especially since it wouldn't be a major change to the algorithm itself. I even know of LM implementations that offer bounds on the variables and general linear constraints, but these implementations aren't much younger than MINPACK itself, and I haven't bothered to evaluate them. $\endgroup$
    – Thomas Klimpel
    Commented Jun 5, 2012 at 8:33
  • 1
    $\begingroup$ A couple nits: I have exactly the opposite perspective on derivative-free methods. Derivatives are the only "fast" way to explore a high-dimensional design space. If the design space is small, it is more affordable to skip derivatives, but the number of iterations necessarily grows as you increase the dimension. Also, semismooth Newton, active set methods, and monotone multigrid can be applied to variational inequalities, including nonsymmetric VIs. Finally, if you discard $g(x)=0$ and minimize $\lVert g(x) \rVert^2$, you no longer have a local measure by which to identify a global solution. $\endgroup$
    – Jed Brown
    Commented Jun 5, 2012 at 11:43
  • $\begingroup$ @JedBrown: I should change the language around. In my view, derivative-free optimization (DFO) is only preferable when function evaluations are very expensive. For some reason, the seminal case that comes to mind is when the objective involves solving a PDE, which is why I said "large-scale" (of course, for me, in optimization, "large-scale PDE" means something different than for you, who solves PDEs in parallel on a regular basis). When I think of "solving equations with constraints", the problem I have in mind is $g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$. (cont'd) $\endgroup$
    – Geoff Oxberry
    Commented Jun 5, 2012 at 23:08
  • $\begingroup$ @JedBrown: A standard way of tackling that problem is to solve $\min_{x \in S} \|g(x)\|^2$. There may be other ways, but I don't know of any. I'm not suggesting that one discard $g(x) = 0$; minima with nonzero objective function values clearly don't solve the system of equations being solved. In the nonconvex case, global optimization methods are necessary to certify the existence or nonexistence of solutions. I don't have a lot of experience with variational inequalities, so it's not immediately clear to me where VIs come into play here, especially since $S$ isn't necessarily a cone. $\endgroup$
    – Geoff Oxberry
    Commented Jun 5, 2012 at 23:14
  • 1
    $\begingroup$ So you still need to be able to precisely define what you mean by a solution that lies on the boundary of $S$. VIs, often written as a complementarity formulation, do exactly that. I have the opposite opinion regarding derivative-free, especially when the design space is large. If the objective involves an expensive PDE solve, I view that as a requirement that we have an adjoint so that we can use gradients to explore the design space. A PDE adjoint costs only a small multiple of a forward solve independent of the dimension of the space. This places extra requirements on model smoothness. $\endgroup$
    – Jed Brown
    Commented Jun 6, 2012 at 0:43
14
$\begingroup$

If a given nonlinear system is the first order optimality condition for an optimization problem, then we can often produce a more robust algorithm by using that information. For example, consider the equation

$$ f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$$

Plot of original objective

This clearly has a unique minimum and we expect our optimization method to find it regardless of starting point. But if we only look at the first order optimality conditions, we are looking for a solution $x$ of $\nabla f(x) = 0$ [Wolfram Alpha]

gradient

which has a unique solution, but many rootfinding methods can get stuck at the local minimum.

If we reformulate a new optimization problem to minimize the norm of the gradient squared, we are looking for a global minimum $x$ of $\lVert\nabla f(x)\rVert^2$ [Wolfram Alpha] which has multiple local minima.

enter image description here

To summarize, we started with an optimization problem that had a unique solution that we could guarantee that a method would find. We reformulated as a nonlinear root finding problem that had a unique solution that we could identify locally, but a rootfinding method (like Newton) might stagnate before reaching it. We then reformulated the root finding problem as an optimization problem that had multiple local solutions (no local measure can be used to identify that we are not at the global minimum).

In general, each time we convert a problem from optimization to rootfinding or vice-versa, we make the available methods and associated convergence guarantees weaker. The actual mechanics of the methods are often very similar so it is possible to reuse a lot of code between nonlinear solvers and optimization.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Jed, those WA links don't quite go to what you say they do. The parentheses are being ignored or improperly passed in the URL. $\endgroup$
    – Bill Barth
    Commented Jun 5, 2012 at 3:28
  • $\begingroup$ Strange, the links work for me. Could it depend on the web browser? Any suggestions for an alternative way to present this? $\endgroup$
    – Jed Brown
    Commented Jun 5, 2012 at 3:35
  • $\begingroup$ Not sure. Cutting and pasting the reformatted link from one tab to the next causes it to screw WA to screw it up again on its own! $\endgroup$
    – Bill Barth
    Commented Jun 5, 2012 at 3:48
  • $\begingroup$ Is anyone else having trouble with the links? I have tried in multiple browsers and it works fine in every case. $\endgroup$
    – Jed Brown
    Commented Jun 5, 2012 at 15:30
  • $\begingroup$ This is a nice answer. However, I decided to accept Geoff Oxberry's answer instead, because part of what I was trying to understand are the "real world" issues related to the question. This includes that people like me use and recommend MINPACK, despite knowing about its shortcomings, and that other people ask for advice about solving "trivially small" non-linear systems, but don't manage to test even a single solver over a three month time frame. $\endgroup$
    – Thomas Klimpel
    Commented Jun 9, 2012 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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