\documentstyle[art11]{article}
\newcommand{\real}{\rm I\!R}
\newcommand{\minimize}{\mathop{\rm minimize}}
\newcommand{\lminimize}{\mathop{\rm  min}}
\newcommand{\maximize}{\mathop{\rm maximize}}
\newcommand{\lmaximize}{\mathop{\rm max}}
\newcommand{\probl}[3]
   {\begin{displaymath}
       \begin{array}{rl}
              f(t) :=   \begin{displaystyle}  \lminimize_{#2} \end{displaystyle}  & #1  \\*
                        \mbox{s.t.} & \left \{  #3 \right .
       \end{array} 
    \end{displaymath}}
\begin{document}

\noindent{\Large \bf  MATHEMATICAL PROGRAMMING}

\bigskip
\noindent {\large \bf Instructions for Depth Exam Students:}  Answer any 6 of the
following 9 questions.
\smallskip

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

\bigskip
\begin{enumerate}
\item  Consider the following tableau
\[ 
\begin{array} {r|rrrr|c|}
\multicolumn{1}{c} { }    &  -y_1 & -y_3 & -x_2 & \multicolumn{1}{c} {-x_1} &
\multicolumn{1}{c} {1} \\ \cline{2-6}
x_3  = &  -2   & 1    &  -4  &  4   &  2  \\
y_2  = &  -1   &  2   &  -1  & -2   &  1  \\
x_4  = &  -1   & 2    &   1  &  0   &  2  \\
y_4  = &  -1   & -1   &   1  &  1   &  4 \\ \cline{2-6}
z    = &   1   & 1    &   0  &  2   &  5 \\ \cline{2-6}
\end{array} \]

Is this tableau optimal?  Why?  If there is another optimal solution
obtain it.  If there is not, give a reason why.
\bigskip
\item  Consider the dual LP's:
\bigskip

\[
\begin{array}{ccc} 
\lminimize \; c^Tx &  &  \lmaximize \; b^Tu \\
Ax \geq b      &  &  A^Tu \leq c    \\
x \geq 0       &  &   u \geq 0      \end{array} \]


Show that if these problems have solutions, then there exists a primal-dual
solution ($\bar x, \bar u$) for which strict complementary holds.

[Hint:  You may need the following lemma (Tucker):
For any skew-symmetric
matrix $M(M= - M^T)$ there exists $z$ such that $z \geq 0$,$Mz \geq 0$,$z^TMz = 0$,$z + Mz > 0$]
\bigskip

\item  Consider the following capacity expansion problem: substations
A and B are currently connected to central switching points C and D by
15 and 20 trunk lines respectively (see figure)
{\Large

\begin{center}
\fbox{A} \raisebox{.6ex}{ $\stackrel {15} {\line(1,0){40}}$} \fbox{C} 
\end{center}

\begin{center}
\fbox{B} \raisebox{.6ex}{ $\stackrel {20} {\line(1,0){40}}$} \fbox{D}
\end{center}

}

Due to increased traffic, A now requires a total of
25 lines to central
switching points C or D, and B requires 30 such lines.  The cost of
installing $\underline {\hbox {new}}$ lines is given by the cost matrix:

\[
\begin{array}{r|c|c|}
\multicolumn{1}{c} {} & \multicolumn{1}{c}{C} & \multicolumn{1}{c} {D} \\ \cline{2-3}
A & 1 & 4 \\ \cline{2-3}
B & 3 & 2 \\ \cline{2-3}
\end{array}
\]
(thus, each new line from A to C costs 1 unit, etc.)  (Note that lines
may go from A to D and B to C.)

 There is no cost for keeping constant or reducing the current
number of lines between points in the network.  Switching points C and
D have capacities of 20 and 40 (total)  lines respectively.
 
\begin{enumerate}
\item  Formulate this problem of meeting the new requirements
at minimum cost as a linear network flow problem (with equality constraints for
the divergences at the nodes.)  Sketch the corresponding network,
indicating arc capacities and costs, and supplies and demands.

\item  State an optimal solution and optimal value for the
given problem.

\item  State why the solution given in part (b) is optimal.
\end{enumerate}

\item  Let $f(t)$ be defined as the following optimal value function:


\probl
 {x_1 + 2y_1 + y_2 + x_2} {x,y}
{\begin{array} {c}
     y_1 + y_2 =  t   \\
 0   \leq   y_2       \leq   T_2 x_2  \leq  (T_2/T_1)y_1    \leq  T_2 x_1 \\
           x_1 = 0 \;\; {\hbox {\rm or}}\;\;   1     \;\;   ;\;\;    x_2 = 0 \;\; {\hbox {\rm or}}\;\;   1      \end{array}}

\bigskip
(Assume that $T_1$ and $T_2$ are positive constants.)

\begin{enumerate}
\item  Sketch $f(t)$ and give an explicit algebraic description
of $f(t)$ (also indicating where it is $+\;\infty$).

\item  Let $g(t)$ be the optimal value function of the linear progam
obtained by replacing the constraints $x_i = 0$ or $1$ by $0\leq x_i \leq 1$
$(i = 1,2)$.  Prove that $g(t) < f(t)$ for $t\;\epsilon\;(0,T_1 + T_2)\,,$
provided that $T_2 \geq 1\;$.
\end{enumerate}
\bigskip
\item  Suppose that $N = (V,E,u)$ is an undirected network,
where $V$ is the mode set, $E$ is the edge set, $u$ is a capacity
function, $u : E \rightarrow {\rm I\!R}_+\;,$ i.e., any flow $x$ in an
edge $e$ can be one of the two directions of $e\;,$ subject to
$$0 \leq x(e) \leq u(e)\;.$$
The value of a maximal flow from node $i$ to node $j$ is denoted
by $V_{ij}\;.$  Thus, $V_{ij} = V_{ji}\;.$  Use the max-flow
min-cut theorem to prove that for any three nodes
$i,j,k\;\epsilon\;V\;,$ the two smaller of the three values
$\{V_{ij}\;,\;V_{jk}\;,V_{ki}\}$ are equal, i.e., if
$V_{ij} \geq V_{jk}\;,\;V_{ij} \geq V_{ki}\;$, then $V_{jk} = V_{ki}\;.$
\bigskip
\item  Function $f : {\rm I\!R}^n \rightarrow {\rm I\!R}$ is defined by
$f(x) : = \|x\|^2 + \|x\|\;,$ where $\|\cdot\|$ is the Euclidean norm.
Compute its conjugate $f^*$ and the subdifferentials of $f$ and $f^*\;.$
 

\bigskip
\item
Let $K$ be a polyhedral convex cone in ${\bf R}^n$. Show
that $K$ contains a semipositive vector ({\it i.e.,} a
vector that is non-negative but not zero) if and only if
its polar $K^\circ$ contains {\it no\/} positive 
vector ({i.e.,} no vector each of whose components is
positive).
\bigskip
\item
Suppose that in solving a constrained optimization problem 
you need to work in a subspace $L$ of ${\bf R}^n$. The
subspace consists of all z satisfying the linear constraints
$Az=0$, where $A$ is a given $k\times n$ matrix of rank $k$.
On this subspace you have to minimize a smooth nonlinear
function $f$. It is known that the second derivative of 
$f$, evaluated at any point of $L$, is a matrix that is
singular, but it is also known that the restriction of $f$
to $L$ is uniformly convex. You wish to use Newton's method to
minimize $f$.

Explain an efficient numerical procedure for implementing
the Newton calculations on $L$. You do not need to discuss
step size calculation, but you must explain how you will
carry out the direction-finding calculation, how you will
deal with the singularity, and how you will represent the
elements of $L$ that you need to use in the calculations.
In all of these explanations you must say how you will
calculate the quantities you need.
\bigskip
\item
Consider the optimization problem $${\rm min}\,\{\,x_1+
x_2\mid \phi(p)x_1^2\le x_2\,\},$$ where $\phi$ is a smooth
function from ${\bf R}^k$ to ${\bf R}$ with $\phi(0)=
{1\over2}$. 
\begin{enumerate}
\item   Show that when $p=0$ the point $x(0)=
(-1,1/2)$ is the unique minimizer (of any kind,
local or global) for this problem.
\item  Prove that there is a smooth function $x$ from
a neighborhood $U$ of the origin in ${\bf R}^k$ to ${\bf R}^2$,
such that for each $p\in U$ the point $x(p)$ is the unique 
minimizer for the problem with that value of $p$.
\item  Compute the derivative of $x$ at $p=0$.
\end{enumerate}
\end{enumerate}

\end{document}

 
                                                     Renato     
