Talk:Quasi-Newton method
![]() | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
An image
editAre there any nice images describing this method? I think that would be really helpful. I eel like I've seen images in text books that made this easy to understand. Chogg (talk) 00:18, 19 August 2017 (UTC)
Relation to Gauss-Newton / Gradient Descent / Levenberg-Marquardt methods
editThis topic is somehow related to Gauss-Newton method and Levenberg-Marquardt Method and Gradient descent. None of these requires second derivatives. Gauss-Newton, however, requires an overdetermined system.
The exact relations are not stated in this article. It would be helpful to show different assumptions or what the algorithms do have in common with quasi-Newton-methods.
Matlab Code
editThe Matlab code presented here is incomplete and unsourced. It calls subroutines Grad() and LineSearchAlfa() that are not defined. Also, there is no indication of the author or source of the code, or of the copyright status of the code. Unless this information can be determined, it should probably be deleted. J Shailer (talk) 19:22, 5 March 2012 (UTC)
- I agree completely with Shailer. Regardless of the quality of the code, this is not the right venue (the right venue is http://www.mathworks.com/matlabcentral/fileexchange/). I propose a compromise step of moving the code to the talk page for now. Lavaka (talk) 13:29, 7 March 2012 (UTC)
- I am posting that code here: Lavaka (talk) 13:34, 7 March 2012 (UTC)
Here is a Matlab example which uses the BFGS method.
%***********************************************************************%
% Usage: [x,Iter,FunEval,EF] = Quasi_Newton (fun,x0,MaxIter,epsg,epsx)
% fun: name of the multidimensional scalar objective function
% (string). This function takes a vector argument of length
% n and returns a scalar.
% x0: starting point (row vector of length n).
% MaxIter: maximum number of iterations to find a solution.
% epsg: maximum acceptable Euclidean norm of the gradient of the
% objective function at the solution found.
% epsx: minimum relative change in the optimization variables x.
% x: solution found (row vector of length n).
% Iter: number of iterations needed to find the solution.
% FunEval: number of function evaluations needed.
% EF: exit flag,
% EF=1: successful optimization (gradient is small enough).
% EF=2: algorithm converged (relative change in x is small
% enough).
% EF=-1: maximum number of iterations exceeded.
% C) Quasi-Newton optimization algorithm using (BFGS) %
function [x,i,FunEval,EF]= Quasi_Newton (fun, x0, MaxIter, epsg, epsx)
% Variable Declaration
xi = zeros(MaxIter+1,size(x0,2));
xi(1,:) = x0;
Bi = eye(size(x0,2));
% CG algorithm
FunEval = 0;
EF = 0;
for i = 1:MaxIter
%Calculate Gradient around current point
[GradOfU,Eval] = Grad (fun, xi(i,:));
FunEval = FunEval + Eval; %Update function evaluation
%Calculate search direction
di = -Bi\GradOfU ;
%Calculate Alfa via exact line search
[alfa, Eval] = LineSearchAlfa(fun,xi(i,:),di);
FunEval = FunEval + Eval; %Update function evaluation
%Calculate Next solution of X
xi(i+1,:) = xi(i,:) + (alfa*di)';
% Calculate Gradient of X on i+1
[Grad_Next, Eval] = Grad (fun, xi(i+1,:));
FunEval = FunEval + Eval; %Update function evaluation
%Calculate new Beta value using BFGS algorithm
Bi = BFGS(fun,GradOfU,Grad_Next,xi(i+1,:),xi(i,:), Bi);
% Calculate maximum acceptable Euclidean norm of the gradient
if norm(Grad_Next,2) < epsg
EF = 1;
break
end
% Calculate minimum relative change in the optimization variables
E = xi(i+1,:)- xi(i,:);
if norm(E,2) < epsx
EF = 2;
break
end
end
% report optimum solution
x = xi(i+1,:);
if i == MaxIter
% report Exit flag that MaxNum of iterations reach
EF = -1;
end
% report MaxNum of iterations reach
Iter = i;
end
%***********************************************************************%
% Broyden, Fletcher, Goldfarb and Shanno (BFGS) formula
%***********************************************************************%
function B = BFGS(fun,GradOfU,Grad_Next,Xi_next,Xi,Bi)
% Calculate Si term
si = Xi_next - Xi;
% Calculate Yi term
yi = Grad_Next - GradOfU;
%
% BFGS formula (Broyden, Fletcher, Goldfarb and Shanno)
%
B = Bi - ((Bi*si'*si*Bi)/(si*Bi*si')) + ((yi*yi')/(yi'*si'));
end
External links modified
editHello fellow Wikipedians,
I have just modified one external link on Quasi-Newton method. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
- Added archive http://web.archive.org/web/20141217013529/http://www.cs.berkeley.edu/~jduchi/papers/Davidon91.pdf to http://www.cs.berkeley.edu/~jduchi/papers/Davidon91.pdf
When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}
).
This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}}
(last update: 5 June 2024).
- If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
- If you found an error with any archives or the URLs themselves, you can fix them with this tool.
Cheers.—InternetArchiveBot (Report bug) 18:11, 20 July 2016 (UTC)
differences in notation w.r.t. the page Newton's method in optimization
editI remarked differences in notation, especially in derivatives, when compared with the page : Newton's method in optimization. Could this be corrected ? I propose to use the notations f'(...) and f"(...) for derivatives of a multivariate function f, as in the page : Newton's method in optimization, as they seem more comprehensible. Pierre g111 (talk) 06:00, 27 July 2023 (UTC)