\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}

\newcommand{\A}{\mathbb{A}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\ol}{\overline}
\newcommand{\J}{\mathcal{J}}
\newcommand{\X}{\mathcal{X}}
\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem{extraProb}{Extra Problem}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\ext}{ext}




\begin{document}
 \thispagestyle{empty}
\begin{center} {\large \textbf{Math 407 -- Homework  7}} \smallskip \\ 
Due on Thursday, November 30\ \\ \ \\
 \end{center}

You are welcome to talk with other students in the class about problems but should write up solutions on your own. 
Solutions can be handwritten or typed but need to be legible and submitted via Gradescope by the end of the day 
on Thursday. You should justify all your answers in order to receive full credit.  


\begin{flushleft}


\begin{prob} 
Consider a linear program in $n=8$ variables and $m=4$ equations whose simplex tableau $\mathcal{T}(\{1,2,3,4\})$ is 
$$
\begin{array}{ccccccccccc}
x_1 & = & \lambda & - & x_5 & + & x_6 &  && - & 2x_8\\
x_2 & = & 2& - & x_5 &   &   &  -&2x_7& - & x_8\\
x_3 & = & 1 &  	&  &  &  &- & x_7 & + & x_8\\
x_4 & = & 2 & - & 2x_5 & - & x_6  & - & x_7 &  & \\
\hline
z & = & 8 & -& x_5 & - &2 x_6 &  - & 3x_7 & - & 5x_8
\end{array}
$$
where $\lambda \in \R$. 
Use the dual simplex method to answer the following: \medskip  \\
\begin{itemize}
\item[(a)] For what values of $\lambda \in  \R$ is this linear program feasible? \medskip 
\item[(b)] For all $\lambda\in \R$ satisfying your answer from (a), give the optimal value and optimal solution. 
\end{itemize}
\end{prob}



\vfill 

\begin{prob} 
Write a linear program that solves the following problem: 
Find the maximum value a monic cubic polynomial $f(t) = t^3+at^2+bt+c$ can take 
at $t=3$ if its values at $t=0,1,2$ all lie in the interval $[-1,1]$. \\ \ \\

\emph{Bonus:} What is this maximum value and the polynomial that achieves it? \\
(Use any method you like to find this, including computer programs or online solvers.)
\end{prob}


\vfill 

\pagebreak 

\begin{prob}
Let $f({\bf x}) = \sum_{j=1}^k|{\bf v}_j^T{\bf x} - w_j |$, where ${\bf v}_1, \hdots, {\bf v}_k\in \R^n$ and $w_1, \hdots, w_k\in \R$ and 
consider the two optimization problems  
\begin{align*}
&{(\rm P1)}  && \min  f({\bf x}) \text{ s.t. } A{\bf x} \leq {\bf b} \\
&{(\rm P2)}&&  \min \sum_{j=1}^ky_j \text{ s.t. } A{\bf x}\leq {\bf b}\text{ and }
{\bf v}_j^T{\bf x} - w_j\leq y_j \text{ and }  w_j-{\bf v}_j^T{\bf x} \leq y_j
\text{ for } j=1, \hdots, k
\end{align*}
where $A\in \R^{m\times n}$, ${\bf b}\in \R^m$. \medskip 


\begin{itemize}
\item[(a)]  Show that for any feasible point ${\bf x}$ of (P1), there exists ${\bf y}\in \R^{k}$ so that $({\bf x}, {\bf y})$ is feasible for (P2) and $\sum_{j=1}^k y_j \leq f({\bf x})$. \medskip 
\item[(b)] Show that for any feasible point $({\bf x},{\bf y})$ of (P2), ${\bf x}$ is feasible for (P1) and $f({\bf x}) \leq \sum_{j=1}^k y_j $. \medskip 
\item[(c)]  Conclude that the optimization problems (P1) and (P2) have the same optimal value.  (This is useful because (P2) is a linear program!) 
\medskip 
\item[(d)] Does this still work if we replace ``min'' with ``max''?  That is, are the optimal values of the following problems (P3) and (P4) always the same? Why or why not?\medskip 
\begin{align*}
&{(\rm P3)}  && \max  f({\bf x}) \text{ s.t. } A{\bf x} \leq {\bf b} \\
&{(\rm P4)}&&  \max \sum_{j=1}^ky_j \text{ s.t. } A{\bf x}\leq {\bf b}\text{ and }
{\bf v}_j^T{\bf x} - w_j\leq y_j \text{ and }  w_j-{\bf v}_j^T{\bf x} \leq y_j \text{ for } j=1, \hdots, k
\end{align*}
\end{itemize}

\end{prob}





\end{flushleft}
\end{document}