Linearization of Branin-system: meaning of eigenvalue analysis

63 Views Asked by At

We are interested in minimizing a function $f: \mathbb{R}^2 \mapsto \mathbb{R}$. The Branin-system for global optimization is the system:

$$\dot{x} = - [\nabla^2f(x)]^{-1} \nabla f(x).$$

In my problem this system has an equilibrium at $x=(0,0)$. After linearizing this system around the point $(0,0)$ I have: $$\dot{x} = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}x.$$

I found somewhere saying:

The eigenvalues of this system being $-1$ implies that the point $(0,0)$ is "locally attractive".

I don't get what is locally attractive. Does this mean this point is a good candidate for being the global optimum since it is, e.g., a local minimum? If yes, I would love to learn what is the relationship between the eigenvalues of the linearization versus its optimality.

Similarly, if I consider the modified Branin-system, the linear approximation of form: $$\dot{x} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}x.$$ and it is being said to be "unstable", again I am lost.

1

There are 1 best solutions below

4
On BEST ANSWER

Your sources appear to be looking at your differential equation from the perspective of dynamical-systems theory. It distinguishes two important types of equilibria (also called fixed points):

  • A stable equilibrium is an equilibrium to which initial conditions in the vicinity converge. You can think of a ball in rest in the lowermost point of a basin. If you slightly move the ball, it will roll down back to the lowermost point of the basin. Such an equilibrium is also called attractor (because it attracts states in its vicinity). The number of points attracted to an equilibrium are called its basin of attraction.

  • An unstable equilibrium is one to which almost none of the initial conditions in the vicinity converge. You can think of a ball balanced at rest at the top of a hill. If you slightly move the ball or give it a slight push, it will roll off the hill.

Mathematically, you can determine the stability of equilibria by linearising the dynamics in their vicinity. If your differential equation is $\dot{x} = g(x)$, you look at the Jacobian of $g$ (at the equilibrium). If the real parts of all eigenvalues are negative, the equilibrium is stable/attractive. If at least one real part of an eigenvalue is positive, the equilibrium is unstable.

If you are considering an iterative optimisation algorithm as a dynamical system, equilibria correspond to solutions of some necessary condition. However, the algorithm can only converge to a stable equilibrium, while it moves away from unstable equilibria. For example, the equilibria for gradient-based minimisers are local minima and maxima, with the minima being stable and the maxima being unstable. If you want to find global minima, the problem arises that you may have multiple basins of attraction. This is where basin hopping and similar techniques come into play.