\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
            pdftitle={Homework 5},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

\title{Homework 5}

\input{preamble.tex}
\title{Homework}



\begin{document}
\maketitle

Please answer the following questions in complete sentences in a clearly
prepared manuscript and submit the solution by the due date on
Gradescope.

Remember that this is a graduate class. There may be elements of the
problem statements that require you to fill in appropriate assumptions.
You are also responsible for determining what evidence to include. An
answer alone is rarely sufficient, but neither is an overly verbose
description required. Use your judgement to focus your discussion on the
most interesting pieces. The answer to ``should I include `something' in
my solution?'' will almost always be: Yes, if you think it helps support
your answer.

\hypertarget{problem-0-homework-checklist}{%
\subsection{Problem 0: Homework
checklist}\label{problem-0-homework-checklist}}

\begin{itemize}
\item
  Please identify anyone, whether or not they are in the class, with
  whom you discussed your homework. This problem is worth 1 point, but
  on a multiplicative scale.
\item
  Make sure you have included your source-code and prepared your
  solution according to the most recent Edstem note on homework
  submissions.
\end{itemize}

\hypertarget{problem-1-steepest-descent}{%
\subsection{Problem 1: Steepest
descent}\label{problem-1-steepest-descent}}

(Nocedal and Wright, Exercise 3.6) Let's conclude with a quick problem
to show that steepest descent can converge very rapidly! Consider the
steepest descent method with exact line search for the function
\(f(\vx) = (1/2) \vx^T \mQ \vx - \vx^T \vb\). Suppose that we know
\(\vx_0 - \vx^*\) is parallel to an eigenvector of \(\mQ\). Show that
the method will converge in a single iteration.

\hypertarget{problem-2-lps-in-standard-form}{%
\subsection{Problem 2: LPs in Standard
Form}\label{problem-2-lps-in-standard-form}}

Show that we can solve: \[ \MIN{}{\sum_i \max (\va_i^T \vx - b_i, 0)} \]
by constructing an LP in standard form.

\hypertarget{problem-3-duality}{%
\subsection{Problem 3: Duality}\label{problem-3-duality}}

Show that the these two problems are dual by showing the equivalence of
the KKT conditions:
\[ \MINone{\vx}{\vc^T \vx}{\mA \vx \ge \vb, \vx \ge 0} \qquad \text{ and } 
\qquad \MAXone{\vlambda}{\vb^T \vlambda}{\mA^T \vlambda \le \vc, \vlambda \ge 0}. \]

\hypertarget{problem-4-geometry-of-lps}{%
\subsection{Problem 4: Geometry of
LPs}\label{problem-4-geometry-of-lps}}

(Griva, Sofer, and Nash, Problem 3.12) Consider the system of
constraints \(\mA \vx = \vb, \vx \ge 0\) with \[ \mA = 
\bmat{ 
1 & 2 & 3 & 1 & 0 & 0 \\
4 & 5 & 6 & 0 & 1 & 0 \\
7 & 8 & 9 & 0 & 0 & 1 }, 
\text{ and } \vb = \bmat{12 \\ 15 \\ 18}
\] Is \(\vx = \bmat{1 & 1 & 1 & 0 & 0 & 0}^T\) a basic feasible point?
Explain your answer precisely in terms of the definition.

\hypertarget{problem-5-using-the-geometry}{%
\subsection{Problem 5: Using the
geometry}\label{problem-5-using-the-geometry}}

(Griva, Sofer, and Nash, Section 4.3, problem 3.13.) Suppose that a
linear program originally included a free variable \(x_i\) where there
were no upper-and-lower bounds on its values. As we described in class,
this can be converted into a pair of variables \(x_i^+\) and \(x_i^-\)
such that \(x_i^+, x_i^- \ge 0\) and \(x_i\) is replaced with the
difference \(x_i^+ - x_i^-\). Prove that a basic feasible point can have
only one of \(x_i^+\) or \(x_i^-\) different from zero. (Hint: this is
basically a one-line proof once you see the right characterization. I
would suggest trying an example.)

\end{document}
