Homework 5: Quadratic programs

CS/ECE/ISyE 524 Introduction to Optimization 
Homework 5: Quadratic programs

See the course website for instructions and submission details.
1. [10 pts] Enclosing circle. Given a set of points in the plane xi ∈ R
2
, we would like to find 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 = linspace(0,2pi,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. [10 pts] Quadratic form positivity. You’re presented with the constraint:
2x
2 + 2y
2 + 9z
2 + 8xy − 6xz − 6yz ≤ 1 (1)
a) 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.
b) Show that the following QCQP is unbounded:
maximize x
2 + y
2 + z
2
subject to (1)
Hint: this is not a convex QCQP because as seen above, (1) is not convex. Moreover, the
objective is not convex because it involves maximizing a positive definite quadratic. So do not
attempt to solve this using JuMP! Instead, show how to construct a vector (x, y, z) of arbitrarily
large magnitude that satisfies (1).
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
3. [10 pts] Hovercraft rendezvous. Alice and Bob are cruising on Lake Mendota in their hovercrafts.
Each hovercraft has the following dynamics:
Dynamics of each hovercraft:
xt+1 = xt +
1
3600 vt
vt+1 = vt + ut
At time t (in seconds), xt ∈ R
2
is the position (in miles), vt ∈ R
2
is the velocity (in miles per hour),
and ut ∈ R
2
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 t = 60 seconds. The location at which they meet is not important, but the time is!
a) Find the sequence of thruster inputs for Alice (u
A) and Bob (u
B) that achieves a rendezvous at
t = 60 while minimizing the total energy used by both hovercraft:
total energy = X
60
t=1

u
A
t


2
+
X
60
t=1

u
B
t


2
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?
c) Alice and Bob forgot about one important detail. The hovercrafts each have a top speed of
35 mph. The solutions found in the previous parts are unacceptable because they require Alice to
exceed the maximum allowable speed. First, verify that this is indeed the case. Second, explain
how to alter your model to account for the speed limit. Finally, solve the rendezvous problem one
last time with all the constraints in place and verify that your solution respects the speed limit.
2 of 2