test_nag.m

function test_nag()
r = randn(2,2);

a00 = 1;
a11 = 40;

A = [a00 0;
    0, a11];
% A = A + r*r';
b = [0; 0];


xs = -40:0.5:40;
ys = -40:0.5:40;
zs = zeros(length(xs), length(ys));
for i = 1:length(xs)
    for j = 1:length(ys)
        zs(j,i) = f([xs(i); ys(j)], A, b); %%%% NOTE: it should be zs(j,i), NOT zs(i,j)
    end
end

max_iter = 100;
% eta = 0.01*4;
% mu = 0.5;

eta = 1/a11/2;
Q = a11/a00;
mu = (sqrt(Q) - 1)/(sqrt(Q)+1);

x0 = [35;35];
[x_array_GD, obj_array_GD] = gradient_descent(x0, A, b, eta,max_iter);
[x_array_CM, obj_array_CM] = momentum(x0, A, b, eta, mu,max_iter);
[x_array_NAG, obj_array_NAG] = nag(x0, A, b, eta, mu,max_iter);
 
figure;
contour(xs,ys,zs,50);hold on;
h1 = plot(x_array_GD(1,:),x_array_GD(2,:),'-ks','MarkerFaceColor','r','MarkerSize',8); hold on;
h2 = plot(x_array_CM(1,:),x_array_CM(2,:),'-ko','MarkerFaceColor','g','MarkerSize',8);hold on;
h3 = plot(x_array_NAG(1,:),x_array_NAG(2,:),'-kd','MarkerFaceColor','b','MarkerSize',8);hold on;
h_legend = legend([h1 h2 h3], 'GD','CM','NAG','Location','SouthWest');
set(h_legend,'FontSize',24);
saveas(gcf,'gd_cm_nag_my.png');

figure;
plot(obj_array_GD, '-b');hold on;
plot(obj_array_CM, '--g');hold on;
plot(obj_array_NAG, ':r');hold on;
legend('GD','CM','NAG');
end

function y = f(x,A,b) % y = x'*A*x + b'*x
y = x'*A*x + x'*b;
end

function y = g(x,A,b) % return gradient
y = 2*A*x + b;
end


function [x_array, obj_array] = gradient_descent(x0, A, b, eta,max_iter)

x = x0;
x_array = [];
x_array = [x_array;x];
obj0 = f(x, A, b);
obj_array = [];
obj_array=[obj_array; obj0];
for i = 1:max_iter
    gradient = g(x,A,b);
    x = x - eta*gradient;
    x_array = [x_array x];
    obj = f(x, A, b);
    obj_array=[obj_array; obj];
%     assert(obj < obj0);
    if obj0 - obj < obj * 1e-4;
       break; 
    end
end
end

function [x_array, obj_array] = momentum(x0, A, b, eta, mu,max_iter)
x = x0;
x_array = [];
x_array = [x_array;x];
obj0 = f(x, A, b);
obj_array = [];
obj_array=[obj_array; obj0];

v = zeros(size(x));
for i = 1:max_iter
    gradient = g(x,A,b);
    v = mu*v - eta*gradient;
    x = x + v;
    x_array = [x_array x];
    obj = f(x, A, b);
    obj_array=[obj_array; obj];
%     assert(obj < obj0);
    if obj0 - obj < obj * 1e-4;
       break; 
    end
end
end

function [x_array, obj_array] = nag(x0, A, b, eta, mu,max_iter)
x = x0;
x_array = [];
x_array = [x_array;x];
obj0 = f(x, A, b);
obj_array = [];
obj_array=[obj_array; obj0];

v = zeros(size(x));
for i = 1:max_iter
    gradient = g(x + mu*v,A,b);
    v = mu*v - eta*gradient;
    x = x + v;
    x_array = [x_array x];
    obj = f(x, A, b);
    obj_array=[obj_array; obj];
%     assert(obj < obj0);
    if obj0 - obj < obj * 1e-4;
       break; 
    end
end
end