\documentclass[11pt]{article}
\usepackage{latexsym, color}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{bbold}

\newcommand{\E}{{\mathbb E}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\eps}{\epsilon}
\renewcommand{\O}{\mathcal{O}}

\newcommand{\1}{\mathbb 1}
\renewcommand{\L}{\widehat L}
\newcommand{\Lf}{f^T \L f}

\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced Algorithms (Spring’20)} \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}[3]{\handout{#1}{#2}{#3}{}{#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}

\begin{document}
\handout{COMS 4995-2: Advanced Algorithms (Spring’20)}
{April 2, 2020}
{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}
{Scribe:\hspace{0.08cm}\emph{Jakwanul Safin} (js5142)}
{Lecture 18: Interior Point Method for Linear Programming}

\section{Introduction}

This lecture focuses the on the Interior Point Method for solving linear programs \([\text {Karmaker } `84]\)

A linear program is an optimization of the form,

\begin{equation}
\begin{aligned}
    \underset{x \in \R^n}{\min} &c^Tx \\
    \text{s.t. } &A x \leq b 
\end{aligned}
\end{equation}

where $A \in \mathbb{R}^{m \times n}$, $c \in \R^n$ and $b \in \R^m$. Additionally, we let $m$ denote the optimal value if it exists and $x^*$ be the point that attains this value.

Our approach in this lecture is to relax this problem into a continuous unconstrained optimization and apply the ideas from the previous lecture find the optima.

\section{Converting To Unconstrained Optimization}

Define the feasibility set as $$k \triangleq\{x: A x \leq b\}$$. 

We want to relax the minimization by defining a new function,
$$f^\prime = c^Tx + F(x)$$
such that
\begin{align*}
    f^\prime(x) &= x^Tx \text{ if } x \in K \\
    f^\prime(x) &= \infty \text{ if } x \notin K
\end{align*}

To do so we define,

$$f_{\eta} = \eta c^Tx + F(x)$$

where $\eta \in \R$ and $F(x)$ has the properties

\begin{align*}
    F(x) &< \infty \quad \text{ for } x\in K\\
    F(x) &\rightarrow \infty \quad \text{ as } x \rightarrow \partial K 
\end{align*}

Let $A_i$ denote the $i$th row of $A$. We will choose

\begin{equation}
    F(x) = \operatorname{log}\left[ \prod_{i = 1}^m \frac{1}{b_i-A_i x} \right] = -\sum_{i = 1}^m \operatorname{log}\left[b_i-A_i x\right]
\end{equation}

Our optimization problem is now 

\begin{equation}
\min _{x \in \mathbb{R}^{n}} f_{n}(x) \triangleq x_{n}^{*}
\end{equation}

Intuitively $x_\eta^*$ approaches $x^*$ as $\eta$ tends to $\infty$.

\section{Solving the optimization}

\begin{center}
    \includegraphics[scale = 0.5]{feabilityDiagram.png}
\end{center}

$$x_0^* \triangleq \text{ the analytic center of $K$}$$
$$l = \{x_\eta^* | \eta \in \R, \eta > 0\} \triangleq \text { the central path }$$

\begin{claim}
For all $\eta > 0$, $f_\eta$ is convex.
\end{claim}
\begin{proof}
First we compute the gradient and the hessian.

\begin{equation}
\begin{aligned}
f_{\eta}(x) &= \eta c^Tx + F(x)\\
\nabla f_{\eta}(x)&=\eta c+\nabla F(x)=\eta c+\sum_{i=1}^{m} \frac{A_{i} x}{b_{i}-A_{i} x}\\
\nabla^{2} f_{n}(x)&=\nabla^{2} F(x)=\sum_{i=1}^{m} \frac{A_{i}^{\top} A_{i}}{\left(b_{i}-A_{i} x\right)^{2}}
\end{aligned}
\end{equation}

For any vector $\gamma \neq 0$,

\begin{equation}
\begin{aligned}
\gamma^{\top} \nabla^{2} f_{\eta}(x) \gamma &=\sum_{i=1}^{m} \frac{\gamma^{\top} A_{i}^{\top} A_{i} \gamma}{\left(b_{i}-A_{i} x\right)^{2}} \\
&=\sum_{i=1}^{m} \frac{\left\|A_{i} \gamma\right\|^{2}}{\left(b_{i}-A_{i} x\right)^{2}} \geq 0
\end{aligned}
\end{equation}

Therefore $f_\eta$ is convex.

\end{proof}

Note that if $A$ is full rank ($\operatorname{vol}(K) > 0$) then $f_\eta$ is strictly convex and there is a unique minimum.

\textbf{Idea 1 (Naive Approach): } 

Why not solve $\eta$ ``very large"? The problem with this approach is that if we use gradient descent then the convergence is very slow. And we can not use Newton's Method since there is no warm start.

\bigskip

\textbf{Idea 2 (Following Central Path): }

\begin{itemize}
    \item Start at $x_{\eta_0}^*$ for small $\eta_0$
    \item Walk along central path. At each iteration $t$:
        \begin{itemize}
            \item $\eta_{t+1} = \eta_t (1+\alpha)$
            \item Run Newton's Method for $f_{\eta_{t+1}}$ with warm start $x_{\eta_t}^*$
        \end{itemize}
    \item Terminate when $\eta$ large enough
\end{itemize}

\bigskip
\textbf{Idea 3 (Improved performance): }

\begin{itemize}
    \item Start at $x_{\eta_0}^*$ for small $\eta_0$
    \item Walk along central path. At each iteration $t$:
        \begin{itemize}
            \item $\eta_{t+1} = \eta_t (1+\alpha)$
            \item $x_{t+1} = x_t + n(x_t)$, where $n(x_t)$ is a single step of Newton's method for $f_{\eta_{t+1}}$
        \end{itemize}
    \item Terminate when $\eta$ large enough
\end{itemize}

\section{Stopping Condition on $\eta$}

\begin{claim}
    $$c^Tx_\eta^* - c^Tx^* \leq \frac{m}{n}$$
\end{claim}

Note that with this claim, if \(\eta=\frac{m}{\eps}\) then \(c^{\top} x_{n}^{*}-c^{\top} x^{*} \leq \eps\)

\begin{proof}

$$0 = \nabla f_{\eta}\left(x_{\eta}^{*}\right)=c^{\top}\eta+\nabla F\left(x_{\eta}^{*}\right)$$
$$\implies c^{\top}=-\frac{\nabla F\left(x_{\eta}^{*}\right)}{\eta}$$

We want to show that

$$c^{\top} x_{\eta}^{*}-c^{\top} x^{*}=c^{\top}\left(x_{\eta}^{*}-x^{*}\right)=\frac{\nabla F\left(x_{\eta}^{*}\right)}{\eta}\left(x^{*}-x_{\eta}^{*}\right) \leqslant \frac{m}{\eta}$$

Now we show that \(\forall x, y \in \mathbb{K}\) : \(\nabla F(x) \cdot(y-x) \leq m\)
$$
\nabla F (x)(y-x)=\sum_{i=1}^{m} \frac{A_{i}}{b_{i}-A_{i} x}(y-x)=\sum_{i=1}^{m} \frac{\left(b_{i}-A_{i} x\right)-\left(b_i-A_i y\right)}{b_{i}-A_{i} x} = m - \sum_{i=1}^m \frac{b_i-A_iy}{b_{i}-A_{i} x}
$$

Since $x, y \in K$, we know that $Ax \geq b$ and $Ay \geq b$, so for all $i$,

$$\frac{b_i-A_iy}{b_{i}-A_{i} x} \geq 0$$

Therefore, 

$$\nabla F (x)(y-x) \leq m$$

as desired.
\end{proof}

\section{Determining $x_{\eta_0}^*$}

We assume $\operatorname{vol}(K) \neq 0$. To find our starting point we start by finding some feasible point, $x^\prime \in K$

\begin{claim}
    Our LP in (1) has nonempty $K$ if and only if the LP
    
    \begin{equation}
    \begin{aligned}
        \underset{x \in R^n, t \in \R^m}{\min} &t \\
        \text{s.t. } &A x \leq b + t 
    \end{aligned}
    \end{equation}
    
    has optima equal to $0$.
\end{claim}

$0$ is a feasible point of (6) so we can use our interior point method to solve.

\begin{claim}
    \(\exists c^{\prime}\) s.t.

$$x^{\prime}=\min \eta {c^{\prime}} x+F(x)$$
\end{claim}
\begin{proof}

If \(x^{\prime}\) is to be opt, then

\begin{align*}
    &\nabla\left(\eta c^{\prime} x^{\prime}+F(x)\right)=0\\
    \Leftrightarrow &\quad \eta^{\prime}c^\prime + \nabla F(x^\prime)=0\\
    \Leftrightarrow & \quad c^\prime = \frac{\nabla F(x^\prime)}{\eta}
\end{align*}
\end{proof}

\textbf{Idea 3.1 (Finding Initial Point)} We walk backward along the central path from our feasible point.
\begin{itemize}
    \item Find feasible point $x^\prime$ by solving (6) and $c^\prime$ from claim 4.
    \item Starting from $c^\prime$, walk backwards along central path for $c^\prime$. At each iteration $t$:
        \begin{itemize}
            \item $\eta_{t+1} = \eta_t (1-\alpha)$
            \item $x_{t+1} = x_t + n(x_t)$, where $n(x_t)$ is a single step of Newton's method for $f_{x_{t+1}}$
        \end{itemize}
    \item Terminate when $\eta$ small enough.
\end{itemize}
Then run our main algorithm from $x_\eta$, which is approximately the analytic center.

\section{Setting $\alpha$ and Runtime}

\begin{claim}
    $\alpha = \tfrac{1}{8\sqrt{m}}$ is sufficient for correctness.
\end{claim}

\begin{proof} \textit{sketch} 

The proof demonstrates an invariant on the distance between $x_t$ and $x_{\eta_t}^*$. At each iteration each newton step decreases this distance, but scaling $\eta$ by $(1 + \alpha)$ increases it. 

\end{proof}

Starting from $\eta_0$, by claim 2, it is sufficient to stop at $\tfrac{m}{\eps}$. 

\begin{align*}
    T &= \operatorname{log} _{1+\alpha} \frac{ m/\eps}{\eta_{0}}\\
    &=\O \left(\tfrac{1}{\alpha} \operatorname{log} \frac{m}{\eps \eta_0}\right)\\
    &=\O \left(\sqrt{m}\operatorname{log} \frac{m}{\eps \eta_0}\right)
\end{align*}


\end{document}
