## 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