1 Mathematical Preliminaries
This section recalls the regularity assumptions and the first- and second-order Taylor expansions used later in constrained optimization.
Throughout these notes, the gradient of a scalar-valued function is a row vector:
\nabla f(\bm x) =\begin{bmatrix} \partial_{x_1}f(\bm x)&\cdots&\partial_{x_n}f(\bm x) \end{bmatrix}\in\mathbb R^{1\times n}.
Vectors such as \bm s,\bm d\in\mathbb R^n are column vectors. Consequently,
\nabla f(\bm x)\,\bm s\in\mathbb R,
and no transpose of the gradient is needed. The Hessian \nabla^2f(\bm x)\in\mathbb R^{n\times n} has the usual entries [\nabla^2f]_{ij}=\partial^2 f/(\partial x_i\partial x_j).
1.1 Taylor expansions and regularity
Definition 1.1 (First-order expansion: differentiability is enough) A function f:\mathbb R^n\to\mathbb R is Fréchet differentiable at \bm x if there exists a row vector \nabla f(\bm x)\in\mathbb R^{1\times n} such that
f(\bm x+\bm s) =f(\bm x)+\nabla f(\bm x)\,\bm s+r_1(\bm s),
where
\lim_{\bm s\to\bm0} \frac{|r_1(\bm s)|}{\|\bm s\|}=0.
Thus the first-order Taylor expansion is
\boxed{ f(\bm x+\bm s) =f(\bm x)+\nabla f(\bm x)\bm s+o(\|\bm s\|). } \tag{1.1}
Thus the first-order expansion with a little-o remainder requires only differentiability at the expansion point. The stronger assumption f\in C^1 in a neighborhood of \bm x is sufficient, but not necessary.
Restriction to a fixed direction
Let \bm s=t\bm d, where \bm d is fixed. From Equation 1.1,
f(\bm x+t\bm d) =f(\bm x)+t\,\nabla f(\bm x)\bm d+r_1(t\bm d).
Moreover,
\frac{|r_1(t\bm d)|}{|t|} = \frac{|r_1(t\bm d)|}{\|t\bm d\|}\,\|\bm d\| \longrightarrow0, \qquad t\to0,
and therefore
\boxed{ f(\bm x+t\bm d) =f(\bm x)+t\,\nabla f(\bm x)\bm d+o(|t|). }
If one considers only t\downarrow0, the remainder is usually written simply as o(t).
1.2 Quantitative first-order remainder for a Lipschitz gradient
Assume that f is differentiable on an open convex neighborhood U of \bm x and that its gradient is Lipschitz continuous there: for some L>0,
\|\nabla f(\bm u)-\nabla f(\bm v)\| \le L\|\bm u-\bm v\|, \qquad \bm u,\bm v\in U. \tag{1.2}
For every \bm s such that the segment \{\bm x+t\bm s:0\le t\le1\} is contained in U,
\boxed{ \left| f(\bm x+\bm s)-f(\bm x)-\nabla f(\bm x)\bm s \right| \le \frac L2\|\bm s\|^2. } \tag{1.3}
Consequently,
f(\bm x+\bm s) =f(\bm x)+\nabla f(\bm x)\bm s+O(\|\bm s\|^2).
Proof
Define the scalar function
\phi(t):=f(\bm x+t\bm s),\qquad 0\le t\le1.
Since a Lipschitz gradient is continuous, \phi\in C^1([0,1]), and the chain rule gives
\phi'(t)=\nabla f(\bm x+t\bm s)\bm s.
By the fundamental theorem of calculus,
\begin{aligned} f(\bm x+\bm s)-f(\bm x) &=\phi(1)-\phi(0)\\ &=\int_0^1\nabla f(\bm x+t\bm s)\bm s\,dt. \end{aligned}
Subtracting \nabla f(\bm x)\bm s yields
R_1(\bm s) = \int_0^1 \bigl[\nabla f(\bm x+t\bm s)-\nabla f(\bm x)\bigr]\bm s\,dt.
Using Cauchy–Schwarz (equivalently, the induced Euclidean operator norm) and Equation 1.2,
\begin{aligned} |R_1(\bm s)| &\le \int_0^1 \|\nabla f(\bm x+t\bm s)-\nabla f(\bm x)\|\,\|\bm s\|\,dt\\ &\le \int_0^1 Lt\|\bm s\|^2\,dt =\frac L2\|\bm s\|^2. \end{aligned}
This proves Equation 1.3.
Definition 1.2 (Second-order expansion under C^2 regularity) Assume that f\in C^2(U) on an open neighborhood U of \bm x. Then
\boxed{ f(\bm x+\bm s) = f(\bm x) +\nabla f(\bm x)\bm s +\frac12\bm s^T\nabla^2f(\bm x)\bm s +o(\|\bm s\|^2). } \tag{1.4}
In particular, for \bm s=t\bm d,
f(\bm x+t\bm d) = f(\bm x) +t\nabla f(\bm x)\bm d +\frac{t^2}{2}\bm d^T\nabla^2f(\bm x)\bm d +o(t^2).
Proof
Again set
\phi(t)=f(\bm x+t\bm s),\qquad 0\le t\le1.
For \bm s sufficiently small the entire segment is contained in U. Because f\in C^2(U),
\phi'(t)=\nabla f(\bm x+t\bm s)\bm s, \qquad \phi''(t)=\bm s^T\nabla^2 f(\bm x+t\bm s)\bm s.
Applying the fundamental theorem of calculus twice gives the integral form of Taylor’s formula,
\phi(1) = \phi(0)+\phi'(0) + \int_0^1(1-t)\phi''(t)\,dt. \tag{1.5}
Hence
f(\bm x+\bm s) ={}f(\bm x)+\nabla f(\bm x)\bm s +\int_0^1(1-t) \bm s^T\nabla^2f(\bm x+t\bm s)\bm s\,dt.
Add and subtract the Hessian at \bm x. Since \int_0^1(1-t)dt=1/2,
\begin{aligned} f(\bm x+\bm s) ={}&f(\bm x)+\nabla f(\bm x)\bm s +\frac12\bm s^T\nabla^2f(\bm x)\bm s +R_2(\bm s),\\ R_2(\bm s) ={}&\int_0^1(1-t)\bm s^T \bigl[\nabla^2f(\bm x+t\bm s)-\nabla^2f(\bm x)\bigr] \bm s\,dt. \end{aligned} \tag{1.6}
Therefore
\frac{|R_2(\bm s)|}{\|\bm s\|^2} \le \int_0^1(1-t) \left\|\nabla^2f(\bm x+t\bm s)-\nabla^2f(\bm x)\right\|_2dt.
Continuity of \nabla^2 f at \bm x implies that the right-hand side tends to zero as \bm s\to\bm0. Thus R_2(\bm s)=o(\|\bm s\|^2), proving Equation 1.4.
The proof shows that Lipschitz continuity of the Hessian is not required for the little-o second-order remainder; continuity of the Hessian at the expansion point is sufficient.
1.3 Cubic remainder for a Lipschitz Hessian
Assume in addition that the Hessian is Lipschitz continuous on a neighborhood of \bm x: there exists L_H>0 such that
\|\nabla^2f(\bm u)-\nabla^2f(\bm v)\|_2 \le L_H\|\bm u-\bm v\|.
Then the remainder in Equation 1.4 satisfies the sharper bound
\boxed{ |R_2(\bm s)| \le \frac{L_H}{6}\|\bm s\|^3. } \tag{1.7}
Consequently,
f(\bm x+\bm s) = f(\bm x)+\nabla f(\bm x)\bm s +\frac12\bm s^T\nabla^2f(\bm x)\bm s +O(\|\bm s\|^3).
Proof
Starting from Equation 1.6,
\begin{aligned} |R_2(\bm s)| &\le \int_0^1(1-t)\|\bm s\|^2 \|\nabla^2f(\bm x+t\bm s)-\nabla^2f(\bm x)\|_2\,dt\\ &\le L_H\|\bm s\|^3\int_0^1t(1-t)\,dt\\ &=\frac{L_H}{6}\|\bm s\|^3. \end{aligned}
1.4 Global and local minima
For \bm a\in\mathbb R^n and \delta>0, the open Euclidean ball with center \bm a and radius \delta is
B(\bm a,\delta) :=\{\bm x\in\mathbb R^n:\|\bm x-\bm a\|_2<\delta\}, \qquad \|\bm v\|_2=\sqrt{\sum_{i=1}^n v_i^2}.
The corresponding closed ball is \overline B(\bm a,\delta)=\{\bm x:\|\bm x-\bm a\|_2\le\delta\}. For a function defined on D\subseteq\mathbb R^n, the definitions below use B(\bm a,\delta)\cap D; the unconstrained first-order conditions require an interior point of D.
A point \bm{x}^\star\in\mathbb R^n is a global minimum of f:\mathbb R^n\to\mathbb R if
f(\bm{x}^\star)\le f(\bm{x}) \qquad\forall\bm{x}\in\mathbb R^n.
A point \bm{x}^\star is a local minimum if there exists \delta>0 such that
f(\bm{x}^\star)\le f(\bm{x}) \qquad \forall\bm{x}\in B(\bm{x}^\star,\delta).
It is a strict local minimum if, for some \delta>0,
f(\bm{x}^\star)<f(\bm{x}) \qquad \forall\bm{x}\in B(\bm{x}^\star,\delta)\setminus\{\bm{x}^\star\}.
1.5 Conditions for an unconstrained local minimum
First-order necessary condition
If f is differentiable at an interior local minimizer \bm{x}^\star, then
\boxed{\nabla f(\bm{x}^\star)=\bm0.}
Proof
Because \bm{x}^\star is an interior point, for every fixed direction \bm d\in\mathbb R^n there exists \varepsilon>0 such that \bm{x}^\star+t\bm d belongs to the domain for all |t|<\varepsilon. Since \bm{x}^\star is a local minimum,
f(\bm{x}^\star+t\bm d)-f(\bm{x}^\star)\ge0
for all sufficiently small positive and negative t. Differentiability at \bm{x}^\star gives
f(\bm{x}^\star+t\bm d)-f(\bm{x}^\star) = t\nabla f(\bm{x}^\star)\bm d+o(|t|).
For t>0, division by t and passage to the limit t\downarrow0 yield
\nabla f(\bm{x}^\star)\bm d\ge0.
For t<0, division by the negative number t reverses the inequality; letting t\uparrow0 gives
\nabla f(\bm{x}^\star)\bm d\le0.
Hence
\nabla f(\bm{x}^\star)\bm d=0 \qquad\forall\bm d\in\mathbb R^n.
The only row vector whose product with every column vector \bm d is zero is the zero row vector. Therefore
\nabla f(\bm{x}^\star)=\bm0.
This condition is necessary but not sufficient: a stationary point may be a minimum, a maximum, or a saddle point.
Symmetric matrices and quadratic forms
Let \bm{A}=\bm{A}^T\in\mathbb R^{n\times n}. Its quadratic form is Q_{\bm{A}}(\bm d)=\bm d^T\bm{A}\bm d. We say that \bm{A} is
- positive definite (\bm{A}\succ0) if \bm d^T\bm{A}\bm d>0 for every \bm d\ne\bm0;
- positive semidefinite (\bm{A}\succeq0) if \bm d^T\bm{A}\bm d\ge0 for every \bm d;
- negative definite (\bm{A}\prec0) if \bm d^T\bm{A}\bm d<0 for every \bm d\ne\bm0;
- negative semidefinite (\bm{A}\preceq0) if \bm d^T\bm{A}\bm d\le0 for every \bm d;
- indefinite if there exist \bm u,\bm v with \bm u^T\bm{A}\bm u>0 and \bm v^T\bm{A}\bm v<0.
For symmetric matrices, positive (semi)definiteness is equivalent to all eigenvalues being strictly positive (nonnegative), respectively.
Rayleigh quotient and eigenvalue bounds
For a real symmetric matrix \bm{A}, define its Rayleigh quotient by
\mathcal R_{\bm{A}}(\bm d)=\frac{\bm d^T\bm{A}\bm d}{\bm d^T\bm d}, \qquad \bm d\in\mathbb R^n\setminus\{\bm0\}.
Theorem (Rayleigh–Ritz). If the eigenvalues of \bm{A}=\bm{A}^T are \lambda_1\le\cdots\le\lambda_n, then
\boxed{\lambda_1\le\mathcal R_{\bm{A}}(\bm d)\le\lambda_n} \quad(\bm d\ne\bm0), \qquad \min_{\bm d\ne\bm0}\mathcal R_{\bm{A}}(\bm d)=\lambda_1, \quad \max_{\bm d\ne\bm0}\mathcal R_{\bm{A}}(\bm d)=\lambda_n.
Proof. By the spectral theorem, \bm{A}=U\operatorname{diag}(\lambda_1,\ldots,\lambda_n)U^T with U^TU=\bm{I}. Setting \bm z=U^T\bm d gives
\mathcal R_{\bm{A}}(\bm d) =\frac{\sum_{i=1}^n\lambda_i z_i^2}{\sum_{i=1}^n z_i^2} =\sum_{i=1}^n w_i\lambda_i, \qquad w_i=\frac{z_i^2}{\|\bm z\|_2^2}\ge0, \quad\sum_iw_i=1.
Thus the quotient is a convex combination of the eigenvalues. The bounds are attained at eigenvectors for \lambda_1 and \lambda_n. In particular, \lambda_1\|\bm d\|_2^2\le\bm d^T\bm{A}\bm d \le\lambda_n\|\bm d\|_2^2.
Second-order necessary condition
Assume f\in C^2 in a neighborhood of \bm{x}^\star. If \bm{x}^\star is a local minimum, then
\boxed{ \bm d^T\nabla^2 f(\bm{x}^\star)\bm d\ge0 \qquad\forall\bm d\in\mathbb R^n. }
Equivalently, the Hessian \nabla^2f(\bm{x}^\star) is positive semidefinite.
Proof
By the first-order necessary condition,
\nabla f(\bm{x}^\star)=\bm0.
Fix any \bm d\in\mathbb R^n. The second-order Taylor expansion along \bm d gives
f(\bm{x}^\star+t\bm d)-f(\bm{x}^\star) = \frac{t^2}{2} \bm d^T\nabla^2f(\bm{x}^\star)\bm d +o(t^2).
Since \bm{x}^\star is a local minimum, the left-hand side is nonnegative for all sufficiently small t. For t\ne0, divide by t^2/2>0:
\bm d^T\nabla^2f(\bm{x}^\star)\bm d + \frac{2o(t^2)}{t^2} \ge0.
Letting t\to0 gives
\bm d^T\nabla^2f(\bm{x}^\star)\bm d\ge0.
Because \bm d was arbitrary, the Hessian is positive semidefinite.
An equivalent contradiction argument is useful to keep in mind: if some \bm d satisfied \bm d^T\nabla^2f(\bm{x}^\star)\bm d<0, then the negative quadratic term would dominate the o(t^2) remainder for all sufficiently small nonzero t, producing values strictly below f(\bm{x}^\star).
Second-order sufficient condition
Assume f\in C^2 in a neighborhood of \bm{x}^\star, and suppose
\nabla f(\bm{x}^\star)=\bm0.
If
\boxed{ \bm d^T\nabla^2f(\bm{x}^\star)\bm d>0 \qquad\forall\bm d\ne\bm0, }
then \bm{x}^\star is a strict local minimum. For a real symmetric Hessian, this is equivalent to all eigenvalues being strictly positive.
Proof
Let
\bm{H}:=\nabla^2f(\bm{x}^\star).
Since f\in C^2, the Hessian is symmetric. Positive definiteness therefore implies that its smallest eigenvalue is strictly positive. Denote it by \lambda_{\min}>0. By the Rayleigh quotient,
\bm s^T\bm{H}\bm s \ge \lambda_{\min}\|\bm s\|^2 \qquad\forall\bm s\in\mathbb R^n. \tag{1.8}
Using stationarity and the second-order Taylor expansion,
f(\bm{x}^\star+\bm s)-f(\bm{x}^\star) = \frac12\bm s^T\bm{H}\bm s+o(\|\bm s\|^2) \ge \frac{\lambda_{\min}}{2}\|\bm s\|^2 +o(\|\bm s\|^2).
By the definition of little-o, for \varepsilon=\lambda_{\min}/4 there exists \delta>0 such that
\left|o(\|\bm s\|^2)\right| \le \frac{\lambda_{\min}}{4}\|\bm s\|^2
whenever 0<\|\bm s\|<\delta. Therefore, for every such nonzero \bm s,
f(\bm{x}^\star+\bm s)-f(\bm{x}^\star) \ge \left( \frac{\lambda_{\min}}2- \frac{\lambda_{\min}}4 \right)\|\bm s\|^2 = \frac{\lambda_{\min}}4\|\bm s\|^2 >0.
Hence
f(\bm{x}^\star+\bm s)>f(\bm{x}^\star) \qquad \text{for }0<\|\bm s\|<\delta,
which is precisely the definition of a strict local minimum.
The proof actually establishes the stronger local quadratic growth estimate
f(\bm{x}^\star+\bm s) \ge f(\bm{x}^\star) + \frac{\lambda_{\min}}4\|\bm s\|^2, \qquad \|\bm s\|<\delta. \tag{1.9}
The positive-definite Hessian condition is sufficient but not necessary for a strict local minimum. For example,
f(x)=x^4
has a strict global minimum at x=0, although f''(0)=0.
Therefore there is an inconclusive case when
\nabla f(\bm{x}^\star)=\bm0, \qquad \nabla^2f(\bm{x}^\star)\succeq0,
but the Hessian is singular. Higher-order terms or a direct analysis of the function are then required.
1.6 Examples: classification of stationary points
The following four functions illustrate how the Hessian test works and why a singular Hessian can be inconclusive. Each figure is a TikZ contour sketch in the (x,y) plane; the marked point is the origin. The TikZ pictures are rendered in PDF/LaTeX output.
Example 1: strict minimum (positive definite Hessian)
Let f(x,y)=x^2+2y^2. Then \nabla f(0,0)=0 and \nabla^2f=\operatorname{diag}(2,4)\succ0. Thus (0,0) is a strict global minimum. Its level curves are ellipses.
Example 2: strict maximum (negative definite Hessian)
Let f(x,y)=-x^2-y^2. The Hessian is -2\bm{I}\prec0 and (0,0) is a strict global maximum. The level curves are concentric circles, with decreasing function values away from the origin.
Example 3: saddle point (indefinite Hessian)
Let f(x,y)=x^2-y^2. At the origin, \nabla^2f=\operatorname{diag}(2,-2) is indefinite. Along the x-axis f(x,0)>0 for x\ne0, whereas along the y-axis f(0,y)<0 for y\ne0. Hence the origin is a saddle point.
Example 4: degenerate stationary point (inconclusive Hessian)
Let f(x,y)=x^4-y^4. At (0,0) both the gradient and the Hessian vanish, so the second-order test is inconclusive. However, f(x,0)=x^4>0 and f(0,y)=-y^4<0 for nonzero arguments: (0,0) is again a saddle point. The zero level set consists of y=x and y=-x, but the contours differ from the quadratic case.
For comparison, g(x,y)=x^4+y^4 has exactly the same zero Hessian at the origin but has a strict global minimum there. Thus a zero (or merely semidefinite) Hessian cannot by itself classify a stationary point.