CS524 Homework 6-Quadratic Programs and Regression Solution

Submit pdf files via Canvas
1. [6 points]
In this problem, you are given a “random” polyhedron
P = {x ∈ Rn | Ax ≤ b},
where ∼ is one of ≤,≥, and b ∈ Rm. You will create each P by choosing its parameters uniformly and randomly in the following intervals:
• bi ∈ [0,100], i = 1,...,m
• aij ∈ [−2,2], i = 1,...,m, j = 1,...,n.
(Note that 0 ∈ P because all the components of b are positive, so we know the polyhedron is nonempty.) Let n = 100,m = 20.
(a) Generate 1000 random points ˆx ∈ Rn whose components ˆxj are chosen randomly from a uniform distribution over [−1,1] for all j = 1,2,...,n. By checking whether or not each of these points lies in P, estimate the probability prob in P of a random point of this type lying in P.
(b) Save one of the ˆx from part (a) that does not lie in P. For this value of ˆx, find the following quantities:
(i) z2 := minx∈P kx − xˆk2
(ii) z1 := minx∈P kx − xˆk1
(iii) z∞ := minx∈P kx − xˆk∞
Recall that
.
Note that the first problem can be solved with convex quadratic programming (convex QP), and the second and third minimum distance problems can be solved with linear programming (LP). Ensure you report scalar outputs for the three projection problems.
Please use set silent(model name) in your code to avoid excessive output. Your code should print only the probability of the point being in P, and the three values of the norm distances to P.
2. [4 points] Quadratic form positivity. You’re presented with the constraint:
2x2 + 6y2 + 2z2 + 4xy − 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)
1 of 2
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 a vector (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).
3. [4 points] 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