EE364a: Convex Optimization I
S. Boyd
June 7–8 or 8–9, 2017
Final Exam Solutions
This is a 24 hour takehome final. Please turn it in at Bytes Cafe in the Packard building,
24 hours after you pick it up.
You may use any books, notes, or computer programs, but you may not discuss the exam
with anyone until 5PM June 9, after everyone has taken the exam. The only exception is
that you can ask us for clarification, via the course staff email address. We’ve tried pretty
hard to make the exam unambiguous and clear, so we’re unlikely to say much.
Please make a copy of your exam, or scan it, before handing it in.
Please attach the cover page to the front of your exam.
Assemble your solutions in
order (problem 1, problem 2, problem 3, . . . ), starting a new page for each problem. Put
everything associated with each problem (
e.g.
, text, code, plots) together; do not attach code
or plots at the end of the final.
We will deduct points from long, needlessly complex solutions, even if they are
correct.
Our solutions are not long, so if you find that your solution to a problem goes on
and on for many pages, you should try to figure out a simpler one. We expect neat, legible
exams from everyone, including those enrolled Cr/N.
When a problem involves computation you must give all of the following: a clear discussion
and justification of exactly what you did, the source code that produces the result, and the
final numerical results or plots.
Files containing problem data can be found in the usual place,
Please respect the honor code. Although we allow you to work on homework assignments in
small groups, you cannot discuss the final with anyone, at least until everyone has taken it.
All problems have equal weight. Some are (quite) straightforward. Others, not so much.
Be sure you are using the most recent version of CVX, CVXPY, or Convex.jl. Check your
email often during the exam, just in case we need to send out an important announcement.
Some problems involve applications.
But you do not need to know
anything
about the
problem area to solve the problem; the problem statement contains everything you need.
Some of the data files generate random data (with a fixed seed), which are not necessarily
the same for Matlab, Python, and Julia.
1
1.
Transforming to a normal distribution.
We are given
n
samples
x
i
∈
R
from an
unknown distribution. We seek an increasing piecewiseaffine function
ϕ
:
R
→
R
for
which
y
i
=
ϕ
(
x
i
) has a distribution close to
N
(0
,
1).
In other words, the nonlinear
transformation
x
7→
y
=
ϕ
(
x
) (approximately) transforms the given distribution to a
standard normal distribution.
You can assume that the samples are distinct and sorted,
i.e.
,
x
1
< x
2
<
· · ·
< x
n
, and
therefore we also have
y
1
< y
2
<
· · ·
< y
n
. The empirical CDF (cumulative distribution
function) of
y
i
is the piecewiseconstant function
F
:
R
→
R
given by
F
(
z
) =
0
z < y
1
,
k/n
y
k
≤
z < y
k
+1
,
k
= 1
, . . . , n

1
,
1
z
≥
y
n
.
The
KolmogorovSmirnov
distance between the empirical distribution of
y
i
and the
standard normal distribution is given by
D
= sup
z

F
(
z
)

Φ(
z
)

,