\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\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{remark}[theorem]{Remark}
\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}

\begin{document}

\lecture{19: Linear Programming Duality, Ellipsoid Algorithm}{Mar 23,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Qianjun Chen, Cheng Zhang}}

\section{Overview}

Today's lecture is about LP duality, and ellipsoid algorithm, which is the first poly-time algorithm for LP.

\section{Linear Programming Duality}
Standard form:
$$\upsilon^{*}= min\,c^{T} x$$
$$s.t.\: Ax = b $$
$$x \geq0 $$
which $c\in\mathbb{R}^n $, $b\in\mathbb{R}^m $, and $A\in\mathbb{R}^{m\times n} $.\\
\begin{enumerate}
\item If we want to prove optimal value $\upsilon^* \leq \upsilon$, just show some $x\in F$, $c^T x\leq \upsilon$.
\item $\upsilon \geq ...?$
\end{enumerate}
\begin{definition}
Dual of standard form linear programming: 
$$ \omega^* = max\, b^Ty$$
$$s.t.\: A^Ty \leq c $$
$$ y \geq \mathbb{R}^m$$
\end{definition}
You'll notice that conveniently the dual of the standard form is what we call the general form of linear program. 
\begin{theorem}[weak duality]
$$\omega^* \leq \upsilon^*$$
\end{theorem}
So in a sense, these dual linear program, will provide such lower bound. It's basically coming from the weak duality theorem. Let's prove this, and basically, this will motivate how we came up with a linear program. 
\begin{proof}
Fix $x\in F$: $Ax=b$ and $x\geq0$. Fix any $y\in\mathbb{R}^m$, $y^T Ax=y^Tb$, which $y^TA$ is a vector $\in \mathbb{R}^n$. Remember, in standard form, x is positive, and the standard form is minimizing the product of x with some vector c.\\*
Suppose y such that $y^T A \leq c^T$ (each coordinate). This implies that:
\begin{enumerate}
    \item $y^Tb=y^TA x\leq c^T x$
    \item $max\: y^Tb\leq min\: c^T x$. y: $y^TA\leq c^T$, which is $\omega^*$. x: $Ax=b$, $x\geq0$, which is $\upsilon^*$.
\end{enumerate}
\end{proof}
So there are two questions. The first is, is this a good lower bound? 

\section{Dual of Dual}
If we take a dual, and take its dual, we get the primal: 
$$\upsilon^{*}= min\,c^{T} x$$
$$s.t.\: Ax = b $$
$$x \geq0 $$
This is the dual:
$$ \omega^* = max\, b^Ty$$
$$s.t.\: A^Ty \leq c $$\\*
Mechanically, once you put the primal in the standard form, then there is an. automatic way to get the dual. We need to take our dual, put it in a standard form. \\
Dual return to the standard form:
$$-\omega^*=min\, -b^Ty, A^Ty\leq c$$
$$=min\,-b^T(y^+-y^-)$$
$$A^T(y^+-y^-)+\delta$$
which $y^+$, $y^-$, $\delta \geq0$, $y^+$, $y^- \in \mathbb{R}^m$, $\delta \in \mathbb{R}^n$. This is our dual return to the standard form.\\\\
Dual of the dual: \\
unknowns: $z\in \mathbb{R}^n$.\\
Objective function: $max \, c^T z$.\\
Constraints:\\
The constraint matrix of dual return to the standard form is :
\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 $A^T$ & $-A^T$ & $I_n$ \\ 
 \hline
 $y^+$ & $y^-$ & $\delta$ \\ 
 \hline
\end{tabular}
\end{center}
So the constraints will look like this:
\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 A &  & $-b$ \\ 
 \cline{1-1} \cline{3-3}
 -A & $\cdot z \leq$ & $+b$ \\ 
 \cline{1-1} \cline{3-3}
 I & & 0 \\
 \hline
\end{tabular}
\end{center}
Each row here we have:
$$A_i^T z=b_i \Leftarrow \left\{\begin{array}{ll}
A_i^T\cdot z \leq -b_i \\
-A_i^T\cdot z \leq +b_i \\
z_i \leq 0 \\
\end{array}\right.$$
which $A_i= ith$ row of A.\\
Let's replace the variable $z'=-z$. What we obtain is that 
Dual of (-Dual): 
$$max\, c^T(-z')$$
$$s.t. \: Az'=b$$
$$z'\geq0$$
So Dual of the Dual:
$$-max\, -c^T(-z')=min\, c^Tz'$$
$$s.t. \: Az'=b$$
$$z'\geq0$$
which is exactly equal to primal. \\
\begin{remark}
It does not prove immediately the strong duality. 
\end{remark}

\section{Strong Duality}

\begin{theorem}
    $w^* = \upsilon^*$
    \hfill
	\fbox{\begin{minipage}[c][3.5cm][t]{4cm}{
	\begin{align*}
		\upsilon^* = &\min c^T x\\
		&Ax = b, x \geq 0\\
		w^* = &\max b^T y\\
		&A^Ty \leq c
	\end{align*}
	} \end{minipage}}
\end{theorem}

The actual proof of strong duality is painful, there are a lot case analysis, so we want to do pseudo proof by its intuition.

\noindent \textbf{Intuition:} Consider dual with $y \rightarrow -y$, $c \rightarrow -c$

$\qquad \qquad \Rightarrow -w^* = \min b^T y$

$\qquad \qquad $s.t, $ A^T y \geq -c$, $y \in \mathbb{R}^m$\\

Consider a ball is pulled down by gravity in a m-dimensional space. Each equation $A_i^T y = c_i$ forms a hyper-plane in this space. The ball can only be dropped into the convex composed by these hyper-planes. 

\includegraphics[scale=0.65]{a1.png}

What does it mean that ball is resting?

At this point, there must exist the same force pushing it upward to against the gravity force pulling it down. This force is exactly these hyper-planes the ball is resting on.

$\Rightarrow$ a set S of constrains/half-spaces 

\begin{enumerate}
	\item[(1)]
	$i \in S \Rightarrow A_i y = c_i$ (tight constrains)
	\item[(2)]
	$\exists$ coefficients $x_1,\cdots,x_n \in \mathbb{R}_+$\\
	$\sum x_i A_i = b \Leftrightarrow Ax = b$ 
	\item[(2')]
	if $i \notin S$, it is not a hyper-plane on which the ball is resting, then $x_i = 0$
\end{enumerate}

Value of primal: $-c^T x$

Value of dual: $-b^T y$

To compute these two values based on part (1) and part (2) above:

\begin{align*}
    \sum x_i A_i y = y^T Ax & \overset{\textcircled{1}}{=}  \sum x_i c_i = c^T x\\
    & \overset{\textcircled{2} }{=} y^T b = b^T y
\end{align*}

Therefore, we've proven the value of primal is equal to the value of dual.\hfill \qedsymbol \\

\noindent \textbf{Note:} for every $i \in [n]$, we must have: $x_i = 0$, or $A_i y = c_i$, or both. (complementary slackness)

\section{Ellipsoid Algorithm \cite{1}}
It solves feasibility problem.\\
First, we need to define what feasibility problem is, feasibility problem (FP) is to find $x \in Q_v$ if exists, for such:
$$Q_\upsilon = \{x: Ax \geq b, c^T x \leq \upsilon\}$$
in general form, that is LP : $\upsilon^* = \min c^T x$, $Ax \geq b$.

The feasibility problem is definitely no harder than solving the LP, since once we solve the LP, we will find the optimal $x$, that can be used to solve FP. 

\begin{remark}
    can solve LP using FP with ploy-time slow-down
\end{remark}

\begin{proof}
    Do binary search on $\upsilon$. \\
    Let R = upper bound on value of $|v^*|$\\
    Without solving a linear program, it is easier to find an upper bound of absolute value of the $V^*$, in particular:\\
    $$\lg_2 R \leq ploy(n,m) \cdot B$$
    where m is the number of constraints, B is the number of bits to represent each input number


\begin{algorithm}[H]
  \caption{Binary Search}
  \label{alg:zero}
  \begin{algorithmic}[1]
    \renewcommand\algorithmicrequire{\textbf{input}}

    \STATE set $l = -R$, $r = +R$
    \STATE $m = \frac{l+r}{2}$
    \IF{$Q_m$ is feasible}
    \STATE recursive on $l = l$, $r = m$
    \ELSE 
    \STATE recursive on $l = m$, $r = r$
    \ENDIF
    \STATE stop when $r-l$ is sufficiently small, $\approx \frac{1}{R^{O(1)}}$
    \STATE then optimal solution $\upsilon^* \approx l \approx r$
  \end{algorithmic}
\end{algorithm}

\noindent number of binary search iterations = $O(\log R)$ = $O(poly(n,m)B)$,\\ 
solving $Q_v = \{x : Ax \geq b, c^T x \leq \upsilon\}$
\end{proof}

From the perspective of this problem, there is no really difference between inequality $Ax\geq b$ and inequality $c^T x \leq \upsilon$. 

\includegraphics[scale=0.4]{a2.png}

The goal is to find any x point inside the space.

\section{Next Class}
How does Ellipsoid Algorithm find such x point, then we will start talking about gradient descent for general functions.

\begin{thebibliography}{1}
	\bibitem[Khachiyan '79]{1} L. G. Khachiyan, “A polynomial algorithm in linear programming”, Dokl. Akad. Nauk SSSR, 244:5 (1979), 1093–1096
\end{thebibliography}

\end{document}