Homework 4

This homework covers the material from lectures 14 to 17

Due date: November 8th, 11:59pm Waterloo time.

PDF version of Homework 4.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Remember that you are only required to turn in 5 out of the 6 exercises below.

Problem 1 - Corner Points of Minimum Vertex Cover Relaxation (20 points)

Given the LP relaxation for minimum vertex-cover:

\begin{align*} \min \ \ &\sum_{v \in V} c_v \cdot x_v \\
\text{s.t.}\ \ 0 \leq \ &x_v \leq 1 \ \text{ for all } v \in V \\
x_u + \ &x_v \geq 1 \ \text{ for all } \{u,v\} \in E \end{align*}

1. Let $y$ be any feasible solution for the LP. Define another solution $y^+$ by: $$y^+_v = \begin{cases} y_v + \varepsilon \ \text{ if } 1/2 < y_v < 1, \\
   y_v - \varepsilon \ \text{ if } 0 < y_v < 1/2, \\
   y_v\ \ \ \ \ \ \text{ if } y_v \in \{0, \frac{1}{2}, 1\}. \end{cases} $$ Similarly define the solution $y^-_v$, by replacing $\varepsilon$ with $-\varepsilon$.

   Prove that one can find $\varepsilon > 0$ such that both $y^+, y^-$ are feasible for the LP above.

2. Show that every extreme point $z$ of the LP above is half-integral, that is $z_v \in \{0, \frac{1}{2}, 1\}$ for all $v \in V$.

Problem 2 - Integer Linear Programming Rounding (20 points)

Given a hypergraph $G(V, E)$ where each hyperedge $e \in E$ is a subset of $V$ , our goal is to color the vertices of $G$ using $\{ -1, +1 \}$ such that each hyperedge is as balanced as possible. Formally, given a coloring $\gamma : V \to \{-1, +1\}$ on the vertices, we define $$ \Delta(e) = \sum_{v \in e} \gamma(v) $$
and $$\Delta(G) = \max_{e \in E} |\Delta(e)|.$$ Prove that if the maximum degree of the hypergraph is $d$ (i.e. each vertex appears in at most $d$ hyperedges), then there is a coloring with $$\Delta(G) \leq 2d - 1.$$

Hint: You may find it useful to consider the following LP, where initially we set $B_e = 0$ for all $e \in E$.

\begin{align*} &\sum_{v \in e} x_v = B_e \ \text{ for all } \ e \in E \\
&-1 \leq x_v \leq 1 \ \text{ for all } \ v \in V \end{align*}

Guidance on how to use the hint:

1. The main approach will be to iteratively update the LP above to try and find our desired solution. At each iteration, we will use a solution of the LP to guide us.
2. What does the LP given in the hint give us? What is captured by solutions to the LP?
3. What are the basic solutions to the LP above? How do we find a basic solution?
4. Now that we have a basic solution, and know how they look, we can prove the following consequence of basic solutions $$x \text{ is basic } \implies \{A_i\}_{i \in \text{supp}^*(n)} \text{ is L.I. where } \text{supp}^*(x) = \{i \in [n] \mid x_i \in (-1, 1)\}$$
5. What happens if a coordinate is not in $\text{supp}^*(x)$?
6. What happens when we cannot update the LP?
7. How do we get unstuck? Hint: Throw away a constraint. Which one?
8. At most how many vertices will THE deleted hyperedge have?
9. What is the worst that can happen to an edge in this process?

Problem 3 - Integer Linear Programming Rounding (20 points)

Consider the following maximum covering problem. Given a graph $G$ and a given number $k$, find a subset of $k$ vertices that touches the maximum number of edges.

Let $OPT(G, k)$ be the optimal number of edges touched in $G$ by a set of at most $k$ vertices.

Design an integer programming formulation for the problem, and then find a randomized rounding procedure for the corresponding linear programming relaxation, such that for given $G$ and $k$, it identifies a set of at most $2k$ vertices that touches at least $c \cdot OPT(G, k)$ edges, for some constant $c > 0$.

Your algorithm should always output a set of at most $2k$ vertices, and succeed with probability at least $1/2$.

Problem 4 - Strong Duality in SDPs (20 points)

1. Let $\alpha \geq 0$ and consider the following SDP: \begin{align*} \text{minimize } \ \ &\alpha \cdot X_{11} \\
   \text{s.t.}\ \ X_{22} &= 0, \\
   X_{11} &+ 2 \cdot X_{23} = 1, \\ X &\succeq 0 \end{align*}

   Where $X$ is a $3 \times 3$ symmetric matrix. Prove that the dual of the SDP above is: \begin{align*} \text{maximize } \ \ &y_2 \\
   \text{s.t.}\ \
   \begin{pmatrix} y_2 & 0 & 0 \\
   0 & y_1 & y_2 \\
   0 & y_2 & 0 \end{pmatrix} &\preceq \begin{pmatrix} \alpha & 0 & 0 \\
   0 & 0 & 0 \\
   0 & 0 & 0 \end{pmatrix} \end{align*}

2. What is the value of the first SDP of part (1)?

3. What is the value of the dual (second SDP) of part (1)?

4. Now consider the following SDP: \begin{align*} \text{minimize } \ \ &x \\
   \text{s.t.}\ \
   \begin{pmatrix} x & 1 \\
   1 & y \end{pmatrix} &\succeq 0 \end{align*} Compute its dual program.

5. Is the primal from part (4) strictly feasible? Is the dual strictly feasible?

6. What can you say about strong duality of the SDPs of parts 1 and 4? Are the results consistent with Slater conditions presented in class?

Problem 5 - Challenge to a Dual (20 points)

Let $G(V,E)$ be a graph, where $n = |V|$. For each $i \in V$, let $v_i \in \mathbb{R}^n$ be a vector variable associated to vertex $i$. Consider the following SDP:

\begin{align*} \min \ \ &t \\
\text{s.t.}\ \ \langle v_i , v_j \rangle &= t \ \text{ for all } i \neq j \in V, \ \{i,j\} \not\in E \\
\langle v_i, v_i \rangle &= 1 \ \text{ for all } i \in V \end{align*}

Let $\Theta \in \mathbb{R}$ be the optimum value of the SDP above.

1. Show that the following SDP has optimal value $- \Theta$: \begin{align*} \max \ \ &\langle X, e_{n+1} e_{n+1}^T \rangle \\
   \text{s.t.}\ \ \langle X , e_i e_j^T \ &+ e_{n+1} e_{n+1}^T \rangle = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \not\in E \\
   \langle X , e_i e_i^T \rangle &= 1 \ \text{ for all } i \in V \\
   &X \succeq 0 \end{align*} Where $X$ is a $(n+1) \times (n+1)$ symmetric matrix, and $e_1, \ldots, e_{n+1}$ are the elementary unit vectors.

2. Write down the dual of the SDP from part (a).

3. Conclude that the dual you just derived is equivalent to the following SDP:

   \begin{align*} \min \ \ &\sum_{1 \leq i \leq n} Z_{ii} \\
   \text{s.t.}\ \ &Z_{ij} = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \in E \\
   &\sum_{i \neq j} Z_{ij} \geq 1 \\
   &Z \succeq 0 \end{align*}

   Where $Z$ is an $n \times n$ symmetric matrix.

4. Rearrange the above SDP to show that the following SDP have value $\dfrac{\Theta-1}{\Theta}$:

   \begin{align*} \max \ \ &\sum_{i,j \in V} Y_{ij} \\
   \text{s.t.}\ \ &Y_{ij} = 0 \ \text{ for all } i \neq j \in V, \ \{i,j\} \in E \\
   &\sum_{1 \leq i \leq n} Y_{ii} = 1 \\
   &Y \succeq 0 \end{align*}

   Where $Y$ is an $n \times n$ symmetric matrix.

Problem 6 - Projections of Spectrahedra (semidefinite representations) & SDP relaxations (20 points)

1. The $k$-ellipse with foci $(u_1, v_1), \ldots, (u_k, v_k) \in \mathbb{R}^2$ and radius $d \in \mathbb{R}$ is the following curve in the plane: $$ \left\{ (x,y) \in \mathbb{R}^2 \ \bigm| \ \sum_{i=1}^k \sqrt{(x-u_i)^2 + (y-v_i)^2} = d \right\} $$

   Let $\mathcal{C}_k$ be the region whose boundary is the $k$-ellipse. That is, $\mathcal{C}_k$ is the set: $$ \left\{ (x,y) \in \mathbb{R}^2 \ \bigm| \ \sum_{i=1}^k \sqrt{(x-u_i)^2 + (y-v_i)^2} \leq d \right\} $$

   Find a semidefinite representation (i.e. projection of a spectrahedron) of the set $\mathcal{C}_k$, and prove that your semidefinite representation is correct. That is, that it captures exactly the set $\mathcal{C}_k$ above.

2. Given a 3-uniform hypergraph $G(V, E)$ (that is, a hypergraph where each hyperedge has exactly 3 vertices), we say that a 2-coloring of $V$ is valid for a hyperedge $e = \{ a, b, c\} \in E$ if the hyperedge $e$ is not monochromatic upon this coloring.

The Max-2C3U problem is the following:

• Input: a 3-uniform hypergraph $G(V, E)$
• Output: a 2-coloring of the vertices of $G$ of maximum value, that is, a function $f : V \rightarrow \{ -1, 1 \}$ (the coloring) which maximizes the number of valid hyperedges.

In this question, you are asked to:

2.1. Write the optimization problem above as a quadratic program

2.2. Formulate an SDP relaxation for the problem, and prove that it is in fact a relaxation

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1

From lecture 13, slide 23: prove that the three definitions of corner points of a polytope are equivalent.