Multivariable optimisation from the ground up
Lets say we want to find the maximum or minimum of a function $f(x,y)$. How do we do that, and how do we prove it? In the single variable case, we look at the derivative and then work out when that is equal to 0. Multidimensional stuff can be a little bit messier, so I want to work at it from the ground up. First lets assume that we have a stationary point, and for ease let that stationary point be $0$. The stationary point can just be found from partial first-derivatives. What we want to understand is how to tell if it is a minima, maxima, or something else. Let’s first work by expanding out $f$ to second order
$$ \begin{aligned} f(v_1,v_2) &\approx f(0,0) +v_1\cdot f_x(0,0) + v_2 \cdot f_y(0,0) \\&+ \frac{1}{2}v_1^2f_{xx}(0,0) + \frac{1}{2}v_1v_2f_{xy}(0,0) + \frac{1}{2}v_2v_1f_{yx}(0,0) + \frac{1}{2}v_2^2f_{yy}(0,0) + \dots. \end{aligned} $$But, because we are at a stationary point, $f_x(0,0)$ and $f_y(0,0)$ are equal to zero. We can then write latter part can be written more succinctly as
$$ f(\mathbf{v}) \approx f(0,0) + \frac{1}{2}\mathbf{v}^TH\mathbf{v} $$Where $H$ is the \textbf{Hessian} matrix. So far we have just manipulated an expansion, so now let’s look at the change in $f$
$$ \Delta f = f(\mathbf{v}) - f(0) \approx \frac{1}{2}\mathbf{v}^TH\mathbf{v}. $$Okay! This is the quadratic form involving $H$, the Hessian. So now lets find $\mathbf{v}$s which maximise and minimise $\mathbf{v}^TH\mathbf{v}$. Let’s first take the derivative
$$ D_\mathbf{v}(\mathbf{v}^TH\mathbf{v}) = 2H\mathbf{v}. $$Furthermore, to be able to compare our vectors $\mathbf{v}$, we will constrain them s.t. $||\mathbf{v}|| = 1$. This turns the problem into something amenable by Lagrange multipliers, and when phrased that way we get
$$ 2H\mathbf{v} = 2\lambda\mathbf{v} $$OMG! This is the eigenvalue equation. What does this tell us? The vectors $\mathbf{v}$ which maximise or minimise the quadratic form of the Hessian are its eigenvectors. Its eigenvalues are correspondingly the `steepness’ in that direction. Now from this we can infer some cool things. Firstly if both of the eigenvalues are positive, then the curvature is positive everywhere so the point is a minima, similarly if they are both negative, then it is a maxima. If they are of opposite sign, then we must be in a saddle point. The really neat thing here is that if we only wish to see if it is a saddle point or not, we don’t actually need to work out the eigenvectors and eigenvalues themselves. All we need to do is work out the \textbf{determinant of the Hessian}, as it is already equal to the product of the eigenvalues. If it is positive, then it is an extrema, if it is negative, it is a saddle point. We can work out which kind of extrema it is from just the individual partial derivatives. e.g. if $\det(H) > 0$ and $f_{xx} > 0$, then also $f_{yy}>0$ and so it is a minima.
>> Home