Starting from:
$30
CS524- Homework 6- Least Squares Solved
1. Hovercraft rendezvous. Alice and Bob are cruising on Lake Mendota in their hovercrafts. Each hovercraft has the following dynamics:
Dynamics of each hovercraft:
At time t (in seconds), xt ∈R2 is the position (in miles), vt ∈R2 is the velocity (in miles per hour), and ut ∈ R2 is the thrust in normalized units. At t = 1, Alice has a speed of 20 mph going North, and Bob is located half a mile East of Alice, moving due East at 30 mph. Alice and Bob would like to rendezvous at exactly t = 60 seconds. The location where they meet is up to you.
a) Find the sequence of thruster inputs for Alice (uA) and Bob (uB) that achieves a rendezvous at t = 60 while minimizing the total energy used by both hovercraft:
total energy =
Plot the trajectories of each hovercraft to verify that they do indeed rendezvous.
b) In addition to arriving at the same place at the same time, Alice and Bob should also make sure their velocity vectors match when they rendezvous (otherwise, they might crash!) Solve the rendezvous problem again with the additional velocity matching constraint and plot the resulting trajectories. Is the optimal rendezvous location different from the one found in the first part?
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:
(L,U) = eigen(Q) # L is the vector of eigenvalues and U is orthogonal
U * diagm(L) * 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 a direction for vector (x,y,z) such that k(x,y,z)k2 (norm) is unbounded (can be made arbitrarily large) while satisfying the constraint (1).
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020
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?
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 fits the data reasonably well. Note: due to numerical inaccuracy in the solver, you may need to round very small coefficients (say less than 10−5) down to zero. Plot the resulting fit.
2 of 2
Dynamics of each hovercraft:
At time t (in seconds), xt ∈R2 is the position (in miles), vt ∈R2 is the velocity (in miles per hour), and ut ∈ R2 is the thrust in normalized units. At t = 1, Alice has a speed of 20 mph going North, and Bob is located half a mile East of Alice, moving due East at 30 mph. Alice and Bob would like to rendezvous at exactly t = 60 seconds. The location where they meet is up to you.
a) Find the sequence of thruster inputs for Alice (uA) and Bob (uB) that achieves a rendezvous at t = 60 while minimizing the total energy used by both hovercraft:
total energy =
Plot the trajectories of each hovercraft to verify that they do indeed rendezvous.
b) In addition to arriving at the same place at the same time, Alice and Bob should also make sure their velocity vectors match when they rendezvous (otherwise, they might crash!) Solve the rendezvous problem again with the additional velocity matching constraint and plot the resulting trajectories. Is the optimal rendezvous location different from the one found in the first part?
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:
(L,U) = eigen(Q) # L is the vector of eigenvalues and U is orthogonal
U * diagm(L) * 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 a direction for vector (x,y,z) such that k(x,y,z)k2 (norm) is unbounded (can be made arbitrarily large) while satisfying the constraint (1).
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020
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?
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 fits the data reasonably well. Note: due to numerical inaccuracy in the solver, you may need to round very small coefficients (say less than 10−5) down to zero. Plot the resulting fit.
2 of 2
1 file (1.1MB)
