function [w, infos] = hgd(problem, options)
% Inputs:
%       problem     function (cost/grad/hess)
%       options     options
% Output:
%       w           solution of w
%       infos       information
%
% This file is part of SGDLibrary.
 
% set dimensions and samples
d = problem.dim();
n = problem.samples();

% extract options
if ~isfield(options, 'step_init')
    step_init = 0.1;
else
    step_init = options.step_init;
end
step = step_init;


if ~isfield(options, 'tol_optgap')
    tol_optgap = 1.0e-12;
else
    tol_optgap = options.tol_optgap;
end


if ~isfield(options, 'max_epoch')
    max_epoch = 100;
else
    max_epoch = options.max_epoch;
end

if ~isfield(options, 'w_init')
    w = randn(d,1);
else
    w = options.w_init;
end

if ~isfield(options, 'f_opt')
    f_opt = -Inf;
else
    f_opt = options.f_opt;
end

if ~isfield(options, 'verbose')
    verbose = false;
else
    verbose = options.verbose;
end

if ~isfield(options, 'store_w')
    store_w = false;
else
    store_w = options.store_w;
end

k=options.k;

% initialize
epoch = 0;
f_opt=0;
% store first infos
clear infos;
infos.time = [0];
f_val = problem.cost(w);
optgap = f_val - f_opt;
infos.optgap = optgap;
 

% display infos
if verbose > 0
    fprintf('GD: Epoch = %03d, cost = %.16e, optgap = %.4e\n', epoch, f_val, optgap);
end

% main loop
 
while (optgap > tol_optgap) && (epoch < max_epoch)
    epoch=epoch+1;
    
    %% upate w
    grad =  problem.full_grad(w);
    w = w - step * grad;
    w = hardthreshold(w, k, d);
    
    %% store info
    infos.time=[infos.time n];
    f_val = problem.cost(w);
    optgap = f_val - f_opt;
    infos.optgap = [infos.optgap optgap];

    if store_w
        infos.w = [infos.w w];
    end

    if verbose > 0
        fprintf('GD: Epoch = %03d, cost = %.16e, optgap = %.4e\n', epoch, f_val, optgap);
    end
end
end
