\documentclass[12pt]{article}

\newcommand{\br}{\mathbf{R}}
\newcommand{\dom}{\mathrm{dom}}
\newcommand{\st}{\mathrm{s.t.}}
\renewcommand{\arraystretch}{1.4}

\begin{document}

\begin{center}
  \textbf{Fall 1995 Qualifier Exam:}\\ 
  \textbf{MATHEMATICAL PROGRAMMING}\\[0.3in]
  \textbf{Instructions:} Answer 5 of the following 7 questions.
\end{center}

\begin{enumerate}
\item
  Solve the following linear program
  \begin{displaymath}
    \begin{array}{ll}
      \max & x_1 - x_2 + 7 \\[0.1in]
      \st & x_1 + 4x_2 = 5 \\
      & x_1 - 3x_2 + x_3 = 7 \\
      & x_1 + x_2 - x_3 \leq 8 \\
      & x_1 \leq 1, \quad x_3 \geq 0
    \end{array}
  \end{displaymath}
\item
  Show that any solvable linear program has a strictly complementary
  solution.
  (You may wish to consider the linear program
  \begin{displaymath}
    \begin{array}{ll}
      \max & \epsilon \\[0.1in]
      \st & Ax \geq b \\
      & c \geq A^T u \\
      & b^Tu \geq c^T x \\
      & u + Ax - b \geq \epsilon 1_m \\
      & x + c - A^Tu \geq \epsilon 1_n \\
      & x, u \geq 0
    \end{array}
  \end{displaymath}
  where $1_m$ and $1_n$ are appropriately dimensioned vectors of 1's.)
\newpage

\item Consider the nonlinear program
\smallskip
$${\min_x}\;\,f(x)\qquad \st \;\,g(x)\leq 0$$
\smallskip
where $f\colon R^n\rightarrow R,\;\;\;g\colon R^n\rightarrow R^m$,  are
differentiable functions on $R^n$. Suppose that a linearization
of the problem at some feasible point $\bar x$ has no {\em strict feasible 
descent direction},
that is the following linearized system has {\bf no} solution in $x$:
\smallskip
$$f(\bar x)+\nabla f(\bar x)(x - \bar x) < f(\bar x)$$
$$g_I(\bar x)+\nabla g_I(\bar x)(x - \bar x) < g_I(\bar x)=0,$$
\smallskip
where $I:=\{i \vert g_i(\bar x)=0\}$.\\
\smallskip
(a) What optimality conditions are satisfied at $\bar x$? Justify.\\
\smallskip
(b) What additional assumptions on $\nabla g_I(\bar x)$ can strengthen
these optimality conditions? Justify.\\
\emph{Hint} The Gordan Theorem may be useful in answering both (a) and (b).

\item Consider the nonlinear program ${\min_{x\in X}}\;f(x)$,
where $f\colon R^n\rightarrow R$ and $X$ is a subset of $R^n$.
Define the exterior penalty function:
\smallskip
$$P(x,\alpha):=f(x)+\alpha \beta(x),$$
\smallskip
where $\beta\colon R^n\rightarrow R$ such that $\beta(x)=0$ on $X$,
else $\beta(x)>0$. Let $\alpha_2 > \alpha_1 > 0$, and 
\smallskip
$$x^i \in \mbox{arg}{\min_{x \in R^n}}\;P(x,\alpha_i),\;\;i=1,2.$$\\
\smallskip
(a) Show that $f(x^i) \le {\inf_{x\in X}}\;f(x)$.\\
\smallskip
(b) $f(x^2) \ge f(x^1)$.\\
\smallskip
(c) Suppose that you are given an arbitrary $x^0 \in X$, and that you
have computed $x^1$ for some $\alpha_1 > 0$. How would you choose
$\alpha_2$ so that $\beta(x^2)<\delta$ for some given infeasibility
tolerance $\delta >0$?

\item
Suppose $f$ is a proper convex function on $\br^n$. Assume that for
some nonzero $y^*\in\br^n$ and $\alpha^*\in\br$, 
and for all $x\in\br^n$, either $f(x)=+\infty$
or $\langle y^*,x\rangle\le\alpha^*$. Let $x^*\in\dom f^*$ and consider 
the halfline from $x^*$ in the direction of $y^*$. Exhibit the least
value of $\alpha$ such that for each $t\ge0$, 
$$f^*(x^*+ty^*)\le f^*(x^*)+t\alpha.$$
You must prove that (i) the bound holds for your $\alpha$, and (ii) your
$\alpha$ is the best possible without more information on $f$. (You may 
find it useful to look at the support function of $\dom f$.)

\item 
Consider the nonlinear integer program:
\smallskip
$$ (NIP)\qquad  \min_x \quad 1-x_1 x_2 \qquad \st \quad Ax \leq b, \quad x 
\geq 0,
\quad x \ \mathrm{integer} $$
\smallskip
a) Assuming that the constraints imply $x_1 \leq 1 $ and $x_2 \leq 1 $,
formulate this problem as a {\it linear integer program} and explain why
your formulation is an equivalent problem.

Now suppose that $Ax \leq b$ is the single constraint $x_1 + x_2 \leq 1 $.

b) What is the optimal solution and optimal value of the corresponding 
nonlinear integer program?

c) Consider an {\em arbitrary } linear integer program (not simply
the one developed in part a) ) that is  equivalent to (NIP), assuming
only that
the constraints $Ax \leq b$ imply  $x_1 \leq 1 $ and $x_2 \leq 1 $. 
Show that the LP relaxation of this arbitrary equivalent linear integer 
program will have optimal value not greater than 1/2 when the constraints
$Ax \leq b$ are specified to be $x_1 + x_2 \leq 1 $. (Hint: use convexity
properties of LP).
\newpage
\item 
Consider a network flow problem with $n$ nodes:
$$ \min_x \quad cx \qquad \st \quad Ax = b, \quad x \geq 0 ,$$ where 
c is a vector all of whose components are 1 in absolute value.

Suppose the dual solution $\pi$ (not necessarily dual feasible)
satisfies the usual complementarity conditions
with respect to a primal feasible solution defined on a spanning tree T. 
\smallskip

a) If $\pi_n $=0, derive a bound for $\pi_1$ in terms of the problem data,
and state necessary and sufficient conditions under which this bound will
be attained.

b) If no assumptions are made on the value of any $\pi_i$, can a bound
still be derived for $\pi_1$ from the complementarity conditions 
for this problem? Explain your answer.

\end{enumerate}

\end{document}