MATP6640/DSES6770 Linear Programming, Homework 6.     Updated April 17.

Due: Monday, April 28, 2008.
10% penalty for each day late.

1. Assume $r_b \neq 0$, $S$ and $X$ are positive definite diagonal matrices, and $A$ is $m \times n$ with rank $m$. Let $g \in I \!\! R^n$ satisfy $AS^{-1}g \neq r_b$. Let $(\Delta x, \Delta y, \Delta s)$ solve
   
   $$\left[ \begin{array}{lll}0&A^T&I\\ A&0&0\\ S&0&X \end{array}... ...= \left[ \begin{array}{c} 0 \\ -r_b \\ -g \end{array} \right].$$
   
   
   What must $g$ satisfy to ensure that $\Delta x^T \Delta s \neq 0$?

2. Let $K$ be a cone. A function $f:\mbox{int}(K) \rightarrow I \!\! R$ is logarithmically homogeneous if there exists a constant $\Theta$ such that $f(tx)=f(x)-\Theta\ln(t)$ for all $x\in\mbox{int}(K)$ and $t>0$. (Here, $\mbox{int}(K)$ denotes the interior of $K$.) Show that the barrier function for the second order cone, namely $f(\xi,x) = - \ln(\xi^2 - x^Tx)$, is logarithmically homogeneous, where $\xi$ is a nonnegative scalar and $x$ is an $n$-vector.
3. Let
   
   $$C := \left[ \begin{array}{rrr} 0&0&0\\ 0&0&0\\ 0&0&2 \end{ar... ..., \quad b := \left[ \begin{array}{r} 1\\ 3 \end{array} \right]$$
   
   
   The primal and dual semidefinite programs are
   
   $$\begin{array}{lrcllrlrcrclr} \min & \mbox{trace}(CX) &&&&& \... ...D) \\ & X & \succeq & 0 &&&&&& S & \succeq & 0 \\ \end{array}$$
   
   
   Show that both $(P)$ and $(D)$ are feasible, but that the optimal value of $(P)$ is not achieved.
4. Let $x \in I \!\! R^n_+$. Show that the constraint $1 \leq \Pi_{i=1}^n x_i$ is equivalent to a collection of O(n) second order cone constraints.
5. Most semidefinite relaxations of combinatorial optimization problems result in a linear constraint on the trace of the primal matrix $X$. For example, in the relaxation of MaxCut, the diagonal entries are all required to equal one, so the trace must equal the number of nodes. Show that if the primal problem contains a constraint of the form trace$(X)=a$ for some constant $a$ then the feasible region for the dual is unbounded. (Hint: trace$(X)=$ trace$(IX)$.)

 John Mitchell  Amos Eaton 325  x6915.  mitchj at rpi dot edu  Office hours: Mondays, 1pm - 2pm. Thursdays, 1pm - 3pm.