4 Calculus Review
When minimizing a function, certain regularity conditions must be assumed to simplify the analysis and prove meaningful results. The first condition is a minimal regularity requirement for the function being studied.
Definition 4.1 (first order regularity) Let f: \mathbb{R}^n \to \mathbb{R} be a multivariate function satisfying the following properties:
f \in C^1(\mathbb{R}^n), meaning f(\bm{x}) is continuously differentiable, and the gradient (row) vector \nabla f(\bm{x}) exists.
The gradient \nabla f(\bm{x}) is Lipschitz continuous, i.e.,
\|\nabla f(\bm{x}) - \nabla f(\bm{y})\| \leq \gamma \|\bm{x} - \bm{y}\|, \qquad \forall \bm{x}, \bm{y} \in \mathbb{R}^n
With these regularity assumptions, the Taylor series for f can be expanded up to the first order as follows:
f(\bm{x} + t\bm{d}) = f(\bm{x}) + t\nabla f(\bm{x})\bm{d} + \mathcal{o}(t)
where the remainder term \mathcal{o}(t) satisfies
\lim_{t \to 0} \frac{\mathcal{o}(t)}{t} = 0
This expansion does not require the existence of second-order derivatives, but it does require that the gradient is Lipschitz continuous.
4.1 Higher Regularity Conditions
In the classification of minimum or maximum points, additional regularity conditions are needed.
Definition 4.2 (second order regularity) Consider again a multivariate function f: \mathbb{R}^n \to \mathbb{R}, but now assume the following:
f \in C^2(\mathbb{R}^n), meaning f(\bm{x}) is twice continuously differentiable. Both the gradient vector \nabla f(\bm{x}) and the Hessian matrix \nabla^2 f(\bm{x}) exist.
The Hessian \nabla^2 f(\bm{x}) is Lipschitz continuous, i.e.,
\|\nabla^2 f(\bm{x}) - \nabla^2 f(\bm{y})\| \leq \gamma \|\bm{x} - \bm{y}\|, \qquad \forall \bm{x}, \bm{y} \in \mathbb{R}^n
With this stronger regularity assumption, the Taylor series can be expanded up to the second order as:
f(\bm{x} + t\bm{d}) = f(\bm{x}) + t\nabla f(\bm{x})\bm{d} + \frac{t^2}{2} \bm{d}^T \nabla^2 f(\bm{x}) \bm{d} + \mathcal{o}(t^2)
Here, the remainder term \mathcal{o}(t^2) does not require the existence of third-order derivatives but does depend on the Lipschitz continuity of the Hessian.
In summary, the first-order expansion requires f \in C^1 and the Lipschitz continuity of the gradient, while second-order expansions demand f \in C^2 and the Lipschitz continuity of the Hessian matrix. These conditions provide the necessary regularity to perform effective analyses of function behavior.
A point \bm{x}^\star \in \Bbb{R}^n is considered a global minimum if
f(\bm{x}^\star) \leq f(\bm{x}) \quad \text{for all } \bm{x} \in \Bbb{R}^n.
4.2 Local Minimum
A point \bm{x}^\star \in \mathbb{R}^n is classified as a local minimum of a function f: \mathbb{R}^n \to \mathbb{R} if:
f(\bm{x}^\star) \leq f(\bm{x}) \quad \text{for all } \bm{x} \in B(\bm{x}^\star, \delta),
where B(\bm{x}^\star, \delta) represents the open ball centered at \bm{x}^\star with radius \delta > 0. This implies that within a small neighborhood around \bm{x}^\star, the value of the function f(\bm{x}) is always greater than or equal to f(\bm{x}^\star).
Strict Local Minimum
If the inequality is strict, meaning:
f(\bm{x}^\star) < f(\bm{x}) \quad \text{for all } \bm{x} \in B(\bm{x}^\star, \delta) \text{ and } \bm{x} \neq \bm{x}^\star,
then \bm{x}^\star is classified as a strict local minimum. In this case, no other point in the neighborhood has a function value equal to or less than f(\bm{x}^\star).
4.3 Conditions for a Local Minimum
First-Order Conditions
For first order condition we assume first order regularity (Definition 4.1). A necessary condition for \bm{x}^\star \in \mathbb{R}^n to be a local minimum is that the gradient of f at \bm{x}^\star must vanish. Mathematically, this is expressed as:
\nabla f(\bm{x}^\star)^T = \bm{0}
This condition is known as the first-order necessary condition. However, it is not sufficient to confirm that \bm{x}^\star is a minimum. This condition alone could indicate a minimum, a maximum, or even a saddle point (a point that is neither a minimum nor a maximum).
Second-Order Conditions
To further classify \bm{x}^\star, we need to examine the second-order derivatives of the function and assume seond order regularity (Definition 4.2).
Necessary Conditions
Assuming that f \in C^2(\mathbb{R}^n), with Lipshitz continuous second derivatives, then the Hessian matrix at \bm{x}^\star must be semi-positive definite, which means: \bm{d}^T \nabla^2 f(\bm{x}^\star) \bm{d} \geq 0 \quad \text{for all} \, \bm{d} \in \mathbb{R}^n
Sufficient Conditions
A sufficient condition for \bm{x}^\star to be a strict local minimum is that the Hessian matrix \nabla^2 f(\bm{x}^\star) is positive definite. That is: \bm{d}^T \nabla^2 f(\bm{x}^\star) \bm{d} > 0 \quad \text{for all} \, \bm{d} \neq \bm{0} \in \mathbb{R}^n
If the Hessian is positive definite, then \bm{x}^\star is guaranteed to be a strict local minimum. This condition is equivalent to saying that all the eigenvalues of the Hessian matrix \nabla^2 f(\bm{x}^\star) are positive.
In summary:
A point where the gradient vanishes may be a local minimum, maximum, or saddle point.
To classify a point as a (strict) local minimum, the Hessian must be positive definite.
If the Hessian matrix is not semi-positive definite the point is surely not a minimum point.
There is a grey zone when the point satisfy necessary condition:
- the Hessian matrix is semi-positive definite
but not the sufficient condition, i.e:
- the Hessian matrix is not positive definite
in this case the point can be a mininimal point or not a require further investigation.