\documentstyle[12pt]{article}

\pagestyle{empty}
\renewcommand{\arraystretch}{1.4}
\newcommand{\textspace}{\openup 3\jot\relax}
\newcommand{\define}{\colon =}
\newcommand{\msp}{\;\;}
\newcommand{\mtext}[1]{\mbox{  #1  }}
\newcommand{\lineitem}[1]{\item[#1]\mbox{}}
\newcommand{\collection}[2]{#1^1, #1^2, \ldots , #1^#2}
\newcommand{\components}[2]{#1_1, #1_2, \ldots , #1_#2}
\newcommand{\oneto}[1]{1, \ldots , #1}
\newcommand{\map}[2]{#1 \mapsto #2}
\newcommand{\function}[3]{#1 \colon #2 \to #3}
\newcommand{\plus}[1]{\left(#1 \right)_+}
\newcommand{\lcp}[2]{\insmat{LCP}(#1,#2)}

% roman text in mathmode commands

\newcommand{\insmat}[1]{\mathop{\rm {#1}}}  % for mathmode (with underlines)
\newcommand{\inmat}[1]{\mbox{\rm {#1}}}     % roman text in mathmode
\newcommand{\maximize}{\insmat{maximize}}
\newcommand{\minimize}{\insmat{minimize}}
\newcommand{\diag}{\insmat{diag}}
\newcommand{\argmin}{\insmat{arg\,min}}
\newcommand{\argvertex}{\insmat{arg\,vertex}}
\newcommand{\argmax}{\insmat{arg\,max}}
\newcommand{\eff}{\insmat{eff}}

% common definitions needed

\newcommand{\real}{\rm I\!R}
\newcommand{\ereal}{\overline{\real}\,}
\newcommand{\natnum}{\rm I\!N}
\newcommand{\ball}{\rm I\!B}
\newcommand{\rball}[2]{\ball_{#2}(#1)}
\newcommand{\con}{{\cal C}}
\newcommand{\KKT}{Karush--Kuhn--Tucker\ }
\newcommand{\ip}[2]{\left\langle #1,#2 \right\rangle}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\pnorm}[2]{\norm{#1}_#2}
\newcommand{\modulus}[1]{\left| #1 \right|}
\newcommand{\brackets}[1]{\left\{ #1 \right\}}
\newcommand{\braced}[1]{\left< \ba{l} #1 \ea \right>}
\newcommand{\set}[2]{\brackets{#1 \left|\; #2 \right.}}
\newcommand{\infconv}{\Box}
\newcommand{\pop}[1]{P_{#1}}
\newcommand{\proj}[2]{P(#1 \mid #2)}
\newcommand{\ppop}[2]{P_{#2,#1}}
\newcommand{\pproj}[3]{P_{#2,#1}(#3)}

% more common naming conventions

\newcommand{\cond}[1]{{\cal K}(#1)}
\newcommand{\grad}{\nabla}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\summ}[2]{\sum_{#1}^{#2}}
\newcommand{\union}{\bigcup}
\newcommand{\intsect}{\bigcap}
\newcommand{\implies}{\;\Longrightarrow\;}
\newcommand{\implied}{\;\Longleftarrow\;}
\newcommand{\downto}{\downarrow}
\newcommand{\epito}{\stackrel{e}{\to}}
% \iff is already defined as \implies but with \Longleftrightarrow

% convex analysis definitions

\newcommand{\dird}[3]{#1' (#2 ; #3)}
\newcommand{\cdd}[3]{#1^{\circ} (#2 ; #3)}
\newcommand{\subd}[3]{#1^{\uparrow} (#2 ; #3)}
\newcommand{\contd}[3]{#1^{\sharp} (#2 ; #3)}
\newcommand{\twoargs}[3]{
\insmat{#1}_{{\scriptstyle \rule{0cm}{.3cm}#2}
\atop{\scriptstyle \rule{0cm}{.3cm}#3}}}
\newcommand{\liminftwo}[2]{\twoargs{\liminf}{#1}{#2}}
\newcommand{\limsuptwo}[2]{\twoargs{\limsup}{#1}{#2}}
\newcommand{\threeargs}[4]{
\insmat{#1}_{{{\scriptstyle \rule{0cm}{.3cm}#2}
\atop{\scriptstyle \rule{0cm}{.3cm}#3}}
\atop{\scriptstyle \rule{0cm}{.3cm}#4}}}
\newcommand{\liminfthree}[3]{\threeargs{\liminf}{#1}{#2}{#3}}
\newcommand{\limsupthree}[3]{\threeargs{\limsup}{#1}{#2}{#3}}

\newcommand{\perpspace}[1]{\left(#1\right)^{\perp}}
\newcommand{\intr}[1]{\insmat{int} #1}
\newcommand{\ri}[1]{\insmat{ri} #1}
\newcommand{\barrier}[1]{\insmat{bar} #1}
\newcommand{\cl}[1]{\insmat{cl} #1}
\newcommand{\dom}[1]{\insmat{dom} #1}
\newcommand{\lin}[1]{\insmat{lin}(#1)}
\newcommand{\spn}[1]{\insmat{span}(#1)}
\newcommand{\co}[1]{\insmat{co}(#1)}
\newcommand{\im}[1]{\insmat{im}(#1)}
\newcommand{\clco}[1]{\overline{\insmat{co}}(#1)}
\newcommand{\bdry}[1]{\insmat{bdry}(#1)}
\newcommand{\cone}[1]{\insmat{cone} #1}
\newcommand{\epi}[1]{\insmat{epi} #1}
\newcommand{\rec}[1]{\insmat{rec} #1}
\newcommand{\conj}[1]{#1^*}
\newcommand{\indicator}[2]{\psi(#1 \mid #2)}
\newcommand{\indfn}[1]{\indicator{\cdot}{#1}}
\newcommand{\support}[2]{\conj{\psi}(#1 \mid #2)}
\newcommand{\suppfn}[1]{\support{\cdot}{#1}}
\newcommand{\dist}[2]{\insmat{dist}(#1 \mid #2)}
\newcommand{\distfn}[1]{\dist{\cdot}{#1}}
\newcommand{\ncone}[2]{N(#1 \mid #2)}
\newcommand{\tcone}[2]{T(#1 \mid #2)}
\newcommand{\contcone}[2]{K(#1 \mid #2)}
\newcommand{\pcone}[1]{{#1}^\circ}
\newcommand{\polar}[1]{{#1}^\circ}
\newcommand{\conjc}[1]{\insmat{conj}{#1}}

% shorter definitions for common usages

\newcommand{\ba}{\begin{array}}
\newcommand{\ea}{\end{array}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqa}{\begin{eqnarray*}}
\newcommand{\eeqa}{\end{eqnarray*}}
\newcommand{\ds}{\displaystyle}
\newcommand{\arrayc}[1]{\ba{c} #1 \ea}
\newcommand{\arrayl}[1]{\ba{l} #1 \ea}
\newcommand{\arrayr}[1]{\ba{r} #1 \ea}
\newcommand{\bref}[1]{(\ref{#1})}

\renewcommand{\choose}[2] {\left( \arrayc{#1\\#2} \right)}
\newcommand{\floor}[1] {\lfloor #1 \rfloor}
\newcommand{\ceil}[1] {\lceil #1 \rceil}
\renewcommand{\matrix}[1] {\left[ \arrayc{#1} \right]}
\renewcommand{\pmatrix}[2] {\matrix{\ba{#1} #2 \ea}}

% problem definitions and mathematical constructions

\newcommand{\simpleeqncond}[2]
    	{\ba{rl} \ds #1 & \mbox{   #2} \ea }
\newcommand{\eeqncond}[3]
    	{\begin{equation} \simpleeqncond{#1}{#2} \label{#3}
     	 \end{equation}}
\newcommand{\eqncond}[2]
    	{\[ \simpleeqncond{#1}{#2} \] }
\newcommand{\simpleproblem}[3]
	{\ba{lc} {\ds #3_{#2}} & {#1} \ea}
\newcommand{\epmin}[3]
   	{\begin{equation} \simpleproblem{#1}{#2}{\minimize} \label{#3}
    	 \end{equation}}
\newcommand{\pmin}[2]
   	{\[ \simpleproblem{#1}{#2}{\minimize} \] }
\newcommand{\epmax}[3]
   	{\begin{equation} \simpleproblem{#1}{#2}{\maximize} \label{#3}
     	 \end{equation}}
\newcommand{\pmax}[2]
   	{\[ \simpleproblem{#1}{#2}{\maximize} \] }
\newcommand{\problem}[4]
	{\ba{lc} {\ds #4_{#1}} & {#2} \\* 
		\inmat{subject to} & \arrayl{#3} 
	 \ea}
\newcommand{\eprobmin}[4]
   	{\begin{equation} \problem{#1}{#2}{#3}{\minimize} \label{#4}
    	 \end{equation}}
\newcommand{\probmin}[3]
   	{\[ \problem{#1}{#2}{#3}{\minimize} \] }
\newcommand{\eprobmax}[4]
   	{\begin{equation} \problem{#1}{#2}{#3}{\maximize} \label{#4}
     	 \end{equation}}
\newcommand{\probmax}[3]
   	{\[ \problem{#1}{#2}{#3}{\maximize} \] }
\newcommand{\compproblem}[2]
	{ \ba{lr} #2 \ge 0, & #1 \ge 0 \\* 
	   \multicolumn{2}{c}{\ip{#1}{#2} = 0} \ea }
\newcommand{\ecomp}[3]
   	{\begin{equation}
		\compproblem{#1}{#2} \label{#3}
    	 \end{equation}}
\newcommand{\comp}[2]
   	{\[ \compproblem{#1}{#2} \] }
\textspace

\begin{document}
{\bf \Large MATHEMATICAL PROGRAMMING}

{\bf Instructions for Depth Exam Students}: Answer 6 of the
following questions, at most 2 from the Linear Programming Section.

{\bf Instructions for Breadth Exam Students}: Answer 3 of the
following questions, at most 2 from the Linear Programming Section.

\bigskip
{\noindent \bf \Large Linear Programming Section}
\hspace{0.1in}(Answer at most 2 questions from this section)

\begin{enumerate}

\item Solve the following problem:
\probmax{}{2 y_1 - y_3}{\ba{ccccccccc}
5y_1 & - & 2y_2 & + & y_3 & - & y_4 & = & 36 \\
y_1 & & & + & y_3 & & & \ge & 4 \\
y_1 & + & 3y_2 & + & y_3 & & & \ge & 1 \\
y_1 \le 8, & & y_2 \ge 0, & & y_3 \le 0, & & y_4 \ge 0 \ea }
Does the problem have a unique optimal solution?  Justify.

\item The optimal solution of the LP problem 
\probmax{ }  {z = 3x_1-12x_2+2x_3} {\ba{c} 
       x_1-3x_2+x_3\leq2 \\
       x_1-x_2-x_3 \leq 3 \\
         x_i \geq 0, i= 1, 2, 3 \ea}
is $x_1^* = 2, x^*_2 = x^*_3 = 0$. 
\begin{enumerate}
\item Find the ranges over which you can vary the cost coefficients of
$x_1$ and $x_2$ individually without changing the solution.
\item Using the given optimal solution, find the optimal solution
of the original problem with the new constraint
\[ 2x_1 + 5x_2 + x_3 \leq 3. \]
\end{enumerate}

\item Consider the following LP's:
\beqa
(LP_1)\hspace{1.5in}
\min_{x} & & cx \\
\rm {s.t.} & & Ax=b,\;\, x\ge 0\\
\hspace{2.0in} & \hspace{0.0in} & \hspace{3.5in}
\eeqa

\beqa
(LP_2)\hspace{1.5in}
\min_{x,\;y} & &\;cx+ey  \\
\rm {s.t.} & & Ax+y=b\\
& &\,\;\;x,y\ge 0,\\
\hspace{2.0in} & \hspace{0.0in} & \hspace{3.5in}
\eeqa
where $x\in\real^n,y\in\real^m,$ and $e=(1,\ldots,1).$
\begin{enumerate}
\item 
Suppose that the simplex method is used on $LP_2$ and terminates with
satisfaction of the unboundedness criterion.  What conditions on the
final tableau (or dictionary) or analytic conditions
are sufficient to guarantee the unboundedness of $LP_1$?
\item
If a final tableau (or dictionary) establishes unboundedness of $LP_2$
but does not satisfy the conditions of part (a), describe an efficient
approach (starting with the final basis generated for $LP_2$ and solving
at most a single LP) for determining the feasibility of $LP_1$.
In the case that no additional LP solution is required to establish
the feasibility of $LP_1$,
what can be
said about the existence of an optimal solution of $LP_1$?
\end{enumerate}

\newpage
{\noindent \bf \Large Advanced Topics Section}

\item Consider the convex program 
\probmin{}{f(x)}{g(x) \le 0}
where $\function{f}{\real^n}{\real}$ and $\function{g}{\real^n}{\real^m}$
are differentiable, convex functions on $\real^n$.  Let the feasible 
region $X \define \set{x}{g(x) \le 0}$ be nonempty and let
\[ 
\nabla g_I(\bar{x}) z \le 0, \nabla f(\bar{x}) z < 0
\mbox{   have {\bf no} solution $z \in \real^n$}
\]
for some nonempty $I \subset \brackets{1,\ldots,m}$ and some 
$\bar{x} \in \real^n$ not necessarily in $X$.
Construct a linear program that provides a lower bound to
$\inf \set{f(x)}{g(x) \le 0}$.  Prove that the linear program is 
solvable and give an explicit expression for your lower bound 
in terms of $\bar{x}$ and a solution to your linear program.

\item 
\begin{enumerate}
\item Construct an augmented Lagrangian for the nonlinear program
\probmin{}{f(x)}{g(x) \le 0}
where $\function{f}{\real^n}{\real}$ and $\function{g}{\real^n}{\real^m}$
are differentiable functions on $\real^n$.
\item Relate an {\bf unconstrained} stationary point of the augmented
Lagrangian to the original nonlinear program.  Establish your claim.
\item Give one step of the augmented Lagrangian algorithm, or any other
algorithm that utilizes the augmented Lagrangian formulation.
\end{enumerate}

\newpage
\item Consider the quadratic program 
\probmin{}{\frac{1}{2} x^TQx + c^Tx}{Ax = b}
Prove that $x^*$ is a local solution if and only if $x^*$ is a global
solution.
[Hint:  Consider first and second order  necessary conditions]

\item
Let $f$ be a convex function and let $x$ be a point of $\ri\dom f$.
Assume that $f(x)>-\infty$, and write $L$ for the subspace parallel
to $\dom f$.
\begin{enumerate}
\item Show that $\partial f(x)\neq\emptyset$.
\item Let $D=\partial f(x)\cap L$. Show from first principles
that $D$ is nonempty, compact, and convex. (You may assume elementary
results about dimensionality, relative interiors, orthogonal decompositions,
etc.)
\item Show that $\partial f(x)=D+L^\perp$.
\end{enumerate}

\item Let $G$ be a directed graph with specified edge lengths $d_{ij}>0$ for
the $m$ edges $(i,j)$.  You may assume that $d_{ij}$ is defined for all
$i,j=1,\cdots,n$ with $i\not=j$.
\begin{enumerate}
\item
Formulate the problem of determining the shortest directed path from node
1 to node $n$ as a network flow problems of the form:
\beqa
\min & &\;cx\\
\rm {s.t.}& &Ax=b\\
& &\;\;\,x\ge 0,
\eeqa
where $A$ is a node-arc incidence matrix.  (Be sure to explain the
correspondence between an appropriate
optimal solution $x^*$ and a directed path.)
\item
What is the relationship between an appropriate set of optimal dual
variables for the network flow problem in part (a) and path lengths for
the original digraph?  (Be precise.)
\end{enumerate}

\item Consider the general fixed charge problem
\probmin{}{\hspace*{-2in}\ip{c}{y}+\ip{d}{x}}
{\ba{l}
       {y \in Y := \{y:Ay=b,\; y\geq 0\} } \\
       x_j = 0 \inmat{ if } y_j = 0, \; 
       x_j = 1 \inmat{ if } y_j > 0 \; \;\; \forall j = 1, \ldots, n \ea }
where A is a $m$x$n$ real matrix and rank($A$) = $m$. 
Show that if every vertex of $Y$ is nondegenerate and all fixed costs
are equal (i.e. $d_j = r$ for all $j = 1, \ldots, n$), then any optimal
vertex solution of the linear program
\probmin{}{\ip{c}{y}}{y\in Y}
solves the fixed charge problem, by providing an optimal value for $y$.

\end{enumerate}

\end{document}