\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}
\spacing{1.06}
\usepackage{ dsfont }
\usepackage{algorithm}
\usepackage{algorithmic}
\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}

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

\newcommand\tspose[1]{#1^{\scriptscriptstyle{\mathsf{T}}}}

\begin{document}

\lecture{17: Linear Programming}{Mar 16,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Xingjian Zhao, Viren Bajaj}}



\section{Linear Programming}
Let's state the problem of Linear Programming (LP) that was introduced last time. 
In the \textit{general form} of LP, we are given $$A\in \mathbb{R}^{m\times n}, \mathbf{b}\in \mathbb{R}^{m}, \mathbf{c} \in \mathbb{R}^{n}\text{ and unknown }\mathbf{x} = [x_1, ..., x_n] \in \mathbb{R}^n$$
And we have to minimize the objective function 
$$\min \tspose{\mathbf{c}} \mathbf{x}$$
such that
$$ A \mathbf{x} \geqslant \mathbf{b} $$ 

\noindent In this set up, 
\begin{itemize}
    \item $ A \mathbf{x} \geqslant \mathbf{b}  \Leftrightarrow$ ( $A_1 \mathbf{x} \geqslant \mathbf{b}_1\ \wedge$  ... $\wedge\ A_m \mathbf{x} \geqslant \mathbf{b}_m) $
    \item $n$ is the number of variables
    \item $m$ is the number of constraints
\end{itemize}

\noindent \textbf{Remarks}:\\
Notice that this form can covers the case where we want to maximize the objective function and captures all linear constraints. This is because of following equivalence relations:
\begin{enumerate}
    \item $\underset{x}{\max}[f(x)]= -\underset{x}{\min}[ -f(x)]$
    \item $A_i\mathbf{x} \leqslant \mathbf{b}_i \Leftrightarrow (-A_i)\mathbf{x} \geqslant -\mathbf{b}_i$
    \item $A_i\mathbf{x} = \mathbf{b}_i \Leftrightarrow (A_i\mathbf{x} \leqslant \mathbf{b}_i\ \wedge \ A_i\mathbf{x} \geqslant \mathbf{b}_i )$
\end{enumerate}

\noindent LP is a very powerful method since many problems can be reduced to it. For example, the 'max-flow' problem we saw in class previously. 

\subsection{Example: Max-Flow via LP}
Lets briefly restate the problem in a manner that resembles our set up for LP. \\
The unknowns are the edge flow variables $f(u,v)\in \mathbb{R}$, $(u,v)\in E$\\
And we want to maximize the objective function: $$\max \left[ \left( \sum_{u:(s,u)\in E}f(s,u)\right) - \left(\sum_{u:(u, s)\in E} f(u, s)\right)\right] $$ 
Subject to the constraints:  \\
 $$f(u,v)\geqslant 0,\ \forall (u,v)\in E$$
 $$f(u,v)\leqslant c_{u,v},\ \forall (u,v)\in E$$
 $$\left( \sum_{v:(u,v)\in E}f(u,v)\right) - \left(\sum_{v:(v, u)\in E} f(v, u)\right)=0,\ \forall v\neq s,t$$
 Here the number of variables equals the number of edges which is $m$.
 
 The number of constraints equals $m+m+(n-2)=2m+n-2$, where $n$ is the number of nodes and $m$ is the number of edges, since the first two constraints are on each edge and the third constraint is on every node except for the source ($s$) and the sink ($t$).
 
 Looking at the objective function we can deduce $\mathbf{c}\in \mathbf{R}^m$, $\mathbf{c}_{u,v}\in\{ \pm 1,0\}$. The right hand sides of the constraint equations make up $\mathbf{b}$. This puts the problem in the form of LP.

Our objective is to talk about the algorithm design for an LP solver. To achieve this goal, we must first talk about the structure of solutions to LP.

\section{Structure of Solutions to LP}
\begin{definition}


Feasible set: set of all values of $\mathbf{x}$ that satisfies all the constraints. 
\begin{equation*} 
\begin{split}
F & = \{\mathbf{x} : A\mathbf{x} \geqslant \mathbf{b}\} \\
 &  \begin{split} =\{\mathbf{x} :  & A_1\mathbf{x} \geqslant \mathbf{b_1},\\ 
 & A_2\mathbf{x} \geqslant \mathbf{b_2},\\
 & \cdot \\
 & \cdot \\
 & A_m\mathbf{x} \geqslant \mathbf{b_m} \}
 \end{split}
\end{split}
\end{equation*}
\end{definition}
\noindent Notice that each constraint $\{A_i\mathbf{x} = \mathbf{b_i}\}$ forms a hyper-plane that splits the space into two half spaces, with our solution lying in the half space $\{x_i: A_i\mathbf{x} \geqslant \mathbf{b_i}\}$. The intersection of all $m$ half spaces forms a \textit{polytope}, which is the feasible set $F$. An example of the polytope and $F$ can be seen in Fig \ref{fig:lpeg}.\\
% TODO ADD IMAGE
The nature of $F$ determines the fate of the solution to LP, $x^*$. Based on the problem definition, one of the following three scenarios may occur:
\begin{enumerate}
    \item $F=\varnothing \Rightarrow$ No solution exists because the problem has conflicting constraints. (e.g. adding $x_1 \le 1$ to example in Fig \ref{fig:lpeg})
    \item $F$ is unbounded (e.g. remove $x_1 \le 2$ from example in Fig \ref{fig:lpeg})\\
    $\Rightarrow \begin{cases}
        \text{The solution is infinite (e.g., if optimization was max $x_1+x_2 \rightarrow x_1 = \infty, x_2 = 0$), or } \\
        \text{The solution is finite (e.g., if optimization was min $x_1 + x_2 \rightarrow x_1 = 0, x_2 =1$)}
    \end{cases} $
    \item $F$ is finite (bounded) $\Rightarrow$ The solution must be finite.
\end{enumerate}

\begin{figure}
    \centering
    \includegraphics[scale=0.7]{lp2.png}
    \caption{Geometric illustration of an LP Problem and Algorithm \ref{alg:zero}.}
    \label{fig:lpeg}
\end{figure}

Now let's look into finding solutions to LP. 

\section{Finding Solutions to LP}
In this section we are trying to answer the question: given an objective function $f(\mathbf{x})=\mathbf{c}^{\mathrm{T}} \mathbf{x}$, how do we find the optimal value(s) for $\mathbf{x}$ that minimize (or maximize) the objective function?\\
Our first attempt to come up with a algorithm will be one that doesn't create a very realistic algorithm because it is difficult to implement. However, it will help us understand what solutions look like and conceptually lead us to more practical algorithms. 
\begin{algorithm}[H]
  \caption{}
  \label{alg:zero}
  \begin{algorithmic}[1]
    \renewcommand\algorithmicrequire{\textbf{input}}

    \REQUIRE $A \in \mathbb{R}^{m\times n}, \mathbf{b}\in \mathbb{R}^{m}, \mathbf{c} \in \mathbb{R}^{n}$.

    % \FOR{$j$ from $1$ to $k$}
    
    \STATE Guess $v=\min \tspose{\mathbf{c}} \mathbf{x}$ such that $A \mathbf{x} \geqslant \mathbf{b}$. Notice, by construction, $v= \tspose{\mathbf{c}} \mathbf{x}$.
    
    \STATE Consider the hyperplane $H_v=\{ \mathbf{x} :\mathbf{c}^{\mathrm{T}} \mathbf{x} = v\}$
    
    \STATE Take $v$ to be a very large value.
    % \ENDFOR

    \STATE Decrease $v$ continuously until $H_v\cap F \neq \phi$. In other words, move the hyperplane $H_v$ towards the polytope $F$ until they touch. 
    \RETURN any $\mathbf{x}^* \in H_v$, each of which is an optimal solution.

  \end{algorithmic}
\end{algorithm}

A geometric illustration of this algorithm can be found in Fig \ref{fig:lpeg}.

This algorithm is difficult to implement because we have to continuously decrease $v$ and check whether $H_v$ intersects $F$.

Notice that the first instance the hyperplane $H_v$ intersects the feasible set $F$ will be at a \textit{corner} or vertex of the polytope $F$. We formally define a corner below. 

\begin{definition}
A corner/vertex of a polytope is defined by a linear system of $n$ (the dimension of the space) equations of the form:\\
\begin{equation*}
    \begin{split}  & A_{i_1}\mathbf{x} = \mathbf{b_{i_1}}\\ 
 & A_{i_2}\mathbf{x} = \mathbf{b_{i_2}}\\
 & \cdot \\
 & \cdot \\
 & A_{i_n}\mathbf{x} = \mathbf{b_{i_n}}
 \end{split}
\end{equation*}
\end{definition} 
\begin{definition}
For some $\mathbf{x}\in F$, if $ A_{i}\mathbf{x} = \mathbf{b_{i}}$, the $i^{th}$ constraint is tight.
\end{definition}
Thus the optimal solution $x^*$ is in the corner of the polytope means that it is defined by the solution to a system of $n$ tight constraints. Thus the number of  optimal solutions can potentially be $n$, because we can take $n$ different hyperplanes. %I dont understand%

Based on this discussion, we can design an implementable but inefficient algorithm for solving LP as follows.
\begin{algorithm}[H]
  \caption{}
  \label{alg:zero-prime}
  \begin{algorithmic}[1]
    \renewcommand\algorithmicrequire{\textbf{input}}

    \REQUIRE $A \in \mathbb{R}^{m\times n}, \mathbf{b}\in \mathbb{R}^{m}, \mathbf{c} \in \mathbb{R}^{n}$.

    % \FOR{$j$ from $1$ to $k$}
    
    \STATE {Try all possible corners/vertices.
    \begin{itemize}
        \item  Try every ${m\choose n}$ sets $S=\{i_1,...i_n \}$. 
        
        \item Solve 
\begin{equation*}
\begin{split}  & A_{i_1}\mathbf{x} = \mathbf{b_{i_1}}\\ 
 & A_{i_2}\mathbf{x} = \mathbf{b_{i_2}}\\
 & \cdot \\
 & \cdot \\
 & A_{i_n}\mathbf{x} = \mathbf{b_{i_n}}
 \end{split}
\end{equation*}
Let the solution be $\mathbf{x}^S$.
\end{itemize}}
    \STATE Consider the hyperplane $H_v=\{ \mathbf{x} :\mathbf{c}^{\mathrm{T}} \mathbf{x} = v\}$
    
    \STATE Check if $\mathbf{x}^S$ is feasible by checking if $A \mathbf{x}^S \geqslant \mathbf{b} $ is satisfied.

    \RETURN  $\min \tspose{\mathbf{c}}\mathbf{x^S}$ for an $\mathbf{x}^S$ that is feasible.
    
  \end{algorithmic}
\end{algorithm}


\textbf{Runtime:} 
\begin{align*}
    \text{The runtime of this algorithm is} = &\text{ number of corners of the polytope } *\\
    &\text{(time to solve the system of n equations} +\\
    &\text{time to check feasibility of $x^S$} +\\ 
    &\text{computing the optimal value $\tspose{c}x^S$)}\\
    =&{m \choose n} ([\text{time to solve }A_sx = b] + m \cdot n + n)
\end{align*}
Notice that ${m \choose n} \approx m^n$, which is very slow. Also note that it is not immediately clear that the time taken to write down a solution to the linear program can be done efficiently. For instance, if a solution involved the number pi, or other transcendental numbers, it might take some time to write down the solution. First, let's look at the time taken to solve a system of linear equations. 
\subsection{Time to solve a system of linear equations}
Given $Ax \in b, A \in \mathds{R}^{m\texttt{x}n}, b \in \mathds{R}^{m}$ and unknown $x \in \mathds{R}^{n}$, we want to solve $Ax=b$.

\subsubsection{Special case: A is a square matrix ($n=m$)}
First, we define a well known theorem from linear algebra.
\begin{theorem}
The following are equivalent: 
\begin{enumerate}
    \item A is invertible ($A^{-1} exists$)
    \item $det(A) \neq 0$
    \item Columns of A are linearly independent
    \item Rows of A are linearly independent
    \item $Ax=b$ has a unique solution. This also means, $x=A^{-1}b$.
\end{enumerate}
\end{theorem}
Some helpful relations:
\begin{enumerate}
    \item $det(A)= \sum_{\pi: [n]\rightarrow [n]}{}sign(\pi)\prod_{i=1}^{n}A_{i,\pi(i)}$, where $\pi$ is a permutation.
    \item $x_i =\frac{det(A_i)}{det(A)}$, where $A_i$ is $A$ with the
      $i$th column replaced with the vector $b$.
\end{enumerate}

\begin{corollary}
Suppose $A_{ij},b_j$ are all integer, described by B bits, then the solution $x_i$ is rational and needs only $O(nlogn+Bn)$ bits to describe.
\end{corollary}
\begin{proof}
Using helpful relation 1, we can see that to describe $x_i$ we need $log(\text{max value of }det(A_i)) + log(\text{max value of }det(A))$ bits.From helpful relation 2, we can see that $|det(A)| \le n! (2^B)^n$. This is because there are $n!$ many permutations, the max value of each $A_{ij}$ of length B bits is $2^B$, which is multiplied $n$ times. Since $n!$ can be upper bounded by $n^n$, we can say $|det(A)| \le n^n 2^{Bn}$.
This implies the number of bits needed to describe $x_i = O(log(n^n 2^{Bn})) = O(nlogn + Bn)$.
\end{proof}
This runtime bound on a solution of a system linear equations also translates to the runtime bound for solutions for linear programs.

Notice that since it takes at least time $n$ to write down $x_i$, it will take time at least $n^2$ to write down any solution to a system of linear equations, and therefore any LP. This time is non-trivial. 

\subsubsection{General case: A is rectangular ($n \neq m$ or $det(A) = 0$)}
Before we tackle this case we look at some more definitions.
\begin{definition}
col(A) = set of columns of $A \subset \mathds{R}^m$
\end{definition}
\begin{definition}
$span(col(A)) = \{y \in \mathds{R}^m: \exists x \in \mathds{R}^n | y = \sum_{i=1}^n x_i A_i = Ax\}$
\end{definition}
Note that $span(col(A))$ is the space of all possible vectors that equal $Ax$. This is important because we want to solve the equation $Ax=b$. Therefore
\begin{itemize}
    \item if $b \notin span(col(A))$ then there is no solution, and
    \item if $b \in span(col(A))$ then one or more solutions exist.
\end{itemize}
Now, given a solution exists, how do we find it? \\
Consider the following sets.
\begin{definition}
$S$ = set of linearly independent vectors from col(A)
\end{definition}
\begin{definition}
$\bar{S}$ = completion of S to a basis
\end{definition}
Thus, $span(S) = span(col(A)) \subseteq \mathds{R}^m$ and $|\bar{S}| = m$. \\
We can index entries of $\bar{S}$ and write $S = \{\bar{S_1}, \dots, \bar{S_m} \}$.
Now, if we solve
$$
\begin{bmatrix} 
\bar{S_1}, \dots, \bar{S_m} 
\end{bmatrix}
\begin{bmatrix}
           x' \\
           y
\end{bmatrix} = b$$
where $x'$ are the entries of the vector $x$ that will multiply with the columns of A, and $y$ are the entries that will multiply with the columns that form the completion, i.e. $\bar{S} \backslash S$.\\
Since $\bar{S}$ is a basis of $\mathds{R}^m$, there exists a unique solution to the equation above $\begin{bmatrix}
           x' \\
           y
\end{bmatrix}$\\

Then our solution to the system of equations becomes:
\[
x_i^* = 
\begin{cases}
    x_i',& \text{if if col $i$ of $A$ is in $S$}\\
    0,              & \text{otherwise}
\end{cases}
\]

The remaining portion of this topic will be covered in the next lecture. 
\end{document}
