% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
%\documentclass{acm_proc_article-sp-no-copyright}
% \usepackage{usenix,times}
\usepackage{times}
%\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
%\setlength{\textwidth}{6in}
%\setlength{\textheight}{9in}
%\setlength{\oddsidemargin}{0.25in}

\pagestyle{plain}

\bibliographystyle{unsrt}

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\begin{document}
\title{Optimization Theory (DS2) HW\#2\\
Certificates, Standard Equality Form and Simplex Iteration}
\maketitle

Problems and page numbers from the paperback edition of \emph{A Gentle
  Introduction to Optimization}, by B. Guenin \emph{et al.}

\begin{enumerate}
\item (Problem 1 in Sec. 2.1 of the text, p. 50.)
\begin{enumerate}
\item 
Prove that the following LP problem is infeasible:
\begin{align}
\operatorname{max}\{ 3x_1 + 4x_2 + 6x_3 \}
\end{align}
subject to
\begin{align}
 3x_1 + 5x_2 - 6x_3 & = 4 \\
  x_1 + 3x_2 - 4x_3 & = 2 \\
 -x_1 + x_2 - x_3 & = -1 \\
  x_1 , x_2 , x_3 & \geq 0.
\end{align}


\item Prove that the following LP problem is unbounded:
\begin{align}
\operatorname{max}\{  -x_3 + x_4\}
\end{align}
subject to
\begin{align}
x_1 + x_3 - x_4 = 1 \\
x_2 + 2x_3 - x_4 = 2 \\
x_1, x_2, x_3, x_4 \geq 0.
\end{align}

\item {\bf Optional:} Prove that the LP Problem
\begin{equation}
max\{\vec{c}^\intercal \vec{x}: A\vec{x} = \vec{b}, \vec{x} \geq \vec{0}\}
\end{equation}
is unbounded, where
\begin{equation}
A=
\left(\begin{array}{ccccc}
 4 & 2 & 1 & -6 & -1 \\
-1 & 1 & -4 & 1 & 3 \\
 3 & -6 & 5 & 3 & -5 
\end{array}\right),
\end{equation}

\begin{equation}
\vec{b} = 
\left(\begin{array}{c}
11 \\
-2 \\
-8
\end{array}\right),
\end{equation}

\begin{equation}
\vec{c} =
\left(\begin{array}{c}
 1 \\
 -2 \\
 1 \\
 1 \\
 1
\end{array}\right)
\end{equation}

Hint: Consider the vectors
\begin{equation}
 \vec{x} = (1, 3, 1, 0, 0)^\intercal \textrm{ and } \vec{d} = (1, 1, 1, 1)^\intercal
\end{equation}

\item {\bf Optional:} For each of the problems in parts (b) and (c),
  give a feasible solution having object value exactly 5000.

\end{enumerate}
\item (Problem 1 in Sec. 2.2 of the text, p. 54.)
\begin{enumerate}
\item Convert the following LPs into SEF:
\begin{equation}
\operatorname{min}\{(2, -1, 4, 2, 4)(x_1, x_2, x_3, x_4, x_5)^\intercal\}
\end{equation}
subject to

\begin{equation}
\left(\begin{array}{ccccc}
1 & 2 & 4 & 7 & 3 \\
2 & 8 & 9 & 0 & 0 \\
1 & 1 & 0 & 2 & 6 \\
-3 & 4 & 3 & 1 & -1 \\
\end{array} \right)  
\left(\begin{array}{c}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5
\end{array} \right) 
\begin{array}{c}
\leq \\
 = \\
 \geq \\
\geq 
\end{array}
\left(\begin{array}{c}
1 \\
2 \\
3 \\
4
\end{array} \right).
\end{equation}
\begin{equation}
x_1, x_2, x_4 \geq 0.
\end{equation}
(Careful, note that not all of the $x_i$ have a non-negativity constraint.)

\item {\bf Optional:} Let $A, B, D$ be matrices and $\vec{b}, \vec{c},
  \vec{d}, \vec{f}$ vectors (all of suitable dimensions). Convert the
  following LP with variables $\vec{x}$ and $\vec{y}$ (where
  $\vec{x}$, $\vec{y}$ are vectors) into SEF:

\begin{equation}
\operatorname{min}\{  \vec{c}^\intercal \vec{x} + \vec{d} ^\intercal \vec{y} \}
\end{equation}
subject to
\begin{align}
A\vec{x} & \geq  \vec{b} \\
B\vec{x} + D\vec{y} & = \vec{f} \\
\vec{x} & \geq \vec{0}.
\end{align}
\end{enumerate}


\item  (Problem 1 in Sec. 2.3 of the text, p. 56.)\\
In this exercise, you are asked to repeat the argument in Section 2.3 with different examples.
\begin{enumerate}
\item Consider the following LP:
\begin{equation}
\operatorname{max}\{(-1, 0, 0, 2)\vec{x}\}
\end{equation}
Subject to
\begin{align}
\left(\begin{array}{cccc}
-1 & 1 & 0 & 2 \\
1 & 0 & 1 & -3 \\
\end{array} \right) \vec{x} & =
\left(\begin{array}{c}
2 \\
3 \\
\end{array} \right) \\
\vec{x} & \geq \vec{0}.
\end{align}

Observe that $\vec{x} = (0, 2, 3, 0)^\intercal$ is a feasible
solution. Starting from $\vec{x}$, construct a feasible solution
$\vec{x'}$ with value larger than that of $\vec{x}$ by increasing as
much as possible the value of exactly one of $x_1$ or $x_4$ (keeping
the other variable unchanged).

\item Consider the following LP:
\begin{equation}
\operatorname{max}\{ (0, 0, 4, -6)\vec{x}\}
\end{equation}
subject to 
\begin{align}
\left(\begin{array}{cccc}
1 & 0 & -1 & 1 \\
0 & 1 & -3 & 2 \\
\end{array} \right) \vec{x} & =
\left(\begin{array}{c}
2\\
1
\end{array}\right) \\
\vec{x} & \geq \vec{0}.
\end{align}
Observe that $\vec{x} = (2, 1, 0, 0)^\intercal$ is a feasible
solution. Starting from $\vec{x}$, construct a feasible solution
$\vec{x'}$ with value larger than that of $\vec{x}$ by increasing as
much as possible the value of exactly one of $x_1$ or $x_4$ (keeping
the other variable unchanged).

\end{enumerate}
\end{enumerate}
\end{document}

