Cmput 466 Assignment 2

Problem 1.
Consider a two dimensional space ℝ . Determine whether the following sets are convex or
2
not. Prove or disprove.
● {(𝑥
1
, 𝑥
2
): 𝑥
1
2
+ 𝑥
2
2 = 1}
● {(𝑥
1
, 𝑥
2
): |𝑥
1
| + |𝑥
2
| ≤ 1}
Hint: Use the triangular inequality: |𝑥 + 𝑦| ≤ |𝑥| + |𝑦|
Problem 2.
Consider the function 𝑓(𝑥
1
, 𝑥
2
) = 𝑥
1
2
+ 𝑥
2
2 − 4𝑥
1
𝑥
2
a) View 𝑥 as a variable and as a constant. Determine whether is convex in and
1
𝑥
2
𝑓 𝑥
1
prove it.
b) View 𝑥 as a variable and as a constant. Determine whether is convex in and
2
𝑥
1
𝑓 𝑥
2
prove it.
c) View 𝑓: ℝ as a function of the input vector . Determine whether is convex
2
→ ℝ (𝑥
1
, 𝑥
2
) 𝑓
in (𝑥 and prove it.
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 λ = and . Prove that is indeed in the -neighbor of .
ε
2||𝑦−𝑥||
𝑧 = (1 − λ)𝑥 + λ𝑦 𝑧 ϵ 𝑥
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.