Description
-
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
-
Quadratic form positivity. You’re presented with the constraint:
-
-
-
-
-
-
2x2 + 2y2 + 9z2 + 8xy 6xz 6yz 1
(1)
-
-
-
-
-
-
Write the constraint (1) in the standard form vTQv 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: kAvk2 k Bvk2 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 magni-tude (i.e. x2 + y2 + z2 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
