% 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-F23}
\assignment{Assignment \#11}
\duedate{6:00pm Friday 15 December 2023 (Dean's Date, so no extensions possible)}
\dropboxurl{https://www.gradescope.com/courses/606160/assignments/3745386}
\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/fall23/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]
An investment firm wants to allocate a budget of \$100,000 across four different investment options: stocks, bonds, real estate, and a startup venture.
The expected annual return rates for these investments are 5\% for stocks, 3\% for bonds, 4\% for real estate, and 10\% for the startup venture.
However, each investment comes with different risk factors and the firm wants to manage its risk exposure.
The firm has established the following risk limits:
\begin{itemize}
\item No more than 40\% of the total investment should be in high-risk options (stocks and startup venture).
\item At least 30\% of the total investment should be in low-risk options (bonds).
\item The investment in real estate should not exceed 35\% of the total investment.
\end{itemize}
Formulate a linear programming model to maximize the firm's expected annual return.
Define the decision variables for the amounts to invest in each option, the objective function for maximizing return, and the constraints based on both the risk limits and the required properties for the percentages to make sense.
\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)=\tanh(x)$
\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 29 November 2023 -- Initial version.
\end{itemize}
%\includepdf[pages=-]{hw11solnb.pdf}
\end{document}