Scribd
Upload
3 views2 pages

Convexity and Optimization Tutorial

The document contains a tutorial with questions on convexity, Hooke's law, and optimization. It includes proofs for the convexity of the function f(x) = x^4, the calculation of the spring constant using least squares, and the uniqueness of global minimizers for strictly convex functions. Additionally, it determines the range of α for strict convexity in a quadratic function involving two variables.

Uploaded by

zybernex
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
3 views2 pages

Convexity and Optimization Tutorial

The document contains a tutorial with questions on convexity, Hooke's law, and optimization. It includes proofs for the convexity of the function f(x) = x^4, the calculation of the spring constant using least squares, and the uniqueness of global minimizers for strictly convex functions. Additionally, it determines the range of α for strict convexity in a quadratic function involving two variables.

Uploaded by

zybernex
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

Tutorial 1

Lecturer: N. Monshizadeh

7 February 2025

Question 1 i) Prove that f (x) = x4 is convex by computing its second derivative. ii) Prove that f is in
fact strictly convex.
2
i) ∂ ∂x
f (x)
2 = 12x2 ≥ 0. =⇒ f (x) is convex
2
ii) Let g(x) := x2 ; thus, ∂ ∂x
g(x)
2 = 2 > 0 =⇒ x2 is strictly convex =⇒ (αx + βy)2 < αx2 + βy 2 where
n
α ∈ [0, 1], β = 1 − α and x, y ∈ R . By using twice this fact:

f (αx + βy) = (αx + βy)4 = ((αx + βy)2 )2


< (αx2 + βy 2 )2
< α(x2 )2 + β(y 2 )2 = αx4 + βy 4

Question 2 Hooke’s law states that the force f needed to extend or compress a spring by some distance
x scales proportionally to that distance, namely f = kx, where the constant k indicates the stiffness of the
spring. For a given spring, we did some experiments and collected the data as
     
f1 f2 f3
, ,
x1 x2 x3

for some positive numbers fi and xi with i = 1, 2, 3. Assuming that the spring approximately satisfies the
Hooke’s law, compute its constant k in terms of the collected data.
Hint: Use the least square method
Let ei := fi − kxi . Then, we use
3
X 3
X
Minimizek∈R e2i = Minimizek∈R (fi − kxi )2
i=1 i=1

To find the minimizer, we write


P3 2 3
∂ i=1 ei
X
= 0 =⇒ −2 xi (fi − kxi ) = 0
∂k i=1

The solution of the minimization problem is


P3
xi fi
k ∗ = Pi=1
3 2
i=1 xi

Question 3 Assume that f is strictly convex. Then prove that the global minimizer of

Minimizex∈Rn f (x)

if exists is unique. (This means that there is at most one optimal solution)

1
We prove the result by contradiction. Assume x and x̂, with x 6= x̂ are both global minimizers (optimal
solutions) to the optimization problem above. Then,

∂f ∂f
(x) = 0, and (x̂) = 0
∂x ∂x

Also, consider the underestimator property of strict convex functions (f (y) > f (x) + (y − x)T ∂f∂x
(x)
). If we
write this property for (x, x̂) and (x̂, x), we get

∂f
(x, x̂) =⇒ f (x̂) > f (x) + (x̂ − x)T (x)
∂x
∂f
(x̂, x) =⇒ f (x) > f (x̂) + (x − x̂)T (x̂)
∂x
∂f ∂f
By employing the assumption (x) = 0, (x̂) = 0, we have
∂x ∂x
f (x̂) > f (x), f (x) > f (x̂)

This is clearly a contradiction, which shows that not more than one optimal solution may exist in this case.

Question 4 Determine the range of α such that f (x1 , x2 ) = x21 + 2x22 + αx1 x2 is strictly convex.
For this question, we use the following fact for 2 × 2 matrices:
 
a b
> 0 ⇐⇒ a > 0 and ad > bc
c d

∂2f
It is sufficient to find the range of α such that > 01 We have
∂x2
∂2f
   
∂f 2x1 + αx2 2 α
(x) = =⇒ =
∂x 4x2 + αx1 ∂x2 α 4

As a result, α should satisfy √ √


8 > α2 =⇒ −2 2 < α < 2 2

1 Since f is a quadratic function, the condition is also necessary.

Page 2

You might also like