\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prove}[theorem]{To Prove}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{23: Interior Point Method}{Apr 6,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Shrihan Pasikanti, Nikhil Cherukupalli}}
  
% \section{General Remarks}

% \begin{enumerate}
%     \item Homework 5 is released and due on 04/15/21
%     \item Final project is due on 4/23/21
% \end{enumerate}


\section{Introduction}

In today's lecture, we dive into the concept of the interior point method by applying the previously visited principles of convexity and Newton’s Method.

\section{Interior Point Method for Linear Programs}
In this section, we try to solve the following problem:

$$\min c^Tx$$ $$  \text{ s.t. } Ax\leq b$$

\noindent
We take $K$ to be the set of acceptable values. That is, $K: = \{x: Ax \leq b \}$.

\begin{definition}\[
      f(x) = \left\{
	\begin{array}{ll}
		c^Tx  & \mbox{if $x \in K$ } \\
		+\infty & \mbox{if $x \not\in K$}
	\end{array}
\right.
\]
\end{definition}

\noindent
The problem is that $f$ may not be sufficiently smooth on the boundary $\partial K$.

%%%\\
\begin{definition}
    \[
    F(x) = \left\{
	\begin{array}{ll}
		< \infty  & \mbox{if $x \in K$ } \\
		+\infty & \mbox{if $x \not\in K$}
	\end{array}
\right.
\]
\end{definition}

\noindent
We want $F(x)\rightarrow\infty$ as $x\rightarrow\partial K$. We will define this function in detail later so that it has the aforementioned property.

\begin{definition}[Barrier Function]
Let's define: $$f_{\eta}(x)=\eta c^{T}x+F(x)$$ 
where $\eta$ is a scalar s.t. $\eta > 0$
\end{definition}

\noindent
Using our new definitions, we can restate the original problem.\\
\textbf{New goal}: Optimize $f_{\eta}(x)$ (i.e find $\underset{x\epsilon\mathbb{R}}{\min}\,f_{\eta}(x)$) \\

\noindent
Now, we take
\begin{align*}
    F(x):&=\lg\underset{i=1}{\overset{m}{\prod}}\,\frac{1}{b_{i}-A_{i}x} \\
    &= \underset{i=1}{\overset{m}{\sum}}\,\lg\frac{1}{b_{i}-A_{i}x}\\
    &= \underset{i=1}{\overset{m}{\sum}}-\lg(b_{i}-A_{i}x)
\end{align*}
where $A_i$ denotes the $i$-th row of matrix $i$.

\begin{definition}
$x_{\eta}^{*}=\underset{x}{\arg\min} \, f_{\eta}(x)=\underset{x}{\arg\min} \, \{\eta c^{T}x+F(x)\}$
\end{definition}

\begin{claim}
$f_{\eta}(x)$ is convex
\end{claim}

\begin{proof}
It is sufficient to show that the Hessian matrix ($\nabla^{2}f_{\eta}$) is positive semi-definite, which implies that all its eigenvalues ($\lambda_i \geq 0$).\\
We know:
\begin{align*}
    f_{\eta}(x)&=\eta c^{T}x+F(x) \\
    \nabla f_{\eta}(x)&=\eta c^{T}+\sum\frac{A_{i}}{b_{i}-A_{i}x} \\
    \nabla^{2}f_{\eta}(x)&=\sum\frac{A_{i}^{T}A_{i}}{(b_{i}-A_{i}x)^{2}}    
\end{align*}
\noindent
Now, consider an arbitrary vector $y$ ,
\begin{align*}
    y^{T}\nabla^{2}f_{\eta}(x).y &= \sum\frac{y^{T}A_{i}^{T}A_{i}.y}{(b_{i}-A_{i}x)^{2}} \\
    &= \sum\frac{||A_{i}y||_{2}^{2}}{(b_{i}-A_{i}x)^{2}} \\
    & \geq 0
\end{align*}
\noindent
Hence, the Hessian is positive semi-definite and therefore, $f_\eta(x)$ is convex.
\end{proof}

\begin{definition}[Slack Variable]
    $\xi := (b_i - A-ix)^2$
\end{definition}
\includegraphics[width=0.95\textwidth]{pictorialRepr.png}

\begin{remark}
If $A$ is a full-rank matrix (vol$(k)>0$), then $\lambda_{min}\left(\nabla f_{\eta}(x)\right)>0$, implying that $f_{\eta}(x)$ is strongly convex.
\end{remark}

\begin{definition}[Analytic Center]
$x_{0}^{*}$ is the analytic center of K if $x_0^* = arg\,min_{x\in K} f_o(x)$
\end{definition}

\noindent
We \textbf{observe} that $x_\eta^*$ is a continuous function w.r.t. $\eta$.

\begin{definition}[Central Path] The set $\{x_\eta^* :\eta > 0\}$ is the central path of $f$.
\end{definition}


\noindent
\textbf{\emph{Algorithm 0: }}We solve $x_{\eta}^{*}$ when $\eta$ is a very
large number
\begin{enumerate}
\item Recall that Gradient Descent depends on condition number ($\kappa$) of $F$, which could be very large.
\item Newton's method is much faster but requires a ``warm'' start.
\end{enumerate}


\noindent
\textbf{\emph{Algorithm 1: }}The main idea here is to walk along the central path as
$\eta$ increases from $\eta\approx0$ to a very large value of $\eta$.
\begin{enumerate}
\item Start at $x_{\eta_{0}}^{*}$for $\eta_{0}>0$ such that $[x_{\eta_0}^{*}\approx x_{0}^{*}]$. Note here we \textbf{assume} that we know $x_{0}^{*}$
\item For each iteration $t$ : let $\eta_{t+1}=\eta_{t}.(1+\alpha)$, for some small value $\alpha>0$.
Then, compute $x_{\eta_{t+1}}^{*}$ using Newton's
method with a warm start setting the initial value to $x_{\eta_{t}}^{*}$
\item Terminate once $\eta_t$ is ``sufficiently large enough''. Return
$x_{\eta_{t_f}}^{*}$ for where $\eta_{t_f}$ is the stopping point.
\end{enumerate}

\begin{fact}
The value $x_{\eta_{i+1}}^{*}$ is within the convergence radius
of $x_{\eta_{i}}^{*}$ (i.e there is only a minor perturbation between
them).
\end{fact}

\noindent
\textbf{\emph{Algorithm 2: }}Here we present an optimization of \emph{Algorithm 1}.\\
\noindent
For each iteration $t$ : $\eta_{t+1}=\eta_{t}.(1+\alpha)$ , we don't
need to compute the optimal value of $x_{\eta_{t+1}}^{*}$'s for each intermediate $\eta_{t+1}$.
In fact, each time we take a Newton's step, we are already in the radius of convergence. So, we are merely trying to approximate $x_{\eta_{t+1}}^{*}$ in this algorithm, which results in a cruder approximation of the central path but also uses fewer steps.

\section{Analysis of the Terminal Condition}
Here we examine some properties of the terminal condition $\eta_T$.
\begin{claim}
\[
c^{T}x_{\eta}^{*}-c^{T}x^{*}\leq m/\eta
\]
\end{claim}

\noindent
Before proving the claim, let us make a brief aside. \\
First, set $\epsilon = \frac{m}{\eta_T}$. Then, $(1 + \alpha)\eta_0^T = \frac{m}{\epsilon}$ So, $T = \mathcal{O}(\frac{\lg{\frac{m}{\epsilon \eta_0}}}{\alpha})$. Note that it suffices to take $\alpha = \frac{1}{Poly(n, m)}$. \\

\noindent
Now, let us prove the claim.
\begin{proof}
By definition of $x_{\eta}^{*}$: the gradient convex function $\nabla f_{\eta}(x^{*})=0$. Then,
\begin{align*}
    \Longleftrightarrow\eta c+\nabla F(x_{\eta}^{*})&=0 \\
    \frac{-\nabla F(x_{\eta}^{*})}{\eta} &= c
\end{align*}

\noindent
So, we need to show that:

\[
\frac{\nabla F(x_{\eta}^{*})^T}{\eta}\left(x^{*}-x_{\eta}^{*}\right)\le\frac{m}{\eta}
\]
Take any $x, y \in K$. Then,
\begin{align*}
    \nabla F(x)^T (y-x) &= \sum_{i=1}^m \frac{A_i}{b_i - A_ix}(y-x) \\
    &= \sum_{i=1}^m \frac{A_iy-A_ix}{b_i - A_ix} \\
    &= \sum_{i=1}^m \frac{b_i - A_ix-(b_i - A_iy)}{b_i - A_ix} \\
    &= m - \sum_{i=1}^m \frac{b_i - A_iy}{b_i - A_ix} \\
    &\leq m
\end{align*}
Then, if we set $x=x_\eta^*, y =x^*$ and divide the expression above by $\eta$, our result is proven. \qedhere \\
Therefore, the assumed value of $T = \mathcal{O}(\frac{\lg{\frac{m}{\epsilon \eta_0}}}{\alpha})$ is correct.
\end{proof}
\vspace{15mm}
\section{Analysis of Starting Point}
Here we analyze the process to compute the true analytical center. \\

\noindent
We can obviously compute $x_{\eta_{0}}^{*}$ from $x_{0}^{*}$ by Newton's method as long as $\eta_{0}$ is sufficiently small. Suppose we have any $x' \in K$ :

\begin{claim}
$\forall$ $x' \in K\,\backslash\,\partial K$ (i.e. $x'$ strictly inside the boundary of $K$), $\exists\,\eta,c'$
such that:

\[
x'=\underset{x}{\arg\min}\left(\eta c'x+F(x)\right)
\]
\end{claim}

\begin{proof}
The gradient at point $x'=0$. So,
\begin{align*}
    \nabla\left(\eta c'x+F(x)\right)\left(x'\right)&=0 \\
    \implies \eta c'+\nabla F(x')&=0 \\
    \implies -\,\frac{\nabla F(x')}{\eta} &= c'
\end{align*}
So, we can merely fix $\eta=1$ and find $c'$.
\end{proof}


\textbf{\emph{Algorithm: }}
\begin{enumerate}
\item Given $x'$ , we compute $c'=-\nabla F(x')$ with $\eta=1$.
\item Walk the central path \emph{back}, and decrease $\eta_{t+1}=\eta_{t}.(1-\alpha)$
by taking Newton's step. This roughly approximates $x_{0}^{*}$ (i.e. the
true analytical center).
\item Stop at $t=T$ large enough so that we are close enough to $x_{0}^{*}$
\end{enumerate}


\begin{remark}
To find a feasible $x'$,
we solve a different linear program $LP'$ to $\min t$ subject to the
constraints $A_{i}x\leq b_{i}+t$. \\
\noindent
For this $LP'$, a feasible solution can be: $x=0, \,t=\underset{i}{\max}(-b_{i})$
\end{remark}

\begin{remark}
It is enough to set $\alpha:=\Theta\left(\frac{1}{\sqrt{m}}\right)$
\end{remark}
\vspace{7mm}

\noindent
In the next lecture, we will prove Remark 14, and proceed to talk about \textit{Multiplicative Weights
Update} and then switch to \textit{Large Scale Models}.

\end{document}
