Fundamentals of Data Science
ENMG 606
Review on Numerical Optimization
Unconstrained Optimization
Mathematical Formulation:
Course number and name 2
Unconstrained Optimization
Mathematical Formulation:
Objective function
Course number and name 3
Unconstrained Optimization
Mathematical Formulation:
Objective function
Constraints/feasibility set
Course number and name 4
Unconstrained Optimization
Mathematical Formulation:
Objective function
Constraints/feasibility set Decision Variables
Course number and name 5
Functions
A function 𝑓 is a mapping from one domain to another
Course number and name 6
Functions
A function 𝑓 is a mapping from one domain to another
takes vector 𝒙 ∈ ℝ𝑛 and returns a scalar ℝ.
Course number and name 7
Functions
A function 𝑓 is a mapping from one domain to another
takes vector 𝒙 ∈ ℝ𝑛 and returns a scalar ℝ.
Examples:
▪ Linear Functions:
Course number and name 8
Functions
A function 𝑓 is a mapping from one domain to another
takes vector 𝒙 ∈ ℝ𝑛 and returns a scalar ℝ.
Examples:
▪ Linear Functions:
▪ Quadratic Functions:
Course number and name 9
Gradient
The gradient of a multi-variate function
Course number and name 10
Gradient
The gradient of a multi-variate function
Examples:
▪ Linear Functions:
Course number and name 11
Gradient
The gradient of a multi-variate function
Examples:
▪ Linear Functions:
Course number and name 12
Gradient
The gradient of a multi-variate function
Examples:
▪ Linear Functions:
▪ Quadratic Functions:
Course number and name 13
Gradient
The gradient of a multi-variate function
Examples:
▪ Linear Functions:
▪ Quadratic Functions:
Course number and name 14
Hessian
The Hessain of a multi-variate function
Course number and name 15
Hessian
The Hessain of a multi-variate function
This matrix
is always
symmetric
Course number and name 16
Hessian
The Hessain of a multi-variate function
This matrix
is always
symmetric
Examples:
▪ Linear Functions:
Course number and name 17
Hessian
The Hessain of a multi-variate function
This matrix
is always
symmetric
Examples:
▪ Linear Functions:
Course number and name 18
Hessian
The Hessain of a multi-variate function
This matrix
is always
symmetric
Examples:
▪ Linear Functions:
▪ Quadratic Functions:
Course number and name 19
Hessian
The Hessain of a multi-variate function
This matrix
is always
symmetric
Examples:
▪ Linear Functions:
▪ Quadratic Functions:
Course number and name 20
Example
Course number and name 21
Example
Course number and name 22
Example
Course number and name 23
Convex Functions
We say 𝑓 is convex if for all 𝒙, 𝒚, 𝛼 ∈ [0,1] we have
Course number and name 24
Convex Functions
We say 𝑓 is convex if for all 𝒙, 𝒚, 𝛼 ∈ [0,1] we have
Graphically:
Course number and name 25
Convex Functions
We say 𝑓 is convex if for all 𝒙, 𝒚, we have
Course number and name 26
Convex Functions
We say 𝑓 is convex if for all 𝒙, 𝒚, we have
Graphically:
Course number and name 27
Convex Functions
We say 𝑓 is convex if for all 𝒙, 𝒚, we have
Graphically:
We say 𝑓 is convex if for all 𝒙, we have
Course number and name 28
Examples of Convex Functions
Course number and name 29
Examples of Convex Functions
Course number and name 30
Examples of Convex Functions
Convex
Course number and name 31
Examples of Convex Functions
Convex
Course number and name 32
Examples of Convex Functions
Convex
Course number and name 33
Examples of Convex Functions
Convex
Convex
Course number and name 34
Examples of Convex Functions
Convex
Convex
Course number and name 35
Examples of Convex Functions
Convex
Convex
Course number and name 36
Examples of Convex Functions
Convex
Convex
Convex
Course number and name 37
Examples of Convex Functions
Convex
Convex
Convex
with
Course number and name 38
Examples of Convex Functions
Convex
Convex
Convex
with
Course number and name 39
Examples of Convex Functions
Convex
Convex
Convex
Convex
with
Course number and name 40
Convex Sets
A set 𝒳 is convex if 𝛼𝒙 + 1 − 𝛼 𝒚 ∈ 𝒳 for all 𝒙, 𝒚 ∈ 𝒳 , 𝛼 ∈ 0,1 .
Course number and name 41
Convex Sets
A set 𝒳 is convex if 𝛼𝒙 + 1 − 𝛼 𝒚 ∈ 𝒳 for all 𝒙, 𝒚 ∈ 𝒳 , 𝛼 ∈ 0,1 .
In simple words, if 𝒙 and 𝒚 belong to a convex set, then all points on the line segment between 𝒙 and 𝒚
are also in the set.
Course number and name 42
Unconstrained Optimization
Mathematical Formulation:
Objective function
Constraints/feasibility set Decision Variables
When the objective function and feasibility set are both convex, we say the optimization problem is convex.
Course number and name 43
Local/Global Solutions
We say 𝒙∗ is a global minimum if 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 ∈ ℝ.
Course number and name 44
Local/Global Solutions
We say 𝒙∗ is a global minimum if 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 ∈ ℝ.
We say 𝒙∗ is a local minimum if there exists 𝛿 > 0 such that 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 with ||𝒙 − 𝒙∗ || ≤ 𝛿.
Course number and name 45
Local/Global Solutions
We say 𝒙∗ is a global minimum if 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 ∈ ℝ.
We say 𝒙∗ is a local minimum if there exists 𝛿 > 0 such that 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 with ||𝒙 − 𝒙∗ || ≤ 𝛿.
Local Maximum Global Maximum
Global Minimum Local Minimum
Course number and name 46
Local/Global Solutions
We say 𝒙∗ is a global minimum if 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 ∈ ℝ.
We say 𝒙∗ is a local minimum if there exists 𝛿 > 0 such that 𝑓 𝒙∗ ≤ 𝑓 𝒙 for all 𝒙 with ||𝒙 − 𝒙∗ || ≤ 𝛿.
Local Maximum Global Maximum
Do such point always exist?
If not provide an example.
Global Minimum Local Minimum
Course number and name 47