Outline
In this part, we will cover the following topics:
Local & global optimality
Existence of optimal solutions
Optimality conditions for unconstrained problems (S = R n S = \mathbb{R}^n S = R n
Optimality conditions for constrained problems (S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n
Before we start with local and global optimality, we will have a short recap of some concepts that we need to use.
Open, closed, and bounded sets
Recall the following properties of sets in R n \mathbb{R}^n R n
Note (Set properties) B ϵ ( x ) ≔ { y ∈ R n ∣ ∥ x − y ∥ < ϵ } B_{\epsilon}(\mathbf{x}) \coloneqq \{\mathbf{y} \in \mathbb{R}^n \mid \Vert \mathbf{x} - \mathbf{y} \Vert < \epsilon \} B ϵ ( x ) : = { y ∈ R n ∣ ∥ x − y ∥ < ϵ } ϵ \epsilon ϵ x \mathbf{x} x
A set S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n open if ∀ x ∈ S , ∃ ϵ > 0 : B ϵ ( x ) ⊆ S \forall \mathbf{x} \in S, \quad \exists \epsilon > 0 : B_{\epsilon}(\mathbf{x}) \subseteq S ∀ x ∈ S , ∃ ϵ > 0 : B ϵ ( x ) ⊆ S
A set S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n closed if its complement R n ∖ S \mathbb{R}^n \setminus S R n ∖ S
A set S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n ∃ M > 0 : ∀ x ∈ S : ∥ x ∥ < M , ∀ x ∈ S \exists M > 0 : \forall \mathbf{x} \in S : \Vert \mathbf{x} \Vert < M, \quad \forall \mathbf{x} \in S ∃ M > 0 : ∀ x ∈ S : ∥ x ∥ < M , ∀ x ∈ S
A set S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n compact if it is closed and bounded.
Local & Global Optimality
Recall, our model problem can be written as,
( P ) { min x ∈ R n f ( x ) subject to x ∈ S , \begin{align*}
(P) \quad &
\begin{cases}
\underset{\mathbf{x} \in \mathbb{R}^n}{\min} & f(\mathbf{x}) \newline
\text{subject to } & \mathbf{x} \in S,
\end{cases}
\end{align*} ( P ) { x ∈ R n min subject to f ( x ) x ∈ S , Optimality conditions will characterize which points x \mathbf{x} x ( P ) (P) ( P )
So the our first question is, where can the problem have local and global solutions?
Figure 1: Candidates for optimalityFrom Figure 1 (and intuition calculus), we can see that the candidates for local and global optimality are:
Points where the gradient is zero (stationary points).
Points where the gradient is undefined (nondifferentiable points).
Boundary points of the feasible set S S S
Discontinuous points of the function f f f
Now, let’s (formally) define what we mean with global and local optimal solutions?
Definition 1 (Global and local optimality) x ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S global minimum of f f f S S S
f ( x ⋆ ) ≤ f ( x ) , ∀ x ∈ S . f(\mathbf{x}^{\star}) \leq f(\mathbf{x}), \quad \forall \mathbf{x} \in S. f ( x ⋆ ) ≤ f ( x ) , ∀ x ∈ S . x ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S local minimum of f f f S S S
∃ ϵ > 0 : f ( x ⋆ ) ≤ f ( x ) , ∀ x ∈ S ∩ B ϵ ( x ⋆ ) . \exists \epsilon > 0 : f(\mathbf{x}^{\star}) \leq f(\mathbf{x}), \quad \forall \mathbf{x} \in S \cap B_{\epsilon}(\mathbf{x}^{\star}). ∃ ϵ > 0 : f ( x ⋆ ) ≤ f ( x ) , ∀ x ∈ S ∩ B ϵ ( x ⋆ ) . x ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S strict local minimum of f f f S S S f ( x ⋆ ) < f ( x ) f(\mathbf{x}^{\star}) < f(\mathbf{x}) f ( x ⋆ ) < f ( x ) x ≠ x ⋆ \mathbf{x} \neq \mathbf{x}^{\star} x = x ⋆
With these definitions, we can define the fundamental theorem of global optimality.
Theorem 1 (Fundamental theorem of global optimality) Consider the problem
( P ) { min x ∈ R n f ( x ) subject to x ∈ S , \begin{align*}
(P) \quad &
\begin{cases}
\underset{\mathbf{x} \in \mathbb{R}^n}{\min} & f(\mathbf{x}) \newline
\text{subject to } & \mathbf{x} \in S,
\end{cases}
\end{align*} ( P ) { x ∈ R n min subject to f ( x ) x ∈ S , where S S S f f f S S S ( P ) (P) ( P )
Let’s now prove this theorem.
Proof (Proof of the fundamental theorem of global optimality) We will use proof by contradiction. Let x ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S
Further, let x ˉ ∈ S \bar{\mathbf{x}} \in S x ˉ ∈ S f ( x ˉ ) < f ( x ⋆ ) f(\bar{\mathbf{x}}) < f(\mathbf{x}^{\star}) f ( x ˉ ) < f ( x ⋆ ) λ ∈ ( 0 , 1 ) \lambda \in (0, 1) λ ∈ ( 0 , 1 )
λ x ˉ + ( 1 − λ ) x ⋆ ∈ S \lambda \bar{\mathbf{x}} + (1 - \lambda) \mathbf{x}^{\star} \in S λ x ˉ + ( 1 − λ ) x ⋆ ∈ S Therefore,
f ( λ x ˉ + ( 1 − λ ) x ⋆ ) ≤ λ f ( x ˉ ) ⏟ < f ( x ⋆ ) + ( 1 − λ ) f ( x ⋆ ) < λ f ( x ⋆ ) + ( 1 − λ ) f ( x ⋆ ) < f ( x ⋆ ) \begin{align*}
f(\lambda \bar{\mathbf{x}} + (1 - \lambda) \mathbf{x}^{\star}) & \leq \lambda \underbrace{f(\bar{\mathbf{x}})}_{< f(\mathbf{x}^{\star})} + (1 - \lambda) f(\mathbf{x}^{\star}) \newline
& < \lambda f(\mathbf{x}^{\star}) + (1 - \lambda) f(\mathbf{x}^{\star}) \newline
& < f(\mathbf{x}^{\star})
\end{align*} f ( λ x ˉ + ( 1 − λ ) x ⋆ ) ≤ λ < f ( x ⋆ ) f ( x ˉ ) + ( 1 − λ ) f ( x ⋆ ) < λ f ( x ⋆ ) + ( 1 − λ ) f ( x ⋆ ) < f ( x ⋆ ) However, if we now let λ → 0 \lambda \rightarrow 0 λ → 0 x ⋆ \mathbf{x}^{\star} x ⋆
With this, we ask our third question, when does ( P ) (P) ( P )
Let’s review some examples first.
Example 1 Consider the following problem
min x ∈ R x subject to x ∈ [ 0 , 1 ] . \begin{align*}
\underset{\mathbf{x} \in \mathbb{R}}{\min} & x \newline
\text{subject to } & x \in [0, 1].
\end{align*} x ∈ R min subject to x x ∈ [ 0 , 1 ] . The problem has a global optimal solution at x ⋆ = 0 x^{\star} = 0 x ⋆ = 0
Example 2 Consider the following problem
min x ∈ R x subject to x ∈ ( 0 , 1 ] . \begin{align*}
\underset{\mathbf{x} \in \mathbb{R}}{\min} & x \newline
\text{subject to } & x \in (0, 1].
\end{align*} x ∈ R min subject to x x ∈ ( 0 , 1 ] . The problem does not have a global optimal solution, the infimum is still 0, but x = 0 x = 0 x = 0 S S S closed .
So it looks like having a closed set is nice.
Example 3 Let f : R → R f : \mathbb{R} \to \mathbb{R} f : R → R
f ( x ) = { x , x > 0 1 , x ≤ 0 f(x) =
\begin{cases}
x, & x > 0 \newline
1, & x \leq 0
\end{cases} f ( x ) = { x , 1 , x > 0 x ≤ 0 Does the following problem have an optimal solution?
min x ∈ R f ( x ) subject to x ∈ [ − 2 , 2 ] . \begin{align*}
\underset{\mathbf{x} \in \mathbb{R}}{\min} & f(x) \newline
\text{subject to } & x \in [-2, 2].
\end{align*} x ∈ R min subject to f ( x ) x ∈ [ − 2 , 2 ] . Again, the infimum is 0, but f ( x ) > 0 f(x) > 0 f ( x ) > 0 f f f continuous .
So it looks like having a continuous function is also nice :).
We will define one more nice property, weakly coercive functions.
Definition 2 (Weakly coercive functions) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n f : S → R f : S \to \mathbb{R} f : S → R f f f weakly coercive with respect to S S S
either S S S
or, for all sequences { x k } ⊂ S \{\mathbf{x}_k\} \subset S { x k } ⊂ S lim k → ∞ ∥ x ∥ → ∞ \lim_{k \to \infty} \Vert \mathbf{x} \Vert \to \infty lim k → ∞ ∥ x ∥ → ∞ lim k → ∞ f ( x k ) → ∞ \lim_{k \to \infty} f(\mathbf{x}_k) \to \infty lim k → ∞ f ( x k ) → ∞
Example 4 Let S : − { x ∣ x ≥ 0 } ⊂ R S \coloneq \{x | x \geq 0 \} \subset \mathbb{R} S : − { x ∣ x ≥ 0 } ⊂ R f ( x ) = e x f(x) = e^x f ( x ) = e x f f f S S S
Solution Yes. First, note that S S S { x k } \{ x_k \} { x k } lim k → ∞ x k → ∞ \lim_{k \to \infty} x_k \to \infty lim k → ∞ x k → ∞ lim k → ∞ f ( x k ) = lim k → ∞ e x k = ∞ \lim_{k \to \infty} f(x_k) = \lim_{k \to \infty} e^{x_k} = \infty lim k → ∞ f ( x k ) = lim k → ∞ e x k = ∞
Example 5 Let S S S f f f
min x ∈ R f ( x ) subject to x ∈ S . \begin{align*}
\underset{\mathbf{x} \in \mathbb{R}}{\min} & f(x) \newline
\text{subject to } & x \in S.
\end{align*} x ∈ R min subject to f ( x ) x ∈ S . Yes, the problem has a global optimal solution at x ⋆ = 0 x^{\star} = 0 x ⋆ = 0
Example 6 Let S : − { x ∣ x ≥ 0 } ⊂ R S \coloneq \{x | x \geq 0 \} \subset \mathbb{R} S : − { x ∣ x ≥ 0 } ⊂ R f ( x ) = e − x f(x) = e^{-x} f ( x ) = e − x f f f S S S
Solution No. First, note that S S S { x k } \{ x_k \} { x k } lim k → ∞ x k → ∞ \lim_{k \to \infty} x_k \to \infty lim k → ∞ x k → ∞ lim k → ∞ f ( x k ) = lim k → ∞ e − x k = 0 ≠ ∞ \lim_{k \to \infty} f(x_k) = \lim_{k \to \infty} e^{-x_k} = 0 \neq \infty lim k → ∞ f ( x k ) = lim k → ∞ e − x k = 0 = ∞
Example 7 Let S S S f f f
min x ∈ R f ( x ) subject to x ∈ S . \begin{align*}
\underset{\mathbf{x} \in \mathbb{R}}{\min} & f(x) \newline
\text{subject to } & x \in S.
\end{align*} x ∈ R min subject to f ( x ) x ∈ S . No, the problem does not have a global optimal solution, the infimum is 0, but f ( x ) > 0 f(x) > 0 f ( x ) > 0 x ∈ S x \in S x ∈ S
With these examples, we will now define Weierstrass’ theorem, which states the existence of globally optimal solutions.
Theorem 2 (Weierstrass’ theorem) Consider the problem,
( P ) { min x ∈ R n f ( x ) subject to x ∈ S , \begin{align*}
(P) \quad &
\begin{cases}
\underset{\mathbf{x} \in \mathbb{R}^n}{\min} & f(\mathbf{x}) \newline
\text{subject to } & \mathbf{x} \in S,
\end{cases}
\end{align*} ( P ) { x ∈ R n min subject to f ( x ) x ∈ S , and assume that,
S S S f f f S S S 1 f f f S S S Then, there exists a non-empty, compact set of global minimizers to ( P ) (P) ( P )
Before we start on optimality conditions, we will see two types of optimality conditions, necessary and sufficient conditions.
Necessary optimality conditions are of the form,
x ⋆ is a local minimum ⟹ "something" holds. \mathbf{x}^{\star} \text{ is a local minimum } \implies \text{ "something" holds.} x ⋆ is a local minimum ⟹ "something" holds. They are called necessray because, if we negate the above logical statement, we get,
"something" does not hold ⟹ x ⋆ is not a local minimum. \text{"something" does not hold } \implies \mathbf{x}^{\star} \text{ is not a local minimum.} "something" does not hold ⟹ x ⋆ is not a local minimum. So, “something” is a property that x \mathbf{x} x
The other type is sufficient optimality conditions, which are of the form,
"something" holds ⟹ x ⋆ is a local minimum. \text{"something" holds } \implies \mathbf{x}^{\star} \text{ is a local minimum.} "something" holds ⟹ x ⋆ is a local minimum. They are called sufficient because, if “something” holds, then we are guaranteed that x \mathbf{x} x
Optimality conditions for unconstrained problems (S = R n S = \mathbb{R}^n S = R n
We will start by looking at the necessary condition for optimality in C 1 C^1 C 1
Theorem 3 (Necessary condition for optimality in C 1 C^1 C 1 If f ∈ C 1 f \in C^1 f ∈ C 1 R n \mathbb{R}^n R n
x ⋆ is a local minimum of f on R n ⟹ ∇ f ( x ⋆ ) = 0. \mathbf{x}^{\star} \text{ is a local minimum of } f \text{ on } \mathbb{R}^n \implies \nabla f(\mathbf{x}^{\star}) = 0. x ⋆ is a local minimum of f on R n ⟹ ∇ f ( x ⋆ ) = 0. Proof (Proof of the necessary condition for optimality in C 1 C^1 C 1 We will use proof by contradiction again.
Let x ⋆ \mathbf{x}^{\star} x ⋆ f f f R \mathbb{R} R ∇ f ( x ⋆ ) ≠ 0 \nabla f(\mathbf{x}^{\star}) \neq 0 ∇ f ( x ⋆ ) = 0 p = − ∇ f ( x ⋆ ) ≠ 0 \mathbf{p} = -\nabla f(\mathbf{x}^{\star}) \neq 0 p = − ∇ f ( x ⋆ ) = 0 α ≤ 0 \alpha \leq 0 α ≤ 0 f ( x ⋆ + α p ) f(\mathbf{x}^{\star} + \alpha \mathbf{p}) f ( x ⋆ + α p )
f ( x ⋆ + α p ) = f ( x ⋆ ) + α ∇ f ( x ⋆ ) T p ⏟ − ∇ f ( x ⋆ ) + O ( α ) = f ( x ⋆ ) − α ∇ f ( x ⋆ ) T ∇ f ( x ⋆ ) ⏟ ∥ ∇ f ( x ⋆ ) ∥ 2 + O ( α ) = f ( x ⋆ ) − α ∥ ∇ f ( x ⋆ ) ∥ 2 ⏟ < 0 + O ( α ) \begin{align*}
f(\mathbf{x}^{\star} + \alpha \mathbf{p}) & = f(\mathbf{x}^{\star}) + \alpha \nabla f(\mathbf{x}^{\star})^T \underbrace{\mathbf{p}}_{-\nabla f(\mathbf{x}^{\star})} + \mathcal{O}(\alpha) \newline
& = f(\mathbf{x}^{\star}) - \alpha \underbrace{\nabla f(\mathbf{x}^{\star})^T \nabla f(\mathbf{x}^{\star})}_{\Vert \nabla f(\mathbf{x}^{\star}) \Vert^2 } + \mathcal{O}(\alpha) \newline
& = \underbrace{f(\mathbf{x}^{\star}) - \alpha \Vert \nabla f(\mathbf{x}^{\star}) \Vert^2}_{< 0} + \mathcal{O}(\alpha)
\end{align*} f ( x ⋆ + α p ) = f ( x ⋆ ) + α ∇ f ( x ⋆ ) T − ∇ f ( x ⋆ ) p + O ( α ) = f ( x ⋆ ) − α ∥∇ f ( x ⋆ ) ∥ 2 ∇ f ( x ⋆ ) T ∇ f ( x ⋆ ) + O ( α ) = < 0 f ( x ⋆ ) − α ∥∇ f ( x ⋆ ) ∥ 2 + O ( α ) But, O ( α ) → 0 \mathcal{O}(\alpha) \to 0 O ( α ) → 0 α \alpha α α \alpha α
f ( x ⋆ + α p ) < f ( x ⋆ ) , f(\mathbf{x}^{\star} + \alpha \mathbf{p}) < f(\mathbf{x}^{\star}), f ( x ⋆ + α p ) < f ( x ⋆ ) , which contradicts the local optimality of x ⋆ \mathbf{x}^{\star} x ⋆
Note A quick counterexample to show that the above theorem does not hold for the reverse direction is the function f ( x ) = x 3 f(x) = x^3 f ( x ) = x 3 x ⋆ = 0 x^{\star} = 0 x ⋆ = 0
Now let’s look at the necessary and sufficient conditions for optimality in C 2 C^2 C 2
Theorem 4 (Necessary conditions for optimality in C 2 C^2 C 2 If f ∈ C 2 f \in C^2 f ∈ C 2 R n \mathbb{R}^n R n
x ⋆ is a local minimum of f on R n ⟹ { ∇ f ( x ⋆ ) = 0 ∇ 2 f ( x ⋆ ) ⪰ 0 \mathbf{x}^{\star} \text{ is a local minimum of } f \text{ on } \mathbb{R}^n \implies
\begin{cases}
\nabla f(\mathbf{x}^{\star}) & = \mathbf{0} \newline
\nabla^2 f(\mathbf{x}^{\star}) & \succeq 0
\end{cases} x ⋆ is a local minimum of f on R n ⟹ { ∇ f ( x ⋆ ) ∇ 2 f ( x ⋆ ) = 0 ⪰ 0 Theorem 5 (Sufficient conditions for optimality in C 2 C^2 C 2 If f ∈ C 2 f \in C^2 f ∈ C 2 R n \mathbb{R}^n R n
{ ∇ f ( x ⋆ ) = 0 ∇ 2 f ( x ⋆ ) ≻ 0 ⟹ x ⋆ is a strict local minimum of f on R n \begin{cases}
\nabla f(\mathbf{x}^{\star}) & = \mathbf{0} \newline
\nabla^2 f(\mathbf{x}^{\star}) & \succ 0
\end{cases}
\implies \mathbf{x}^{\star} \text{ is a strict local minimum of } f \text{ on } \mathbb{R}^n { ∇ f ( x ⋆ ) ∇ 2 f ( x ⋆ ) = 0 ≻ 0 ⟹ x ⋆ is a strict local minimum of f on R n Again, for a counterexample to show that the sufficient condition does not hold for the reverse direction, we can use the function f ( x ) = x 4 f(x) = x^4 f ( x ) = x 4 x ⋆ = 0 x^{\star} = 0 x ⋆ = 0
Optimality conditions for constrained problems (S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n
We will now look at optimality conditions for constrained problems. When we dealt with unconstrained problems, we used the fact that we could move in any direction.
But this is not the case for constrained problems, we can only move in directions that keeps us in the feasible set S S S
Let’s define what a feasible and descent direction is.
Definition 3 (Feasible direction) Let x ∈ S \mathbf{x} \in S x ∈ S p ∈ R n \mathbf{p} \in \mathbb{R}^n p ∈ R n feasible direction at the point x \mathbf{x} x
∃ δ > 0 : x + α p ∈ S , ∀ α ∈ [ 0 , δ ] \exists \delta > 0 : \mathbf{x} + \alpha \mathbf{p} \in S, \quad \forall \alpha \in [0, \delta] ∃ δ > 0 : x + α p ∈ S , ∀ α ∈ [ 0 , δ ] Definition 4 (Descent direction) Let x ∈ S \mathbf{x} \in S x ∈ S p ∈ R n \mathbf{p} \in \mathbb{R}^n p ∈ R n descent direction with respect to f f f x \mathbf{x} x
∃ δ > 0 : f ( x + α p ) < f ( x ) , ∀ α ∈ ( 0 , δ ] \exists \delta > 0 : f(\mathbf{x} + \alpha \mathbf{p}) < f(\mathbf{x}), \quad \forall \alpha \in (0, \delta] ∃ δ > 0 : f ( x + α p ) < f ( x ) , ∀ α ∈ ( 0 , δ ] Note
For x ⋆ \mathbf{x}^{\star} x ⋆ feasible descent directions at x ⋆ \mathbf{x}^{\star} x ⋆
Recall that, for two vectors, y , z ∈ R n \mathbf{y}, \mathbf{z} \in \mathbb{R}^n y , z ∈ R n
y T z = ∥ y ∥ ∥ z ∥ cos ( θ ) , \mathbf{y}^T \mathbf{z} = \Vert \mathbf{y} \Vert \Vert \mathbf{z} \Vert \cos(\theta), y T z = ∥ y ∥∥ z ∥ cos ( θ ) , where θ \theta θ y \mathbf{y} y z \mathbf{z} z
If f ∈ C 1 f \in C^1 f ∈ C 1 x \mathbf{x} x ∇ f ( x ) T p < 0 \nabla f(\mathbf{x})^T \mathbf{p} < 0 ∇ f ( x ) T p < 0 p \mathbf{p} p f f f x \mathbf{x} x θ < 90 ∘ \theta < 90^{\circ} θ < 9 0 ∘ − ∇ f ( x ) -\nabla f(\mathbf{x}) − ∇ f ( x )
With this, we can now state the necessary condition for optimality in constrained problems.
Theorem 6 (Necessary condition for optimality in constrained problems) 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 f on S ⟹ ∇ f ( x ⋆ ) T p ≥ 0 , ∀ p feasible direction at x ⋆ \mathbf{x}^{\star} \text{ is a local minimum of } f \text{ on } S \implies \nabla f(\mathbf{x}^{\star})^T \mathbf{p} \geq 0, \quad \forall \mathbf{p} \text{ feasible direction at } \mathbf{x}^{\star} x ⋆ is a local minimum of f on S ⟹ ∇ f ( x ⋆ ) T p ≥ 0 , ∀ p feasible direction at x ⋆
If S S S
x ⋆ is a local minimum of f on S ⟹ ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S \begin{equation}
\mathbf{x}^{\star} \text{ is a local minimum of } f \text{ on } S \implies \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \quad \forall \mathbf{x} \in S
\end{equation} x ⋆ is a local minimum of f on S ⟹ ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S Theorem 7 (Necessary and sufficient condition for optimality in constrained problems) 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 global minimum of f on S ⟺ ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S \mathbf{x}^{\star} \text{ is a global minimum of } f \text{ on } S \iff \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \quad \forall \mathbf{x} \in S x ⋆ is a global minimum of f on S ⟺ ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S Note If S = R n S = \mathbb{R}^n S = R n ∇ f ( x ⋆ ) = 0 \nabla f(\mathbf{x}^{\star}) = 0 ∇ f ( x ⋆ ) = 0
Solution Because, if ∇ f ( x ⋆ ) ≠ 0 \nabla f(\mathbf{x}^{\star}) \neq 0 ∇ f ( x ⋆ ) = 0 p \mathbf{p} p − p -\mathbf{p} − p ∇ f ( x ⋆ ) = 0 \nabla f(\mathbf{x}^{\star}) = 0 ∇ f ( x ⋆ ) = 0
We will now present three additional definitions that are all equivalent to Equation (1) , i.e., a stationary point,
Definition 5 (Stationary point) 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 ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S stationary if,
∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \quad \forall \mathbf{x} \in S ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S Further,
Theorem 8 (Stationary points) 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 f on S ⟹ x ⋆ is stationary . \mathbf{\mathbf{x}^{\star} \text{ is a local minimum of } f \text{ on } S} \implies \mathbf{\mathbf{x}^{\star} \text{ is stationary}}. x ⋆ is a local minimum of f on S ⟹ x ⋆ is stationary . Let’s now define the normal cone .
Definition 6 (Normal cone) Let S ⊆ R n S \subseteq \mathbb{R}^n S ⊆ R n x ∈ S \mathbf{x} \in S x ∈ S normal cone at the point x \mathbf{x} x
N S ( x ) : − { p ∈ R n ∣ p T ( y − x ) ≤ 0 , ∀ y ∈ S } N_S(\mathbf{x}) \coloneq \{ \mathbf{p} \in \mathbb{R}^n \mid \mathbf{p}^T (\mathbf{y} - \mathbf{x}) \leq 0, \quad \forall \mathbf{y} \in S \} N S ( x ) : − { p ∈ R n ∣ p T ( y − x ) ≤ 0 , ∀ y ∈ S } Note
This gives x ⋆ \mathbf{x}^{\star} x ⋆ ⟺ − ∇ f ( x ⋆ ) ∈ N S ( x ⋆ ) \iff -\nabla f(\mathbf{x}^{\star}) \in N_S(\mathbf{x}^{\star}) ⟺ − ∇ f ( x ⋆ ) ∈ N S ( x ⋆ )
Theorem 9 (Equivalent statements for stationary points) 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 ⋆ ∈ S \mathbf{x}^{\star} \in S x ⋆ ∈ S stationary point ,
∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) \geq 0, \quad \forall \mathbf{x} \in S ∇ f ( x ⋆ ) T ( x − x ⋆ ) ≥ 0 , ∀ x ∈ S − ∇ f ( x ⋆ ) ∈ N S ( x ⋆ ) -\nabla f(\mathbf{x}^{\star}) \in N_S(\mathbf{x}^{\star}) − ∇ f ( x ⋆ ) ∈ N S ( x ⋆ ) min x ∈ S ∇ f ( x ⋆ ) T ( x − x ⋆ ) = 0 \underset{\mathbf{x} \in S}{\min} \nabla f(\mathbf{x}^{\star})^T (\mathbf{x} - \mathbf{x}^{\star}) = 0 x ∈ S min ∇ f ( x ⋆ ) T ( x − x ⋆ ) = 0 x ⋆ = p r o j S ( x ⋆ − ∇ f ( x ⋆ ) ) \mathbf{x}^{\star} = \mathrm{proj}_S(\mathbf{x}^{\star} - \nabla f(\mathbf{x}^{\star})) x ⋆ = proj S ( x ⋆ − ∇ f ( x ⋆ )) 