## Description

## Problem 1: Eigenvalues (30 pts)

A real number t ∈ R is an eigenvalue of a symmetric matrix A ∈ R

n×n

if there exists a vector

x 6= 0 ∈ R

n

that Ax = tx. Here, x is called an eigenvector for the eigenvalue t. Consider the

following optimization problem,

max

x∈Rn

x

T Ax

such that

||x||2

2 = 1

1. Construct a dual of this optimization problem using the method of Lagrange multipliers.

2. Argue that strong duality holds regardless of whether or not the problem above is convex.

What is the solution to the primal problem?

3. Use the method of Lagrange multipliers (for positive semidefinite constraints) to construct a

dual of your dual.

## Problem 2: Interior Point Methods (50 pts)

We saw in class how we can apply Newton’s method with equality constraints. However, applying

Newton’s method with general inequality can be a bit trickier. Here, we will explore one such strategy that results in a family of optimization strategies known as interior point methods (sometimes

called barrier methods).

Interior point methods take optimization problems of the following form

min

x∈Rn

f0(x)

subject to:

Ax = b

gk(x) ≤ 0, for all k ∈ {1, . . . , K}

and approximate them using some δ > 0 as

min

x∈Rnst.Ax=b

”

δf0(x) −

X

K

k=1

log(−gk(x))#

.

1

As δ → ∞, this approximation becomes better and better. Given an initial x

(0), δ(0) > 0, ρ > 1,

the interior point method then iterates the following starting at t = 0.

• Find an x

∗ ∈ arg minx∈Rnst.Ax=b

h

δ

(t)f0(x) −

PK

k=1 log(−gk(x))i

by using Newton’s method

starting at x

(t)

.

• Set x

(t+1) = x

∗

.

• Update δ

(t+1) = ρδ(t)

.

Recall the problem of computing the projection of a query point q onto the convex hull of the

given x

(1), . . . , x(M) ∈ R

n

from Homework 2.

min

λ∈RM

1

2

||q −

X

M

m=1

λmx

(m)

||2

2

such that

X

M

m=1

λm = 1

λ ≥ 0

1. Explain why the subproblem solved by the interior point method is a convex optimization

problem.

2. Implement the interior point method in Python for the above problem. Your function should

take as input the initial guess x

(0)

, δ

(0)

, ρ, the number of iterations t of the interior point

method to perform, and a threshold > 0 for the convergence of Newton’s method. It should

return the vector x

(t)

. For Newton’s method, you should terminate if .5(x

∗

)

T H(x

(t)

)x

∗ ≤ ,

where x

∗

is the solution to the Newton subproblem at x

(t)

, see Slide 33.

3. How should you assess the convergence of the interior point method? In particular, what

would be a good stopping criteria?

## Problem 3: Power Iteration (20 pts)

The power iteration method attempts to find the eigenvalue of maximum magnitude a matrix

A ∈ R

n×n by iterating the following steps:

• Pick an initial x

(0) ∈ R

n

.

• Repeat until convergence

– Set x

(t+1) =

Ax(t)

||Ax(t)

||2

.

1. In Python, implement the power iteration method to find the eigenvalue of maximum magnitude of a matrix A ∈ R

n×n

. Your function should take in the matrix A, the initial guess

x

(0), and the number of iterations to perform.

2

2. How should you pick the initial vector? Explain.

3. Explain how to use the same approach to find the eigenvalue with second largest magnitude

of a matrix by only changing the way in which you pick the initial vector.

4. Is it possible that the power iteration method is ill-defined, i.e., can the denominator in the

update become zero?

3