\documentclass[11pt,twoside]{article}
\newcommand{\HW}{}
\newcommand{\HWnumb}{3}
\newcommand{\HWdate}{Friday April 25}
\input{hw0}
\input{macros}

\thispagestyle{empty}

\begin{enumerate}

\item Consider the LP problem
  \begin{align*}
     \min        \quad  & c\T x 
  \\ \mathrm{s.t.\quad} & Ax = b,     \tag{a}
  \\                    & x \ge \ell, \tag{b}
  \end{align*}
  where $A$ is $m \times n$ ($m < n$).
  The Primal Simplex method is an active-set method that moves from
  vertex to vertex within the feasible region.
  A vertex is defined by a set of $n$ independent equations
  drawn from the constraints (a) and (b).  In terms
  of the usual basis partition
  \[
     AP = \pmat{B & N}, \qquad x = P \pmat{x\B \\ x\N},
  \]
  write a single matrix equation that defines the current basic and
  nonbasic variables $x\B$, $x\N$ as a vertex.
    You may assume that $\ell$ is finite and the nonbasic variables are
  currently on their lower bounds.  The matrix equation should involve
  $B$ and $N$ and a few other items.

\item Suppose $P = I$ and the above basic solution is optimal, with
  dual variables $(y,z)$ satisfying $B\T y = c\B$ and $z = c - A\T y$.
  Also suppose the last nonbasic variable has bound $\ell_n = 1$
  and reduced gradient $z_n = c_n - a_n^T y = 1.0$.
    Now suppose $\ell_n$ is changed from 1 to $-1$.
  Is the previous solution still optimal?
  (Yes/No.  Why?  What does $z_n$ tell us?)
  
\item Primal Simplex proceeds by
  \emph{moving a nonbasic variable away from its current value},
  while remaining feasible.
  Show how it can be restarted at the previous optimal solution
  (with $x_n = 1$).  What will happen during the first iteration?
  
\item Some systems would set $x_n = -1$ before restarting.
  What does the first basic solution $x\B$ look like?
  (What linear system defines $x\B$?
  Is the solution sure to be feasible?
  Why was it a good idea to start with $x_n = 1$?)

\item Suppose the vector $x$ satisfies $\ell \le x \le u$
  and $d$ is a search direction.  Write some \Matlab{}
  commands to solve the 1D optimization problem
  \\ $\null\qquad\qquad\qquad\qquad\qquad
     \max\ \alpha \hbox{\quad s.t.\quad} \ell \le x + \alpha d \le u$.

\item When the $p$\,th column of $B$ is replaced by $\abar$,
  we have $\Bbar = B + (\abar - a)e_p^T = BT$, where
  $T = I + (v - e_p)e_p^T$ is a
  special matrix constructed from a sparse vector $v$.
  Note that Primal Simplex needs $v$ anyway in order to compute
  the direction $\Delta x$ that led to this basis change.
  The original product-form (PF) update was therefore remarkably
  simple: Pack the nonzeros of $v$ into a sequential file
  (with $v_p$ first so we know where it is).

  Later iterations require the solution of $Tx = w$ and $T\T x = w$
  for various rhs's $w$.  By thinking of $T$ as a permuted triangle,
  show how to solve such systems.  (Observe that we \emph{don't}
  have to work with $T\inv$.  Triangles are already ideal!)

\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: