Homework 4

Homework 4#

Note

This homework is due Friday, March 20, 11:59pm on Crowdmark. No credit will be given after Sunday, March 22, 11:59pm.

Instructions#

Problems are worth points as noted. You may receive partial credit for correct work leading to a solution. Note you will upload solutions for each question individually to Crowdmark. This can either be handwritten or typed, but make sure your work is clear and legible.

You will also enter information about what resources you used to complete the homework (e.g., textbook, lecture notes, online resources, generative AI, study groups, etc.) when you upload your solutions to Crowdmark.

import cvxpy as cp 
import numpy as np
import matplotlib.pyplot as plt

Problem 1#

Consider the following optimization problem.

\[ \min_{x_1,x_2,x_3,x_4} \; \; x_1^2+ e^{x_2^2}+x_3^2+3x_4^2+3x_4 \quad \; \text{s.t.} \; \quad 2x_1+3x_2 \geq 4 \]

  • Why does this problem have at most one optimal solution? Justify your answer with the theorems from class.

  • Use CVXPY to solve the problem.

Problem 2#

A working alpaca farm in Albuquerque, New Mexico would like to prepare a signature alpaca wool blend at a minimal cost by mixing wool from two alpacas, Braxton and Manzie. The owners would like the mixture to contain at least 40 units of magic, at least 20 units of sparkles and at least 45 units of fluff. Wool from Braxton costs the shop $1 per pound. Wool from Manzie costs the shop $2 per pound. Braxton’s wool contains 6 units of magic, 1 unit of sparkles and 3 units of fluff. Manzie’s wool contains 4 units of magic, 4 units of sparkles and 5 units of fluff.

  • Write down the linear programming optimization problem that needs to be solved in order to figure out how many pounds of each alpaca’s wool the shop needs to use to minimize its cost.

  • Sketch the feasible region. What are the potential options for the optimal solution? List all the points.

  • Use CVXPY to solve the problem.

Problem 3#

Suppose that we are given 40 points in the plane. Each of these points belongs to one of two classes, red and blue. These points are generate by the code below. The goal is to find a hyperplane given by \(\mathbf{w}^\top \mathbf{x} + \beta = 0\) so that the smallest perpendicular distance between the observations and the hyperplane is as large as possible. See the figure below for the notation

Notation for the maximal margin classifier

np.random.seed(42)  # for reproducibility

P = np.random.rand(40,2)
label = np.array(['red' if 2 * P[i,0] < P[i,1] + 0.5 else 'blue' for i in range(40)])

red_mask = label == 'red'
blue_mask = ~red_mask

plt.scatter(P[red_mask,0], P[red_mask,1], c='red', marker='o', label='red')
plt.scatter(P[blue_mask,0], P[blue_mask,1], c='blue', marker='x', label='blue')
plt.legend(loc = 'lower right');
Contents