Proof

Let $\bold{u} \in \Re^N$ with $\bold{u} \neq 0$. For sufficiently small t we have

$$f(\bold{x}^* + t\bold{u})=f(\bold{x}^*) + t\nabla f(\bold{x}... ...\frac{t^2}{2}\bold{u}^T\nabla^2 f(\bold{x}^*)\bold{u} + o(t^2).$$

But $\nabla f(\bold{x}^*) = 0$ giving

$$f(\bold{x}^* + t\bold{u})=f(\bold{x}^*) + \frac{t^2}{2}\bold{u}^T\nabla^2 f(\bold{x}^*)\bold{u} + o(t^2).$$

If $\nabla^2 f(\bold{x}^*)$ is positive definite, its smallest eigenvalue $\lambda$ obeys $\lambda\gt$.So we have

$$f(\bold{x}^* + t\bold{u})- f(\bold{x}^*) \geq \frac{\lambda}{2}\parallel t\bold{u}\parallel^2 + o(t^2) \gt 0.$$

Then, $\bold{x}^*$ is a local minimizer for f.

We see that a sufficient condition for a local minimizer is $\nabla f(\bold{x}^*) = 0$ and $\nabla^2 f(\bold{x}^*)$ (Hessian) is positive definite. These conditions are very important and should guide us in the choice of an optimization strategy.

Quadratic functions form the basis for most of the algorithms in optimization, in particular for the quasi-Newton method detailed in this paper. It is then important to discuss some issues involved with these functions. Now, if we pose a quadratic objective function

$$f(\bold{x})=-\bold{x}^T\bold{b}+\frac{1}{2}\bold{x}^T\bold{H}\bold{x},$$

we see that we want to solve

$$\nabla f(\bold{x})= -\bold{b} + \bold{H}\bold{x}=0.$$

We may assume that the Hessian $\bold{H}$ is symmetric because

$$\bold{x^T}\bold{H}\bold{x}=\bold{x^T}\frac{\bold{H^T}+\bold{H}}{2}\bold{x}.$$

So, the unique global minimizer is the solution of the system above if $\bold{H}$ (the Hessian) is spd.