Convexity and Optimization

Convexity and Optimization

Richard Lusby

DTU Management Engineering

Class Exercises From Last Time

Today’s Material

•Extrema

•Convex Function

•Convex Sets

•Other Convexity Concepts

•Unconstrained Optimization

Extrema

Problem

max f(x)s.t. x∈S

max{f(x) :x∈S}

•Global maximumx^∗

f(x^∗)≥f(x) ∀x∈S

•Local maximumx^o:

f(x^o)≥f(x) ∀xin a neighborhood aroundx^o

•strictmaximum/minimum defined similarly

Weierstrass theorem:

Theorem

A continuous function achieves its max/min on a closed and bounded set

Supremum and Infimum

Supremum

The supremum of a setS having a partial order is the least upper bound ofS (if it exists) and is denoted supS.

Infimum

The infimum of a setS having a partial order is the greatest lower bound ofS (if it exists) and is denoted infS.

•If the extrema are not achieved:

•max→sup

•min →inf

•Examples

Finding Optimal Solutions

Every method for finding and characterizing optimal solutions is based on

- either

or

Necessary Condition

A conditionC1(x)isnecessaryifC1(x^∗)is satisfied by every optimal solution x^∗(and possibly some other solutions as well).

Sufficient Condition

A conditionC2(x)issufficientifC2(x^∗)ensures thatx^∗ is optimal (but some optimal solutions may not satisfyC2(x^∗).

Mathematically

{x|C2(x)} ⊆ {x|xoptimal solution} ⊆ {x|C1(x)}

Finding Optimal Solutions

An example of a necessary condition in the case

is “well-behaved”

Feasible Direction

Considerx^o∈S, s∈Rⁿ is called afeasibledirection if there exists (s)>0 such that

x^o+s∈S ∀: 0< ≤(s)

We denote the

of feasible directions from

in

as

)

s∈Rⁿ is called animprovingdirection if there exists (s)>0 such that f(x^o+s)< f(x^o) ∀: 0< ≤(s)

Finding Optimal Solutions

Local Optima

Ifx^o is a local minimum, then there existnos∈S(x^o)for which f(.) decreases alongs, i.e. for which

f(x^o+2s)< f(x^o+1s)for0≤1< 2≤(s)

Stated otherwise: A necessary condition for local optimality is

(x

)

) =

Improving Feasible Directions

If for a given direction

it holds that

∇f(x^o)s <0

Then

is an improving direction

Well known necessary condition for local optimality of

for a differentiable function:

∇f(x^o) = 0

In other words,

is

with respect to

What if stationarity is not enough?

•Supposef is twice continuously differentiable

•Analyse the Hessian matrix forf atx^o

∇²f(x^o) =

∂²(f(x^o))

∂xi∂xj

, i, j= 1, . . . , n

Sufficient Condition

If∇f(x^o) = 0and∇²f(x^o)ispositive definite:

x^T∇²f(x^o)x>0 ∀ x∈Rⁿ\{0} thenx^o is a local minimum

What if Stationarity is not Enough?

•A necessary condition for local optimality is “Stationarity +positive semidefinitenessof∇²f(x^o)”

•Note that positive definiteness is not a necessary condition

•E.g. look at f(x) =x⁴ forx^o= 0

•Similar statements hold for maximization problems

•Key concept here is negative definiteness

Definiteness of a Matrix

•A number of criteria regarding the definiteness of a matrix exist

•A symmetricn×nmatrixAispositive definiteif and only if x^TAx>0 ∀x∈Rⁿ\{0}

•Positive semidefiniteis defined likewise with⁰⁰≥⁰⁰ instead of⁰⁰>⁰⁰

•Negative (semi) definiteis defined by reversing the inequality signs to⁰⁰<⁰⁰and

00≤⁰⁰, respectively.

Necessary

conditions for positive definiteness:

•Ais regular withdet(A)>0

•A⁻¹ is positive definite

Definiteness of a Matrix

Necessary+Sufficient

conditions for positive definiteness:

•Sylvestor’s Criterion: All principal submatrices have positive determinants

(a11) a11 a12

a21 a22

!







a11 a12 a13

a21 a22 a23

a31 a32 a33







•All eigenvalues ofAare positive

Necessary and Sufficient Conditions

Theorem

Suppose thatf(.)is differentiable at a local minimumx^o. Then∇f(x^o)s≥0for s∈S(x^o). Iff(.)is twice differentiable atx^o and∇f(x^o) = 0, then

s^T∇²f(x^o)s≥0∀s∈S(x^o)

Theorem

Suppose thatS is convex and non-empty,f(.)differentiable, and thatx^o∈S.

Suppose furthermore thatf(.)is convex.

•x^ois a local minimum if and only ifx^o is a global minimum

•x^ois a local (and hence global) minimum if and only if

∇f(x^o)(x−x^o)≥0∀x∈S

Convex Combination

Convex combination

Theconvex combinationof two points is the line segment between them α1x1+α2x2forα1, α2≥0andα1+α2= 1

Convex function

Convex Functions

A convex function lies below itschord

f(α1x₁+α2x₂)≤α1f(x1) +α2f(x2)

•Astrictlyconvex function has no more than one minimum

•Examples: y=x²,y=x⁴,y=x

•The sum of convex functions is also convex

•A differentiable convex function lies above its tangent

•A differentiable function is convex if its Hessian is positive semi-definite

•Strictly convex not analogous!

•A functionf is concaveiff−f is convex

EOQ objective function: T(Q) =dK/Q+cd+hQ/2?

Convex function

Convex Functions

A convex function lies below itschord

f(α1x₁+α2x₂)≤α1f(x1) +α2f(x2)

•Astrictlyconvex function has no more than one minimum

•Examples: y=x²,y=x⁴,y=x

•The sum of convex functions is also convex

•A differentiable convex function lies above its tangent

•A differentiable function is convex if its Hessian is positive semi-definite

•Strictly convex not analogous!

•A functionf is concaveiff−f is convex

Economic Order Quantity Model

The problem

TheEconomic Order Quantity Model is an inventory model that helps manafacturers, retailers, and wholesalers determine how they should optimally replenish their stock levels.

Costs

•K= Setup cost for odering one batch

•c= unit cost for producing/purchasing

•h= holding cost per unit per unit of time in inventory

Assumptions

•d= A known constant demand rate

•Q= The order quantity (arrives all at once)

Convex sets

Definition

Aconvex setcontains all convex combinations of its elements α1x1+α2x2∈S ∀ x1,x2∈S

•Some examples of E.g. (1,2],x²+y²<4,∅

•Level curve (2 dimensions):

{(x, y) :f(x, y) =β}

•Level set:

{x:f(x)≤β}

Lower Level Set Example

x₂ x₁

x1+x2≤3 x1+ 3x2≤7

Lower Level Set Example

y₂ y₁

y1+y2≥1 y1+ 3y2≥2

Upper Level Set Example

−

4

−

2

0 2

4

4

2

0 2 4

0 100

x y

z

Plot of 2x

+ 4y

0

50

100

150

Upper Level Set Example

140 140

130

130 120130

120 110

110

100

100 100 100

90 90

90

90 90

90

80 80

80

80 80

80

70 70

70

70 70

70

60

60

60 60

60

50 60 50

50

50

50 50

50 40

40

40

40 40 40

30

30

30

30 30

20

20

20 20

10 10

10

−

4

−

2 0 2 4

y

Plot of 2x

+ 4y

Example

0

2

4 0

2

4 0

100 200

x y

z

Plot of 54x +

9x

+ 78y

13y

0

50

100

150

Example

180

180

180 180 160 160

160

160

160

160 140 140

140

140 140

120

120

120

120

120 100

100 100

100

80 80

20 60

1 2 3 4 5

y

Plot of 54x +

9x

+ 78y

13y

Convexity, Concavity, and Optima

Theorem

Suppose thatS is convex and thatf(x)is convex onS for the problem minx∈Sf(x), then

•Ifx^∗ is locally minimal, thenx^∗ is globally minimal

•The setX^∗of global optimal solutions is convex

•Iff is strictly convex, then x^∗is unique

Examples

Problem 1

Minimize −x2lnx1+^x₉¹ +x²₂ Subject to: 1.0≤x1≤5.0 0.6≤x2≤3.6

What does the function look like?

−

2

0 2

2

0

−

1 2 0 1

x

y

z

z=_exp(x^7xy2+y²)

−

1

−

0.5

0

0.5

1

Problem 2

Minimize P3

i=1−ilnxi

Subject to: P3

i=1xi = 6

xi ≤3.5i= 1,2,3 xi ≥1.5i= 1,2,3

Class exercises

•Show thatf(x) =||x||=pP

ix²_i is convex

•Prove that any level set of a convex function is a convex set

Other Types of Convexity

•The idea ofpseudoconvexityof a function is to extend the class of functions for which stationarity is a sufficient condition for global optimality. Iff is defined on an open setX and is differentiable we define the concept of pseudoconvexity.

•A differentiable functionf ispseudoconvexif

∇f(x)·(x⁰−x)≥0⇒f(x⁰)≥f(x) ∀x, x⁰∈X

•or alternatively ..

f(x⁰)< f(x)⇒ ∇f(x)(x⁰−x)<0 ∀x, x⁰∈X

•A functionf is pseudoconcaveiff −f is pseudoconvex

•Note that iff is convex and differentiable, andX is open, thenf is also

Other Types of Convexity

•A function isquasiconvexif all lower level sets are convex

•That is, the following sets are convex

S⁰={x:f(x)≤β}

•A function isquasiconcaveif all upper level sets are convex

•That is, the following sets are convex

S⁰={x:f(x)≥β}

•Note that iff is convex and differentiable, andX is open, thenf is also quasiconvex

•Convexity properties

Convex ⇒ pseudoconvex ⇒ quasiconvex

Exercises

Show the following

•f(x) =x+x³ ispseudoconvexbut notconvex

•f(x) =x³ isquasiconvexbut not pseudoconvex

Graphically

1.2

1.2

1

1

0.8

0.8

0.6 0.6

0.6 0.6

0.4

0.4 0.4

0.4

0.2 0.2

0.2

0.2 0.2

0.2

0

00

0

−0.2

−0.2

−0.2

−0.2

−0.2

−0.2

−0.4

−0.4

−0.4

−0.4

−0.6

−0.6

−0.6

−0.6

−0.8

−0.8

−1

−1

−1.2

−1.2

−

2

1 0 1 2

−

2

−

1 0 1 2

y

z=_exp(x^7xy2+y²)

Exercises

Convexity Questions

•Can a function be both convex and concave?

•Is a convex function of a convex function convex?

•Is a convex combination of convex functions convex?

•Is the intersection of convex sets convex?

Unconstrained problem

min

(x) s.t.

•Necessaryoptimality condition for x^o to be a local minimum

∇f(x^o) = 0andH(x^o)is positive semidefinite

•Sufficientoptimality condition forx^oto be a local minimum

∇f(x^o) = 0andH(x^o)is positive definite

•Necessary and sufficient

•Supposef is pseudoconvex

•x^∗ is a global minimum iff∇f(x^∗) = 0

Unconstrained example

min

(x) = (x

1)

•f⁰(x) = 6x(x²−1)²= 0 forx= 0,±1

•H(x) = 24x²(x²−1) + 6(x²−1)²

•H(0) = 6 andH(±1) = 0

•Thereforex= 0is a local minimum (actually the global minimum)

•x=±1are saddle points

What does the function look like?

1 2

3 4

5 1 2

3 4

5 0

20

x1 x2

f

(

)

Plot of

) +

+

0

5

10

15

20

25

Class Exercise

Problem

SupposeAis anm∗nmatrix,bis a givenmvector, find min||Ax−b||²

Richard M. Lusby

DTU Management Engineering, Technical University of Denmark

Building 424, Room 208 rmlu@dtu.dk

2800 Kgs. Lyngby, Denmark phone +45 4525 3084 http://www.man.dtu.dk