pr8.tex

\documentclass{article}
% Include macros here
\input{macros}
\usepackage{fancyhdr}
%\include{macros}
\usepackage{pifont}

% Number of problem sheet
\newcounter{problemSheetNumber}
\setcounter{problemSheetNumber}{8}
\newcommand{\matlabprob}{\ding{100} \ }
\newcommand{\examprob}{\ding{80} \ }
%\setcounter{section}{\theproblemSheetNumber}  
%\renewcommand{\theparagraph}{(\thesection.\arabic{paragraph})}
\newcounter{problems}
\setcounter{problems}{0}
%\setlength{\parindent}{0cm}
\renewcommand{\problem}{\paragraph{(\theproblemSheetNumber.\theproblems)}\addtocounter{problems}{1}}

%\theoremstyle{remark}
%\newtheorem{problem}[problemSheetNumber]{}

\pagestyle{fancy}
\lhead{MATH36061}
\chead{Convex Optimization}
\rhead{December 3, 2016}

\begin{document} 
\begin{center}
{\Large {\bf Problem Sheet \theproblemSheetNumber}}
\end{center}

Problems in Part A will be discussed in class. Problems in Part B come with solutions and should be tried at home. 


\section*{Part A}


\problem Consider the general convex optimization problem
\begin{equation*}
 \minimize f(\vct{x})\quad \subjto \vct{f}(\vct{x})\leq \zerovct,\quad \mtx{A}\vct{x} = \vct{b}.
\end{equation*}
The central path consists of the set of solutions $\vct{x}(t)$, $t>0$, of the barrier problem
\begin{equation*}
\minimize  tf(\vct{x})+\phi(\vct{x})\quad
\subjto  \mtx{A}\vct{x}=\vct{b},
\end{equation*}
where $\phi(\vct{x}) = -\sum_{i=1}^m \log(-f_i(\vct{x}))$ is the logarithmic barrier function.
Show that a point $\vct{x}$ is equal to a point $\vct{x}^*(t)$ on the central path if and only if there exist dual multipliers $\vct{\lambda}^*$ and $\vct{\mu}^*$ such that the following conditions are satisfied:
 \begin{align*}
\begin{split}
  \vct{f}(\vct{x}^*) & \leq \zerovct\\
  \mtx{A}\vct{x}^* & = \vct{b}\\
  \vct{\lambda}^*&\geq \zerovct\\
  -\lambda_i^*f_i(\vct{x}^*) & =\frac{1}{t}, \ 1\leq i\leq m\\
  \nabla_{\vct{x}} f(\vct{x}^*)+\sum_{i=1}^m \lambda_i^* \nabla_{\vct{x}}f_i(\vct{x}^*)+\mtx{A}^{\trans}\vct{\mu}^* &= \zerovct,
 \end{split}
 \end{align*}
 
\problem Let $\{\vct{x}_1,\dots,\vct{x}_n\}$ be a series of data points with $\vct{x}_i\in \R^p$ for $1\leq i\leq n$, and associated labels $\{y_1,\dots,y_n\}$ with $y_i\in \{-1,1\}$. Consider the following version of the Support Vector Machine optimization problem 
that allows for few mistakes:

\begin{align*}
\minimize &\frac{1}{2}\norm{\vct{w}}^2+\mu\sum_{j=1}^n s_j\\
\subjto & y_i(\vct{w}^{\trans}\vct{x}_i+b)-1+s_i \geq 0, \quad 1\leq i\leq n\\
& s_i\geq 0, \quad 1\leq i\leq n,
\end{align*}

Formulate the Lagrange dual and the KKT conditions for this problem. Show that the Lagrange dual does only depend on the inner products $\ip{\vct{x}_i}{\vct{x}_j}$ of the data points.

\problem A matrix
\begin{equation*}
 \mtx{A} = \begin{pmatrix}
            \mtx{B} & \vct{v}\\
            \vct{v}^{\trans} & b
           \end{pmatrix},
\end{equation*}
is positive definite if and only if $b-\vct{v}^{\trans}\mtx{B}^{-1}\vct{v}\geq 0$.
Use this, and the fact that a symmetric matrix factors as $\mtx{A}=\vct{M}^{\trans}\vct{M}$ for some $\mtx{M}$, to show that the QCQP from Problem Sheet 7 can be formulated as a semidefinite programming problem. 

\newpage
 \section*{Part B}

\problem Given a symmetric matrix $\mtx{A}$, formulate the problem of computing the largest eigenvalue $\lambda_{\mathrm{max}}(\mtx{A})$ as a semidefinite programming problem.



\problem In many applications one is interested in finding a matrix of low rank that satisfies certain constraints. For example, one could have a covariance matrix, or a matrix containing user ratings of products, or a matrix whose entries are the squared distances between objects, but where only some entries are known. A common heuristic is to replace the rank of a symmetric matrix with the sum of the eiganvalues

\begin{itemize}
 \item[(a)] Show that for a symmetric matrix $\mtx{A}$, the sum of the eigenvalues $\lambda_1+\cdots+\lambda_n$ equals the trace $\mathrm{tr}(\mtx{A})$. We can therefore write
 \begin{equation*}
  \lambda_1+\cdots+\lambda_n = \mathrm{tr}(\mtx{A}) = \mtx{I}\bullet \mtx{A}.
 \end{equation*}
\item[(b)] Formulate the problem of minimizing the trace of a symmetric positive semidefinite matrix $\mtx{X}$ subject to constraints of the form
\begin{equation*}
 x_{ij} = a_{ij}
\end{equation*}
for some subset of indices $(i,j)\in \Omega \subseteq \{1,\dots,n\}^2$. The problem is that of finding the matrix of smallest trace with some predetermined entries. Determine the dual of this problem.
\item[(c)] Using CVXPY in Python or CVX in MATLAB, perform the following experiment:
\begin{itemize}
\item Generate a random matrix $\mtx{X}_0\in \mathrm{SYM}_{100}$ of rank $10$. 
\item For an increasing subcollection of ``known'' entries from $\vct{X}_0$, solve the trace minimization problem and determine if the solution of this optimization problem coincides with the matrix $\mtx{X}_0$, thus effectively recovering it from only limited information.
\end{itemize}
\end{itemize}


\end{document}