CSE524 Homework 6- Quadratic programs Solution

Submit pdf files via Canvas
1. Enclosing circle. Given a set of points in the plane xi ∈ R2, we would like to find the circle with smallest possible area that contains all of the points. Explain how to model this as an optimization problem. To test your model, generate a set of 50 random points using the code X = 4 .+ randn(2,50) (this generates a 2×50 matrix X whose columns are the xi). Produce a plot of the randomly generated points along with the enclosing circle of smallest area.
To get you started, the following Julia code generates the points and plots a circle:
using PyPlot
X = 4 .+ randn(2,50) # generate 50 random points
t = range(0,stop=2*3.141592654,length=100) # parameter that traverses the circle r = 2; x1 = 4; x2 = 4 # radius and coordinates of the center
plot( x1 .+ r*cos.(t), x2 .+ r*sin.(t)) # plot circle radius r with center (x1,x2) scatter( X[1,:], X[2,:], color="black") # plot the 50 points
axis("equal") # make x and y scales equal
2. Quadratic form positivity. You’re presented with the constraint:
2x2 + 2y2 + 9z2 + 8xy − 6xz − 6yz ≤ 1 (1) a) Write the constraint (1) in the standard form vTQv ≤ 1. Where Q is a symmetric matrix. What is Q and what is v?
b) It turns out the above constraint is not convex. In other words, the set of (x,y,z) satisfying the constraint (1) is not an ellipsoid. Explain why this is the case.
Note: you can perform an orthogonal decomposition of a symmetric matrix Q in Julia like this:
(Lambda,U) = eigen(Q) # Lambda is the vector of eigenvalues and U is orthogonal
U * diagm(Lambda) * U’ # this is equal to Q (as long as Q was symmetric to begin with)
c) We can also write the constraint (1) using norms by putting it in the form:
kAvk2−kBvk2 ≤ 1
What is v and what are the matrices A and B that make the constraint above equivalent to (1)?
d) Explain how to find (x,y,z) that satisfies the constraint (1) and that has arbitrarily large magnitude (i.e. x2 + y2 + z2 is as large as you like).
1 of 2
3. Lasso regression. Consider the data (x,y) plotted below, available in lasso_data.csv.

In this problem, we will investigate different approaches for performing polynomial regression.
a) Perform ordinary polynomial regression. Make plots that show the data as well as the best fit to the data for polynomials of degree d = 5 and d = 15. Also comment on the magnitudes of the coefficients in the resulting polynomial fits. Are they small or large?
b) In order to get smaller coefficients, we will use ridge regression (L2 regularization). Re-solve the d = 15 version of the problem using a regularization parameter λ = 10−6 and plot the new fit. How does the fit change compared to the non-regularized case of part a? How do the magnitudes of the coefficients in the resulting polynomial fit change?
2 of 2