\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