\documentclass[10pt,twoside]{article} \newcommand{\HW}{} \newcommand{\HWnumb}{4} \newcommand{\HWdate}{Monday May 20} \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: