Convex Optimization Homework #2

Convex Optimization Homework #2,

1. (100%) In this problem, we use the Newton’s method to solve an unconstrained optimization problem. We wish to
minimize
f(x) = Xm
i=1
e
a
T
i x−bi
where A ∈ R
m×n with ai being the transponse of the ith row of A, b ∈ Rm, and the variable x ∈ Rn. A special case of
this is when we choose m = 3, n = 2, and
A =


1 3
1 −3
−1 0

 , b =


0.1
0.1
0.1

 , (1)
then it reduces to Eq. (9.20) in the textbook:
f(x) = e
x1+3x2−0.1 + e
x1−3x2−0.1 + e
−x1−0.1
.
(a) Find dom f. Show that dom f is a convex set.
(b) Derive Of(x) and O
2f(x) for any x ∈ dom f.
(c) Write a matlab m-file as a function which takes inputs A, b, and x, and evaluates the objective function at the point
x, as well as the gradient and the Hessian.
Hint: the function can have a header that looks like the following.
function [f, g, H] = my_objective(x, A, b)
(d) From this step on, write another m-file as the main function for your program to solve the unconstrained problem.Set
A and b as in Eq. (1) and set the initial point x
(0) = 0.
(e) Use the Newton step’s formula: ∆xnt = −(O
2f(x))−1Of(x) and calculate the first Newton step ∆x
(0)
nt .
(f) Calculate the Newton decrement λ(x) = (−Of(x)
T ∆xnt)
1/2
.
(g) Perform backtracking line search along search direction using β = 0.7 starting from t = 1 until f(x + t∆x
(0)
nt ) ≤
f(x) − αtλ(x)
2
, where α = 0.1.
(h) Perform the update x
(1) = x
(0) + t∆x
(0)
nt . Determine whether λ
2/2 <  where  = 10−10
.
(i) Repeat (e)-(i) for the next iteration. Wrap up these steps in a main loop. For the kth iteration, record the following
items: (1) f(x
(k)
), (2) λ(x
(k)
), (3) t
(k)
. Plot λ(x
(k)
)
2/2 versus k.
(j) Use the cvx toolbox to solve the problem. Compare the results (i.e., optimal value and optimal point) with those you
obtained through Newton’s method. Do they coincide with each other?
(k) Set A =


1 2
1 −2
−1 0

 , b =


0.2
0.1
0.3

 , and x
(0) = 0. Repeat (e)-(j).
Homework submission guidelines:
• Submit your answer online as a set of three files: two m-filesand a document file (in *.pdf or *.docx) that contains all
answers (including plots) in this problem set.
• If you choose to do the homework in Python, then submit *.py files instead of m-files.
• Submit your files online at the Ceiba website. No paper shall be handed in.
• Late submissions will be treated under the principle elaborated as follows.
(1) Homework received by 9pm, June 5 (t1) will be counted fully.
(2) Homework received after midnight (0am), June 6 (t2) will not be counted.
(3) Homework received between t1 and t2 will be counted with a discount rate
t2 − t
t2 − t1
where t is the received time. Note that t2 − t1 is three hours.
• Plagiarism is strongly prohibited. While discussions among classmates are allowed (and encouraged), you shall not ask
anyone else to share his/her codes with you, nor should you attempt to share with anyone your codes. You should write
every line of the code by yourself. If any part of your submission is found to be copied from someone else’s submission,
then both of your homework submissions will be counted zero.
1