230
A. Riccardi et al.
Moving along any vector of this cone (with vertex in a local minimum point x ∗ )
either increases the objective value or keeps it the same.
Theorem 7.2.2 (First-order necessary condition) If x ∗ is a local solution of the
optimisation problem and f is differentiable in x ∗ , then
∇f (x
∗ ) · w ≥ 0 ∀w ∈ C(x
∗ ).
For the directions w for which ∇f (x ∗ ) · w = 0, it is not possible to determine, from
first derivative information alone, whether a move along this direction will increase
or decrease the objective function. It is necessary to examine the second derivatives
of the objective function and constraints to see whether this extra information
resolves the issue. The directions for which the behaviour of f is not clear from
the first derivative form the following set:
Definition 7.2.5 Given a pair (x ∗ , λ ∗ ) satisfying the KKT conditions
C(λ
∗ ) = {w ∈ C(x
∗ ) | ∇c i (x
∗ ) · w = 0, for all i ∈ A (x
∗ ) ∩ I , with λ
∗
i > 0}
is called the critical cone.
Indeed for w ∈ C(λ ∗ ) from the first KKT condition it follows that
∇f (x
∗ ) · w =
i∈A (x ∗ )
λ
∗
i ∇c i (x
∗ ) · w
= 0.
If x ∗ is a local solution, then the curvature of the Lagrangian along the directions in
C(λ ∗ ) must be non-negative in the case of qualified constraints. A positive curvature
is instead a sufficient condition for a local optimum.
Theorem 7.2.3 (Second-order necessary condition) Let f and c be twice continuously differentiable; x ∗ is a local solution of the constrained problem and that the
LICQ condition is satisfied. Let λ ∗ ∈ R m be the Lagrange multiplier for which the
pair (x ∗ , λ ∗ ) satisfies the KKT conditions. Then
w
T
∇
2
xx L (x
∗ , λ
∗ ) w ≥ 0, ∀w ∈ C(λ
∗ )
Theorem 7.2.4 (Second-order sufficient condition) Let f and c be twice continuously differentiable; x ∗ is a feasible point, λ ∗ ∈ R m such that (x ∗ , λ ∗ ) satisfies the
KKT conditions and
w
T
∇
2
xx L (x
∗ , λ
∗ ) w > 0, ∀w ∈ C(λ
∗ ), w = 0.
Then x ∗ is a strict local minimum of the constrained problem.