# Newton's method for minimisation returns a critical point

3 vues (au cours des 30 derniers jours)
Dussan Radonich le 10 Nov 2020
Modifié(e) : Bruno Luong le 11 Nov 2020
I am trying to implement the newton's method to find the minima in the Himmelblau function.
The code does work most of the time, but on cases like this where my initial guess is (0.5 , 1) it returns a critical point of the function. I understand this is because the gradient becomes 0 and no new points are generated.
Now my question would be, is this normal with this method? Is there a way of getting around this problem?
Thanks for any help
close all; clear; clc
% Initialisation of variables to use
x0 = [0.5;1];
tol = 1e-4;
maxits = 50;
% Himmelblau function
him = @(x,y) (x.^2 + y - 11).^2 + (x + y.^2 - 7).^2;
grad_him = @(x,y) [[4*x.^3 + 4*x.*y - 42*x + 2*y.^2 - 14];[4*y.^3 + 4*x.*y - 26*y + 2*x.^2 - 22]];
% Hessian matrix of the Himmelblau
hessian_him = @(x,y) [[ 12*x.^2 + 4*y - 42 , 4*x + 4*y ];[ 4*x + 4*y , 12*y.^2 + 4*x - 26 ]];
% Call to newton's function and displaying our results accordingly
fprintf ("<strong>Newton's method</strong>\n\n");
switch (flag)
case 0
fprintf ("There was a convergence on f\n\n");
fprintf("The minima found is: \n");
disp(r);
fprintf("It took %d iterations.\n\n",iters);
case 1
fprintf ("There was a convergence on x\n\n");
fprintf("The minima found is: \n");
disp(r);
fprintf("It took %d iterations.\n\n",iters);
otherwise
fprintf ("There was no convergence\n\n");
end
function [r, iters, flag] = newton_min(dg,ddg,x0,tol,maxits)
x = x0(1); y = x0(2);
r = NaN;
flag = -1;
for iters = 1 : maxits
x_old = [x;y];
x_new = x_old - (ddg(x,y)\dg(x,y));
if norm(dg(x,y)) < tol
flag = 0;
r = x_new;
return;
end
if norm(x_new - x_old) <= (tol + eps*norm(x_new))
flag = 1;
r = x_new;
return;
end
x = x_new(1);
y = x_new(2);
end
end
##### 0 commentairesAfficher -2 commentaires plus anciensMasquer -2 commentaires plus anciens

Connectez-vous pour commenter.

### Réponse acceptée

Matt J le 10 Nov 2020
Yes, it's normal.
##### 30 commentairesAfficher 28 commentaires plus anciensMasquer 28 commentaires plus anciens
Matt J le 11 Nov 2020
But that is not the point where the gradient would be zero, it is the critical point (-0.1280, -1.9537).
Yes, but as long as the algorithm goes downhill from (0.5,1) at every iteration, it can never approach the inflection point (-0.1280, -1.9537). The inflection point lies uphill from your initial point:
>> him(0.5,1)
ans =
125.3125
>> him(-0.1280, -1.9537)
ans =
178.3372
Dussan Radonich le 11 Nov 2020
Great guys, I got it! Thank you so much

Connectez-vous pour commenter.

### Plus de réponses (2)

J. Alex Lee le 10 Nov 2020
Yes this looks normal, you are only asking to zero the gradient of the function, so naturally that includes non-optimal points where the gradient is [vector] zero.
You can use a non-gradient minimizer, like fminsearch to seek local minima
##### 1 commentaireAfficher -1 commentaires plus anciensMasquer -1 commentaires plus anciens
Dussan Radonich le 10 Nov 2020
Thank you, the idea is not to used fminsearch as I am trying to compare newton's method against fminsesarch

Connectez-vous pour commenter.

Bruno Luong le 10 Nov 2020
Modifié(e) : Bruno Luong le 10 Nov 2020
"Now my question would be, is this normal with this method?"
Your code juts shows it: yes it is normal.
Now in practice it is very rare that one falls on a stationary point that is not a local minimum. As soon as you work with a non-academic objective function. You won't ever get the gradient == 0 exactly.
"Is there a way of getting around this problem?"
All the book I read about optmization, no one care about this specific problem,since as I said it only happens in academic example. However, many methods will compute for each iteration an approximation of the Hessian, and the positiveness of the Hessian is either enforced or monitored. The Hessian that has negative eigenvalues like yours at (0.5,1) will has automatically a special treatment to escape from non-mimum.
##### 1 commentaireAfficher -1 commentaires plus anciensMasquer -1 commentaires plus anciens
Dussan Radonich le 10 Nov 2020
Thank you, good to know

Connectez-vous pour commenter.

### Catégories

En savoir plus sur Assumptions dans Help Center et File Exchange

R2020b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by