\documentstyle[12pt]{article}

\pagestyle{empty}
\newcommand{\textspace}{\openup 3\jot\relax}
\textspace
\renewcommand{\arraystretch}{1.4}
\newcommand{\define}{\colon =}
\newcommand{\msp}{\;\;}
\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{\function}[3]{#1 \colon #2 \mapsto #3}
\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{argmin}}
\newcommand{\eff}{\insmat{eff}}

% common definitions needed

\newcommand{\real}{\rm I\!R}
\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{\set}[2]{\left\{ #1 \left|\; #2 \right. \right\}}
\newcommand{\seq}[1]{\left\{ #1 \right\}}
\newcommand{\pop}[1]{P_{#1}}
\newcommand{\proj}[2]{P(#2 \mid #1)}
\newcommand{\ppop}[2]{P_{#2,#1}}
\newcommand{\pproj}[3]{P_{#2,#1}(#3)}

% more common naming conventions

\newcommand{\grad}{\nabla}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\summ}[2]{\sum_{#1}^{#2}}
\newcommand{\union}{\bigcup}
\newcommand{\intsect}{\bigcap}
\newcommand{\implies}{\;\Longrightarrow\;}
% \iff is already defined as \implies but with \Longleftrightarrow

% convex analysis definitions

\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{\co}[1]{\insmat{co}(#1)}
\newcommand{\clco}[1]{\overline{\insmat{co}}(#1)}
\newcommand{\bdry}[1]{\insmat{bdry} #1}
\newcommand{\cone}[1]{\insmat{cone} #1}
\newcommand{\rec}[1]{\insmat{rec} #1}
\newcommand{\conj}[1]{#1^*}
\newcommand{\indicator}[2]{\psi(#2 \mid #1)}
\newcommand{\indfn}[1]{\indicator{#1}{\cdot}}
\newcommand{\support}[2]{\conj{\psi}(#2 \mid #1)}
\newcommand{\suppfn}[1]{\support{#1}{\cdot}}
\newcommand{\distance}[2]{\insmat{dist}(#2 \mid #1)}
\newcommand{\distfn}[1]{\distance{#1}{\cdot}}
\newcommand{\ncone}[2]{N(#2 \mid #1)}
\newcommand{\tcone}[2]{T(#2 \mid #1)}
\newcommand{\pcone}[1]{{#1}^\circ}
\newcommand{\polar}[1]{{#1}^\circ}

% shorter definitions for common usages

\newcommand{\ba}{\begin{array}}
\newcommand{\ea}{\end{array}}
\newcommand{\ds}{\displaystyle}
\newcommand{\arrayc}[1]{\ba{c} #1 \ea}
\newcommand{\arrayr}[1]{\ba{r} #1 \ea}

\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} & \arrayr{#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} \] }

% theorem definitions (labelled consecutively)

\newtheorem{definition}{Definition}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{corollary}[definition]{Corollary}

% environment definitions

\newenvironment{proof}
	{\begin{trivlist}\item[\hspace{\labelsep}
	{\bf Proof }]}{\rule{0.3em}{1.2ex} \end{trivlist}}
\newcommand{\memolabel}[1]{\hspace{\labelsep}\bf #1:\hfill}
\newenvironment{memo}[1]{\begin{list}{}{\renewcommand{\leftmargin}{#1} 
	\renewcommand{\labelwidth}{#1}
	\renewcommand{\makelabel}{\memolabel}}}{\end{list}}

\newcommand{\bref}[1]{(\ref{#1})}
\renewcommand{\cases}[1]{\left\{ \ba{rr} #1 \ea \right.}
\newcommand{\tableau}[4]{
\[ \ba{|#1|c|} \hline #2 \\ \hline #3 \\ \hline #4 \\ \hline \ea \] }

\begin{document}
{\bf MATHEMATICAL PROGRAMMING}

{\bf Instructions for Depth Exam Students}: Answer any 6 of the
following questions.

{\bf Instructions for Breadth Exam Students}: Answer any 3 of the
following questions.

\begin{enumerate}

\item Use the simplex method to solve the following problem:
\probmin{}{7 \modulus{x} - y + 3z}{\ba{ccccccc}
& & y & - & 2z & \le & 4 \\
-x & - & y & + & 3z & \le & -2 \\
3x & - & y & + & 3z & \ge & 0 \\
& y & \ge & 3, & z & \le & 1 \ea }

\item Let $X$ be a convex set in the $n$--dimensional
real space $\real^n$ and let $f$ be a differentiable 
function on $\real^n$.
\begin{enumerate}
\item What can you say about the quantity 
\[ \grad f(\bar{x})(x - \bar{x}) \]
on $X$ if $\bar{x}$ is a local solution of
\pmin{f(x)}{x \in X}
\item Let $\bar{x} \in \bar{X}$, where $\bar{X}$ is the solution set 
of $\displaystyle \min_{x \in X} f(x)$, that is
\[ \bar{X} \define \arg\min_{x \in X} f(x) \]
If $f$ is convex on $\real^n$, what is the relation between
$\bar{X}$ and the set
\[ \bar{Y} \define \arg\min_{x \in X} \grad f(\bar{x})(x - \bar{x}) \]
Establish your claim.
\end{enumerate}

\item Consider the problem 
\probmin{}{f(x)}{g(x) \le 0}
where $f\colon \real^n \mapsto \real$ and $g\colon \real^n \mapsto \real^m$
are differentiable and convex functions on $\real^n$.  Suppose
that
\[ x(\alpha) = \arg\min_x \{ 
    f(x) - \alpha \sum_{j=1}^n \log (-g_j(x)) \mid g(x) < 0 \} \]
for $\alpha > 0$.  What should $\alpha$ satisfy in order that
\[ f(x(\alpha)) - \inf_x \{ f(x) \mid g(x) \le 0 \} \le 10^{-6} \]
Prove your claim.

\item Consider the following problem.
\begin{quotation}
A company must assign $n$ plants to $n$ distinct locations.  Each
location will be assigned exactly 1 plant.  The number
of units to be shipped from $p$ to $q$ is $d_{pq} \ge 0$,
$(p,q = \oneto{n})$.  The unit shipping cost from location $i$ 
to location $j$ is $c_{ij} > 0$, $(i,j = \oneto{n})$.  The
plants are to be assigned to locations so as to minimize
total shipping cost.
\end{quotation}
\begin{enumerate}
\item Formulate the problem as a (not necessarily linear)
integer program using only the $n^2$ variables $x_{pi}$,
where $x_{pi} = 1$ implies that plant $p$ is assigned to
location $i$.
\item Formulate the problem as a {\bf linear} integer program
using the variables of part (a) plus any additional variables that 
you require.
\end{enumerate}

\item \mbox{} \\
\begin{picture}(400,180)(0,0)
\put(80,50){\circle{20}}
\put(78,48){3}
\put(80,150){\circle{20}}
\put(78,148){2}
\put(89,47){\vector(1,0){202}}
\put(90,50){\vector(2,1){200}}
\put(90,150){\vector(2,-1){200}}
\put(89,153){\vector(1,0){202}}
\put(300,50){\circle{20}}
\put(295,48){-4}
\put(300,150){\circle{20}}
\put(295,148){-1}
\put(190,163){-10}
\put(190,34){2}
\put(170,72){1}
\put(170,120){1}
\end{picture}
\begin{enumerate}
\item Formulate the ``big M'' problem corresponding to the 
min cost network problem above, where divergences are shown at the 
nodes and unit costs are shown on the arcs.  Describe how you
compute the {\bf numerical} value of ``big M'' for this problem.
Do one pivot of the network simplex method on the big M problem,
indicating the primal and dual values before and after the pivot
(start with the ``all artificial'' solution).
\item Given the {\bf orientation} of the arcs in the network
above, what conclusion may be drawn regarding the {\bf existence}
of an optimal solution of the corresponding big M problem?
Explain your answer.
\item Given the result of part (b), what additional property 
(observable from the original data of this problem) relates the
big M problem to the original problem?
Explain your answer.
\end{enumerate}

\item Let A be an integral matrix of full row rank. 
Show that all basis submatrices of A are
unimodular iff for all integer vectors b

\[ \{ x\in \real^n : Ax = b, \; x \geq 0 \} =  conv\{ x\in \real^n : Ax = b, \; x \geq 0 ,
x \inmat{  integer} \} \]

Hint: {\it To show that a matrix $B$ is unimodular it suffices to show that $B^{-1}t$ is
integer for all vectors t.}

\item Consider the linear program:
\eprobmin { } {\ip{q}{z}} { {Mz + q \geq 0} \\ {z \geq 0}} {lab1} 
where M is a skew-symmetric  that is 
\[ M = - M^T. \]
Suppose $z^*$ is a solution of (\ref{lab1}). 
Give a solution of the dual of (\ref{lab1})
in terms of $z^*$

\item
Let $f$ be a closed proper convex function from $\real^n$ to $\real$.
Suppose that for each nonzero $y$ in $\real^n$ there exists some 
positive $\eta$  such that $f(\eta y)>f(0)$. 
\begin{enumerate}
\item Prove that the set 
$$L(1)=\{\,x\in\real^n\mid f(x)\le1\,\}$$ is compact.
\item Can you draw any conclusion about the compactness of
$$L(n)=\{\,x\in\real^n\mid f(x)\le n\,\},$$ where $n$ is an arbitrarily
large natural number?  Explain.
\end{enumerate}

\end{enumerate}

\end{document}