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 Problem Set 3 CS 4301
