7 Introduction to Optimisation
229
rank(∇c i (x), i ∈ A (x)) = |A |.
Note that if this condition holds, none of the active constraint gradients can be zero.
7.2.1.1 Optimality Conditions
These definitions allow the statement of the following optimality conditions (refer
to [2], for a proof of the Theorems).
Theorem 7.2.1 (First-order necessary condition) Suppose that x ∗ is a local solution of the constrained non-linear programming (NLP) problem and that the LICQ
holds at x ∗ . Then a Lagrange multiplier vector λ ∗ exists such that the following
conditions are satisfied at the point (x ∗ , λ ∗ )
∇ x L (x
∗ , λ
∗ ) = 0,
(7.1)
c(x
∗ ) ≤ 0,
(7.2)
λ
∗
≥ 0,
(7.3)
(λ
∗ )
T c(x
∗ ) = 0.
(7.4)
These conditions are known as the Karush-Kuhn-Tucker (KKT) conditions.
Remark 7.2.1 The last condition implies that the Lagrange multipliers corresponding to inactive inequality constraints are zero; hence it is possible to rewrite the first
equation as
0 = ∇ x L (x
∗ , λ
∗ ) = ∇f (x
∗ ) −
i∈A (x ∗ )
λ
∗
i ∇c i (x
∗ ).
The optimality condition presented above gives information on how the derivatives
of objective and constraints are related at the minimum point x ∗ . Another fundamental first-order necessary condition that gives additional information on the gradient
of the objective function in the optimal point can be stated. For this an additional
definition is needed.
Definition 7.2.4 Given a feasible point x ∈ D, a sequence {x k } ∞
k=0 with x k ∈ Ω is
a feasible sequence if, for all k ∈ N, x k ∈ D\{x ∗ } and
lim
k→∞
x k = x.
Given a feasible sequence, the set of the limiting directions w ∈ Ω\{0}
lim
k→∞
x k − x
x k − x 2
=
w
w 2
is called the cone of the feasible directions, C(x).