\baselineskip=15pt
\lineskip=1.5pt
\lineskiplimit=1pt
\magnification=\magstep1
\hsize=6.1truein
\mathsurround=1pt
\vglue 0pt plus 1 fill
\tolerance=10000
\vskip -.5in
\centerline {\bf MATHEMATICAL PROGRAMMING}
\smallskip
\noindent
\centerline {\bf Depth Exam:  Answer any 6 of the following 8 questions}
\centerline {\bf Breadth Exam:  Answer any 3 of the following 8 questions}

\vskip 0.2in

\noindent
\item{1.}
A textile firm is capable of producing 3 products in amounts $x_1,\; x_2,\;
x_3$.  Its production plan for the next month must satisfy the
constraints:
$$\eqalign{x_1+2x_2+2x_3&\le 12\cr
2x_1+4x_2+x_3&\le f\cr
x_1\ge 0,\;x_2\ge 0,\;x_3&\ge 0\cr}$$
The first constraint is determined by equipment availability and is
fixed.  The second constraint is determined by the availability of
cotton, with $f$ being the amount of cotton available.  The net profits
of the products are 2, 3 and 3 per unit respectively, excluding the cost
of cotton.
\smallskip
\itemitem {(a)}
Find the optimal dual variable (shadow price) $\lambda_2$ of the cotton
input as a function of $f$.  Plot $\lambda_2(f)$ and the net profit $z(f)$,
excluding the cost of cotton.
\smallskip
\itemitem {(b)}
The firm may purchase cotton on the open market at a price of $1\over
6$.   However, it may acquire a limited amount $s$ at a price of $1\over
12$ from a major supplier that it purchases from frequently.  Determine
the net profit of the firm $\Pi(s)$ as a function of $s$.
\bigskip
\noindent
\item{2.}
Consider the following linear system:
$$\eqalign{Ax&=b\cr
x&\ge 0\cr}$$
where $A$ is an $m\times n$ real matrix with rank $(A) = m$ and $0\not=
b\in{\rm I\!R}^m$.  Let
$\Omega=\{x\in {\rm I\!R}^n:Ax=b,\;x\ge0\}\not=\emptyset$ and for each $x$ let
$X:=\rm{diag}\;(x_1,x_2,\ldots,x_n)$.  Show that the two following
statements are {\bf equivalent}:
\smallskip
\itemitem {(a)}
rank $(AX)=m\qquad\forall x\in\Omega$
\smallskip
\itemitem {(b)}
$b$ cannot be expressed as nonnegative linear combination of $m-1$ or
fewer columns of $A$.
\smallskip
\hangindent=51pt
\hangafter=1
Hint:
The matrix $AX$ is comprised of positively-scaled columns of $A$
and columns of zeros.
\bigskip
\item{3.}
Let $P(x)$ denote the pure network flow problem
$$\eqalign {{\min_{x}}\quad &cx\cr
\rm {s.t.}\quad&Ax=b\cr
&0\le x\le u,\cr}$$
where $A$ is a node-arc incidence matrix.  Suppose that $\bar x$ is a
BFS (basic feasible solution) of $P(x)$ and that $x_1$ and $x_2$
correspond to two pivot-eligible arcs (relative to $\bar x$).
\smallskip
\itemitem {(a)}
State conditions under which $x_1$ and $x_2$ can be ``simultaneously''
(i.e. in parallel) brought into the basis, producing the same new primal
BFS that would result if they were brought in sequentially (in either
order).
\smallskip
\itemitem {(b)}
State corresponding conditions for the \underbar {dual} variable
updates associated with $x_1$ and $x_2$.
\smallskip
\itemitem {(c)}
Give a \underbar {numerical} example in which the conditions of part (a)
are satisfied and the conditions of part (b) are violated.
\bigskip
\medskip
\item{4.}
Let $k(s)$ be a ``separation counter'' defined by
$$k(s)=\cases{0&if$\;\;\;$$s<\delta$\cr
\noalign{\vskip 5pt}
1&if$\;\;\;$$s\ge\delta$\cr}$$
where $\delta$ is a given \underbar {positive} constant.  Formulate as a \underbar {mixed integer} \hfill
\underbar {linear program} the following pattern separation problem:
$$\eqalign {{\max_{c,\alpha,s,t}}\quad &\sum_{i=1}^p\;k(s_i)+\sum_{i=1}^p\;k(t_i)\cr
\rm {s.t.}\quad&cx_i-\alpha\ge\;\;s_i\quad (i=1,\ldots,p)\cr
&cy_i-\alpha\le -t_i\quad (i=1,\ldots,p)\cr
&\|c\|_\infty\le 1\cr}$$
where $x_1,\ldots,x_p$ and $y_1,\ldots,y_p$ are given sets of points in
${\rm I\!R}^n$; and $c$ (a row vector), $\alpha$, $s=(s_1,\ldots,s_p)$, and
$t=(t_1,\ldots,t_p)$ are unknowns.  Be sure to define any constants
(which may depend on the $x_i$ and $y_i)$ used in the formulation.
(Note:  Without loss of generality assume:  $s_i\le \delta,\;t_i\le
\delta,i=1,\ldots,p.)$
\bigskip
\noindent
\break
\item{5.}
Consider the problem $\displaystyle{\min_{x\ge0}}\;f(x)$ where
$f:{\rm I\!R}^n\rightarrow {\rm I\!R}$ is differentiable and convex on ${\rm
I\!R}^n$.  Assume that
a solution $\bar x$ exists.  For $z\in {\rm I\!R}^n$ define
$\bigl((z)_+\bigr)_i=\max\;\{z_i,\;0\},i=1,\ldots,n$.
\smallskip
\itemitem {(a)}
Suppose that for some $\hat x\ge0,\;\nabla f(\hat x)>0$.  Find
an upper bound on $\|\bar x\|_1$ in terms of $\hat x$ and
$\nabla f(\hat x)$, where $\|\cdot\|_1$ denotes the 1-norm.
\smallskip
\itemitem {(b)}
Suppose, in addition, that $f$ has a Lipschitz-continuous gradient, from
which you can assume that for some number $L>0$:
$$L\bigl\|y-x\bigr\|^2\ge\bigl(\nabla f(y)-\nabla
f(x)\bigr)(y-x)\ge {1\over L}\,\bigl\|\nabla f(y)-\nabla
f(x)\bigr\|^2$$
where $\|\cdot\|$ denotes the 2-norm.  Obtain for any $x\ge 0$ in ${\rm
I\!R}^n$,
an upper bound on $\|\nabla f(x)-\nabla f(\bar
x)\|$ in terms of $L$, $\hat x$ and the quantities, $x\nabla
f(x),\;$$\bigl(-\nabla f(x)\bigr)_+$.  (The last 2 quantities measure
the violations by $x\ge 0$ of the Karush-Kuhn-Tucker conditions for
the problem).
\bigskip
\noindent
\item{6.}
Consider the proximal point algorithm defined by
$$x^{k+1}=\arg{\min_{x\in X}}\;\bigl(f(x)+{\gamma\over 2}\,\bigl\|x-x^k\bigr\|^2\bigr)$$
where $\|\cdot\|$ denotes the 2-norm, $\gamma > 0$, $f$ is
differentiable and convex on ${\rm I\!R}^n,\;$ $X$ is a convex subset
of ${\rm I\!R}^n$.

Define
$$\bar X:=\arg{\min_{x\in X}}\;f(x):=\;\hbox{\rm set of minimizers of}\;f\;{\rm
on}\;X$$
\item {}
Suppose that for some $k,\;x^k\in\bar X$.  Prove that
$x^k=P(x^{k-1}\big\vert \bar X)$ where $P(x\big\vert\bar X)=\displaystyle\arg
{\min_{y\in\bar X}}\;\|x-y\|$.
\medskip
\noindent
\item {}
Hint:  You may want to use the fact that:
$$z=P(x\big\vert\bar X)\Leftrightarrow\langle x-z,\;y-z\rangle\le
0\quad\forall y\in\bar X$$
\bigskip
\break
\noindent
\item{7.}
Let the function $f:{\rm I\!R}^n\rightarrow{\rm I\!R}$ have a Lipschitz continuous
gradient on ${\rm I\!R}^n$ with constant $L$.  You are given a point $x\in {\rm
I\!R}^n$
and a direction vector $p\in {\rm I\!R}^n$ such that $\nabla f(x)p<0$
and $\|p\|=1$, where $\|\cdot\|$ denotes the 2-norm.
\smallskip
\itemitem {(a)}
For what interval of $\lambda$ can you guarantee that $f(x+\lambda
p)<f(x)$?  Establish your claim.
\smallskip
\itemitem {(b)}
What specific value of $\lambda$ will give you the biggest guaranteed
decrease in $f$?  Establish your claim.
\smallskip
\itemitem {(c)}
Suppose $p=-\nabla f(x)\big\slash\|\nabla f(x)\|$.  What can you say about
each accumulation point $\bar x$ of the sequence $\{x^i\}$ where
$x^{i+1}=x^i+\lambda^ip^i$, and $\lambda^i$ is chosen according to part
(b)?  Establish your claim assuming that $\nabla f(x^i)\not= 0$ for all
$i$.
\medskip
\item\item {}
Hint:  Assume $f(x+\lambda p)-f(x)-\lambda\nabla f(x)p\le
{{L\lambda^2}\over 2}\;\|p\|^2$
\bigskip
\medskip
\item {8.}
Suppose $f$ is a closed proper convex function on ${\rm I\!R}^n$, and $\rho$
is a fixed positive number.  Let
$$f_\rho(x)=\inf _yg(x,y),$$

where
$$g(x,y)=f(y)+(2\rho)^{-1}\|y-x\|^2.$$

\noindent
\itemitem {(a)}
Show that $f_\rho$ is a convex function.
\smallskip
\itemitem {(b)}
Show that the infimum in $y$ of $g(x,y)$ is attained at a unique point
of ${\rm I\! R}^n$.

\bigskip
\hangindent=75pt
\hangafter=1
Suggestion:
As part of your answer for (b), consider establishing the following
intermediate facts:  (i)  $g(x,\cdot)$ is lower semicontinuous; (ii)
$g(x,\cdot)$ has bounded level sets; (iii)  $g(x,\cdot)$ is strictly
convex.
\vfill
\eject
\bye