\part{Linear Programming}



\chapter{Linear programs}


A class of optimization problems that tackle a decent range of real life applications are linear programs. Indeed, linear programs form the basic theory for more complex optimation problems.

\begin{definition}
	A \emph{linear program} (LP) is an optimization problem equivalent to some $(X,f,\min)$, with matrix $\mathbf{A}$ and vectors $\mathbf{b},\mathbf{c}$ such that:
	\[X = \{ \mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} \geq \mathbf{b} \land \mathbf{x} \geq \mathbf{0}\}\]
	\[f(\mathbf{x})=\mathbf{c}^{\intercal}\mathbf{x}\]
	Since this matrix and pair of vectors can define a linear program, the 4-tuple $(\mathbf{A},\mathbf{b},\mathbf{c},g)$ may be used to refer to LPs.
\end{definition}

Indeed the previous exampe from the last chapter is a linear program with representation as such: 

\section{Graphical method}

\section{Canonical form}

The following definition of an LP has been given in its \emph{standard form}; all LPs have this representation.
LPs may also be converted to \emph{canonical form}, which is the form required for an algorithm that we will investivage later.
\begin{definition}
	An LP $(X,f,g)$ is in \emph{canonical form} iff
	\[X = \{ \mathbf{x} \in \mathbb{R}^n: \mathbf{A}\mathbf{x} = \mathbf{b} \land \mathbf{x} \geq \mathbf{0} \land \mathbf{b} \geq \mathbf{0} \}\]
\end{definition}

How does one convert inequalities to equalities? By increasing the amount of nonnegative variables involved, one can emulate inequalities within equalities.

\begin{proposition}
\[x,y \in [0,\infty) \implies [ x \leq y \iff \exists s \in [0,\infty) (x+s=y)  ]\]
\[x,y \in [0,\infty) \implies [ x \geq y \iff \exists e \in [0,\infty) (x-e=y)  ]\]
\[x \in \mathbb{R} \iff \exists x_1,x_2 \in [0,\infty) [ x = x_1 -x_2 ]\]
\end{proposition}

Slack variables are dummy variables used to represent remaining addable quantity to reach equality.
Surplus variables are dummy variables that represent excess quantity from equality.

\section{Application of convex analysis}

Now that we have the sufficient tool to convert any problem to canonical form, we turn to some results from convex analysis that affect the field of linear programming.

\begin{proposition}
For any LP $(X,f,g)$, $X$ is convex,
\[(X,f,g) \text{ is an LP } \implies X \text{ is convex}\]
\end{proposition}
\begin{proposition}
feasible sets have optimal solution at an extreme point
feasible sets have finite extreme points
\end{proposition}

These results mean that if any extreme point can be calculated, any LP can theoretically be solved by calculating the finite amount of extreme points, passing them through the OF, and taking the most optimal value of this set. Hence extreme points in an LP are called \emph{basic feasilbe solutions}, due to their potential of being a solution by the proposition.

\begin{definition}
\emph{basic feasible solution} (BFS) of an LP is an extreme point of its feasible region.
\end{definition}


Unfortunately, larger problems have astronomical amounts of BFSs; for $n$ variables and $m$ constraints, one has $\binom{n}{m} $ BFSs in the worst case(depending on factors such as linear dependence etc.). For a practical algorithm, one must reduce the amount of BFSs involved.

\chapter{Simplex method}

We shall develop a greedy algorithm that starts with some initial BFS and seeks an 'adjacent' BFS that is 'more optimal'.
Consider $m$ constraints and $n$ variables, where $n \geq m$. Then we have $n-m$ redundant variables that may be set to zero. The remaining $m$ variables are called the \emph{basis elements}, let them form the set $B$. It is most conventient to make the initial BFS that where the slack variables are the basis elements.
For a given basis $B$, let us define the following notations:
\begin{itemize}
	\item $\mathbf{B}$ is the matrix of columns of $\mathbf{A}$ corresponding to basis elements
	\item $\mathbf{N}$ is the matrix of columns of $\mathbf{A}$ corresponding to non-basis elements
	\item $\mathbf{x}_{B}$ is the vector of variables corresponding to basis elements (which we set as zeros)
	\item $\mathbf{x}_{N}=\mathbf{0}$ is the vector of variables corresponding to non-basis elements 
	\item $\mathbf{c}_{B}$ is the vector of cost coefficients corresponding to basis elements
	\item $\mathbf{c}_{N}=\mathbf{0}$ is the vector of cost coefficients corresponding to non-basis elements
\end{itemize}

Adjacent BFSs are those that differ by a single variable; our algorithm should jump to an adjacent BFS by determining the most optimal nonbasis variable to and the least optimal basis variable to boot from our BFS.

\section{Calculating arbitrary BFS}
\[\mathbf{A}\mathbf{x}=\mathbf{b}\]
Since $A$ is not necessarily square (so there may not exist an $\mathbf{A}^{-1}$), we consider breaking it up in the following manner.
\[\mathbf{B}\mathbf{x}_{B}+ \mathbf{N}\mathbf{x}_{N}=\mathbf{b}\]
Recall that we set $\mathbf{x}_{N}=\mathbf{0}$
\[\mathbf{B}\mathbf{x}_{B}=\mathbf{b}\]
\[\mathbf{x}_{B}=\mathbf{B}^{-1}\mathbf{b}\]

This is the solution of the current BFS:
\[\mathbf{x}_{B}=\mathbf{B}^{-1}\mathbf{b}\]


\section{Determining 'optimal' variable}


Consider rewriting basis elements with respect to non-basis elements
\[\mathbf{B}\mathbf{x}_{B}+ \mathbf{N}\mathbf{x}_{N}=\mathbf{b}\]
\[\mathbf{x}_{B} =\mathbf{B}^{-1}(\mathbf{b} - \mathbf{N}\mathbf{x}_{N})\]
\[\mathbf{x}_{B} =\mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}\]

Now to consider what the OF results to

\[z=\mathbf{c}^{\intercal}\mathbf{x}\]
\[z=\mathbf{c}_{B}^{\intercal}\mathbf{x}_{B}+\mathbf{c}_{N}^{\intercal}\mathbf{x}_{N}\]
\[z=\mathbf{c}_{B}^{\intercal}\mathbf{x}_{B}\]
\[z=\mathbf{c}_{B}^{\intercal}(\mathbf{B}^{-1}\mathbf{b} - \mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N})\]
\[z=\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{b} - \mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N}\]
\[z+\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N}\mathbf{x}_{N} =\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{b} \]

We define the added to $z$ as the \emph{reduced cost vector}; this gives a method to determine which nonbasis element it would be most desirable to 'switch on'.
\[\hat{\mathbf{c}^{\intercal}}=\mathbf{c}_{B}^{\intercal}\mathbf{B}^{-1}\mathbf{N}\]


\section{Determining 'impeding' variable (ratio test)}
\emph{ratio test}
\[ i = \argmin \{ \frac{\hat{\mathbf{b}}_i}{\hat{\mathbf{A}}_{ij}} : \hat{\mathbf{A}}_{ij}  \gt 0 \]

\section{Simplex method}
- simplex method
\begin{itemize}
	\item Set initial BFS where slack variables are the only nonzero variables
	\item Add most helpful variable to BFS (allow it to be nonzero in new BFS)
	\item Drop least helpful variable from BFS (force it to be zero in new BFS)
	\item Repeat until optimal solution acquired
\end{itemize}

All these steps come together for form our greedy algorithm for optimizing LPs; the \emph{simplex method}.

The simplex method below updates the basis set $B$ and the basis matrix $\mathbf{B}$ according to the Simplex algorithm for a minimization LP in standard form.
\begin{algorithmic}
	\While {\max_{i} \{ (\mathbf{c}^{\intercal}_{\mathbf{B} \mathbf{B}^{-1} \mathbf{N} - \mathbf{c}^{\intercal}_{\mathbf{N}})_{i} \} \gt 0}
	\State e \gets \argmax_{i} (\mathbf{c}^{\intercal}_{\mathbf{B} \mathbf{B}^{-1} \mathbf{N} - \mathbf{c}^{\intercal}_{\mathbf{N}})_{i} \Comment{Find index of entering variable}
	\State l \gets \argmin_{i} \{ \frac{(\mathbf{B}^{-1}\mathbf{b})_{i}}{(\mathbf{B}^{-1}\mathbf{A})_ie} : (\mathbf{B}^{-1}\mathbf{A})_ie \gt 0 \} \Comment{Find index of leaving variable (ratio test)}
	\State B \gets B \cup \{x_e\}
	\State B \gets B \setminus \{x_l\}
	\State \text{Update }\mathbf{B} \text{ as columns of } \mathbf{A} \text{ corresponding to elements of }B
\EndWhile
	\State \mathbf{x}_{\mathbf{B}} \gets \mathbf{B}^{-1}\mathbf{b} \Comment{Optimal parameter}
	\State z \gets \mathbf{c}^{\intercal}_{\mathbf{B}} \mathbf{x}_{\mathbf{B}} \Comment{Optimal solution}
\end{algorithmic}

This is relatively straightforward to program on a modern computer, however the linear algebra required can be quite demanding if all components are calculated directly.

A \emph{simplex method tableau} is often used for human computers so that instead of directly doing operations such as inverting $\mathbf{B}$ and matrix multiplication, one finds only the necessary row reduction steps required to:
\item Ensure columns of $\hat{\mathbf{A}}$ relating to basis elements  are colums of identity matrix
\item Ensure indexes of $\hat{\mathbf{C}^{\intercal}}$ relating to basis elements are equal to 0
\item Ensure simplex method tableau is in \emph{cannonical form}

- simplex method tableau
- canonical form simplex method tableau


\chapter{Simplex method revisions}

- two phase simplex method
- big M method
- revized simplex method



\chapter{Duality theory}

Every LP is associated with some other 'similar' LP called is 'dual problem'.

- normal form LP
- A dual LP of an LP $(X,f,\min)$
the LP from which the dual LP is formed is called the \emph{primal LP}.
- optimality gap
-The \emph{duality gap} of an LP is the difference between the optimal solutions of a prime LP and its dual LP.
- asymmetric dual problem


\begin{lemma}
The dual of the primal's dual is the primal.
- duality operator is an involution
\end{lemma}

\begin{theorem}\emph{Weak Duality Theorem (WDT)}
Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},g)$ be a primal problem and $D$ the dual of $P$. If $\mathbf{x}$ and $\mathbf{y}$ are feasible for $P$ and $D$ respectively, then the following inequality holds.
\[ \mathbf{c}^{\intercal}\mathbf{x} \geq \mathbf{b}^{\intercal}\mathbf{y}\]
\end{theorem}



\begin{corollary}
Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},g)$ be a primal problem and $D$ the dual of $P$. If $P$ is unbounded, then $D$ is infeasible.
\end{corollary}


\begin{theorem}\emph{Strong Duality Theorem for Linear Programs (SDT)}
Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},\min)$ be a primal problem and $D$ the dual of $P$. $\mathbf{x}$ and $\mathbf{y}$ are optimal for $P$ and $D$ respectively iff the following equality holds.
\[ \mathbf{c}^{\intercal}\mathbf{x} = \mathbf{b}^{\intercal}\mathbf{y}\]
\end{theorem}

A corollary of equalities derived by SDT is the \emph{complementary slackness theorem}.

\begin{theorem}\emph{Complementary Slackness Theorem (CST)}
Let $P=(\mathbf{b},\mathbf{A},\mathbf{c},\min)$ be a primal problem and $D$ the dual of $P$. If $\mathbf{x}$ and $\mathbf{y}$ are optimal for $P$ and $D$ respectively, then the following equality holds.
\[ (\mathbf{c}^{\intercal}-\mathbf{y}^{\intercal}\mathbf{A})\mathbf{x}=0 \land \mathbf{y}^{\intercal}(\mathbf{b}-\mathbf{A}\mathbf{x})=0\]

\[\mathbf{x} \text{ optimizes }P \land \mathbf{y} \text{ optimizes } D \iff (\mathbf{c}^{\intercal}-\mathbf{y}^{\intercal}\mathbf{A})\mathbf{x}=0 \land \mathbf{y}^{\intercal}(\mathbf{b}-\mathbf{A}\mathbf{x})=0 \]
\end{theorem}

CST is used to find 'active constraints' in dual simplex method (to be covered).

\section{Dual simplex method}



One can use the simplex method to solve a dual problem, use SDT to deduce the optimal solution of the primal problem, and then use CST to determine the optimal parameters for the primal problem. 

The simplex method tries to iteratively optimize a BFS while keeping in the feasible region, however since feasibility of a primal problem is equivalent to feasibility of a dual problem, could one iterate a simplex method that ensures dual feasibility? This is known as the \emph{dual simplex method}; it works almost identically to the simplex method, except that one finds the leaving variable first using $\hat{\mathbf{b}}$ and the entering variable second using the ratio test with $\hat{\mathbf{c}^{\intercal}}$.


\chapter{Sensitivity analysis on LPs}

Often one may need to make slight adjustments to an optimization problem to reflect new conditions (cost of resource rises, amount of resources available depletes etc.). Sensitivity analysis studies how an optimization problem may be modified while retaining its feasible region, optimal solution or both. Here we discuss sensitivity analysis in the context of LPs; of which common modifications are the following.
\begin{itemize}
	\item Small changes for entries of $\mathbf{c}$
	\item Small changes for entries of $\mathbf{b}$
	\item Small changes for entries of $\mathbf{A}$
	\item Appending a new constraint
	\item Appending a new variable
\end{itemize}


\section{Cost vector entries $\mathbf{c}$}

Small changes in $\mathbf{c}$ change the LP in different ways depending on whether the entry of $\mathbf{c}$ being changed is associated with a basis variable in the final tableau. Hence we will discuss the case of modifying nonbasis coefficients and basis coefficients separately.

\subsection{Nonbasis}
\[ \mathbf{c}_{\mathbf{N}}'^{\intercal}= \mathbf{c}_{\mathbf{N}}^{\intercal} + (\Delta\mathbf{c}_{\mathbf{N}})^{\intercal} \]

\[ (\Delta\mathbf{c}_{\mathbf{N}})^{\intercal} - \hat{\mathbf{c}_{\mathbf{N}}} \geq \mathbf{0} \implies \text{ doesn't change optimal solution}\]
\subsection{Basis}
\[ \mathbf{c}_{\mathbf{B}}'^{\intercal}= \mathbf{c}_{\mathbf{B}}^{\intercal} + (\Delta\mathbf{c}_{\mathbf{B}})^{\intercal} \]
\[ (\Delta\mathbf{c}_{\mathbf{B}})^{\intercal} \mathbf{B}^{-1}\mathbf{N} + \hat{\mathbf{c}_{\mathbf{N}}}^{\intercal} \leq \mathbf{0} \implies \text{ doesn't change optimal solution}\]


\section{Constraint vector entries $\mathbf{b}$}
			<p>\(\mathbf{b}' = \mathbf{b}+ \Delta\mathbf{b}  \)</p>
			<p>\( \mathbf{B}^{-1}(\mathbf{b}+\Delta\mathbf{b}) \geq \mathbf{0} \implies \text{ doesn't change feasible region}\)</p>

\section{Constraint matrix entries $\mathbf{A}$}
\subsection{Nonbasis}
			<p>\( \mathbf{A}'_{j} = \mathbf{A}_{j} +\Delta \mathbf{A}_j \)<p>
			<p>\(  \hat{\mathbf{c}}^{\intercal}_{j} + \mathbf{c}_{\mathbf{B}}^{\intercal} \mathbf{B}^{-1} ( \Delta\mathbf{A}_j ) \geq 0\)<p>
\subsection{Basis}
The case where the entry is in a basis column is quite complex.
\emph{Sherman-Morrison formula}



\section{Additional constraint}
			<p>check that optimal solution satisfies new constraint, if so optimal solution unchanged. if not, use row reductions to get in canonical form and add to tableau as a basis element. note that it may be infeasible; in thos case continue using dual simplex method</p>
\section{Additional variable}

			<p>if ctb binv Aj - cj leq 0 for min, it can safely be entered into nonbasis without changing optimal solution, otherwise entee column Binv Aj into final tabealu and ctb Binv Aj -cj into reduced cost and continue simplex method</p>
			<p>\(  \hat{\mathbf{c}_{\mathbf{B}}}^{\interal} \mathbf{B}^{-1} \mathbf{A}_{j} - \mathbf{c}^{\intercal}_{j} \leq 0  \implies \text{ nonbasis entry doesn't change optimal solution}\)<p>




