Quasi-Newton methods - Revision history

Wc593 at 10:21, 21 December 2020

2020-12-21T10:21:57Z

← Older revision		Revision as of 06:21, 21 December 2020
Line 1:		Line 1:
	Author: Jianmin Su (ChemE 6800 Fall 2020)		Author: Jianmin Su (ChemE 6800 Fall 2020)

	~~Steward: Allen Yang, Fengqi You~~

	'''Quasi-Newton Methods''' are a kind of methods used to solve nonlinear optimization problems. They are based on Newton's method yet can be an alternative to Newton's method when the objective function is not twice-differentiable, which means the Hessian matrix is unavailable, or it is too expensive to calculate the Hessian matrix and its inverse.		'''Quasi-Newton Methods''' are a kind of methods used to solve nonlinear optimization problems. They are based on Newton's method yet can be an alternative to Newton's method when the objective function is not twice-differentiable, which means the Hessian matrix is unavailable, or it is too expensive to calculate the Hessian matrix and its inverse.

Jianminsu at 21:27, 13 December 2020

2020-12-13T21:27:40Z

← Older revision		Revision as of 17:27, 13 December 2020
Line 10:		Line 10:
	During the following years, numerous variants were proposed, include '''[https://en.wikipedia.org/wiki/Broyden%27s_method Broyden's method]''' (1965), the '''[https://en.wikipedia.org/wiki/Symmetric_rank-one SR1 formula]''' (Davidon 1959, Broyden 1967), the '''[https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula DFP method]''' (Davidon, 1959; Fletcher and Powell, 1963), and the '''[https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm BFGS method]''' (Broyden, 1969; Fletcher, 1970; Goldfarb, 1970; Shanno, 1970)<ref>Hennig, Philipp, and Martin Kiefel. "Quasi-Newton method: A new direction." Journal of Machine Learning Research 14.Mar (2013): 843-865.</ref>.		During the following years, numerous variants were proposed, include '''[https://en.wikipedia.org/wiki/Broyden%27s_method Broyden's method]''' (1965), the '''[https://en.wikipedia.org/wiki/Symmetric_rank-one SR1 formula]''' (Davidon 1959, Broyden 1967), the '''[https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula DFP method]''' (Davidon, 1959; Fletcher and Powell, 1963), and the '''[https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm BFGS method]''' (Broyden, 1969; Fletcher, 1970; Goldfarb, 1970; Shanno, 1970)<ref>Hennig, Philipp, and Martin Kiefel. "Quasi-Newton method: A new direction." Journal of Machine Learning Research 14.Mar (2013): 843-865.</ref>.

	In optimization problems, Newton's method uses first and second derivatives, gradient and the Hessian in multivariate scenarios, to find the optimal point, it is applied to a twice-differentiable function <math>f(x)</math> to find the roots of the first derivative (solutions to <math>f'(x)=0</math>), also known as the stationary points of <math>f(x)</math><ref>''Newton’s Method'', 8 ~~December 2020‎~~. Retrieved from: https://en.wikipedia.org/wiki/Quasi-Newton_method</ref>.		In optimization problems, Newton's method uses first and second derivatives, gradient and the Hessian in multivariate scenarios, to find the optimal point, it is applied to a twice-differentiable function <math>f(x)</math> to find the roots of the first derivative (solutions to <math>f'(x)=0</math>), also known as the stationary points of <math>f(x)</math><ref>''Newton’s Method'', 8.Dec (2020)‎. Retrieved from: https://en.wikipedia.org/wiki/Quasi-Newton_method</ref>.

	The iteration of Newton's method is usually written as: <math>x_{k+1}=x_k-H^{-1}\cdot\bigtriangledown f(x_k) </math>, where <math>k </math> is the iteration number, <math>H</math> is the Hessian matrix and <math>H=[\bigtriangledown ^2 f(x_k)]</math>		The iteration of Newton's method is usually written as: <math>x_{k+1}=x_k-H^{-1}\cdot\bigtriangledown f(x_k) </math>, where <math>k </math> is the iteration number, <math>H</math> is the Hessian matrix and <math>H=[\bigtriangledown ^2 f(x_k)]</math>
Line 93:		Line 93:
	=== DFP method ===		=== DFP method ===

	The DFP method, which is also known as the Davidon–Fletcher–Powell formula, is named after W.C. Davidon, Roger Fletcher, and Michael J.D. Powell. It was proposed by Davidon in 1959 first and then improved by Fletched and Powell. DFP method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the inverse of Hessian matrix and its algorithm is shown below<ref>''Davidon–Fletcher–Powell formula''. Retrieved from: https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula</ref>.		The DFP method, which is also known as the Davidon–Fletcher–Powell formula, is named after W.C. Davidon, Roger Fletcher, and Michael J.D. Powell. It was proposed by Davidon in 1959 first and then improved by Fletched and Powell. DFP method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the inverse of Hessian matrix and its algorithm is shown below<ref>''Davidon–Fletcher–Powell formula'', 7.June (2020). Retrieved from: https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula</ref>.

	==== DFP Algorithm ====		==== DFP Algorithm ====
Line 110:		Line 110:
	=== BFGS method ===		=== BFGS method ===

	BFGS method is named for its four discoverers Broyden, Fletcher, Goldfarb, and Shanno. It is considered the most effective quasi-Newton algorithm. Unlike the DFP method, the BFGS method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the Hessian matrix<ref>''Broyden–Fletcher–Goldfarb–Shanno algorithm''. Retrieved from: https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm</ref>.		BFGS method is named for its four discoverers Broyden, Fletcher, Goldfarb, and Shanno. It is considered the most effective quasi-Newton algorithm. Unlike the DFP method, the BFGS method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the Hessian matrix<ref>''Broyden–Fletcher–Goldfarb–Shanno algorithm'', 12.Dec (2020). Retrieved from: https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm</ref>.

	==== BFGS Algorithm ====		==== BFGS Algorithm ====

Jianminsu: /* Introduction */

2020-12-13T21:24:47Z

Introduction

← Older revision		Revision as of 17:24, 13 December 2020
Line 10:		Line 10:
	During the following years, numerous variants were proposed, include '''[https://en.wikipedia.org/wiki/Broyden%27s_method Broyden's method]''' (1965), the '''[https://en.wikipedia.org/wiki/Symmetric_rank-one SR1 formula]''' (Davidon 1959, Broyden 1967), the '''[https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula DFP method]''' (Davidon, 1959; Fletcher and Powell, 1963), and the '''[https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm BFGS method]''' (Broyden, 1969; Fletcher, 1970; Goldfarb, 1970; Shanno, 1970)<ref>Hennig, Philipp, and Martin Kiefel. "Quasi-Newton method: A new direction." Journal of Machine Learning Research 14.Mar (2013): 843-865.</ref>.		During the following years, numerous variants were proposed, include '''[https://en.wikipedia.org/wiki/Broyden%27s_method Broyden's method]''' (1965), the '''[https://en.wikipedia.org/wiki/Symmetric_rank-one SR1 formula]''' (Davidon 1959, Broyden 1967), the '''[https://en.wikipedia.org/wiki/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula DFP method]''' (Davidon, 1959; Fletcher and Powell, 1963), and the '''[https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm BFGS method]''' (Broyden, 1969; Fletcher, 1970; Goldfarb, 1970; Shanno, 1970)<ref>Hennig, Philipp, and Martin Kiefel. "Quasi-Newton method: A new direction." Journal of Machine Learning Research 14.Mar (2013): 843-865.</ref>.

	In optimization problems, Newton's method uses first and second derivatives, gradient and the Hessian in multivariate scenarios, to find the optimal point, it is applied to a twice-differentiable function <math>f</math> to find the roots of the first derivative (solutions to <math>f'(x)=0</math>), also known as the stationary points of <math>f</math><ref>''Newton’s Method''. Retrieved from: https://en.wikipedia.org/wiki/Quasi-Newton_method</ref>.		In optimization problems, Newton's method uses first and second derivatives, gradient and the Hessian in multivariate scenarios, to find the optimal point, it is applied to a twice-differentiable function <math>f(x)</math> to find the roots of the first derivative (solutions to <math>f'(x)=0</math>), also known as the stationary points of <math>f(x)</math><ref>''Newton’s Method'', 8 December 2020‎. Retrieved from: https://en.wikipedia.org/wiki/Quasi-Newton_method</ref>.

	The iteration of Newton's method is usually written as: <math>x_{k+1}=x_k-H^{-1}\cdot\bigtriangledown f(x_k) </math>, where <math>k </math> is the iteration number, <math>H</math> is the Hessian matrix and <math>H=[\bigtriangledown ^2 f(x_k)]</math>		The iteration of Newton's method is usually written as: <math>x_{k+1}=x_k-H^{-1}\cdot\bigtriangledown f(x_k) </math>, where <math>k </math> is the iteration number, <math>H</math> is the Hessian matrix and <math>H=[\bigtriangledown ^2 f(x_k)]</math>

Jianminsu: /* Application */

2020-12-13T21:18:16Z

Application

← Older revision		Revision as of 17:18, 13 December 2020
Line 231:		Line 231:
	== Application ==		== Application ==

	Quasi-newton methods are applied to various areas such as physics, biology, engineering, geophysics, chemistry, and industry to solve the nonlinear systems of equations because of their faster calculation. '''''The ICUM (Inverse Column-Updating Method)''''', one type of quasi-Newton methods, is not only efficient in solving large scale sparse nonlinear systems but also perfumes well in not necessarily large-scale systems in real applications. It is used to solve '''''the Two-pint ray tracing problem''''' in geophysics, to '''''estimate the transmission coefficients for AIDS and for Tuberculosis''''' in Biology, and in '''''Multiple target 3D location airborne ultrasonic system'''''. <ref>Pérez, Rosana, and Véra Lucia Rocha Lopes. "Recent applications and numerical implementation of quasi-Newton methods for solving nonlinear systems of equations." Numerical Algorithms 35.2-4 (2004): 261-285.</ref> Moreover, they can be applied and developed into the Deep Learning area as sampled quasi-Newton methods to help make use of more reliable information.<ref> Berahas, Albert S., Majid Jahani, and Martin Takáč. "Quasi-newton methods for deep learning: Forget the past, just sample." arXiv preprint arXiv:1901.09997 (2019). </ref>		Quasi-newton methods are applied to various areas such as physics, biology, engineering, geophysics, chemistry, and industry to solve the nonlinear systems of equations because of their faster calculation. '''''The ICUM (Inverse Column-Updating Method)''''', one type of quasi-Newton methods, is not only efficient in solving large scale sparse nonlinear systems but also perfumes well in not necessarily large-scale systems in real applications. It is used to solve '''''the Two-pint ray tracing problem''''' in geophysics. A two-point ray tracing problem consists of constructing a ray that joins two given points in the domain and it can be formulated as a nonlinear system. ICUM can also be applied to '''''estimate the transmission coefficients for AIDS and for Tuberculosis''''' in Biology, and in '''''Multiple target 3D location airborne ultrasonic system'''''. <ref>Pérez, Rosana, and Véra Lucia Rocha Lopes. "Recent applications and numerical implementation of quasi-Newton methods for solving nonlinear systems of equations." Numerical Algorithms 35.2-4 (2004): 261-285.</ref>

			Moreover, they can be applied and developed into the Deep Learning area as sampled quasi-Newton methods to help make use of more reliable information.<ref> Berahas, Albert S., Majid Jahani, and Martin Takáč. "Quasi-newton methods for deep learning: Forget the past, just sample." arXiv preprint arXiv:1901.09997 (2019). </ref> The methods they proposed sample points randomly around the current iterate at each iteration to create Hessian or inverse Hessian approximations, which is different from the classical variants of quasi-Newton methods. As a result, the approximations constructed make use of more reliable (recent and local) information and do not depend on past iterate information that could be significantly stale. In their work, numerical tests on a toy classification problem and on popular benchmarking neural network training tasks show that the methods outperform their classical variants.

	Besides, to make quasi-Newton methods more available, they are integrated into programming languages so that people can use them to solve nonlinear optimization problems conveniently, for example, [http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html Mathematic (quasi-Newton solvers)], [http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html MATLAB (Optimization Toolbox)], [http://finzi.psych.upenn.edu/R/library/stats/html/optim.html R], [http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html SciPy] extension to Python.		Besides, to make quasi-Newton methods more available, they are integrated into programming languages so that people can use them to solve nonlinear optimization problems conveniently, for example, [http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html Mathematic (quasi-Newton solvers)], [http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html MATLAB (Optimization Toolbox)], [http://finzi.psych.upenn.edu/R/library/stats/html/optim.html R], [http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html SciPy] extension to Python.

Jianminsu: /* Application */

2020-12-13T20:01:52Z

Application

← Older revision		Revision as of 16:01, 13 December 2020
Line 233:		Line 233:
	Quasi-newton methods are applied to various areas such as physics, biology, engineering, geophysics, chemistry, and industry to solve the nonlinear systems of equations because of their faster calculation. '''''The ICUM (Inverse Column-Updating Method)''''', one type of quasi-Newton methods, is not only efficient in solving large scale sparse nonlinear systems but also perfumes well in not necessarily large-scale systems in real applications. It is used to solve '''''the Two-pint ray tracing problem''''' in geophysics, to '''''estimate the transmission coefficients for AIDS and for Tuberculosis''''' in Biology, and in '''''Multiple target 3D location airborne ultrasonic system'''''. <ref>Pérez, Rosana, and Véra Lucia Rocha Lopes. "Recent applications and numerical implementation of quasi-Newton methods for solving nonlinear systems of equations." Numerical Algorithms 35.2-4 (2004): 261-285.</ref> Moreover, they can be applied and developed into the Deep Learning area as sampled quasi-Newton methods to help make use of more reliable information.<ref> Berahas, Albert S., Majid Jahani, and Martin Takáč. "Quasi-newton methods for deep learning: Forget the past, just sample." arXiv preprint arXiv:1901.09997 (2019). </ref>		Quasi-newton methods are applied to various areas such as physics, biology, engineering, geophysics, chemistry, and industry to solve the nonlinear systems of equations because of their faster calculation. '''''The ICUM (Inverse Column-Updating Method)''''', one type of quasi-Newton methods, is not only efficient in solving large scale sparse nonlinear systems but also perfumes well in not necessarily large-scale systems in real applications. It is used to solve '''''the Two-pint ray tracing problem''''' in geophysics, to '''''estimate the transmission coefficients for AIDS and for Tuberculosis''''' in Biology, and in '''''Multiple target 3D location airborne ultrasonic system'''''. <ref>Pérez, Rosana, and Véra Lucia Rocha Lopes. "Recent applications and numerical implementation of quasi-Newton methods for solving nonlinear systems of equations." Numerical Algorithms 35.2-4 (2004): 261-285.</ref> Moreover, they can be applied and developed into the Deep Learning area as sampled quasi-Newton methods to help make use of more reliable information.<ref> Berahas, Albert S., Majid Jahani, and Martin Takáč. "Quasi-newton methods for deep learning: Forget the past, just sample." arXiv preprint arXiv:1901.09997 (2019). </ref>

	Besides, to make quasi-Newton methods more available, they are integrated into programming languages so that people can use them to solve nonlinear optimization problems conveniently, for example, ~~Mathematic (quasi-Newton solvers)<ref>~~http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html~~</ref>, MATLAB~~ (~~Optimization Toolbox~~)~~<ref>~~http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html~~</ref>~~, ~~R<ref>~~[http://finzi.psych.upenn.edu/R/library/stats/html/optim.html]~~</ref>~~, ~~SciPy extension to Python<ref>~~http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html~~</ref>~~.		Besides, to make quasi-Newton methods more available, they are integrated into programming languages so that people can use them to solve nonlinear optimization problems conveniently, for example, [http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html Mathematic (quasi-Newton solvers)], [http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html MATLAB (Optimization Toolbox)], [http://finzi.psych.upenn.edu/R/library/stats/html/optim.html R], [http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html SciPy] extension to Python.

	== Conclusion ==		== Conclusion ==

Jianminsu: /* BFGS Algorithm */

2020-12-13T19:48:53Z

BFGS Algorithm

← Older revision		Revision as of 15:48, 13 December 2020
Line 116:		Line 116:
	# Given the starting point <math>x_0</math>; convergence tolerance <math>\epsilon, \epsilon>0</math>; the initial estimation of Hessian matrix <math>B_0=I</math>; <math>k=0</math>.		# Given the starting point <math>x_0</math>; convergence tolerance <math>\epsilon, \epsilon>0</math>; the initial estimation of Hessian matrix <math>B_0=I</math>; <math>k=0</math>.
	# Compute the search direction <math>d_k=-B_k^{-1}\cdot \bigtriangledown f_k</math>.		# Compute the search direction <math>d_k=-B_k^{-1}\cdot \bigtriangledown f_k</math>.
	# Compute the step length <math>\lambda_k</math> with a line search procedure that satisfies Wolfe conditions. And then set <br /> <math>s_k={\lambda}_k d_k</math>, <br /> <math>x_{k+1}=x_k+s_k</math>		# Compute the step length <math>\lambda_k</math> with a line search procedure that satisfies Wolfe conditions. And then set <br /> <math>s_k={\lambda}_k d_k</math>, <br /> <math>x_{k+1}=x_k+s_k</math>
	# If <math>\|\|\bigtriangledown f_{k+1}\|\|<\epsilon</math>, then end of the iteration, otherwise continue step5.		# If <math>\|\|\bigtriangledown f_{k+1}\|\|<\epsilon</math>, then end of the iteration, otherwise continue step5.
	# Computing <math>y_k=\bigtriangledown f_{k+1}-\bigtriangledown f_k</math>.		# Computing <math>y_k=\bigtriangledown f_{k+1}-\bigtriangledown f_k</math>.
	# ~~According~~ to (1~~.12)~~, (1.~~13) and (1.14)~~, update ~~the~~ <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>		# Update<math>B_{k+1}</math> with <math>B_{k+1}=B_k+\frac{y_k y_k^T}{y_k^T s_k}-\frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} </math> <br /> Since we need to update <math>B_{k+1}^{-1}</math>, we can apply the Sherman-Morrison formula to avoid complicated calculation of inverse. <br /> With Sherman-Morrison formula, we can update <math>B_{k+1}^{-1}</math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>
	# Update <math>k</math> with <math>k=k+1</math> and go back to step2.<br />		# Update <math>k</math> with <math>k=k+1</math> and go back to step2.<br />


	According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>

	~~We skip procedures of solving the minimization problem (1.10) and here is the unique solution of (1.10):~~

	~~<math> B_{k+1}=(I-\rho y_ks_k^T)B_k(I-\rho s_ky_k^T)+\rho y_ky_k^T</math> (1.12)~~

	~~where <math>\rho=\frac{1}{y_k^Ts_k}</math> (1.13)~~

	~~Finally, we get the updated <math>B_{k+1}</math>. However, according to (1.2) and (1.3), we also need the inverse of <math>B_{k+1}</math> in next iterate.~~

	~~To get the inverse of <math>B_{k+1}</math>, we can apply the Sherman-Morrison formula to avoid complicated calculation of inverse.~~

	~~Set <math>M_k=B_k^{-1} </math>, with Sherman-Morrison formula we can get:~~

	~~<math>M_{k+1}=M_k+\frac{s_k s_k^T}{s_k^T y_k}-\frac{M_k y_k y_k^T M_k}{y_k^T M_k y_k} </math> (1.14)~~

	== Numerical Example ==		== Numerical Example ==

Jianminsu at 19:31, 13 December 2020

2020-12-13T19:31:23Z

← Older revision		Revision as of 15:31, 13 December 2020
Line 124:		Line 124:

	According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>		According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>

			We skip procedures of solving the minimization problem (1.10) and here is the unique solution of (1.10):

			<math> B_{k+1}=(I-\rho y_ks_k^T)B_k(I-\rho s_ky_k^T)+\rho y_ky_k^T</math> (1.12)

			where <math>\rho=\frac{1}{y_k^Ts_k}</math> (1.13)

			Finally, we get the updated <math>B_{k+1}</math>. However, according to (1.2) and (1.3), we also need the inverse of <math>B_{k+1}</math> in next iterate.

			To get the inverse of <math>B_{k+1}</math>, we can apply the Sherman-Morrison formula to avoid complicated calculation of inverse.

			Set <math>M_k=B_k^{-1} </math>, with Sherman-Morrison formula we can get:

			<math>M_{k+1}=M_k+\frac{s_k s_k^T}{s_k^T y_k}-\frac{M_k y_k y_k^T M_k}{y_k^T M_k y_k} </math> (1.14)

	== Numerical Example ==		== Numerical Example ==

Jianminsu: /* BFGS method */

2020-12-13T19:29:13Z

BFGS method

← Older revision		Revision as of 15:29, 13 December 2020
Line 110:		Line 110:
	=== BFGS method ===		=== BFGS method ===

	BFGS method is named for its four discoverers Broyden, Fletcher, Goldfarb, and Shanno. It is considered as the most effective quasi-Newton algorithm. Unlike the DFP method, the BFGS method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the Hessian matrix<ref>''Broyden–Fletcher–Goldfarb–Shanno algorithm''. Retrieved from: https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm</ref>.		BFGS method is named for its four discoverers Broyden, Fletcher, Goldfarb, and Shanno. It is considered the most effective quasi-Newton algorithm. Unlike the DFP method, the BFGS method uses an <math>n\times n </math> symmetric positive definite matrix <math>B_k </math> to estimate the Hessian matrix<ref>''Broyden–Fletcher–Goldfarb–Shanno algorithm''. Retrieved from: https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm</ref>.

	==== BFGS Algorithm ====		==== BFGS Algorithm ====
Line 121:		Line 121:
	# According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>		# According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>
	# Update <math>k</math> with <math>k=k+1</math> and go back to step2.<br />		# Update <math>k</math> with <math>k=k+1</math> and go back to step2.<br />


			According to (1.12), (1.13) and (1.14), update the <math>B_{k+1}^{-1} </math> with <br /> <math> B_{k+1}^{-1}=(I-\rho s_ky_k^T)B_k^{-1}(I-\rho y_ks_k^T)+\rho s_ks_k^T</math> , <math>\rho=\frac{1}{y_k^Ts_k}</math>

	== Numerical Example ==		== Numerical Example ==

Jianminsu: /* Theory and Algorithm */

2020-12-12T17:08:16Z

Theory and Algorithm

← Older revision		Revision as of 13:08, 12 December 2020
Line 84:		Line 84:
	To get the inverse of <math>B_{k+1}</math>, we can apply the Sherman-Morrison formula to avoid complicated calculation of inverse.		To get the inverse of <math>B_{k+1}</math>, we can apply the Sherman-Morrison formula to avoid complicated calculation of inverse.

	Set <math>~~H_k~~=B_k^{-1} </math>, with Sherman-Morrison formula we can get:		Set <math>M_k=B_k^{-1} </math>, with Sherman-Morrison formula we can get:

	<math>H_{k+1}=~~H_k~~+\frac{s_k s_k^T}{s_k^T y_k}-\frac{~~H_k~~ y_k y_k^T ~~H_k~~}{y_k^T ~~H_k~~ y_k} </math> (1.14)		<math>M_{k+1}=M_k+\frac{s_k s_k^T}{s_k^T y_k}-\frac{M_k y_k y_k^T M_k}{y_k^T M_k y_k} </math> (1.14)

	With the derivation<ref>Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.</ref> above, we can now understand how do quasi-Newton methods get rid of calculating the Hessian matrix and its inverse. We can directly estimate the inverse of Hessian, and we can use (1.14) to update the approximation of the inverse of Hessian, which leads to the DFP method, or we can directly estimate the Hessian matrix, and this is the main idea in the BFGS method.		With the derivation<ref>Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.</ref> above, we can now understand how do quasi-Newton methods get rid of calculating the Hessian matrix and its inverse. We can directly estimate the inverse of Hessian, and we can use (1.14) to update the approximation of the inverse of Hessian, which leads to the DFP method, or we can directly estimate the Hessian matrix, and this is the main idea in the BFGS method.

Jianminsu: /* Theory and Algorithm */

2020-12-01T20:54:43Z

Theory and Algorithm

← Older revision		Revision as of 16:54, 1 December 2020
Line 88:		Line 88:
	<math>H_{k+1}=H_k+\frac{s_k s_k^T}{s_k^T y_k}-\frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k} </math> (1.14)		<math>H_{k+1}=H_k+\frac{s_k s_k^T}{s_k^T y_k}-\frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k} </math> (1.14)

	With the derivation<ref>Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.</ref> above, we can now understand how do quasi-Newton methods get rid of calculating the Hessian matrix and its inverse. We can directly estimate the inverse of Hessian and we can use (1.14) to update the approximation of the inverse of Hessian, which leads to the DFP method, or we can directly estimate the Hessian matrix and this is the main idea in the BFGS method.		With the derivation<ref>Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.</ref> above, we can now understand how do quasi-Newton methods get rid of calculating the Hessian matrix and its inverse. We can directly estimate the inverse of Hessian, and we can use (1.14) to update the approximation of the inverse of Hessian, which leads to the DFP method, or we can directly estimate the Hessian matrix, and this is the main idea in the BFGS method.