\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 6},
            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 6}

\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.

\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 Piazza note on homework
  submissions.
\end{itemize}

\subsection{Problem 1}\label{problem-1}

Using the codes from class (or your own implementations in another
language) illustrate the behavior of the simplex method on the LP from
problem 13.9 in Nocedal and Wright:
\[ \MINthree{}{-5 x_1 - x_2}{x_1 + x_2 \le 5}{2 x_1 + (1/2) x_2 \le 8 }{ \vx \ge 0} \]
starting at \([0,0]^T\) after converting the problem to standard form.

Use your judgement in reporting the behavior of the method.

\subsection{Problem 2}\label{problem-2}

Using the codes from class (or your own implementations in another
language) illustrate the behavior of the simplex method on the LP.
\[ \MINthree{}{-x_1 - 3x_2}{-2x_1 + x_2 \le 2}{-x_1 + 2x_2 \le 7 }{ \vx \ge 0} \]
starting at \([0,0]^T\) after converting the problem to standard form.

Use your judgement in reporting the behavior of the method.

\subsection{Problem 3}\label{problem-3}

Using the codes from class (or your own implementations in another
language) illustrate the behavior of the simplex method on the LP.
\[ \begin{array}{ll}
    \displaystyle\minimize & -3/4 x_1 + 150 x_2 -1/50 x_3 +6 x_4 \\
    \subjectto & 1/4 x_1 - 60 x_2 -1/25 x_3 + 9x_4 \le 0 \\
               & 1/2 x_1 -90 x_2 + 1/50 x_3 + 3 x_4 \le 0 \\
               & x_3 \le 1 \\
               & \vx \ge 0
               \end{array} 
\] starting at \([0,0,0,0]^T\) after converting the problem to standard
form.

Use your judgement in reporting the behavior of the method.

\subsection{Problem 4}\label{problem-4}

Show that if we have: \[
\begin{array}{ll}
    \displaystyle\minimize & \vc^T \vx \\
    \subjectto & \mA \vx \le \vb \\
               & \vx \ge 0 \\
               \end{array}  \] and \(\vb \ge 0\), then \(\vx = 0\) is
always a vertex after converting to standard form.

\subsection{Problem 5}\label{problem-5}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  The goal here is to develop an LP-based solver for a \(\infty\)-norm
  regression problem. Consider the problem:
  \[ \MIN{\vx}{\normof{\mA \vx - \vb}_{\infty} = \max_{i} |\va_i^T \vx - b_i| }, \]
  where \(\va_i^T\) is the \(i\)th row of \(\mA\). This can be converted
  into a linear program and solved via the simplex method. Compute the
  solution for the sports ranking problem. You cannot call external
  solvers.
\item
  Ask an LLM to develop a specialized solver for this problem and
  explain how it works. Which algorithm is faster?
\end{enumerate}

\subsection{\texorpdfstring{\textbf{OPTIONAL} Problem
6}{OPTIONAL Problem 6}}\label{optional-problem-6}

Work with an LLM to learn about how you can update an LU factorization
to avoid recomputing the LU factorization from scratch in each step of
the simplex method. Develop some tests and improve our solver to do an
updated factorization instead.

\end{document}