Homework 6: Convex programs

CS/ECE/ISyE 524 Introduction to Optimization 
Homework 6: Convex programs

See the course website for instructions and submission details.
1. [15 pts] The Huber loss. In statistics, we frequently encounter data sets containing outliers, which
are bad data points arising from experimental error or abnormally high noise. Consider for example
the following data set consisting of 15 pairs (x, y).
x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y 6.31 3.78 24 1.71 2.99 4.53 2.11 3.88 4.67 4.25 2.06 23 1.58 2.17 0.02
The y values corresponding to x = 3 and x = 12 are outliers because they are far outside the expected
range of values for the experiment.
a) Compute the best linear fit to the data using an `2 cost (least squares). In other words, we are
looking for the a and b that minimize the expression:
`2 cost: X
15
i=1
(yi − axi − b)
2
Repeat the linear fit computation but this time exclude the outliers from your data set. On a
single plot, show the data points and both linear fits. Explain the difference between both fits.
b) It’s not always practical to remove outliers from the data manually, so we’ll investigate ways of
automatically dealing with outliers by changing our cost function. Find the best linear fit again
(including the outliers), but this time use the `1 cost function:
`1 cost: X
15
i=1
| yi − axi − b |
Include a plot containing the data and the best `1 linear fit. Does the `1 cost handle outliers
better or worse than least squares? Explain why.
c) Another approach is to use an `2 penalty for points that are close to the line but an `1 penalty
for points that are far away. Specifically, we’ll use something called the Huber loss, defined as:
φ(x) = (
x
2
if − M ≤ x ≤ M
2M|x| − M2 otherwise
Here, M is a parameter that determines where
the quadratic function transitions to a linear
function. The plot on the right shows what
the Huber loss function looks like for M = 1.
−3 −2 −1 0 1 2 3
0
1
2
3
4
5
6
The formula above is simple, but not in a form that is useful for us. As it turns out, we can
evaluate the Huber loss function at any point x by solving the following convex QP instead:
φ(x) =



minimize
v,w
w
2 + 2Mv
subject to: |x| ≤ w + v
v ≥ 0, w ≤ M



1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
Verify this fact by solving the above QP (with M = 1) for many values of x in the interval
−3 ≤ x ≤ 3 and reproducing the plot above. Finally, find the best linear fit to our data using a
Huber loss with M = 1 and produce a plot showing your fit. The cost function is:
Huber loss: X
15
i=1
φ( yi − axi − b)
2. [10 pts] Hyperbolic program. In this problem, we start with a problem that doesn’t appear to be
convex and show that it is in fact convex by converting it into an SOCP.
a) Recall from class that for any w ∈ R
n and x, y ∈ R, the following constraints are equivalent:
w
Tw ≤ xy, x ≥ 0, y ≥ 0 ⇐⇒





2w
x − y




≤ x + y
Suppose we have an optimization problem with variables t ≥ 0 and x ∈ R
n. Express the constraint:
t(a
Tx + b) ≥ 1 as a second-order cone constraint. Specifically, write the constraint in the form
kAx + bk ≤ c
Tx + d. What are A, b, c, d, x?
b) Consider the following hyperbolic optimization problem (note the nonlinear objective):
minimize
x
Xp
i=1
1/(a
T
i x + bi)
subject to a
T
i x + bi > 0, i = 1, . . . , p
c
T
j x + dj ≥ 0, j = 1, . . . , q
Write this optimization problem as an SOCP. Hint: the first part of this problem is very relevant!
3. [10 pts] Heat pipe design. A heated fluid at temperature T (degrees above ambient temperature)
flows in a pipe with fixed length and circular cross section with radius r. A layer of insulation, with
thickness w, surrounds the pipe to reduce heat loss through the pipe walls (w is much smaller than r).
The design variables in this problem are T, r, and w.
The energy cost due to heat loss is roughly equal to α1T r/w. The cost of the pipe, which has a fixed
wall thickness, is approximately proportional to the total material, i.e., it is given by α2r. The cost of
the insulation is also approximately proportional to the total insulation material, i.e., roughly α3rw.
The total cost is the sum of these three costs.
The heat flow down the pipe is entirely due to the flow of the fluid, which has a fixed velocity, i.e., it
is given by α4T r2
. The constants αi are all positive, as are the variables T, r, and w.
Now the problem: maximize the total heat flow down the pipe, subject to an upper limit Cmax on total
cost, and the constraints
Tmin ≤ T ≤ Tmax, rmin ≤ r ≤ rmax wmin ≤ w ≤ wmax, w ≤ 0.1r
a) Express this problem as a geometric program, and convert it into a convex optimization problem.
b) Consider a simple instance of this problem, where Cmax = 500 and α1 = α2 = α3 = α4 = 1.
Also assume for simplicity that each variable has a lower bound of zero and no upper bound.
Solve this problem using JuMP. Use the Mosek solver and the command @NLconstraint(...)
to specify nonlinear constraints such as log-sum-exp functions. Note: Mosek can solve general
convex optimization problems! What is the optimal T, r, and w?
2 of 2