Description

Enclosing circle. Given a set of points in the plane x_{i} 2 R^{2}, 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 x_{i}). 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

Quadratic form positivity. You’re presented with the constraint:






2x^{2} + 2y^{2} + 9z^{2} + 8xy 6xz 6yz 1
(1)






Write the constraint (1) in the standard form v^{T}Qv 1. Where Q is a symmetric matrix. What is Q and what is v?

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)

We can also write the constraint (1) using norms by putting it in the form: kAvk^{2} k Bvk^{2} 1
What is v and what are the matrices A and B that make the constraint above equivalent to (1)?

Explain how to nd (x; y; z) that satis es the constraint (1) and that has arbitrarily large magnitude (i.e. x^{2} + y^{2} + z^{2} is as large as you like).
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.
2 of 2