1. Consider the following logistic regression problem:
min
1 m
b
wT a
c
1
∥
w
2
)) + 100m
w∈Rn,c∈R m i=1
log(1 + exp(− i
i +
∥
where ai, bi are given data. Use the following MATLAB code to generate the data:
m = 500; n = 1000;
A = randn(n,m); b = sign(rand(m,1)-0.5);
Use your student ID as the random seed and the zero vector as starting point. Termi-nate your code when the Euclidean norm of the gradient is smaller than 10−4 or the maximum iteration number 3000 is reached. Implement gradient descent method to solve this problem and compare the convergence rate. You need to implement the line search gradient descent and constant step size gradient descent with at least two small fixed step size such that the algorithms can converge. Plot the results in one figure.
2. Consider the following logistic regression problem:
min
1
m
log(1 + exp(
b
wT a
)) +
1
∥
w
2
w∈Rn m
i=1
− i
i
100m
∥
where ai, bi are given. Test your algorithms on three real datasets from libsvm: ’a9a.test’, ’CINA.test’ and ’ijcnn1.test’. You may use the following MATLAB code to generate the data:
d a t a s e t
= ’ a9a . t e s t ’ ;
[ b ,A]
=
l i b s v m r e a d ( d a t a s e t ) ;
[m, n ]
=
s i z e (A ) ;
mu = 1 e−2/m;
(a) Use the zero vector as starting point. Terminate your code when the Euclidean norm of the gradient is smaller than 10−6. Implement Newton’s method and inexact Newton (Newton-CG) method (with three different inexact rules) to solve
this problem and compare the convergence rate. The three different tolerance rules for inexact Newton methods are η = min(0.5, ∥g ∥)∥g∥, η = min(0.5, ∥g∥)∥g∥, and η = 0.5∥g∥. You need to use Armijo rule line search for both methods. Plot the results (four lines) on gradient norm in one figure, and on function values l(xk) −l(x∗), for each dataset. (l(x∗) can be obtained by running Newton’s method for higher accuracy.)
(b) Implement gradient descent with Armijo rule line search. Terminate your code with maximum iteration number 1000. Plot the results, together with two New-ton’s methods in the previous question, in one figure for each dataset.
1
