\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Tr}{Tr}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 3220: Homework 5}\\
Instructor: Anil Damle\\
Due: December 7\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please refrain from looking at their code or writeups (or sharing your own). Ultimately, you must implement your own code and write up your own solution to be turned in. Your solution, including plots and requested output from your code should be submitted via the CMS as a pdf file. Additionally, please submit any code written for the assignment via the CMS as well.\\
\hrule
\vspace{5mm}
\subsection*{Question 1:}
In class, we discussed how often we look for local minima with our optimization algorithms and finding a global minimum is generally much harder. However, there is a nice class of functions for which any local minimum is a global minimum. Specifically, this is the class of convex functions and they are common enough entire courses are dedicated to their study.
A function $f:\R\rightarrow \R$ is convex if for any two points $x,y\in\R$ and any value $t\in[0,1]$
\[
f(tx + (1-t)y) \leq tf(x) + (1-t)f(y).
\]
Show that if $f$ is convex then any local minimum is a global minimum. (Hint: assume that you have a local minimum that is not a global minimum and show a contradiction.)
\subsection*{Question 2:}
Say we are optimizing a function $\phi(x)$ with $x\in\R^n.$ Assume we have found a point $x_c$ such that $\nabla \phi(x_c) = 0,$ but that $\nabla^2\phi(x_c)$ has at least one negative eigenvalue. Show that $x_c$ is not a local minimizer.
\end{document}