% No 'submit' option for the problems by themselves.
\documentclass{cos302}
% Use the 'submit' option when you submit your solutions.
%\documentclass[submit]{cos302}
% Put in your full name and email address.
\name{Your Name}
\email{email@princeton.edu}
\discussants{Marie Curie \\ Leonhard Euler}
% You don't need to change these.
\course{COS302-F22}
\assignment{Assignment \#11}
\duedate{6:00pm Friday 16 December 2022 (Dean's Date)}
\dropboxurl{https://www.gradescope.com/courses/438130/assignments/2486355}
\usepackage{bm} % for bold math
\usepackage{mathtools} % colon-equals
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{underscore}
\begin{document}
% IMPORTANT: Uncomment the \documentclass command above with the [submit] option and put your name where it says ``your name''.
\begin{center}
Assignments in COS 302 should be done individually. See the \href{https://www.cs.princeton.edu/courses/archive/fall22/cos302/files/syllabus.pdf}{course syllabus} for the collaboration policy.
\end{center}
\vspace{\baselineskip}
\begin{problem}[20pts]
Solve the following problem using Lagrange multipliers:
\begin{align*}
\text{minimize:}\quad &x^2 + y^2\\
\text{subject to:}\quad &x - y = 3
\end{align*}
\end{problem}
\newpage
\begin{problem}[25pts]
Your friend manages a coffee shop and is trying to figure out how to schedule their employees for the next week.
The shop has two eight-hour shifts, seven days a week.
There are ten employees and each of them has a productivity level~$\rho_i$; you want to maximize the productivity level summed over all the shifts.
No one should work double-shifts or work more than 40 hours per week.
Every shift needs at least two people working.
Nobody should work more than five out of seven days of the week.
\\
\\
You tell your friend that this problem can be solved using linear programming.
Explain how to set that up by explaining what the decision variables would be, what the objective function is, and what the constraints are.
\end{problem}
\newpage
\begin{problem}[25pts]
Determine whether the following functions are convex and explain your reasoning.
\begin{enumerate}[(A)]
\item $f(x)=e^x$
\item $f(x)=x^3$
\item $f(x)=|x|$
\item $f(\bm{x}) = (\bm{x}-\bm{a})^{T}\bm{B}\bm{x}$ for $\bm{x}\in\mathbb{R}^d$, constant~$\bm{a}$, and constant symmetric positive definite~$\bm{B}$.
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[28pts]
The Rosenbrock function
\begin{align*}
f(x,y) &= 100(y-x^2)^2 + (1-x)^2 \,,
\end{align*}
is a classic test function for optimization routines.
It has a global minimum of $0$ at $(1,1)$.
\begin{enumerate}[(A)]
\item Use \texttt{\href{https://numpy.org/doc/stable/reference/generated/numpy.meshgrid.html}{meshgrid}} and \texttt{\href{https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.contourf.html}{contourf}} to make a contour plot of the function on the range~$x\in[-2,2]$, $y\in[-1,3]$.
You'll want to write code that looks kind of like \href{https://matplotlib.org/stable/plot_types/arrays/contourf.html}{this}.
\item Write a function that computes the gradient of the Rosenbrock function.
\item Starting from $(-1,2)$, perform gradient descent to minimize the function. You'll need to set the learning rate (probably to a very small number) and it may require quite a few steps (like thousands). Plot the path of your optimization on the contour plot from part (A).
\item Now, minimize the problem using an off-the-shelf optimization tool. One powerful and widely-used method is the \href{https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm}{Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm}. Fortunately, \texttt{\href{https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html}{scipy.optimize.minimize}} implements it (and many other methods). Check out the documentation, but you'll want to use it doing something along the lines of:
\begin{verbatim}
from scipy.optimize import minimize
steps = []
def cb(x):
global steps
steps.append(x)
result = minimize(func, x0, jac=grad_func, method='BFGS', callback=cb)
\end{verbatim}
There are a few things going on here. \texttt{func} is the function you want to minimize. The argument \texttt{x0} is the initialization. The keyword argument \texttt{jac} takes the gradient function. The keyword argument \texttt{callback} is letting us keep track of the steps the algorithm takes, putting them into the variable \texttt{steps}. The structure \texttt{result} contains various things telling us how the optimization went and what minimum was found, if any.
As in (C), plot the path of the optimization (in \texttt{steps}). Explain what differences you see with the path from part (C).
\end{enumerate}
\end{problem}
\newpage
\begin{problem}[2pts]
Approximately how many hours did this assignment take you to complete?
\end{problem}
My notebook URL:
{\small \url{https://colab.research.google.com/XXXXXXXXXXXXXXXXXXXXXXX}}
\subsection*{Changelog}
\begin{itemize}
\item 6 December 2022 -- Initial version.
\end{itemize}
%\includepdf[pages=-]{hw11solnb.pdf}
\end{document}