\documentclass[10pt,twoside]{article}
\newcommand{\HW}{}
\newcommand{\HWnumb}{4}
\newcommand{\HWdate}{Monday May 21}
\input{hw0}
\input{../notes/macros}

\thispagestyle{empty}

%\enlargethispage{0.15in}

\newcommand{\maxmod} {\mathit{maxmod}}  % math mode
\newcommand{\tmaxmod}{\textit{maxmod}}  % text mode
\newcommand{\myrule}{\rule[-2.50mm]{0.5mm}{6.4mm}}
\newcommand{\myprop}{\rule[-1.30mm]{0.0mm}{4.0mm}}
\newcommand{\Uij}[2]{\framebox[25pt][c]{\myprop$U_{#1#2}$}}
\newcommand{\Ux}    {\framebox[25pt][c]{\myprop--}}

\medskip

\begin{enumerate}
% \item Consider the problem
% \begin{equation}
% \min_x f(x) := \textstyle{\max_{i\in[m]} a_i^Tx + b_i},
% \label{eq:bundle}
% \end{equation}
% where $A\in\Re^{m\times n}$ and $b\in\Re^n$ are given. The problem is an LP, but for very large instances, a first-order method may be the only practical option. Since $f$ is non-smooth, we adopt a smoothing approach. A closely related problem is the Chebyshev approximation problem:
% \[
% \min_x \|Ax + b\|_\infty.
% \]

% The function $f$ has conjugate representation $\sup_{y \ge 0,\,e^Ty = 1}y^T(Ax+b).$ Show that
% \[
% f_\lambda(x) = \sup_{y \ge 0,\,e^Ty = 1}y^T(Ax + b) - \lambda d(y):d(y) = \sum_{i=1}^n y_i\log y_i,
% \]
% is given by $\lambda\log\sum_{i=1}^me^{\frac1\lambda(a_i^Tx + b_i)}.$ This is the log-sum-exp approximation to the non-smooth max function. Solving problems of the form \eqref{eq:bundle} is the basic step in \emph{bundle methods} for non-smooth optimization.

\item Consider the LO problem
  \begin{align}
     \min              \quad  & c\T x         \nonumber
  \\[-3pt] \mathrm{s.t.\quad} & Ax = b,       \label{eq:1}
  \\[-3pt]                    & \,x \ge \ell, \label{eq:2}
  \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 \eqref{eq:1} and \eqref{eq:2}.  In terms
  of the usual basis partition
  \[
     AP = \pmat{B & N}, \qquad x = P \pmat{x\B \\ x\N}
  \]
  (where $P$ is a column permutation),
  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/Maybe.  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.  For the
  previous example, show how primal simplex can be restarted at the
  previous optimal solution (with $x_n = 1$).  What will (or might)
  happen during the first iteration?

\item If the simplex implementation thought that nonbasic variables
  had to be on a bound, it would set $x_n = -1$ before restarting.
  What does the first basic solution $x\B$ then look like?
  (Which 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 $p$ is a search direction.  Write an efficient
  (vectorized) \Matlab{} function to solve the 1D optimization problem
  \begin{equation}
     \label{eq:alphamax}
     \max\ \alpha \hbox{\quad s.t.\quad} \ell \le x + \alpha p \le u,
  \end{equation}
  returning $\alpha$ and the index $r$ that keeps $\alpha < \infty$
  (else $r=0$).  Allow for some elements of $\ell$ and $u$ being
  infinite, and some elements of $p$ being zero.  Avoid creating
  \texttt{inf}s and \texttt{nan}s.

% \item In the steplength procedure, several variables might satisfy
%   $x_j = \ell_j$ or $u_j$ exactly when $\alpha=0$ or when $\alpha =
%   \alpha_{\max}$ (the solution of \eqref{eq:alphamax}).  This could
%   mean that more than one variable determines $\alpha_{\max}$.
%   Suggest a good precaution in the event of ties (in terms of stability).

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

%   Later iterations require the solution of $Tv = w$ or $T\T v = w$
%   with 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!)

% \item (Magic formula) The block-LU update works with a dense
%   factorization $LC = U$, where $L$ is square and well-conditioned,
%   and $U$ is upper triangular.  The maximum dimension of $L$ and $U$
%   is a predetermined number \tmaxmod.  Although we typically set
%   $\maxmod \le 200$, we save memory (and cache) by storing $L$ and $U$
%   row-wise in 1D arrays \texttt{L} and \texttt{U}.  If $\maxmod=4$ and
%   $U$ is currently full-size, we would have
%   \[
%     \mathtt{U} = \myrule \Uij11 \Uij12 \Uij13 \Uij14 \myrule
%                                 \Uij22 \Uij23 \Uij24 \myrule
%                                        \Uij33 \Uij34 \myrule
%                                               \Uij44 \, ,
%   \]
% and if $U$ is currently only $3 \times 3$ or $2 \times 2$, we would have
%   \[
%     \mathtt{U} = \myrule \Uij11 \Uij12 \Uij13 \Ux \myrule
%                                 \Uij22 \Uij23 \Ux \myrule
%                                        \Uij33 \Ux \myrule
%                                               \Ux \, \phantom,
%   \]
% or
%   \[
%     \mathtt{U} = \myrule \Uij11 \Uij12 \Ux    \Ux \myrule
%                                 \Uij22 \Ux    \Ux \myrule
%                                        \Ux    \Ux \myrule
%                                               \Ux \, ,
%   \]
% with the diagonal of each row starting in the \emph{same position}.
% Show that the location of the $i$th diagonal of $U$ is
% $\mathit{ldiag} = (i - 1)*\mathit{maxmod} + (3 - i)*i/2$. % Magic formula!

\end{enumerate}

\end{document}

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