%
% This is a borrowed LaTeX template file for lecture notes for CS267,
% Applications of Parallel Computing, UCBerkeley EECS Department.
% Now being used for CMU's 10725 Fall 2012 Optimization course
% taught by Geoff Gordon and Ryan Tibshirani.  When preparing 
% LaTeX notes for this class, please use this template.
%
% To familiarize yourself with this template, the body contains
% some examples of its use.  Look them over.  Then you can
% run LaTeX on this file.  After you have LaTeXed this file then
% you can look over the result either by printing it out with
% dvips or using xdvi. "pdflatex template.tex" should also work.
%

\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% ADD PACKAGES here:
%


\usepackage{amsmath,amsfonts,graphicx}
\usepackage[tight]{subfigure}
\usepackage{hyperref}
%
% The following commands set up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf 10-725: Optimization
	\hfill Fall 2012} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Lecture #1: #2  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribes: #4} }
      \vspace{2mm}}
   }
   \end{center}
   \markboth{Lecture #1: #2}{Lecture #1: #2}

   {\bf Note}: {\it LaTeX template courtesy of UC Berkeley EECS dept.}

   {\bf Disclaimer}: {\it These notes have not been subjected to the
   usual scrutiny reserved for formal publications.  They may be distributed
   outside this class only with the permission of the Instructor.}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
% Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
        {[\arabic{equation}]}{\usecounter{equation}
         \setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
         \setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
			\vspace{#2}
			\begin{center}
			Figure \thelecnum.#1:~#3
			\end{center}
	}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\newcommand\E{\mathbb{E}}

\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{22}{Introduction to Interior Point
Methods}{Geoff Gordon/Ryan Tibshirani}{Abhinav Shrivastava}
%\footnotetext{These notes are partially based on those of Nigel Mansell.}

% **** YOUR NOTES GO HERE:

% Some general latex examples and examples making use of the
% macros follow.  
%**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN,
%**** ARE NEVER READ BY ANYBODY.
\section{Interior-point methods}
Interior-point methods are important because they are by far the most efficient
methods to solve optimization problems with relatively small numbers of variables
and potentially very large numbers of linear constraints (specially if we need
very accurate solutions.) Also, they are based on geometric intuition and
deriving the interior-point method for a problem can give interesting insights.

{\bf Historical Interest}: $(1)$ First practical polynomial time algorithm
for solving an LP. (It is still an open question whether they are strongly
polynomial time or not.) $(2)$ First proposed method in literature: Ellipsoid
Method.
(Though it is not practical for a lot of problems, it is a great theoretical
tool.)

{\bf Combinatorial or real analysis of LPs}: We can either think of solving for
Linear Program (LP) as being a combinatorial algorithm (for example, in case of the
simplex algorithm, searching amongst discrete sets of vertices for solution)  
or a continuous problem (for example, maximizing a continuous function over a
convex set). Interior-point methods can act as a bridge between both forms of
reasoning (as we will see further in lectures.)

\subsection{Ball Center (aka Chebyshev center)}
Suppose for a problem, the feasible region (figure~\ref{ballcenter}) is given by
\begin{align}
 X = \{ \; x \;| \; Ax + b \ge 0 \}.
\label{feasibleeq}
\end{align}
In general, this is too big of a
description (e.g.\, intersection of too many linear inequalities), and we
would
like to come up with a shorter description of this feasible region. One try
might be to find the ball center, which is the center of the largest sphere that
can be inscribed inside this feasible region (dotted blue line
in figure~\ref{ballcenter}.) As an optimization problem, we can write it as: 
\begin{align}
 \max_x \; \min_i \; \texttt{dist}(x,\, a_i^Tx+b_i=0)
\label{ballcenter1} 
\end{align}
where $a_i^Tx+b_i=0$ is the constraint line for the $i^{th}$ constraint,
$\texttt{dist}$ is euclidean distance of x to that constraint line, $\min_i$ 
finds closest constraint to the point $x$ and $\max_x$ maximizes the distance
of $x$ to that closest constraint. Thus, (eq. \ref{ballcenter1}) will maximize
the radius of the ball that we can inscribe centered at $x$. We can find
this ball center using a LP as follows:
\begin{enumerate}
  \item  If $\|a_i\|=1$ (i.e.\, $a_i$ is normalized), then 
$\texttt{dist}(x, a_i^Tx+b_i=0)$ is just $a_i^Tx+b_i$ (a linear function of x).
So we can re-write (eq. \ref{ballcenter1}) as:
\begin{align}
&\displaystyle\max_{x, t} \; t \quad \mbox{subject to } Ax+b \ge t\,\mathbf{1}
\\
&\displaystyle\max_{x, t} \; t \quad \mbox{subject to } \mathbf{s} \ge
t\,\mathbf{1} \mbox{ where } \mathbf{s}=Ax+b
\label{ss}
\end{align}
\item In general, we can write the constraint as
$\displaystyle\frac{s_i}{\|a_i\|} \ge t \; \forall \; i$. Since $\|a_i\|$ is
constant, the constraint is linear in $s_i$ and $t$, therefore we have a LP.
\end{enumerate}

\begin{figure}[!hb!]
 \centering
\includegraphics[width=0.3\textwidth, keepaspectratio=true]
{./images/ballcenter1.pdf}
\vspace{-0.1in}
 \caption{Ball Center (solid blue circle) for the feasible region (white
polyhedron) (corresponding ball center in dotted blue)}
\label{ballcenter}
\end{figure}

\begin{figure}[!hb!]
 \centering
\subfigure[Feasible region with bad conditioning]{
\includegraphics[height=1.5in, keepaspectratio=true]
{./images/ballcenterbad1.pdf}
\label{skinnyfig}
}
$\quad$
\subfigure[]{
\includegraphics[height=1.5in,keepaspectratio=true]
{./images/ballcenterbad2.pdf}
\label{cutskinnyfig}
}

\vspace{-0.1in}
 \caption{Ball center (dashed red
circle) for a feasible region (white
polyhedron) (corresponding center marked by ``x''.) For two very varied
feasible
regions given in (a) and (b), we have the same ball center. }
\label{ballcenter}
\end{figure}

{\bf Bad News}: Consider the feasible region shown in figure~\ref{skinnyfig} (long
skinny triangle). The selected ball center is not a very good summary of the
feasible region because we will have the same ball center if we had the
feasible region from figure~\ref{cutskinnyfig}, which is indeed very different
from figure~\ref{skinnyfig}. A symptom of this problem is that the ball may
contain an arbitrarily small fraction of the volume of the feasible region.

\subsection{Ellipsoid Center (aka max-volume inscribed ellipsoid)}
It is the center of the inscribed ellipsoid with the largest possible volume.
The ellipse centered at $d$ is given by 
\begin{align}
  E = \{ Bu+d \; | \; \|u\|_2 \le 1 \} 
\label{ellipsoideq}
\end{align}
i.e.\ a scaled and shifted version of the unit sphere. 
The volume of $E$ is proportional to $\det B$, therefore $1$/volume is
proportional to $\det B^{-1}$. It turns out that we can
find the ellipse centered at $d$ as a solution of the semi-definite program
given by
\begin{align*}
\min \; &\log \det B^{-1} \\
\mbox{ subject to: } &a_i^T(Bu+d)+b_i \ge 0 \quad \forall i \quad \forall u
\mbox{ with } \|u\| \le 1 \\
&B\succeq 0
\end{align*}
The above constraints imply that the entire ellipse has to be contained in the
feasible region. For each $i$ and each $u$, we have a linear constraint in $B$
and $d$ (actually, there are infinitely many such constraints.) The constraints
are linear, and therefore we have a convex optimization problem.

\begin{figure}[!hb!]
 \centering
\includegraphics[width=0.3\textwidth, keepaspectratio=true]
{./images/ellipsoid.pdf}
\vspace{-0.1in}
 \caption{Maximum volume ellipsoid (shaded) inscribed in the feasible region
(polyhedron)}
\label{ellipsoidfig}
\end{figure}

As can be seen in example shown in figure~\ref{ellipsoidfig}, the resulting
ellipsoid fills up the feasible region quite nicely. We can show that in
general the $\texttt{Volume}(E) \ge
\left(\frac{1}{n^n}\right)\texttt{Volume}(X)$ ($E$ from eq. \ref{ellipsoideq}
and $X$ from eq. \ref{feasibleeq}) i.e.\ at least a polynomial fraction of the
feasible region is covered by the ellipsoid.

In conclusion, we have a convex optimization problem to find a good summary
of the feasible region. But the problem is very expensive, with infinitely many
constraints in an SDP (but we can still do it.)

So, the next obvious question: Is there some summary of the feasible region
which can be computed cheaply, and which can be said to be a good summary?
(e.g.\ if it contains at least a polynomial fraction of the volume of the
feasible region, like ellipsoid center discussed above.) Find the answer in the
next section!

\subsection{Analytic Center}
Take the slack $\mathbf{s}=Ax+b \Leftrightarrow s_i=a_i^Tx+b_i$ from
eq.~\ref{ss}. We can define analytic center as:
\begin{align}
\max_{x, s>=0} \; \prod_i \frac{s_i}{\|a_i\|} 
\label{ac1}
\end{align}
This is similar to maximizing the minimum distance (from eq.~\ref{ballcenter1},
see general formulation) as if we have a small distance, then the above product
is going to be small. On the other hand, the only way to maximize the product is
to make all the slacks ($s_i$) approximately equal or at least some subset of
slacks approximately equal and others bigger than that (can be seen as a soft
version of the ball center.) Since $-\log$ is anti-monotone function, therefore
we can rewrite eq. \ref{ac1} as
\begin{align}
\max_{x, s>=0} &\; \prod_i \; \frac{s_i}{\|a_i\|}\\
\Leftrightarrow \max_{x, s>=0} &\; -\sum_i \; \log\frac{s_i}{\|a_i\|}\\
\Leftrightarrow \max_{x, s>=0} &\; -\sum_i \; \log s_i + \sum_i log \|a_i\|\\
\Leftrightarrow \max_{x, s>=0} &\; -\sum_i \; \log s_i
\label{ac2}
\end{align}
since $\|a_i\|$ is constant. Thus, minimizing the sum of negative logs of the
slacks is same as maximizing the product in eq. \ref{ac1}. Therefore, the
definition analytic center of a feasible region is given by eq. \ref{ac2} ($x$
in figure \ref{acfigure} is the analytic center.) 

\begin{figure}[!h!]
 \centering
\includegraphics[width=0.3\textwidth, keepaspectratio=true]
{./images/analyticcenter.pdf}
\vspace{-0.1in}
 \caption{Analytic Center (blue ``x'') for the feasible region (white
polyhedron) (corresponding Dikin Ellipsoid in dotted blue)}
\label{acfigure}
\end{figure}

It turns out that we can define an ellipse, centered at the analytic center,
that contains at least the polynomial fraction of the volume of the feasible
region (for e.g.\ dikin ellipsoid, more on this in next
lecture.). More concretely, for $n$ dimensional problem with $m$ constraints, we
at least cover a factor of $(1/m^n)$ of the feasible region
$\left(\texttt{Volume}(\text{Dikin Ellipsoid}) \ge
\left(\frac{1}{m^n}\right)\texttt{Volume}(X)\right)$(the proof is in book).
Therefore, we have a similar polynomial fraction guarantee as in ellipsoid
center (though weaker). But how much weaker? In $n$ dimensions, we need at least
$m=n+1$ constraints to make a closed polyhedron. So, $m>n \Leftrightarrow
(1/m^n) < (1/n^n)$ . Recall from previous section that
$\texttt{Volume}(\text{Ellipsoid Center}) \ge
\left(\frac{1}{n^n}\right)\texttt{Volume}(X)$, therefore we have
$\texttt{Volume}(\text{Dikin Ellipsoid}) \le \texttt{Volume}(\text{Ellipsoid
Center})$ i.e.\ the ellipsoid center's volume has to be at least as large as
analytic center's ellipsoid volume (but both are polynomial fraction of the
total volume of the feasible region)

{\bf Invariance}: The analytic center is invariant to scaling of the rows of $A$
(scaling will only change the constant that we dropped.) i.e.\ it is invariant
to individual scaling of the constraints ($a_i$).

{\bf Comparison to Ball Center} Unlike the ball center, analytic center will be
effected by every constraint, even the inactive ones, as the product/sum has
every constraint (though far away constraints will have less effect.) That means
that the analytic center is not the analytic center of the feasible region, it
is just the center of this particular representation of the feasible region, as
we could move an inactive constraint back and forth (a bit) and it will change
the analytic center.

{\bf So why analytic centers?} Some cool results in next lecture!
\begin{figure}[!h]
 \centering
\includegraphics[height=3in, keepaspectratio=true]
{./images/analyticcenterbad.pdf}
 \caption{Example of badly conditioned feasible region (white polyhedron).
Analytic Center (blue ``x'') for the feasible region (corresponding Dikin
Ellipsoid in dotted blue)}
\label{acbad}
\end{figure}

{\bf Feasible region with bad conditioning}: Analytic relieves the problem of
bad conditioning by stretching out the ellipse a lot (as shown in figure
\ref{acbad}) and we still get a decent volume of the feasible region. And
in fact, we can show that not only analytic center is invariant to individual
scaling of the constraints, but also any affine scaling of the feasible region.
That is, we can shift and scale our feasible region, and the analytic center
will shift and scale in exactly the same way, and the ellipsoid (dikin
ellipsoid) will shift and scale the same way as well. 

\subsubsection{Newton's method for Analytic Center}
The sum-of-logs in eq. \ref{ac2} is very smooth and infinitely differentiable
function, we know that Newton's method might be a good way to find the analytic
center. From eq. \ref{ac2} we have \\

{\bf Objective}: $\displaystyle f(x) = -\sum_i \log(a_i^Tx+b_i) = \sum_i
\log(s_i)$ where $\mathbf{s} = Ax+b$\\
{\bf Gradient}: $\displaystyle \frac{df(x)}{dx} = -\sum_i \frac{a_i}{a_i^Tx+b_i}
= -\sum_i a_i\frac{1}{s_i} = -A^T\left(\frac{1}{s}\right)$ where $(1/s)$ is
component-wise. \\
{\bf Hessian}: $\displaystyle \frac{d^2f(x)}{d^2x}= \sum_i
\frac{a_i a_i^T}{(a_i^Tx+b_i)^2} = A^T S^{-2} A$ where $S =
\texttt{diag}(\mathbf{s})$

Using this gradient and hessian, therefore we can run Newton's method on $f(x)$.
Because, our objective is strictly convex function, the hessian is strictly
positive definite and hence the Newton's direction is actually a descent
direction. This implies that the Newton's method converges from any feasible
initializer (as long as we use line search).

But we still have to fine a strictly feasible initializer, where the objective
is finite (see next lecture to get around this requirement). It turns out that
the Newton's method will converge globally in a very small number of iterations.

{\bf Adding an Objective}\\
Analytic center was for feasibility problem like finding $x$ such
that $Ax+b\ge 0$. Instead of this, now we want to find solution to $\min c^Tx$
subject to $Ax+b\ge 0$.\\
We can use the same trick and solve
\begin{align*}
 \min f_t(x) = c^Tx - \left(\frac{1}{t}\right) \sum_i\log(a_i^Tx+b_i)
\end{align*}
where $t>0$, is the trade-off between two terms. As $t \rightarrow 0$,
$\left(\frac{1}{t}\right) \rightarrow \infty$ and the log part of $f_t(x)$
dominates, and we have the solution for analytic center. As $t \rightarrow
\infty$, $\left(\frac{1}{t}\right) \rightarrow 0$ and the log part vanishes,
thus we just get the LP optimal. The center path is smooth (infinitely
differentiable for any finite t) and so the central path smoothly connects the
analytic center to the LP optimal (more details on this in next lecture.)

% **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE:

\end{document}





