%
\documentclass[12pt]{article}
%% make references and citations clickable
\usepackage[backref,colorlinks=true, linkcolor=blue, citecolor=blue, urlcolor=blue, pdfborder={0 0 0}]{hyperref}
%% set the paper geometry
\usepackage[left=1in,top=1in,right=1in,bottom=1in,letterpaper]{geometry}
%% uncomment the next line if you need to present an algorithm
%\usepackage{algorithm,algorithmic}
%% standard AMS stuff
\usepackage{amssymb,amsmath}
%% for including urls by \url{url text}
\usepackage{url}
\begin{document}
\title{Homework Assignment 2 -- Math 273a, Fall 2015}
\date{}
\maketitle
\begin{itemize}
\item This homework assignment is open to all textbooks (listed above or not), class notes, and Internet documents except for any solution manual or the solutions from the previous quarters.
\item You are encouraged to ask questions and discuss the questions and solutions on \url{http://piazza.com/ucla/fall2015/math273a/home}.
However, copying othersâ€™ solutions or programs is considered a \textbf{serious violation}.
\item Please type your answers in Latex and \textbf{submit a single PDF file}. Note that you can insert an external PDF file to your latex file by using
\begin{verbatim}
\usepackage{pdfpages} % add this line before \begin{document}
\includepdf[pages={1,2,3}]{myfile.pdf}
\end{verbatim}
\item Although not required, you are encouraged to use notation similar to the course slides.
\item Please \textbf{do {not} include your name anywhere in the submitted PDF file}.
\end{itemize}
%% -------------- Problem ------------------
\newpage
\subsection*{Problem 1. (10 points)} [Type the problem here, or give its reference.]
\medskip
\noindent\textbf{Answer:} [Type your answer here. Make sure you clearly define all mathematical objects in the answer.]
%% -------------- Problem ------------------
\newpage
\subsection*{Problem 2. (10 points)} [Start a problem on a new page. Type the problem here, or give its reference.]
\medskip
\noindent\textbf{Answer:} [Type your answer here. Make sure you clearly define all mathematical objects in the answer.]
%% -------------- Problem ------------------
\newpage
\subsection*{Problem 3. (10 points)} [Start a problem on a new page. Type the problem here, or give its reference.]
\medskip
\noindent\textbf{Answer:} [Type your answer here. Make sure you clearly define all mathematical objects in the answer.]
%% -------------- Problem ------------------
\newpage
\subsection*{Problem 4. (10 points)} Suppose that the polyderon $P=\{x\in\mathbb{R}^n: a_i^Tx \ge b_i,~i=1,\ldots,m\}$ is nonempty. Show that the following statements are equivalent:
\begin{enumerate}
\item[(a)] $P$ has a least one extreme point;
\item[(b)] $P$ does not contain a line;
\item[(c)] There exist $n$ vectors out of $a_1,\ldots,a_m$ that are linearly independent.
\end{enumerate}
(Comments: $P$ is not a standard--form polyhedron. A vector $x\in P$ is an \emph{extreme point} if there do not exist two vectors $y,z\in P$, both different from $x$, and a scalar $\alpha\in(0,1)$ such that $x=\alpha y+(1-\alpha)z$. Given vectors $x$ and $d$, $\{x+\lambda d: \lambda\in\mathbb{R}\}$ is a line. Each direction has 3 points. If all the three directions are correct, add one extra point.)
\medskip
\noindent\textbf{Answer:} [Type your answer here. Make sure you clearly define all mathematical objects in the answer.]
%% -------------- Problem ------------------
\newpage
\subsection*{Problem 5. (10 points)}
Consider a linear program in the standard form. Let $x$ be a basic feasible solution associated with the basis matrix $B$. Prove the following statements:
\begin{enumerate}
\item[(a)] If the reduce cost of every nonbasic variable is positive, then $x$ is the \emph{unique} solution;
\item[(b)] If $x$ is the unique solution and is nondegenerate, then the reduced cost of every nonbasic solution is positive.
\end{enumerate}
(5 points for each statement.)
\medskip
\noindent\textbf{Answer:} [Type your answer here. Make sure you clearly define all mathematical objects in the answer.]
\end{document}