clear; close all; clc;

%% Exercises 3-4

Q = [ 1 0 ; 0 2 ];
c = [ -3 ; -4 ];
A = [-2 1 ; 1 1 ; 0 -1 ];
b = [ 0 ; 4 ; 0 ];

x0 = [0;0];
tolerance = 1e-2;

%% method

fprintf('Frank-Wolfe method\n\n');
fprintf('iter \t x(1) \t\t x(2) \t\t y(1) \t\t y(2) \t\t gap \n\n');

iter = 0;
x = x0;
while true
    % solve the linearized problem
    g = Q*x + c ;
    y = linprog(g,A,b,[],[],[],[],[],optimset('Display','off'));
    d = y-x;
    
    % optimality gap
    gap = g'*d ;
    fprintf('%1.0f \t %1.6f \t %1.6f \t %1.6f \t %1.6f \t %1.6f\n',iter,x(1),x(2),y(1),y(2),gap);
    if gap > -tolerance
        break
    else    
        % step size
        t = min(1,(-g'*d)/(d'*Q*d)); % exact line search
%         t = 1/(iter+1); % predetermined step size
        
        % new point
        x = x + t*d ;
        iter = iter + 1 ;
    end
end
