Handin7
a) Determine the gradient and Hessian for the function
f(x) = log(sum(exp(a_i' * x)))
where a_i' is row i in the matrix A.
Hint: See pp 74, 642 and 645 in the book.
b) Your task is to implement a Newton algorithm with line search for the following problem (described in CVX language):
randn('seed',0); m=500; n=100; A = randn(m,n);
cvx_begin
variable x(n)
minimize(log_sum_exp(A*x))
cvx_end
(with optimal value 6.0899388).
As a help you can use the following code fragment, which however solves problem 9.30 for the goal function in that problem. Note: you can remove the first while statement which iterates to find a feasible solution.
Use "cputime" to measure the runtime of your code. You should be able to beat CVX easily. My code was e.g. > 100 times faster than CVX.
ALPHA = 0.01; % feel free to tune these parameters
BETA = 0.5;
MAXITERS = 100;
NTTOL = 1e-8;
x = zeros(n,1);
for iter = 1:MAXITERS
val = -sum(log(1-A*x)) - sum(log(1+x)) - sum(log(1-x)); % change here
d = 1./(1-A*x);% change here
grad = A'*d - 1./(1+x) + 1./(1-x);% change here
hess = A'*diag(d.^2)*A + diag(1./(1+x).^2 + 1./(1-x).^2);% change here
v = -hess\grad;
fprime = grad'*v;
if abs(fprime) < NTTOL, break; end;
t = 1;
while ((max(A*(x+t*v)) >= 1) | (max(abs(x+t*v)) >= 1)),% you can erase this search
t = BETA*t;
end;
while ( -sum(log(1-A*(x+t*v))) - sum(log(1-(x+t*v).^2)) > val + ALPHA*t*fprime ) % change here
t = BETA*t;
end;
x = x+t*v;
end;