Introduction
Recall our constrained optimization problem of the form,
( P ) { min f ( x ) subject to x ∈ S (P) \quad \begin{cases}
\min & f(\mathbf{x}) \newline
\text{subject to} & \mathbf{x} \in S
\end{cases} ( P ) { min subject to f ( x ) x ∈ S where f : R n ↦ R f : \mathbb{R}^n \mapsto \mathbb{R} f : R n ↦ R S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n
We have previously derived optimality conditions of the form,
" x ⋆ is a local minimum of ( P ) ⟹ There is no feasible descent direction at x ⋆ . " "
\mathbf{x}^{\star} \text{ is a local minimum of } (P) \implies \text{There is no feasible descent direction at } \mathbf{x}^{\star}.
" " x ⋆ is a local minimum of ( P ) ⟹ There is no feasible descent direction at x ⋆ ." In this part, we will generalize to statements of the form,
x ⋆ is a local minimum of ( P ) ⟹ A ( x ⋆ ) ⏟ Set of descent directions ∩ B ( x ⋆ ) ⏟ Set of feasible directions = ∅ , \mathbf{x}^{\star} \text{ is a local minimum of } (P) \implies \underbrace{A(\mathbf{x}^{\star})}_{\text{Set of descent directions}} \cap \underbrace{B(\mathbf{x}^{\star})}_{\text{Set of feasible directions}} = \emptyset, x ⋆ is a local minimum of ( P ) ⟹ Set of descent directions A ( x ⋆ ) ∩ Set of feasible directions B ( x ⋆ ) = ∅ , where we will characterize A ( x ⋆ ) A(\mathbf{x}^{\star}) A ( x ⋆ ) B ( x ⋆ ) B(\mathbf{x}^{\star}) B ( x ⋆ )
Tangent and Gradient Cones
To neatly characterize the set of feasible directions, we will introduce the concept of tangent and gradient cones.
But, let’s firstly define the cone of descent directions and cone of feasible directions.
Definition 1 (Cone of Descent Directions) The cone of descent directions in x ∈ S \mathbf{x} \in S x ∈ S
F ∘ ( x ) ≔ { p ∈ R n ∣ ∇ f ( x ) T p < 0 } \overset{\circ}{F}(\mathbf{x}) \coloneqq \{ \mathbf{p} \in \mathbb{R}^n \mid \nabla f(\mathbf{x})^T \mathbf{p} < 0 \} F ∘ ( x ) : = { p ∈ R n ∣ ∇ f ( x ) T p < 0 } Definition 2 (Cone of Feasible Directions) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n x ∈ S \mathbf{x} \in S x ∈ S
R S ( x ) ≔ { p ∈ R n ∣ ∃ δ > 0 , x + α p ∈ S , ∀ α ∈ [ 0 , δ ] } R_S(\mathbf{x}) \coloneqq \{ \mathbf{p} \in \mathbb{R}^n \mid \exists \delta > 0, \ \mathbf{x} + \alpha \mathbf{p} \in S, \ \forall \alpha \in [0, \delta] \} R S ( x ) : = { p ∈ R n ∣ ∃ δ > 0 , x + α p ∈ S , ∀ α ∈ [ 0 , δ ]} With these, we can rewrite our previous optimality condition as follows.
Theorem 1 (Optimality Condition using Cones) x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ R S ( x ⋆ ) = ∅ \mathbf{x}^{\star} \text{ is a local minimum of } (P) \implies \overset{\circ}{F}(\mathbf{x}^{\star}) \cap R_S(\mathbf{x}^{\star}) = \emptyset x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ R S ( x ⋆ ) = ∅ Example 1 (Cone of Feasible Directions) Let S = { x ∈ R 2 ∣ x 2 = x 1 2 } S = \{\mathbf{x} \in \mathbb{R}^2 \mid x_2 = x_1^2 \} S = { x ∈ R 2 ∣ x 2 = x 1 2 }
We can rewrite S S S S = { x ∈ R 2 ∣ − x 1 2 + x 2 = 0 } S = \{\mathbf{x} \in \mathbb{R}^2 \mid -x_1^2 + x_2 = 0 \} S = { x ∈ R 2 ∣ − x 1 2 + x 2 = 0 }
Thus, R S ( x ) = ∅ R_S(\mathbf{x}) = \emptyset R S ( x ) = ∅ x ∈ S \mathbf{x} \in S x ∈ S
Now, we can introduce the tangent cone.
Tangent Cone
Definition 3 (Tangent Cone) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n x ∈ S \mathbf{x} \in S x ∈ S
T S ( x ) ≔ { p ∈ R n ∣ ∃ { x k } k = 1 ∞ ⊆ S , ∃ { λ t } t = 1 ∞ ⊂ ( 0 , ∞ ) , such that lim t → ∞ x t = x , and lim k → ∞ λ k ( x k − x ) = p } \begin{align*}
T_S(\mathbf{x}) & \coloneqq \{ \mathbf{p} \in \mathbb{R}^n \mid \exists \{\mathbf{x}_k\}_{k=1}^{\infty} \subseteq S, \exists \{\lambda_t\}_{t=1}^{\infty} \subset (0, \infty), \newline
& \quad \quad \text{such that} \ \lim_{t \to \infty} \mathbf{x}_t = \mathbf{x}, \ \text{and} \newline
& \quad \quad \lim_{k \to \infty} \lambda_k (\mathbf{x}_k - \mathbf{x}) = \mathbf{p} \}
\end{align*} T S ( x ) : = { p ∈ R n ∣ ∃ { x k } k = 1 ∞ ⊆ S , ∃ { λ t } t = 1 ∞ ⊂ ( 0 , ∞ ) , such that t → ∞ lim x t = x , and k → ∞ lim λ k ( x k − x ) = p } Example 2 (Tangent Cone) Let S = { x ∈ R 2 ∣ x 2 = x 1 2 } S = \{\mathbf{x} \in \mathbb{R}^2 \mid x_2 = x_1^2 \} S = { x ∈ R 2 ∣ x 2 = x 1 2 } x = 0 \mathbf{x} = \mathbf{0} x = 0
Thus, the tangent cone at 0 \mathbf{0} 0
T S ( 0 ) = { p ∈ R 2 ∣ p 2 = 0 } T_S(\mathbf{0}) = \{ \mathbf{p} \in \mathbb{R}^2 \mid p_2 = 0 \} T S ( 0 ) = { p ∈ R 2 ∣ p 2 = 0 } Theorem 2 (Geometric Optimality Conditions) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n f ∈ C 1 f \in C^1 f ∈ C 1 S S S
x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ T S ( x ⋆ ) = ∅ \mathbf{x}^{\star} \text{ is a local minimum of } (P) \implies \overset{\circ}{F}(\mathbf{x}^{\star}) \cap T_S(\mathbf{x}^{\star}) = \emptyset x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ T S ( x ⋆ ) = ∅ To get more useful conditions, we will need more concrete feasible regions.
Consider this form of optimization problems,
( P ) { min f ( x ) subject to g i ( x ) ≤ 0 , i = 1 , … , m (P) \quad \begin{cases}
\min & f(\mathbf{x}) \newline
\text{subject to} & g_i(\mathbf{x}) \leq 0, \ i = 1, \ldots, m \newline
\end{cases} ( P ) { min subject to f ( x ) g i ( x ) ≤ 0 , i = 1 , … , m where f , g i ∈ C 1 f, g_i \in C^1 f , g i ∈ C 1 i = 1 , … , m i = 1, \ldots, m i = 1 , … , m S = { x ∈ R n ∣ g i ( x ) ≤ 0 , i = 1 , … , m } S = \{\mathbf{x} \in \mathbb{R}^n \mid g_i(\mathbf{x}) \leq 0, \ i = 1, \ldots, m \} S = { x ∈ R n ∣ g i ( x ) ≤ 0 , i = 1 , … , m }
Definition 4 (Active Constraints) The set of active constraints at x ∈ S \mathbf{x} \in S x ∈ S
I ( x ) ≔ { i ∈ { 1 , … , m } ∣ g i ( x ) = 0 } \mathcal{I}(\mathbf{x}) \coloneqq \{ i \in \{1, \ldots, m\} \mid g_i(\mathbf{x}) = 0 \} I ( x ) : = { i ∈ { 1 , … , m } ∣ g i ( x ) = 0 } Example 3 (Active Constraints) Let g i : R 2 → R g_i : \mathbb{R}^2 \to \mathbb{R} g i : R 2 → R i = 1 , 2 , 3 i = 1, 2, 3 i = 1 , 2 , 3
g 1 ( x ) = − x 1 g 2 ( x ) = − x 2 g 3 ( x ) = x 1 + x 2 − 1 \begin{align*}
g_1(\mathbf{x}) & = -x_1 \newline
g_2(\mathbf{x}) & = -x_2 \newline
g_3(\mathbf{x}) & = x_1 + x_2 - 1
\end{align*} g 1 ( x ) g 2 ( x ) g 3 ( x ) = − x 1 = − x 2 = x 1 + x 2 − 1 For x ˉ = [ 1 0 ] \bar{\mathbf{x}} = \begin{bmatrix} 1 \newline 0 \end{bmatrix} x ˉ = [ 1 0 ]
g 1 ( x ˉ ) = − 1 < 0 g 2 ( x ˉ ) = − 0 = 0 g 3 ( x ˉ ) = 1 2 + 0 − 1 = 0 \begin{align*}
g_1(\bar{\mathbf{x}}) & = -1 < 0 \newline
g_2(\bar{\mathbf{x}}) & = -0 = 0 \newline
g_3(\bar{\mathbf{x}}) & = 1^2 + 0 - 1 = 0
\end{align*} g 1 ( x ˉ ) g 2 ( x ˉ ) g 3 ( x ˉ ) = − 1 < 0 = − 0 = 0 = 1 2 + 0 − 1 = 0 Thus, I ( x ˉ ) = { 2 , 3 } \mathcal{I}(\bar{\mathbf{x}}) = \{2, 3\} I ( x ˉ ) = { 2 , 3 }
Definition 5 (Inner Gradient Cone) a
The inner gradient cone at x ∈ S \mathbf{x} \in S x ∈ S
G ∘ ( x ) ≔ { p ∈ R n ∣ ∇ g i ( x ) T p < 0 , ∀ i ∈ I ( x ) } \overset{\circ}{G}(\mathbf{x}) \coloneqq \{ \mathbf{p} \in \mathbb{R}^n \mid \nabla g_i(\mathbf{x})^T \mathbf{p} < 0, \ \forall i \in \mathcal{I}(\mathbf{x}) \} G ∘ ( x ) : = { p ∈ R n ∣ ∇ g i ( x ) T p < 0 , ∀ i ∈ I ( x )} Definition 6 (Gradient Cone) The gradient cone at x ∈ S \mathbf{x} \in S x ∈ S
G ( x ) ≔ { p ∈ R n ∣ ∇ g i ( x ) T p ≤ 0 , ∀ i ∈ I ( x ) } G(\mathbf{x}) \coloneqq \{ \mathbf{p} \in \mathbb{R}^n \mid \nabla g_i(\mathbf{x})^T \mathbf{p} \leq 0, \ \forall i \in \mathcal{I}(\mathbf{x}) \} G ( x ) : = { p ∈ R n ∣ ∇ g i ( x ) T p ≤ 0 , ∀ i ∈ I ( x )} Note The only difference between the inner gradient cone and the gradient cone is that the inequalities are strict in the inner gradient cone.
Theorem 3 (Gradient Cone Relations) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n x ∈ S \mathbf{x} \in S x ∈ S
G ∘ ( x ) ⊆ R S ( x ) ⊆ T S ( x ) ⊆ G ( x ) \overset{\circ}{G}(\mathbf{x}) \subseteq R_S(\mathbf{x}) \subseteq T_S(\mathbf{x}) \subseteq G(\mathbf{x}) G ∘ ( x ) ⊆ R S ( x ) ⊆ T S ( x ) ⊆ G ( x ) Lemma 1 (Optimality Condition using Gradient Cone) x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ G ∘ ( x ⋆ ) = ∅ \mathbf{x}^{\star} \text{ is a local minimum of } (P) \implies \overset{\circ}{F}(\mathbf{x}^{\star}) \cap \overset{\circ}{G}(\mathbf{x}^{\star}) = \emptyset x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ G ∘ ( x ⋆ ) = ∅ Abadie’s Constraint Qualifications and Karush-Kuhn-Tucker Conditions
With all these definitions, we can now introduce Abadie’s constraint qualifications (and later the Karush-Kuhn-Tucker conditions).
Definition 7 (Abadie’s Constraint Qualifications) Abadie’s constraint qualifications is said to hold in x ∈ S \mathbf{x} \in S x ∈ S
T S ( x ) = G ( x ) T_S(\mathbf{x}) = G(\mathbf{x}) T S ( x ) = G ( x ) In other words, Abadie’s constraint qualifications holds in x ∈ S \mathbf{x} \in S x ∈ S
Example 4 (Gradient Cone) Let S = { x ∈ R 2 ∣ ( x 1 − 1 ) 2 + x 2 2 ⏟ g 1 ( x ) ≤ 1 , ( x 1 + 1 ) 2 + x 2 2 ⏟ g 2 ( x ) ≤ 1 } S = \{\mathbf{x} \in \mathbb{R}^2 \mid \underbrace{(x_1 - 1)^2 + x_2^2}_{g_1(\mathbf{x})} \leq 1, \ \underbrace{(x_1 + 1)^2 + x_2^2}_{g_2(\mathbf{x})} \leq 1 \} S = { x ∈ R 2 ∣ g 1 ( x ) ( x 1 − 1 ) 2 + x 2 2 ≤ 1 , g 2 ( x ) ( x 1 + 1 ) 2 + x 2 2 ≤ 1 } x = [ 0 0 ] T \mathbf{x} = \begin{bmatrix} 0 & 0 \end{bmatrix}^T x = [ 0 0 ] T R S ( x ) R_S(\mathbf{x}) R S ( x ) T S ( x ) T_S(\mathbf{x}) T S ( x ) G ∘ ( x ) \overset{\circ}{G}(\mathbf{x}) G ∘ ( x ) G ( x ) G(\mathbf{x}) G ( x ) x \mathbf{x} x
Firstly, we rewrite our constraints to normal form,
g 1 ( x ) = ( x 1 − 1 ) 2 + x 2 2 − 1 ≤ 0 g 2 ( x ) = ( x 1 + 1 ) 2 + x 2 2 − 1 ≤ 0 \begin{align*}
g_1(\mathbf{x}) & = (x_1 - 1)^2 + x_2^2 - 1 \leq 0 \newline
g_2(\mathbf{x}) & = (x_1 + 1)^2 + x_2^2 - 1 \leq 0
\end{align*} g 1 ( x ) g 2 ( x ) = ( x 1 − 1 ) 2 + x 2 2 − 1 ≤ 0 = ( x 1 + 1 ) 2 + x 2 2 − 1 ≤ 0 Since we are working in R 2 \mathbb{R}^2 R 2 x = [ 0 0 ] T \mathbf{x} = \begin{bmatrix} 0 & 0 \end{bmatrix}^T x = [ 0 0 ] T
Thus, we know that there are no feasible directions, i.e., R S ( x ) = ∅ R_S(\mathbf{x}) = \emptyset R S ( x ) = ∅
Since we only have one point, the only allowed sequence that converges to x \mathbf{x} x x k = x \mathbf{x}_k = \mathbf{x} x k = x k k k T S ( x ) = { 0 } T_S(\mathbf{x}) = \{ \mathbf{0} \} T S ( x ) = { 0 }
Now, we compute the gradients of the constraints,
∇ g 1 ( x ) = [ 2 ( x 1 − 1 ) 2 x 2 ] = [ − 2 0 ] ∇ g 2 ( x ) = [ 2 ( x 1 + 1 ) 2 x 2 ] = [ 2 0 ] \begin{align*}
\nabla g_1(\mathbf{x}) & = \begin{bmatrix} 2(x_1 - 1) \newline 2x_2 \end{bmatrix} = \begin{bmatrix} -2 \newline 0 \end{bmatrix} \newline
\nabla g_2(\mathbf{x}) & = \begin{bmatrix} 2(x_1 + 1) \newline 2x_2 \end{bmatrix} = \begin{bmatrix} 2 \newline 0 \end{bmatrix}
\end{align*} ∇ g 1 ( x ) ∇ g 2 ( x ) = [ 2 ( x 1 − 1 ) 2 x 2 ] = [ − 2 0 ] = [ 2 ( x 1 + 1 ) 2 x 2 ] = [ 2 0 ] Since both constraints are active at x \mathbf{x} x I ( x ) = { 1 , 2 } \mathcal{I}(\mathbf{x}) = \{1, 2\} I ( x ) = { 1 , 2 }
G ∘ ( x ) = { p ∈ R 2 ∣ [ − 2 0 ] T p < 0 , [ 2 0 ] T p < 0 } = { p ∈ R 2 ∣ p 1 > 0 , p 1 < 0 } = ∅ G ( x ) = { p ∈ R 2 ∣ [ − 2 0 ] T p ≤ 0 , [ 2 0 ] T p ≤ 0 } = { p ∈ R 2 ∣ p 1 ≥ 0 , p 1 ≤ 0 } = { p ∈ R 2 ∣ p 1 = 0 } \begin{align*}
\overset{\circ}{G}(\mathbf{x}) & = \{ \mathbf{p} \in \mathbb{R}^2 \mid \begin{bmatrix}-2 \newline 0 \end{bmatrix}^T \mathbf{p} < 0, \ \begin{bmatrix}2 \newline 0 \end{bmatrix}^T \mathbf{p} < 0 \} = \{ \mathbf{p} \in \mathbb{R}^2 \mid p_1 > 0, \ p_1 < 0 \} = \emptyset \newline
G(\mathbf{x}) & = \{ \mathbf{p} \in \mathbb{R}^2 \mid \begin{bmatrix}-2 \newline 0 \end{bmatrix}^T \mathbf{p} \leq 0, \ \begin{bmatrix}2 \newline 0 \end{bmatrix}^T \mathbf{p} \leq 0 \} = \{ \mathbf{p} \in \mathbb{R}^2 \mid p_1 \geq 0, \ p_1 \leq 0 \} = \{ \mathbf{p} \in \mathbb{R}^2 \mid p_1 = 0 \}
\end{align*} G ∘ ( x ) G ( x ) = { p ∈ R 2 ∣ [ − 2 0 ] T p < 0 , [ 2 0 ] T p < 0 } = { p ∈ R 2 ∣ p 1 > 0 , p 1 < 0 } = ∅ = { p ∈ R 2 ∣ [ − 2 0 ] T p ≤ 0 , [ 2 0 ] T p ≤ 0 } = { p ∈ R 2 ∣ p 1 ≥ 0 , p 1 ≤ 0 } = { p ∈ R 2 ∣ p 1 = 0 } Finally, we can say that Abadie’s constraint qualifications does not hold in x \mathbf{x} x
T S ( x ) = { 0 } ≠ { p ∈ R 2 ∣ p 1 = 0 } = G ( x ) T_S(\mathbf{x}) = \{ \mathbf{0} \} \neq \{ \mathbf{p} \in \mathbb{R}^2 \mid p_1 = 0 \} = G(\mathbf{x}) T S ( x ) = { 0 } = { p ∈ R 2 ∣ p 1 = 0 } = G ( x ) Theorem 4 (Karush-Kuhn-Tucker (KKT) Conditions) Assume that Abadie’s constraint qualifications holds in x ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S
x ⋆ is a local minimum of ( P ) ⟹ The following system is solvable for μ , { ∇ f ( x ⋆ ) + ∑ i m μ i ∇ g i ( x ⋆ ) = 0 μ i g i ( x ⋆ ) = 0 , i = 1 , … , m μ i ≥ 0 , i = 1 , … , m \begin{align*}
\mathbf{x}^{\star} \text{ is a local minimum of } (P) & \implies \text{The following system is solvable for } \mu, \newline
& \quad \quad \begin{cases}
\nabla f(\mathbf{x}^{\star}) + \sum_i^m \mu_i \nabla g_i(\mathbf{x}^{\star}) = 0 \newline
\mu_i g_i(\mathbf{x}^{\star}) = 0, \ i = 1, \ldots, m \newline
\mu_i \geq 0, \ i = 1, \ldots, m
\end{cases}
\end{align*} x ⋆ is a local minimum of ( P ) ⟹ The following system is solvable for μ , ⎩ ⎨ ⎧ ∇ f ( x ⋆ ) + ∑ i m μ i ∇ g i ( x ⋆ ) = 0 μ i g i ( x ⋆ ) = 0 , i = 1 , … , m μ i ≥ 0 , i = 1 , … , m To prove the KKT conditions, we will need Farkas’ lemma (which is a theorem, but for historical reasons is called a lemma).
Theorem 5 (Farkas’ Lemma) Let A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n b ∈ R m \mathbf{b} \in \mathbb{R}^m b ∈ R m
{ A x = b x ≥ 0 { A T y ≤ 0 b T y > 0 \begin{cases}
A \mathbf{x} = \mathbf{b} \newline
\mathbf{x} \geq 0
\end{cases}
\quad \quad
\begin{cases}
A^T \mathbf{y} \leq 0 \newline
\mathbf{b}^T \mathbf{y} > 0
\end{cases} { A x = b x ≥ 0 { A T y ≤ 0 b T y > 0 We will not prove this now, we will prove this later on, more specifically in a LP setting.
Proof (Karush-Kuhn-Tucker (KKT) Conditions) We know that,
x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ T S ( x ⋆ ) = ∅ ⟺ F ∘ ( x ⋆ ) ∩ G ( x ⋆ ) = ∅ (By Abadie’s) ⟹ { ∇ f ( x ⋆ ) T p < 0 ∇ g i ( x ⋆ ) T p ≤ 0 , i ∈ I ( x ⋆ ) we notice that if we let, A T = [ ∇ g i ( x ⋆ ) ] i ∈ I ( x ⋆ ) , b = − ∇ f ( x ⋆ ) , we can use Farkas’ lemma ⟹ { A x = b x ≥ 0 We now index x as x = [ x i ] i ∈ I ( x ⋆ ) , and let μ i = x i for i ∈ I ( x ⋆ ) and μ i = 0 for i ∉ I ( x ⋆ ) ⟹ { ∇ f ( x ⋆ ) + ∑ i m μ i ∇ g i ( x ⋆ ) = 0 μ i g i ( x ⋆ ) = 0 , i = 1 , … , m μ i ≥ 0 , i = 1 , … , m which are precisely the KKT conditions. ■ \begin{align*}
\mathbf{x}^{\star} \text{ is a local minimum of } (P) & \implies \overset{\circ}{F}(\mathbf{x}^{\star}) \cap T_S(\mathbf{x}^{\star}) = \emptyset \newline
& \iff \overset{\circ}{F}(\mathbf{x}^{\star}) \cap G(\mathbf{x}^{\star}) = \emptyset \ \text{(By Abadie's)} \newline
& \implies \begin{cases}
\nabla f(\mathbf{x}^{\star})^T \mathbf{p} < 0 \newline
\nabla g_i(\mathbf{x}^{\star})^T \mathbf{p} \leq 0, \ i \in \mathcal{I}(\mathbf{x}^{\star})
\end{cases} \newline
& \text{we notice that if we let,} \newline
& A^T = \begin{bmatrix} \nabla g_i(\mathbf{x}^{\star}) \end{bmatrix}_{i \in \mathcal{I}(\mathbf{x}^{\star})}, \newline
& \mathbf{b} = -\nabla f(\mathbf{x}^{\star}), \newline
& \text{ we can use Farkas' lemma} \newline
& \implies \begin{cases}
A \mathbf{x} = \mathbf{b} \newline
\mathbf{x} \geq 0
\end{cases} \newline
& \text{We now index } \mathbf{x} \text{ as } \mathbf{x} = \begin{bmatrix} x_i \end{bmatrix}_{i \in \mathcal{I}(\mathbf{x}^{\star})}, \newline
& \text{and let } \mu_i = x_i \text{ for } i \in \mathcal{I}(\mathbf{x}^{\star}) \text{ and } \mu_i = 0 \text{ for } i \notin \mathcal{I}(\mathbf{x}^{\star}) \newline
& \implies \begin{cases}
\nabla f(\mathbf{x}^{\star}) + \sum_i^m \mu_i \nabla g_i(\mathbf{x}^{\star}) = 0 \newline
\mu_i g_i(\mathbf{x}^{\star}) = 0, \ i = 1, \ldots, m \newline
\mu_i \geq 0, \ i = 1, \ldots, m \newline
\end{cases}
\newline
& \text{which are precisely the KKT conditions.} \ _\blacksquare
\end{align*} x ⋆ is a local minimum of ( P ) ⟹ F ∘ ( x ⋆ ) ∩ T S ( x ⋆ ) = ∅ ⟺ F ∘ ( x ⋆ ) ∩ G ( x ⋆ ) = ∅ (By Abadie’s) ⟹ { ∇ f ( x ⋆ ) T p < 0 ∇ g i ( x ⋆ ) T p ≤ 0 , i ∈ I ( x ⋆ ) we notice that if we let, A T = [ ∇ g i ( x ⋆ ) ] i ∈ I ( x ⋆ ) , b = − ∇ f ( x ⋆ ) , we can use Farkas’ lemma ⟹ { A x = b x ≥ 0 We now index x as x = [ x i ] i ∈ I ( x ⋆ ) , and let μ i = x i for i ∈ I ( x ⋆ ) and μ i = 0 for i ∈ / I ( x ⋆ ) ⟹ ⎩ ⎨ ⎧ ∇ f ( x ⋆ ) + ∑ i m μ i ∇ g i ( x ⋆ ) = 0 μ i g i ( x ⋆ ) = 0 , i = 1 , … , m μ i ≥ 0 , i = 1 , … , m which are precisely the KKT conditions. ■ Note
If g i ( x ⋆ ) = 0 g_i(\mathbf{x}^{\star}) = 0 g i ( x ⋆ ) = 0 μ i \mu_i μ i μ i ≥ 0 \mu_i \geq 0 μ i ≥ 0
If g i ( x ⋆ ) < 0 g_i(\mathbf{x}^{\star}) < 0 g i ( x ⋆ ) < 0 μ i = 0 \mu_i = 0 μ i = 0
− ∇ f ( x ⋆ ) -\nabla f(\mathbf{x}^{\star}) − ∇ f ( x ⋆ ) non-negative linear combination of the gradients of the active constraints ∇ g i ( x ⋆ ) \nabla g_i(\mathbf{x}^{\star}) ∇ g i ( x ⋆ ) i ∈ I ( x ⋆ ) i \in \mathcal{I}(\mathbf{x}^{\star}) i ∈ I ( x ⋆ )
We can interpret the above as a generalization of the normal cone, since we assumed convexity, here we do not assume convexity.
Definition 8 (KKT Point) A KKT point is a point x ∈ S \mathbf{x} \in S x ∈ S μ \mu μ
Example 5 (KKT Point) Consider the following optimization problem,
{ min − x 1 + x 2 subject to x 1 2 + x 2 2 − 1 ≤ 0 − x 2 ≤ 0 \begin{cases}
\min & -x_1 + x_2 \newline
\text{subject to} & x_1^2 + x_2^2 - 1 \leq 0 \newline
& -x_2 \leq 0
\end{cases} ⎩ ⎨ ⎧ min subject to − x 1 + x 2 x 1 2 + x 2 2 − 1 ≤ 0 − x 2 ≤ 0 Which points are KKT points?
(a) x 1 = [ 0 0 ] T \mathbf{x}_1 = \begin{bmatrix} 0 & 0 \end{bmatrix}^T x 1 = [ 0 0 ] T x 2 = [ − 1 0 ] T \mathbf{x}_2 = \begin{bmatrix} -1 & 0 \end{bmatrix}^T x 2 = [ − 1 0 ] T x 3 = [ 1 0 ] T \mathbf{x}_3 = \begin{bmatrix} 1 & 0 \end{bmatrix}^T x 3 = [ 1 0 ] T R 2 \mathbb{R}^2 R 2
The next step is to calculate the gradients of the cost and constraints,
∇ f ( x ) = [ − 1 1 ] ∇ g 1 ( x ) = [ 2 x 1 2 x 2 ] ∇ g 2 ( x ) = [ 0 − 1 ] \begin{align*}
\nabla f(\mathbf{x}) & = \begin{bmatrix} -1 \newline 1 \end{bmatrix} \newline
\nabla g_1(\mathbf{x}) & = \begin{bmatrix} 2x_1 \newline 2x_2 \end{bmatrix} \newline
\nabla g_2(\mathbf{x}) & = \begin{bmatrix} 0 \newline -1 \end{bmatrix}
\end{align*} ∇ f ( x ) ∇ g 1 ( x ) ∇ g 2 ( x ) = [ − 1 1 ] = [ 2 x 1 2 x 2 ] = [ 0 − 1 ]
As we stated previously, the (negative) gradient of the cost should be a non-negative linear combination of the gradients of the active constraints.
We can see that for x 2 \mathbf{x}_2 x 2 x 2 \mathbf{x}_2 x 2
For x 1 \mathbf{x}_1 x 1 x 1 \mathbf{x}_1 x 1
However, for x 3 \mathbf{x}_3 x 3 x 3 \mathbf{x}_3 x 3
{ ∇ f ( x 3 ) + μ 1 ∇ g 1 ( x 3 ) + μ 2 ∇ g 2 ( x 3 ) = 0 [ − 1 1 ] + μ 1 [ 2 0 ] + μ 2 [ 0 − 1 ] = 0 ⟹ { − 1 + 2 μ 1 = 0 1 − μ 2 = 0 ⟹ { μ 1 = 1 2 μ 2 = 1 \begin{cases}
\nabla f(\mathbf{x}_3) + \mu_1 \nabla g_1(\mathbf{x}_3) + \mu_2 \nabla g_2(\mathbf{x}_3) = 0 \newline
\begin{bmatrix} -1 \newline 1 \end{bmatrix} + \mu_1 \begin{bmatrix} 2 \newline 0 \end{bmatrix} + \mu_2 \begin{bmatrix} 0 \newline -1 \end{bmatrix} = 0 \newline
\implies \begin{cases}
-1 + 2\mu_1 = 0 \newline
1 - \mu_2 = 0
\end{cases} \newline
\implies \boxed{\begin{cases}
\mu_1 = \frac{1}{2} \newline
\mu_2 = 1
\end{cases}} \newline
\end{cases} ⎩ ⎨ ⎧ ∇ f ( x 3 ) + μ 1 ∇ g 1 ( x 3 ) + μ 2 ∇ g 2 ( x 3 ) = 0 [ − 1 1 ] + μ 1 [ 2 0 ] + μ 2 [ 0 − 1 ] = 0 ⟹ { − 1 + 2 μ 1 = 0 1 − μ 2 = 0 ⟹ { μ 1 = 2 1 μ 2 = 1 Thus, the only KKT point is x 3 = [ 1 0 ] T \mathbf{x}_3 = \begin{bmatrix} 1 & 0 \end{bmatrix}^T x 3 = [ 1 0 ] T μ 1 = 1 2 \mu_1 = \frac{1}{2} μ 1 = 2 1 μ 2 = 1 \mu_2 = 1 μ 2 = 1
We can see that there is only one single point that meets both constraints, which is .
Again, since we are in , we can easily visualize the problem.
We can see that the feasible region is the upper half of the unit circle, including the boundary.
We can draw these out to get a better understanding.