Scribd
Upload
32 views12 pages

Convex Functions in Optimization

The document discusses definitions of convex functions. It defines a convex function as one where the line segment between any two points on the graph of the function lies above the graph. Alternatively, a function is convex if its Hessian matrix is positive semidefinite, or if it is underestimated by its affine approximation. The gradient of a convex function is monotone, as proven using the three definitions of convexity.

Uploaded by

apeelec10337
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views12 pages

Convex Functions in Optimization

The document discusses definitions of convex functions. It defines a convex function as one where the line segment between any two points on the graph of the function lies above the graph. Alternatively, a function is convex if its Hessian matrix is positive semidefinite, or if it is underestimated by its affine approximation. The gradient of a convex function is monotone, as proven using the three definitions of convexity.

Uploaded by

apeelec10337
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Lecture 4

EE 506: Engineering Mathematics

UET, Lahore

November 3, 2023
Outline

Convex Functions

Convex Functions 2
Definition 1

Consider an optimization problem

minimize x)
f (x
subject to x∈Ω

where f : Rn → R is the objective function and Ω ⊆ Rn is a convex set.


Then, f is a convex function if ∀x
x, y and ∀α ∈ [0, 1], we have

x + (1 − α)yy ) ≤ αf (x
f (αx x) + (1 − α)f (yy )

Convex Functions 3
Definition 1

x + (1 − α)yy ) ≤ αf (x
f (αx x) + (1 − α)f (yy )

Figure: Geometric interpretation

Convex Functions 4
Definition 2

If f : Rn → R is a continuously differentiable function or its gradient


exists, then it is a convex function if it is underestimated by an affine
approximation. In other words, f is convex if ∀x x, y , we have

f (yy ) ≥ f (x
x) + h∇f (x
x), y − x i

Convex Functions 5
Definition 2

f (yy ) ≥ f (x
x) + h∇f (x
x), y − x i

Figure: Geometric interpretation

Convex Functions 6
Definition 3

If f : Rn → R is a twice differentiable function (f ∈ C 2 ), then it is a


convex function if its Hessian matrix is positive semidefinite.

∇2 f (x
x)  0

Convex Functions 7
Definition 3

∇2 f (x
x)  0

Figure: Geometric interpretation

Convex Functions 8
Example: Quadratic Function

x) = x >Qx where Q  0 is a positive semidefinite matrix. Apply


Let f (x
all three definitions to establish the convexity of f
I Definition 3: ∇2 f (x x) = 2QQ  0 . Hence, it is a convex function.

I Definition 2:
?
f (yy ) ≥ f (x
x) + h∇f (x
x), y − x i, ∀yy
?
y >Qy
y Qy x>Qx
≥ x Qx + h2Qx
Qx, y − x i
Qx
?
y >Qy ≥ x >Qx + 2x x>Q (yy − x )
y >Qy − 2x
x>Qy + x >Qx >
= (yy − x ) Q (yy − x )
≥ 0

Convex Functions 9
Monotonic Gradient

If f : Rn → R is a convex function, then its gradient is monotone:

h∇f (x
x) − ∇f (yy ), x − y i ≥ 0

(Use Definition 2 to prove it)

Convex Functions 10
Definition 3 Implies Monotonic Gradient

If ∇2 f (x
x)  0 then it implies that its gradient is monotone:

h∇f (x
x) − ∇f (yy ), x − y i ≥ 0

Recall fundamental theorem of calculus


Z 1
F 0 (t)dt = F (1) − F (0)
0

Applying this with chain rule


R1
x − y )> ∇f (tx
(x x + (1 − t)yy )dt
R01 d
= 0 dt (∇f (t(x x − y ) + y )) dt
= ∇f (x x) − ∇f (yy )

Convex Functions 11
Definition 3 Implies Monotonic Gradient

R1
x − y )> ∇2 f (tx
(x x + (1 − t)yy )dt
R01 d
= 0 dt (∇f (t(x x − y ) + y )) dt
= ∇f (xx) − ∇f (yy )
x − y ):
Take inner product with (x
Z 1
x − y )> ∇2 f (tx
(x x + (1 − t)yy )(x
x − y )dt
0
= h∇f (x
x) − ∇f (yy ), x − y i

The LHS is ≥ 0 which means that RHS is also ≥ 0

Convex Functions 12

You might also like