CSE 535: Homework #4

Due: Sun, Dec 12
Gradescope Link

1. Interior point methods (IPM) [42 points]

In this problem, you will give an alternate proof of convergence of IPM for linear programs. Define the reasible region , where . Our goal is to solve the problem: Given a cost vector ,

Define the slack function for the th constraint:

and the IPM objective

Define also the central path:

Note that we have changed the weighting so that corresponds to solving the original problem , i.e., as . The second term in \eqref{eq:lp} is the barrier function that ensures we have

Let us calculate the gradient ahd Hessian of \eqref{eq:ipm}:

where is the th row of .

Definition (Local ellipsoid): Define

This is the -ball around in the local norm .

  1. [2 points] Show that

  2. [4 points] Prove that for any , we have . Therefore if we sit at some , it is safe to move to any .

  3. [12 points] Fix a value of . The goal of this part is to prove that for any and , if , then

    This means that if we are close to , then taking a Newton step gets us even closer (in terms of the local norms).

    1. [4 points] For any vector $y$ on the line segment joining $x$ and $x^*(t)$, prove that $$ (1-3R) \nabla^2 F_t(x) \preceq \nabla^2 F_t(y) \preceq (1+3R) \nabla^2 F_t(x). $$
    2. [4 points] Prove that $$ \nabla F_t(x) = \left(\nabla^2 F_t(x) + E\right) (x-x^*(t)), $$ for some matrix $E$ satisfying $|E| \preceq 3R\ \nabla^2 F_t(x)$. [Hint: Use the Fundamental Theorem of Calculus.]
    3. *[4 points] Use the previous two parts to conclude that \eqref{eq:goal} holds.
  4. [12 points] You will now show that we can increase by a factor of .

    1. [4 points] Consider $x \in \mathrm{int}(\mathsf{K})$ and $x+h$ on the boundary of $\mathcal{E}(x,R)$ for some $0 \leq R \leq \frac{1}{12}$. Show that $$ F_t(x+h) = F_t(x) + \langle \nabla F_t(x), h\rangle + \frac{R^2}{2} \pm \frac32 R^3. $$
    2. [4 points] Prove that $$ \max \left\{ t \langle c, x-x^*(t)\rangle : x \in \mathcal{E}(x^*(t),R) \right\} \leq R \sqrt{m}. $$
    3. [4 points] Combine the preceding two parts to show that if $t' \leq t\left(1+\frac{R}{4 \sqrt{m}}\right)$, then $x^*(t') \in \mathcal{E}(x^*(t),R)$.
  5. [4 points] Combine the results of parts 3 and 4 to show that , where , and , and where is the result of a Newton step

  6. [4 points] Prove that for any and ,

    [Hint: Start with D(ii).]

  7. [4 points] Combine all these results to conclude a bound on the iteration complexity of IPM to obtain a point within of the optimum in terms of , , and , where is the initial value of . (I.e., you may assume that you are given to start.)

2. JL for low-space computation [20 points]

Let be a random matrix where the entries are i.i.d. random variables. In this problem, you may assume that for , it holds that with probability at least , for any fixed vector , we have

  1. [10 points] Suppose we maintain a vector as follows. Initially, . At the th step, we update

    where are the standard basis vectors.

    Suppose that you have a memory that only allows you to store numbers as the updates arrive one by one. Show how to maintain an estimate for so that by the final iteration, the estimate is correct up to multiplicative error with probability at least .

  2. [10 points] In the same “online” setting as the previous part, suppose you are told that the final vector has some index such that . Show that by using only bits of memory, we can find the index with probability at least . (Note: You may assume that each number uses only bits of precision.)