92 lines
2.9 KiB
Matlab
Executable file
92 lines
2.9 KiB
Matlab
Executable file
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
|