Continuous Assessment for EE5138
Optimization for Electrical Engineering
Semester 2, 21/22
This continuous assessment has 40 marks in total. Answer all the questions. Please
submit your answer in one single PDF file (with your name indicated as the file name) on
the class website (under the folder “Student Submission”) by 11:59pm April 17 2022
(a firm deadline with no extension allowed). Please show your working in all the answers
and include all the used Matlab codes in your submitted PDF file.
[40 marks] Consider the following unconstrained problem,
minimize f(x) = −
m∑
i=1
log(1− aTi x)−
n∑
i=1
log(1− x2i ),
with variable x ∈ Rn, and dom f = {x|aTi x < 1, i = 1, · · · ,m, |xi| < 1, i = 1, · · · , n}.
Note that this is the problem for computing the analytic center of the set of linear in-
equalities:
aTi x < 1, i = 1, · · · ,m, |xi| ≤ 1, i = 1, · · · , n.
(a) Show the gradient and Hessian of f(x) are, respectively,
∇f(x) =
m∑
i=1
ai
1− aTi x
−
(
1
1 + x1
− 1
1− x1 , · · · ,
1
1 + xn
− 1
1− xn
)T
,
∇2f(x) =
m∑
i=1
aia
T
i
(1− aTi x)2
+ diag
(
1
(1 + x1)2
+
1
(1− x1)2 , · · · ,
1
(1 + xn)2
+
1
(1− xn)2
)
,
where diag(z) denotes a diagonal matrix with its main diagonal given by vector z.
[10 marks]
1
(b) Use gradient method to solve this problem. Consider the case of m = 300 and
n = 200. Note that the parameters ai’s are stored in the matrix A = [a1, · · · , am]T ,
which is given in the attached A.txt file. Please read matrix A in matlab using the
command “A=dlmread(‘A.txt’)” and then solve the problem based on this given
A. Choose x(0) = 0 as your initial point, and ∥∇f(x(k))∥2 ≤ 10−3 as the stopping
criterion for gradient method. Use the backtracking line search with each of the
following four groups of parameters: α = 0.01, β = 0.1; α = 0.01, β = 0.5; α = 0.2,
β = 0.1; α = 0.2, β = 0.5.
(b.1) Find the optimal value p∗ of this problem obtained by gradient method.
(b.2) Plot f(x(k))−p∗ versus iteration for the given 4 sets of backtracking parameters
in one figure and comment on the effect of backtracking parameters α and β
on the total number of iterations required for convergence.
(b.3) Plot the step size t(k) versus iteration for the case of α = 0.01, β = 0.5.
[15 marks]
(c) Use Newton method to solve this problem. Consider again the case of m = 300
and n = 200 and use the same matrix A as in part (b). Choose x(0) = 0 as your
initial point, and λ(x(k))2 ≤ 10−8 as the stopping criterion for Newton method. Set
α = 0.01 and β = 0.5 for the backtracking line search.
(c.1) Find the optimal value p∗ of this problem obtained by Newton method.
(c.2) Plot f(x(k))− p∗ versus iteration and comment on the quadratic local conver-
gence observed.
(c.3) Plot the step size t(k) versus iteration.
[15 marks]
– END –
2