Necessary and Sufficient Conditions for a Minimum

Directional derivatives can be used to provide simple necessary or sufficient conditions for a minimum [Demyanov [2009, propositions 8 and 10]].

Result: If $x$ is a local minimizer of $f$ then $\delta^-f(x,z)\geq 0$ and $d^-f(x,z)\geq 0$ for all directions $z$ . If $d^-f(x,z)>0$ for all $z\not= 0$ then $f$ has a strict local minimum at $x$ .

The special case of a quadratic deserves some separate study, because the quadratic model is so prevalent in optimization. So let us look at $f(x)=c+b'x+\frac12 x'Ax$ , with $A$ symmetric. Use the eigen-decomposition $A=K\Lambda K'$ to change variables to $\tilde x\mathop{=}\limits^{\Delta}K'x$ , also using $\tilde b\mathop{=}\limits^{\Delta}K'b$ . Then $f(\tilde x)=c+\tilde b'\tilde x+\frac12\tilde x'\Lambda\tilde x$ , which we can write as $\begin{align*} f(\tilde x)=\ &c-\frac12\sum_{i\in I_+\cup I_-}\frac{\tilde b_i^2}{\lambda_i}\\ &+\frac12\sum_{i\in I_+}|\lambda_i|(\tilde x_i+\frac{\tilde b_i}{\lambda_i})^2+\\ &-\frac12\sum_{i\in I_-}|\lambda_i|(\tilde x_i+\frac{\tilde b_i}{\lambda_i})^2+\\ &+\sum_{i\in I_0}\tilde b_i\tilde x_i. \end{align*}$ Here $\begin{align*} I_+&\mathop{=}\limits^{\Delta}\{i\mid\lambda_i>0\},\\ I_-&\mathop{=}\limits^{\Delta}\{i\mid\lambda_i<0\},\\ I_0&\mathop{=}\limits^{\Delta}\{i\mid\lambda_i=0\}. \end{align*}$

If $I_-$ is non-empty we have $\inf_x f(x)=-\infty$ .
If $I_-$ is empty, then $f$ attains its minimum if and only if $\tilde b_i=0$ for all $i\in I_0$ . Otherwise again $\inf_x f(x)=-\infty.$

If the minimum is attained, then $\min_x f(x) = c-\frac12 b'A^+b,$ with $A^+$ the Moore-Penrose inverse. And the minimum is attained if and only if $A$ is positive semi-definite and $(I-A^+A)b=0$ .