Problem 1.
Consider a two dimensional spacenot. Prove or disprove. ℝ2. Determine whether the following sets are convex or
Hint: Use the triangular inequality: |𝑥 + 𝑦| ≤ |𝑥| + |𝑦|
Problem 2.
Consider the function 𝑓(𝑥1, 𝑥2) = 𝑥12 + 𝑥22 − 4𝑥1𝑥2
Viewprove it.𝑥1as a variable and 𝑥2 as a constant. Determine whether 𝑓 is convex in 𝑥1and
Viewprove it.𝑥2as a variable and 𝑥1 as a constant. Determine whether 𝑓 is convex in 𝑥2 and
Viewin 𝑓: ℝ2and prove it.→ ℝ as a function of the input vector (𝑥1, 𝑥2). Determine whether 𝑓 is convex (𝑥1, 𝑥2)
Hints: For a) and b), treat one variable as a constant, and calculate the second-order derivative of a single-variable function.
For c), calculate the Hessian matrix H first. You may use numpy in Python to calculate the eigenvalue
import numpy as np from numpy import linalg as LA
H = np.array([ [11, 12], [21, 22]]) # your values here eigenval, eigenvec = LA.eig(H)
Print eigenval. If any number is less than or equal to 0, Then, the function is not convex. Otherwise, it is convex. Eigenvalues may also be calculated manually.
The example shows that an element-wise convex function may not be jointly convex.
Problem 3. Suppose is a differentiable convex function. Show that if satisfies the
first-order condition. 𝑓 𝑓
Hint: http://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf
Problem 4. In our proof of local optimality implying global optimality of convex functions, we define λ = 2||𝑦ε−𝑥|| and 𝑧 = (1 − λ)𝑥 + λ𝑦. Prove that 𝑧 is indeed in the ϵ-neighbor of 𝑥.
Hint: Calculate the distance between 𝑥 and 𝑦, and show it’s less than ϵ.
W2 will be due on Sep 28, extended to Sep 30 (combined with the questions in week of Sep 21 -- 23). Please check back next week.
