Numerical Optimization

Unconstrained Optimization (I)

Shirish Shevade

Computer Science and Automation

Indian Institute of Science
Bangalore 560 012, India.

NPTEL Course on Numerical Optimization

Shirish Shevade Numerical Optimization

Global Minimum

Let X ⊆ Rn and f : X → R
Consider the problem,
Constrained optimization problem

min f (x)
x
s.t. x ∈ X

Definition
x∗ ∈ X is is said to be a global minimum of f over X if
f (x∗ ) ≤ f (x) ∀ x ∈ X.

Question: Under what conditions on f and X does the function f attain

its maximum and/or minimum in the set X?

Shirish Shevade Numerical Optimization

 20

16

12
f(x)

0
−2 −1 0 1 2 3 4 5 6

Shirish Shevade Numerical Optimization

Global Minimum

X = R, f : X → R defined as f (x) = x3 .

8000

6000

4000

2000

f(x)
0

−2000

−4000

−6000

−8000
−20 −15 −10 −5 0 5 10 15 20

f attains neither a minimum nor a maximum on X

Note: X is closed, but not bounded; that is, X is not a compact set

Shirish Shevade Numerical Optimization

Constrained Optimization

X = (a, b), f : X → R defined as f (x) = x.

f attains neither a minimum nor a maximum on X

Note:
X is bounded, but not closed; that is, X is not a compact set
f does attain infimum at a and supremum at b

Shirish Shevade Numerical Optimization

Constrained Optimization

X = [−1, 1], f : X → R defined as f (x) = x if −1 < x < 1 and 0

otherwise.

f attains neither a minimum nor a maximum on X

Note:
X is closed and bounded; X is compact
f is not continuous on X

Shirish Shevade Numerical Optimization

Weierstrass’ Theorem

Theorem
Let X ⊂ Rn be a nonempty compact set and f : X → R be a
continuous function on X. Then, f attains a maximum and a minimum
on X; that is, there exist x1 and x2 in X such that

f (x1 ) ≥ f (x) ≥ f (x2 ) ∀x ∈ X.

Note: Weierstrass’ Theorem provides only sufficient conditions for

the existence of optima.

Shirish Shevade Numerical Optimization

Constrained Optimization

X = [a, b], f : X → R

f (x) not continuous; but f attains a minimum

Shirish Shevade Numerical Optimization

Constrained Optimization

X = R, f : X → R defined as f (x) = (x − 2)2 .

20

16

12
f(x)

0
−2 −1 0 1 2 3 4 5 6

f (x) continuous, X not compact; but f attains a minimum

Shirish Shevade Numerical Optimization

Unconstrained Optimization

20

16

12
f(x)

0
−2 −1 0 1 2 3 4 5 6

Shirish Shevade Numerical Optimization

Global Minimum

Let X ⊆ Rn and f : X → R
Consider the problem,
Constrained optimization problem

min f (x)
x
s.t. x ∈ X

Definition
x∗ ∈ X is is said to be a global minimum of f over X if
f (x∗ ) ≤ f (x) ∀ x ∈ X.

Global minimum is difficult to find or characterize for a general

nonlinear function

Shirish Shevade Numerical Optimization

Local Minimum

Let X ⊆ Rn and f : X → R
Consider the problem,
Constrained optimization problem

min f (x)
x
s.t. x ∈ X

Definition
x∗ ∈ X is is said to be a local minimum of f if there is a δ > 0 such
that f (x∗ ) ≤ f (x) ∀ x ∈ X ∩ B(x∗ , δ).

Shirish Shevade Numerical Optimization

Strict Local Minimum

Definition
x∗ ∈ X is is said to be a strict local minimum of f if
f (x∗ ) < f (x) ∀ x ∈ X ∩ B(x∗ , δ), x 6= x∗ .

Shirish Shevade Numerical Optimization

Different Types of Minima

Shirish Shevade Numerical Optimization

Global Minimum and Local Minimum

Every global minimum is also a local minimum.

It may not be possible to identify a global min by finding all
local minima

f does not have a global minimum

Shirish Shevade Numerical Optimization

Optimization Problems
Let X ⊆ Rn and f : X → R
Constrained optimization problem:

min f (x)
x
s.t. x ∈ X

Unconstrained optimization problem:

min f (x)
x∈Rn

Now, consider f : R → R
Unconstrained one-dimensional optimization problem:

min f (x)
x∈R

Shirish Shevade Numerical Optimization

Unconstrained Optimization

Let f : R → R
Unconstrained problem

min f (x)
x∈R

What are necessary and sufficient conditions for a local

minimum?
Necessary conditions: Conditions satisfied by every local
minimum
Sufficient conditions: Conditions which guarantee a local
minimum
Easy to characterize a local minimum if f is sufficiently smooth

Shirish Shevade Numerical Optimization

First Order Necessary Condition
Let f : R → R, f ∈ C 1 .
Consider the problem, minx∈R f (x)
Result (First Order Necessary Condition)
If x∗ is a local minimum of f , then f 0 (x∗ ) = 0.
Proof.
Suppose f 0 (x∗ ) > 0. f ∈ C 1 ⇒ f 0 ∈ C 0 .
Let D = (x∗ − δ, x∗ + δ) be chosen such that f 0 (x) > 0 ∀ x ∈ D.
Therefore, for any x ∈ D, using first order truncated Taylor series,

f (x) = f (x∗ ) + f 0 (x̄)(x − x∗ ) where x̄ ∈ (x∗ , x).

Choosing x ∈ (x∗ − δ, x∗ ) we get,

f (x) < f (x∗ ), a contradiction.

Similarly, one can show, f (x) < f (x∗ ) if f 0 (x∗ ) < 0.

Shirish Shevade Numerical Optimization
First Order Necessary Condition
20 2

16
−2

−4

12
−6
f(x)

f(x)
−8
8

−10

−12
4

−14

0 −16
−2 −1 0 1 2 3 4 5 6 −4 −3 −2 −1 0 1 2 3 4

x x

f (x) = (x − 2)2 f (x) = −x2

f 0 (2) = 0 f 0 (0) = 0

Slope of the function is zero at local minimum and also at local

maximum

Shirish Shevade Numerical Optimization

First Order Necessary Condition
20 8000

6000

16
4000

2000
12
f(x)

f(x)
0

8
−2000

−4000
4

−6000

0 −8000
−2 −1 0 1 2 3 4 5 6 −20 −15 −10 −5 0 5 10 15 20

x x

f (x) = (x − 2)2 f (x) = x3

f 0 (2) = 0 f 0 (0) = 0

Slope of the function is zero at a saddle point

Shirish Shevade Numerical Optimization

Stationary Points

Let f : R → R, f ∈ C 1 .
Consider the problem, minx∈R f (x).
Definition
x∗ is called a stationary point if f 0 (x∗ ) = 0.

f 0 (x∗ ) = 0 is a necessary but not sufficient condition for a local

minimum.

Question: How do we ensure that a stationary point is a local

minimum?

Shirish Shevade Numerical Optimization

Second Order Necessary Conditions

20 2

16
−2

−4

12
−6
f(x)

f(x)
−8
8

−10

−12
4

−14

0 −16
−2 −1 0 1 2 3 4 5 6 −4 −3 −2 −1 0 1 2 3 4

x x

f (x) = (x − 2)2 , f 0 (2) = 0 f (x) = −x2 , f 0 (0) = 0

f 00 (2) = 4 f 00 (0) = −2

Shirish Shevade Numerical Optimization

Second Order Necessary Conditions
Let f : R → R, f ∈ C 2 .
Consider the problem, minx∈R f (x)
Result (Second Order Necessary Conditions)
If x∗ is a local minimum of f , then f 0 (x∗ ) = 0 and f 00 (x∗ ) ≥ 0.
Proof.
By the first order necessary conditions, f 0 (x∗ ) = 0.
Suppose f 00 (x∗ ) < 0. Now, f ∈ C 2 ⇒ f 00 ∈ C 0 .
Let D = (x∗ − δ, x∗ + δ) be chosen such that f 00 (x) < 0 ∀ x ∈ D.
Therefore, for any x ∈ D, using second order truncated Taylor series,
1
f (x) = f (x∗ ) + f 0 (x∗ )(x − x∗ ) + f 00 (x̄)(x − x∗ )2 where x̄ ∈ (x∗ , x).
2
Using f 0 (x∗ ) = 0 and f 00 (x̄) < 0 ∀ x ∈ D, we get,

f (x) < f (x∗ ), a contradiction.

Shirish Shevade Numerical Optimization

Second Order Sufficient Conditions

Are the second order necessary conditions also sufficient?

No
Example: min x3 subject to x ∈ R
At x∗ = 0, f 0 (x∗ ) = f 00 (x∗ ) = 0; but x∗ is a saddle point!

8000

6000

4000

2000
f(x)

−2000

−4000

−6000

−8000
−20 −15 −10 −5 0 5 10 15 20

f (x) = x3
f 0 (0) = f 00 (0) = 0

Shirish Shevade Numerical Optimization

Second Order Sufficient Conditions
Let f : R → R, f ∈ C 2 .
Consider the problem, minx∈R f (x)
Result (Second Order Sufficient Conditions)
If x∗ ∈ R such that f 0 (x∗ ) = 0 and f 00 (x∗ ) > 0, then x∗ is a strict local
minimum of f over R.
Proof.
f ∈ C 2 ⇒ f 00 ∈ C 0 .
Let D = (x∗ − δ, x∗ + δ) be chosen such that f 00 (x) > 0 ∀ x ∈ D.
Therefore, for any x ∈ D, using second order truncated Taylor series,
1
f (x) = f (x∗ ) + f 0 (x∗ )(x − x∗ ) + f 00 (x̄)(x − x∗ )2 where x̄ ∈ (x∗ , x).
2
Therefore, f 0 (x∗ ) = 0 ⇒ f (x) − f (x∗ ) = 12 f 00 (x̄)(x − x∗ )2 > 0.
That is, f (x) > f (x∗ ) ∀ x ∈ D ⇒ x∗ is a strict local minimum.

Shirish Shevade Numerical Optimization

Second Order Sufficient Conditions

Note: Second order sufficient conditions

guarantee that the local minimum is strict, and
are not necessary. (For f (x) = x4 , x∗ = 0 is a strict local
minimum; but f 0 (x∗ ) = f 00 (x∗ ) = 0.)

Shirish Shevade Numerical Optimization

Sufficient Optimality Conditions

Let f : R → R, f ∈ C ∞ .
Let us assume that f is not a constant function.
Let the k-th derivative of f at x be denoted by f (k) (x).
Consider the problem, minx∈R f (x).

Result
x∗ is a local minimum if and only if the first non-zero element of the
sequence {f (k) (x∗ )} is positive and occurs at even positive k.

Result
Consider the problem, maxx∈R f (x). x∗ is a local maximum if and
only if the first non-zero element of the sequence {f (k) (x∗ )} is
negative and occurs at even positive k.

Shirish Shevade Numerical Optimization

Example 1

Consider the problem,

min (x2 − 1)2

x∈R

Find the stationary points of f (x) = (x2 − 1)2

f 0 (x) = 0 ⇒ 4x(x2 − 1) = 0 ⇒ f 0 (0) = f 0 (1) = f 0 (−1) = 0

Second Derivatives
f 00 (1) = f 00 (−1) = 8 > 0 ⇒ 1 and −1 are strict local minima
f 00 (0) = −4 < 0 ⇒ 0 is a strict local maximum

Shirish Shevade Numerical Optimization

Example 2

Consider the problem,

min (x2 − 1)3

x∈R

Find the stationary points of f (x) = (x2 − 1)3

f 0 (x) = 0 ⇒ 6x(x2 − 1)2 = 0 ⇒ f 0 (0) = f 0 (1) = f 0 (−1) = 0

Second Derivative: f 00 (x) = 6(x2 − 1)(5x2 − 1)

f 00 (0) = 6 > 0 ⇒ 0 is a strict local minimum
f 00 (1) = f 00 (−1) = 0 ⇒ Higher order derivatives need to be
considered
Third derivative: f 000 (x) = 12(4x + 1)(x2 − 1) + 48x3

f 000 (1) = 48 > 0


⇒ 1 and − 1 are saddle points
f 000 (−1) = −48 < 0

Shirish Shevade Numerical Optimization

Example 3

Consider the problem, minx∈R x4

Find the stationary points of f (x) = x4

f 0 (x) = 0 ⇒ 4x3 = 0 ⇒ f 0 (0) = 0

Second Derivative: f 00 (x) = 12x2

f 00 (0) = 0
Third Derivative: f 000 (x) = 24x
f 000 (0) = 0
Fourth Derivative: f 0000 (x) = 24
f 0000 (0) = 24
f 0 (0) = f 00 (0) = f 000 (0) = 0, f 0000 (0) = 24 > 0
⇒ 0 is a strict local minimum

Shirish Shevade Numerical Optimization

Necessity of an Algorithm

Consider the problem

min (x − 2)2
x∈R

We first find the stationary points (which satisfy f 0 (x) = 0).

f 0 (x) = 0 ⇒ 2(x − 2) = 0 ⇒ x∗ = 2.

f 00 (2) = 2 > 0 ⇒ x∗ is a strict local minimum.

Stationary points are found by solving a nonlinear equation,

g(x) ≡ f 0 (x) = 0.

Finding the real roots of g(x) may not be always easy.

Consider the problem to minimize f (x) = x2 + ex .
g(x) = 2x + ex
Need an algorithm to find x which satisfies g(x) = 0.
Shirish Shevade Numerical Optimization