Problem Set 2 CS 4301 solution

Description

Problem 1: Duals of Duals (10 pts)

Consider the following optimization problem.
min
x,y∈R
x
2 + y
2
such that
2x + y ≤ 1
x ≥ 0
y ≥ 0

1. Is Slater’s condition satisfied for this optimization problem?
2. Use the method of Lagrange multipliers to construct a dual of this optimization problem.

3. Use the method of Lagrange multipliers to construct a dual of your dual from (2) of this
optimization problem. Did you recover the primal problem?

Problem 2: Projections onto Convex Hulls (30 pts)

For this problem, you will implement the Frank-Wolfe algorithm using scipy.linprog in the Python
scipy package to help you solve the per-iteration subproblems. Recall that, given x
(1), . . . , x(M) ∈
R
n
, their convex hull is the set of all x that can be written as a convex combination of these points.

1. Use the Frank-Wolfe algorithm to compute the projection of a query point q onto the convex
hull of the given x
(1), . . . , x(M) ∈ R
n

. That is, you should solve the following optimization
problem.
min
λ∈RM
1
2
||q −
X
M
m=1
λmx
(m)
||2
2
such that
X
M
m=1
λm = 1
1
λ ≥ 0

Your Python function should take as input the x’s, the query point q, an initial value for λ
that satisfies the constraints, and the tolerance  for the Frank-Wolfe convergence condition
and return the best function value found during the iterative procedure.

2. Use the method of Lagrange multipliers to construct a dual of this optimization problem.

Problem 3: Convex Envelopes (60 pts)

Consider a collection of points x
(1), . . . , x(M) ∈ R
n with corresponding function values y
(1), . . . , y(M) ∈

R. The convex envelope of these points is the convex function fenv : R
n → R such that fenv(x
(m)
) ≤
y
(m)

for all m and for any other convex function g : R
n → R such that g(x
(m)
) ≤ y
(m)
for all m,
fenv(x) ≥ g(x) for all x ∈ R
n
.

1. For a finite point set, is the convex envelope differentiable? Explain.
2. Recall that, for any convex function f : R
n → R, and any x, x0 ∈ R, f(x) ≥ f(x
0
)+w
T
(x−x
0
),
where w is a subgradient of f at x
0

.

Using this, we can formulate the problem of evaluating the
convex envelope of our collection of points at a query point x ∈ R
n as a convex optimization
problem:
fenv(x) = sup
w∈Rn,y∈R
y
such that
y
(m) ≥ y + w
T
(x
(m) − x), for all m ∈ {1, . . . , M}.

(a) Explain why this optimization problem is unbounded for certain choices of x ∈ R
n
.
(b) To fix the unboundedness, we can add an additional constraint that ||w||2
2 ≤ γ
2
for some
given γ ≥ 0.

In Python, implement projected gradient descent to solve the optimization
problem under this additional constraint. Your Python function should take as input
the x’s, the y’s, γ, the query point x, and the number of iterations of projected gradient
ascent to perform and return the best function value found during the iterative procedure
stating from w = 0 and y = minm y
(m)

. Hint: you can do the projection analytically if
you reformulate the optimization problem to eliminate the linear constraints.

(c) Construct a dual of the optimization problem in (b) using the method of Lagrange
multipliers.

(d) In Python, implement the Frank-Wolfe algorithm to maximize your dual in (c). Your
Python function should take as input the x’s, the y’s, γ, the query point x, a feasible
initial point for the Lagrange multipliers, a tolerance  that terminates the Frank-Wolfe
algorithm whenever the convergence criteria from class is met, and an upper bound
max it on the number of iterations, and returns the best function value found during
the iterative procedure.

Hint: you can analytically eliminate the Lagrange multiplier
corresponding to the constraint ||w||2
2 ≤ γ
2
.
2