Overview
- Prove that if g(x) : Rd → R is convex and f(x) : R → R is convex and non-decreasing then f(g(x)) is convex.
- Show that f(x) = x3 is not Lipshitz differentiable.
- Recall the least squares problem x∗ = argmin∥Ax−b∥2 and let f(x) = ∥Ax−b∥2, so that the problembecomes x∗ = argminf(x).
- (a) Showthat∇f(x)=2A⊤(Ax−b).
- (b) Show that f(x) is Lipschitz differentiable with constant L = 2σ1(A)2.
- (c) Now, write code for solving the least squares problem using gradient descent. For A, use a random 100 × 50 matrix generated using the Python command np.random.randn(100,50). For b, use a random vector generated using numpy.random.randn(100). Experiment with different step-sizes, α. How large can you take α before the algorithm fails to converge?
- Solve the following linear program graphically. That is, sketch the feasible region, identify the corners and evaluate which one yields the minimal value of the cost function.minimize 2x1 + 5x2 subject to: x1 + x2 ≤ 8x1 ≤4andx2 ≤6 x1 ≥0andx2 ≥0
- Convert the following linear programming problem to standard form:minimize 2x1 + x2 subject to: x1 + x2 ≤ 3x1 + 2x2 ≤ 5
x1 ≥0andx2 ≥0 - The non-negative least squares problem is:
arg min ∥Ax − b∥2. (1)x∈Rn :x≥0That is, we are seeking to minimize the function f (x) = ∥Ax − b∥2 over the constraint set X = {x : x ≥ 0} ⊂ Rn}. Implement the projected gradient descent algorithm for this problem, and then use it to (approximately) solve (2) for:
1 −2 4 A = −3 7 0 5 2 −1
−3 b = 1
2 −507 12
7. The simplex constrained least squares problem is: arg min ∥Ax − b∥2. (2)
x∈∆n
where ∆n := {x ∈ Rn : x ≥ 0 and 1⊤x = 1} is the probability simplex (Here, 1 denotes the all-ones vector). Implement the Frank-Wolfe algorithm for this problem (using A and b as in Question 6). Hint: You may use the fact that solving linear programs over ∆n is very simple:
argminc⊤x = ei⋆ where i⋆ = argminci x∈∆n i
and ei is the vector with a 1 in the i-th position and zeros elsewhere.