Homework 6

Homework 6#

Note

This homework is due Friday, April 17, 11:59pm on Crowdmark. No credit will be given after Sunday, April 19, 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 numpy as np
import matplotlib.pyplot as plt
import cvxpy as cp

Problem 1#

Consider the problem

\[\begin{split} \begin{aligned} \min &\quad (x-1)^2+(y+2)^2\\ \text{s.t.} &\quad x^2+y^2\leq4 \end{aligned} \end{split}\]

Solve the problem using duality. For full credit, you must:

  • Clearly state the dual problem, including a simplifed version of the function \(q(\lambda)\).

  • Solve the dual problem.

  • Use the solution above to solve the primal problem.

  • If you are claiming that your dual solution is equal to the primal solution, you must justify why you can do that.

Problem 2#

Consider the linear programming problem

\[\begin{split} \begin{aligned} \min \quad & 2x+y\\ \text{s.t.}\quad & x+y\le 4,\\ & -x-2y\le -2. \end{aligned} \end{split}\]

Use the dual formulation to solve the problem. For full credit you must:

  • Write out the full formulation of the dual problem (Note this needs to be the same as the setup in class).

  • Solve the dual problem.

  • Use this to solve the original problem.

  • Give justification for why you came to the conclusion in the previous step.

Problem 3 (coding)#

Use CVXPY to solve the convex quadratic optimization problem

\[\begin{split} \begin{aligned} \min_{\mathbf{x} \in \mathbb{R}^2} \quad & \mathbf{x}^\top Q\mathbf{x} + 2\mathbf{c}^\top \mathbf{x} \\ \text{s.t.} \quad & A\mathbf{x} \leq \mathbf{b}, \end{aligned} \end{split}\]

where

\[\begin{split} Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{c} = \begin{bmatrix} -2 \\ -3 \end{bmatrix}, \qquad A = \begin{bmatrix} 1 & 1 \\ -1 & 0 \\ 0 & -1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 3 \\ 0 \\ 0 \end{bmatrix}. \end{split}\]

For full credit, you must:

  • Write CVXPY code to define the problem data and solve the primal problem.

  • Report the optimal solution \(\mathbf{x}^*\) and the optimal primal value \(f^*\).

  • Use the dual values returned by CVXPY for the inequality constraints to report the optimal dual variables \(\boldsymbol{\lambda}^*\).

You do not need to derive or separately solve the dual problem by hand.

Contents