Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS6550: Continuous Algorithms: Optimization and Sampling Spring 2025
Homework 6
Lecturer: Santosh Vempala Due Date: noon, 7 April 2025
Notes:
• You are allowed/encouraged to discuss and collaborate, but please write your own solutions.
• Submit on Canvas via Gradescope.
• Start each question on a new page, and try to limit the solution to each part to no more than a page (typically half a page).
1. Initial Solution
Consider the following linear program min c
⊤x s.t. Ax = b, x ≥ 0. Assume that A has full row rank. To find a feasible initial solution consider the following extension:
Note that when x
− = 0, this is the same as the original program. On the other hand, for any solution ˆx of Axˆ = b, we can write x
+ = max(x, 0), x− = − min(x, 0) to get a feasible initial solution.
1. Suppose we have a feasible solution to the initial linear program with bounded optimum value, show that C can be set to be a large enough scalar so that setting x = x
+ for some optimal solution achieves ∥Ax − b∥1 ≤ ϵ for any target ϵ > 0.
2. Suppose the feasible region of the original LP is bounded and it has a solution x s.t. Ax = b and xi ≥ r in every coordinate for some r > 0. Can we set C large enough so that an optimal solution to the extended LP gives a feasible solution of the original LP?
2. Interior Point Method
1. Let K be a convex set defined as follows:
K = {x ∈ R
n
: x
⊤Aix ≤ 1, for i = 1, . . . , m}
where Ai are positive definite matrices. Define a convex barrier function ϕK : K → R+ and prove that it is self-concordant and bound its barrier parameter ν. [Hint: first define it for a single ellipsoid.]
2. Consider the optimization problem minx∈K c
⊤x. Define the central path for this problem using ϕK and bound the number of iterations needed to converge to a solution with at most ϵ additive error. What is a good and easy way to find a starting point?
3. Given an algorithm for computing one Newton step of the method and bound its running time.
3. Newton Method
Let p: R → R be an degree n polynomial with real roots, so that p(x) = a
Q
n
i=1 (x−λi) for some (unknown) a, λ1, . . . , λn ∈ R where λ1 ≥ · · · ≥ λn. Suppose p is given by an evaluation oracle. Show that given x
(0) ∈ R and ϵ > 0, satisfying x
(0) ≥ λ1 + M for some M > 0, a point x
∗
satisfying
λ1 ≤ x
∗ ≤ λ1 + ϵ · (x
(0) − λ1)
can be found using O(n log 1
ϵ
) oracle calls. [Hint: Approximate the gradient.]
