Homework 6: Quadratic programs

    1. Enclosing circle. Given a set of points in the plane xi 2 R2, we would like to nd 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 k Bvk2 1
What is v and what are the matrices A and B that make the constraint above equivalent to (1)?

    d) Explain how to nd (x; y; z) that satis es the constraint (1) and that has arbitrarily large magni-tude (i.e. x2 + y2 + z2 is as large as you like).














1 of 2
CS/ECE/ISyE 524    Introduction to Optimization    Steve Wright,    Spring 2021


3. Lasso regression. Consider the data (x; y) plotted below, available in lasso_data.csv.










y




1.0


0.5


0.0


0.5


1.0


0.1
0.2
0.3
0.4
0.5


x



In this problem, we will investigate di erent approaches for performing polynomial regression.

    a) Perform ordinary polynomial regression. Make plots that show the data as well as the best t to the data for polynomials of degree d = 5 and d = 15. Also comment on the magnitudes of the coe cients in the resulting polynomial ts. Are they small or large?

    b) In order to get smaller coe cients, 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 t. How does the t change compared to the non-regularized case of part a? How do the magnitudes of the coe cients in the resulting polynomial t change?

    c) Our model is still complicated because it has so many parameters. One way to simplify our model is to look for a sparse model (where many of the parameters are zero). Solve the d = 15 problem once more, but this time use the Lasso (L1 regularization). Start with a large and progressively make smaller until you obtain a model with a small number of parameters that ts the data reasonably well. Note: due to numerical inaccuracy in the solver, you may need to round very small coe cients (say less than 10 5) down to zero. Plot the resulting t.


























2 of 2