\documentclass[11pt]{article}

\usepackage{exercises}
\usepackage[numbers]{natbib}

\usebiggeometry
\bluehyperref

\newcommand{\cg}{\mathop{\textup{cg}}}
\newcommand{\optgap}{\mathsf{gap}}
\newcommand{\size}{\mathop{\textup{size}}}

\begin{document}

\setcounter{section}{7}

\title{ee364m Exercise Set \thesection\
  \ifdefined\showanswer
  Solutions
  \fi
}

\author{Due date: February 28, 11:59pm}
\date{}
\maketitle

\begin{question}[An efficient representation of robustness]
  In robust optimization problems, one has uncertain problem data:
  abstractly, there is an uncertainty set $\mc{U}$ capturing
  potential noise, and we wish to guarantee that problem
  constraints are satisfied for all potential values $u \in \mc{U}$. This
  (abstractly) gives rise to convex optimization problems of the form
  \begin{equation}
    \label{eqn:robust-problem}
    \begin{array}{ll} \minimize & f(x) \\
      \subjectto & g_i(x, u) \le 0
      ~ \mbox{for~all~} u \in \mc{U},
      ~~ i = 1, \ldots, m,
    \end{array}
  \end{equation}
  where for each $u \in \mc{U}$, $g_i(\cdot, u)$ is convex.  See, for
  example, the book~\cite{Ben-TalGhNe09} for much much more on such
  problems. The challenge is that, while the problem~\eqref{eqn:robust-problem}
  is convex whenever $f$ is, the constraints in
  problem~\eqref{eqn:robust-problem} are typically infinite,
  making efficient computation challenging; a common approach is to
  use duality to obtain an alternative representation of the constraint
  $g_i(x, u) \le 0$ for all $u \in \mc{U}$ that is efficiently representable.
  Typical choices for $\mc{U}$ include sets defined by probability
  distributions, so that $\mc{U}$ covers (say) a $1 - \alpha$ fraction
  of possible realizations of noise $u$ in a system.

  Recall the $\ell_2$-operator norm
  $\opnorm{A} = \sup \{u^T A v \mid \ltwo{u} = \ltwo{v} = 1\}$.
  Fix (nominal) problem data $A_0, b$, let $\gamma \ge 0$,
  and consider the constraint
  that $(x, t) \in \R^n \times \R_+$ satisfy
  \begin{equation}
    \label{eqn:constraint}
    \ltwo{(A_0 + \Delta) x + b} \le t
    ~~ \mbox{for~all~} \opnorm{\Delta} \le \gamma.
  \end{equation}
  Show that $(x, t)$ satisfy the constraint~\eqref{eqn:constraint}
  if and only if there exists $\lambda \ge 0$ such that
  \begin{equation*}
    \left[\begin{matrix}
        t I_n - \lambda I_n & 0 & (A_0 x + b) \\
        0 & \lambda I_n & \gamma x \\
        (A_0 x + b)^T & \gamma x^T & t
      \end{matrix}\right] \succeq 0.
  \end{equation*}

  \emph{Hints.}
  In my solution, I used the following results.
  If you use Lemma~\ref{lemma:lorentz-as-sdp},
  you should prove it. You may assume Lemmas~\ref{lemma:schur}
  and~\ref{lemma:s-lemma}.
  \begin{lemma}
    \label{lemma:lorentz-as-sdp}
    Let $K = \{(x, t) \mid \ltwo{x} \le t\}$ be the Lorentz cone.
    Then $(x, t) \in K$ if and only if
    \begin{equation*}
      \left[\begin{matrix} t I & x \\ x^T & t \end{matrix} \right]
      \succeq 0.
    \end{equation*}
  \end{lemma}
  \begin{lemma}[Schur complements]
    \label{lemma:schur}
    Let $A, B, C$ be matrices of appropriate size. Then
    \begin{equation*}
      M = \left[\begin{matrix} A & B \\ B^T & C \end{matrix} \right]
      \succeq 0
    \end{equation*}
    if and only if $A \succeq 0$,
    $C - B^T A^\dagger B \succeq 0$, and
    $\linspan(A)$ contains the columns of $B$.
  \end{lemma}
  \noindent
  Using these, I showed that the constraint~\eqref{eqn:constraint} was
  equivalent to
  \begin{equation}
    \label{eqn:almost-time-to-apply-s-lemma}
    t \ltwo{v}^2 + t s^2
    + 2 s v^T (A_0 x + b)
    - 2 \gamma s u^T x
    \ge 0
    ~~ \mbox{whenever} ~ \ltwo{v}^2 \ge \ltwo{u}^2.
  \end{equation}
  Now apply
  \begin{lemma}[Inhomogeneous S-Lemma]
    \label{lemma:s-lemma}
    Assume the constraint qualification that there exists
    $\wb{x}$ such that
    $\wb{x}^T A_0 \wb{x} + 2 b_0^T \wb{x} + c_0 > 0$.
    Then the following two statements are equivalent:
    \begin{equation*}
      x^T A_0 x + 2 b_0^T x + c_0 \ge 0
      ~~ \mbox{implies} ~~
      x^T A_1 x + 2 b_1^T x + c_1 \ge 0
    \end{equation*}
    and
    \begin{equation*}
      \left[\begin{matrix} A_1 - \lambda A_0 &
          b_1 - \lambda b_0 \\
          (b_1 - \lambda b_0)^T & c_1 - \lambda c_0
        \end{matrix} \right]
      \succeq 0
      ~~ \mbox{for~some}~ \lambda \ge 0.
    \end{equation*}
  \end{lemma}
\end{question}

\bibliography{bib364m}
\bibliographystyle{abbrvnat}

\end{document}