Saddle Point Proof Suppose that a real-valued function, $f$, has continuous second order partial derivatives and let $x$ be a point at which $\nabla f(x) = 0.$ Assume also that there are points $u$ and $v$ such that $\langle \nabla ^2f(x)u,u\rangle > 0$ and $\langle \nabla ^2f(x)v,v\rangle < 0$. Show that $x$ is neither a local maximum or minimum of $f$. 
I'm sure that $x$ is a saddle point, but I'm unsure how to show this. Do I show that the Hessian matrix is neither positive definite nor negative definite? 
 A: From the given information you know that $Hf$ has at least one positive and one negative eigenvalue (it cannot be positive- or negative-semidefinite.) That is enough to show that a critical point is a saddle point, if you've learned about that result already.
Otherwise, you can also prove the statement directly. Consider the curve $\gamma(t) = x + ut$. Then $$\frac{d}{dt} f(\gamma(t)) = u\cdot \nabla f(\gamma)$$ 
and 
$$\frac{d^2}{dt^2}f(\gamma(t)) = u^T Hf(\gamma) u.$$
Since $u^THf(x)u>0$ and is continuous, there exists an $\delta > 0$ with $u^THf(\gamma[t])u>0$ for $|t| < \delta$. Then
$$u\cdot \nabla f(\gamma[t]) = u\cdot \nabla f(\gamma[t]) - u\cdot \nabla f(\gamma(0) = \int_0^t u^THf(\gamma[s])u\,ds > 0$$
for $0 < t < \delta$. And then
$$f(\gamma(t))-f(\gamma(0)) = \int_0^t u\cdot\nabla f(\gamma[s])\,ds > 0$$
for $0 < t < \delta$, and so $x$ is not a local maximum. An identical argument holds for $v$.
A: All this sort of optimization relies on is Taylor's expansion. That is the workhorse.
First consider the expansion of $f$ about $x$ in the direction $u$:
\begin{align*}
  f(x + \lambda u) - f(x) & =
  \lambda \nabla f(x)^T u +
  \tfrac{1}{2} \lambda^2 u^T \nabla^2 f(x) u + o(\|\lambda u\|^2) \\ & =
  \tfrac{1}{2} \lambda^2 u^T \nabla^2 f(x) u + o(\|\lambda u\|^2)
\end{align*}
for all $\lambda \in \mathbb{R}$. Choose $\lambda \neq 0$ and divide by $\lambda^2 \|u\|^2$:
$$
\frac{f(x + \lambda u) - f(x)}{\lambda^2 \|u\|^2} =
\tfrac{1}{2} \frac{u^T}{\|u\|} \nabla^2 f(x) \frac{u}{\|u\|} + o(1).
$$
Because the first term on the right-hand side is fixed and positive, the left-hand side is also positive for all sufficiently small values of $|\lambda|$, since the remainder is a term that converges to zero as $|\lambda| \to 0$. But because the denominator on the left-hand side is positive, this means that the numerator must be positive. This shows that for all sufficiently small $|\lambda| \neq 0$,
$$
 f(x + \lambda u) > f(x).
$$
Formally, there is a threshold $\lambda_{\min}$ such that for all $|\lambda| \in (0,\lambda_{\min})$, the left-hand side is larger than
$$
\mathbf{\tfrac{1}{4}} \frac{u^T}{\|u\|} \nabla^2 f(x) \frac{u}{\|u\|}
$$
(note the factor $1/4$).
Similarly, you can show that for all sufficiently small $|\lambda| \neq 0$,
$$
 f(x + \lambda v) < f(x).
$$
Therefore, any ball centered at $x$ contains points $y$ and $z$ such that $f(x) < f(y)$ and $f(x) > f(z)$, so $x$ cannot be a local minimizer. It cannot be a local maximizer either. In fact, we have proved that the definition of a saddle point is verified.
