\baselineskip=15pt
\lineskip=1.5pt
\lineskiplimit=1pt
\nopagenumbers
\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.4in
\item{1.}
Solve by the simplex method the following Linear Programming Problem:
$$\matrix{ \hbox{\rm max}  & {\hskip -2cm }-4x_2 -2x_3-7x_4\cr \cr
 \hbox{\rm s.t.}          &
{\matrix{ 2x_1 & + & x_2 & + & x_3 & + & 3x_4 &= &3\cr
         x_1 &-  & x_2 &   &     & + &x_4  &\le & 1\cr
          2x_1& + & 2x_2&   &     & + &4x_4&\le & 3\cr}}\cr
               & x_i\ge 0\quad i=1,\ldots,4\cr}$$
\bigskip
\noindent
\item {}
\hangindent=49pt
\hangafter=1
Hint:  Start with $x_3$ as a basic variable even though it also occurs in the
objective function.
\bigskip
\bigskip
\item{3.}
Let $f: R^n\rightarrow R$ be a differentiable convex function on $R^n$
and let $x^1,\ldots,x^k$ be $k$ points in $R^n$ such that for some $\bar
u\in R^k:$
$$\sum_{i=1}^k\,\bar u_i\nabla f(x^i)=0,\;\,\sum_{i=1}^k\,\bar
u_i=1,\;\,\bar u\ge 0$$
Give a lower bound to $\displaystyle\inf_{x\in R^n}\,f(x)$ in terms of
$x^1,\ldots,x^k$ and
$\bar u$.
\vfill
\eject
\bye
\bigskip
\bigskip
\noindent
\item{6.}
Suppose that $G$ is a directed graph consisting of $n$ nodes and $K$
(connected) components.  Prove that the rank of the corresponding
node-arc incidence matrix is $n-K$.
\bigskip
\bigskip
\medskip
\item{7.}
Consider the integer program
$$\eqalign {{\min_{x}}\quad &cx\cr
\rm {s.t.}\quad&Ax=b\cr
&x_i=0\;{\rm or}\; 1\quad\;(i=1,\ldots,n)\cr}\leqno(IP)$$
Assuming (IP) is feasible, prove that for sufficiently large $M,$ every
optimal solution of (IP) is also an optimal solution of
$$\eqalign {{\min_{x}}\quad &cx +M\sum\,x_i(1-x_i)\cr
\rm {s.t.}\quad&Ax=b\cr
&0\le x_i\le1\quad\;(i=1,\ldots,n).\cr}\leqno(NLP)$$
\bigskip
\bigskip
\item{8.}
Consider the function $f:[0,2]\rightarrow{\rm I\!R}$ defined by
$$f(x):=\cases{0&if\quad $x=0$\cr a&if\quad $x\in (0,1]$\cr
bx+c&if\quad $x\in(1,2]$\cr}$$
where $a,b$ and $c$ are real numbers.  Determine conditions on $a,b$
and $c$ such that
\smallskip
\itemitem{(a)}
there exists a Linear Program Minimization Model for $f(x)$ on $[0,2]$;
\smallskip
\itemitem{(b)}
there exists a Mixed Integer Minimization Model for $f(x)$ on $[0,2]$.
\bigskip
\item{}
Write a Mixed Integer Minimization Model for $f(x)$ on $[0,2]$ (under
conditions found in (b)).
\def\br{{\bf R}}
\def\dom{\hbox{\rm dom}\,}
\def\inf{\hbox{\rm inf}\,} 
\def \endstate {\vrule height8pt width3pt depth0pt\medbreak}
\def\ri{\hbox{\rm ri}\,}
\def\subpar{\hfill\break\indent\indent}
\centerline {\bf Convex programming question Spring 90}
\bigskip
\bigskip
Suppose $f$ is a closed proper convex function on $\br^n$, and
let $K$ be a nonempty closed convex cone, also in $\br^n$. Consider the
primal problem of minimizing $f$ on $K$. Using the duality
structure given by
$$F(x,p)=\cases{f(x)&if $x\in K+p$,\cr +\infty&otherwise,\cr}$$
obtain the Lagrangian and the dual objective function for
this problem in the simplest practical form. Also prove that
the dual problem has a maximum (attained) if
$$\ri K\cap\ri\dom f\neq\emptyset.$$

\vfill \eject
\end

\vfill
\eject
\bye

\documentstyle[12pt]{article}

\pagestyle{empty}
\newcommand{\textspace}{\openup 3\jot\relax}
\textspace
\renewcommand{\arraystretch}{1.4}
\input{macros}

\begin{document}

\begin{enumerate}

\item
Consider the following problem
\probmin{}{c^Tx}{\sum_{j=1}^n a_jx_j = b \\ l_j \le x_j \le u_j, j=1,\ldots,n}
where $l$ and $u$ are finite, and $b$, $a_j$ and $c_j$ are all positive numbers.
\begin{enumerate}
\item If $\tilde{x}$ is an optimal solution for this problem, prove
that there exists $\tilde{\pi}$ such that $\tilde{\pi} a_j < c_j$ implies
$\tilde{x}_j = l_j$, 
$\tilde{\pi} a_j > c_j$ implies $\tilde{x}_j = u_j$, and
$l_j < \tilde{x}_j < u_j$ implies $\tilde{\pi} a_j = c_j$.
\item Suppose the variables are listed in the problem so that
\[ (c_1/a_1) < (c_2/a_2) < \ldots < (c_n/a_n) \]
Prove that if a feasible solution exits, then there is an optimal
solution $\bar{x}$ satisfying the property that for some $s$:
$\bar{x}_j = u_j$, $j=1$ to $s-1$,
$l_s \le \bar{x}_s \le u_s$, and
$\bar{x}_j = l_j$, $j=s+1$ to $n$.
\end{enumerate}

\pagebreak

\item Let $\function{g}{\real^n}{\real}$ be the quadratic function
$g(x) = \frac{1}{2} x^TAx - b^Tx + c$, where $A \in \real^{n\times n}$ is
symmetric and positive definite.  For arbitrary $x^0 \in \real^n$
and linearly independent vectors $p^0, \ldots, p^{k-1}$, let
\[ V_k = \set{x \in \real^n}{ x = x^0 + \sum_{i=0}^{k-1} \alpha_i p^i, 
\forall \alpha_i \in \real} \]
Show that the unique minimizer of the restriction of $g$ to $V_k$ is
given by
\[ x^0 + P_k \inv{(P_k^T A P_k)} P_k^T (b - Ax^0) \]
where $P_k$ is the matrix with columns $p^0, \ldots, p^{k-1}$.

Suppose the conjugate gradient method is applied to minimize $g$, 
that is 
\[ x^{k+1} = x^k - \alpha_k p^k, k = \oneto{n} \]
where 
\[ \alpha_k = \frac{(Ax^k - b)^T p^k}{(Ap^k)^T p^k} \]
and $p^0, \ldots, p^{n-1}$ are A--conjugate, that is 
$(Ap^i)^T p^j = 1$ if $i=j$ and $0$ otherwise.
Show that
\[ g(x^k) = \min \set{g(x)}{x \in V_k}, k = \oneto{n} \]
\end{enumerate}

\end{document}