8
$\begingroup$

In many areas of application, one needs to solve a nonlinear system of equations $$ F(x) = 0. $$ Sometimes, the formulation $$ \|F(x)\|^2 \to\min $$ is used. Clearly, every solution $\hat{x}$ of $F(x)=0$ is also a solution of the second problem; the converse is also true (if a solution exists).

The question is if one can tell a-priori which formulation is better suited for a given problem. Have people worked on this before?


One example

Consider the function $$ F(x, y) = \begin{pmatrix} x^3 - 3x y^2 - 1\\ 3 x^2 y - y^3 \end{pmatrix}. $$ It has the three roots $x_1=(1,0)$ (green in the figure below), $x_2=(-0.5,\sqrt{3}/2)$ (blue), $x_3=(-0.5,-\sqrt{3}/2)$ (red). When applying Newton's method to $F$, the starting point will determine to which of the three solutions we converge.

enter image description here

The darker the color, the more Newton iterations were required. The typical Newton fractals appear.

When finding critial points $\nabla (\|F(x)\|^2) = 0$, again with Newton's method, the picture is a little different.

enter image description here

Note that the point $(0,0)$ is a critical point of $\|F(x)\|^2$, but no solution of $F(x)=0$.

This highlights one possible problem with the $\min$-formulation.

$\endgroup$
4
$\begingroup$

You used nice graphics in the question, but I think I answered the question fairly clearly in this answer, which contains another worked example.

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.

Feel free to refine your question if you meant to ask something more specific.

$\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.