function [beta, norm_grad_f_beta, f_beta, norm_delta, nb_it, exitflag] ...
          = Algo_Newton(Hess_f, beta0, option)
%************************************************************
% Fichier  ~gergaud/ENS/Optim1a/TP-optim-20-21/Newton_ref.m *
% Novembre 2020                                             *
% Université de Toulouse, INP-ENSEEIHT                      *
%************************************************************
%
% Newton résout par l'algorithme de Newton les problemes aux moindres carres
% Min 0.5||r(beta)||^2
% beta \in R^p
%
% Parametres en entrees
% --------------------
% Hess_f_C14 : fonction qui code la hessiennne de f
%              Hess_f_C14 : R^p --> matrice (p,p)
%              (la fonction retourne aussi le residu et la jacobienne)
% beta0  : point de départ
%          real(p)
% option(1) : Tol_abs, tolérance absolue
%             real
% option(2) : Tol_rel, tolérance relative
%             real
% option(3) : nitimax, nombre d'itérations maximum
%             integer
%
% Parametres en sortie
% --------------------
% beta      : beta
%             real(p)
% norm_gradf_beta : ||gradient f(beta)||
%                   real
% f_beta    : f(beta)
%             real
% res       : r(beta)
%             real(n)
% norm_delta : ||delta||
%              real
% nbit       : nombre d'itérations
%              integer
% exitflag   : indicateur de sortie
%              integer entre 1 et 4
% exitflag = 1 : ||gradient f(beta)|| < max(Tol_rel||gradient f(beta0)||,Tol_abs)
% exitflag = 2 : |f(beta^{k+1})-f(beta^k)| < max(Tol_rel|f(beta^k)|,Tol_abs)
% exitflag = 3 : ||delta)|| < max(Tol_rel delta^k),Tol_abs)
% exitflag = 4 : nombre maximum d'itérations atteint
%      
% ---------------------------------------------------------------------------------

% TO DO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   
    [H_f0, res0, J_res0] = Hess_f(beta0);
    norm_grad_f_beta0 = norm(J_res0.'*res0);

    nb_it = 0;
    beta = beta0;
    
    continuer = 1;
    
    while continuer

        nb_it = nb_it + 1;

        beta_last = beta;
        [H_f_last, res_last, J_res_last] = Hess_f(beta_last);
        
        beta = beta - H_f_last\(J_res_last.'*res_last);
        [H_f, res, J_res] = Hess_f(beta);
        
        norm_grad_f_beta = norm(J_res.'*res);
        f_beta = norm(res)/2;
        delta = beta - beta_last;
        norm_delta = norm(delta);

        if norm_grad_f_beta <= max(option(2)*norm_grad_f_beta0, option(1))
            exitflag = 1;
            continuer = 0;
        elseif abs(norm(res)/2 - norm(res_last)/2) <= max(option(2)*norm(res)/2, option(1))
            exitflag = 2;
            continuer = 0;
        elseif norm_delta <= max(option(2)*norm(beta), option(1))
            exitflag = 3;
            continuer = 0;
        elseif nb_it >= option(3)
            exitflag = 4;
            continuer = 0;
        end
    
    end

end