Gradient descent - Revision history

Miguel Caro at 07:17, 31 August 2022

2022-08-31T07:17:33Z

Miguel Caro: /* Example input file */

2021-11-01T08:00:20Z

Example input file

Miguel Caro at 07:59, 1 November 2021

2021-11-01T07:59:19Z

Miguel Caro: /* Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borwein step optimization */

2021-11-01T07:57:08Z

Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borwein step optimization

Miguel Caro: /* Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization */

2021-11-01T07:56:27Z

Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization

Miguel Caro at 07:53, 1 November 2021

2021-11-01T07:53:51Z

Miguel Caro: /* Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization */

2021-10-31T17:41:20Z

Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization

Miguel Caro at 17:38, 31 October 2021

2021-10-31T17:38:09Z

Miguel Caro at 17:35, 31 October 2021

2021-10-31T17:35:34Z

Miguel Caro at 16:23, 31 October 2021

2021-10-31T16:23:53Z

@@ Line 39: / Line 39: @@
 Note: [[energy minimization]] is invoked with the <code>[[Documentation#turbogap md|turbogap md]]</code> command.
-  [[optimize]] = "gd" ! Do gradient descent minimization
+  [[optimize]] = "gd"    ! Do gradient descent minimization
-  [[e_tol]] = 1.e-6 ! Energy threshold for convergence
+  [[e_tol]] = 1.e-6      ! Energy threshold for convergence (per atom)
-  [[md_nsteps]] = 1000 ! Maximum number of iterations (it will break earlier if convergence to e_tol is reached)
+ [[f_tol]] = 0.01       ! Maximum force on any given atom for convergence
   [[max_opt_step]] = 0.1 ! Angstrom

@@ Line 37: / Line 37: @@
 === Example input file ===
-Note: [[energy minimization]] is invoked with the <code>[[Documentation#Turbogap md|turbogap md]]</code> command.
+Note: [[energy minimization]] is invoked with the <code>[[Documentation#turbogap md|turbogap md]]</code> command.
   [[optimize]] = "gd" ! Do gradient descent minimization

@@ Line 37: / Line 37: @@
 === Example input file ===
-Note: [[energy minimization]] is invoked with the <code>[[turbogap md]]</code> command.
+Note: [[energy minimization]] is invoked with the <code>[[Documentation#Turbogap md|turbogap md]]</code> command.
   [[optimize]] = "gd" ! Do gradient descent minimization

@@ Line 9: / Line 9: @@
 === Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borwein step optimization ===
-In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search. During the backtracking line search, we start by (over)estimating the position update according to the user provided [[max_opt_step]] (default 0.1 Angstrom), <math>\delta x_\text{ṃax}</math>:
+In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search. During the backtracking line search, we start by (over)estimating the position update according to the user provided [[max_opt_step]] (default 0.1 Angstrom), <math>\delta x_\text{max}</math>:
 <math>
-\gamma_0 = \frac{\delta x_\text{ṃax}}{F_\text{max}},
+\gamma_0 = \frac{\delta x_\text{max}}{F_\text{max}},
 </math>

@@ Line 7: / Line 7: @@
 until we reach the criterion for convergence (set with the <code>[[e_tol]]</code> keyword), <math>|E_{n+1} - E_n| < E_\text{tol}</math>. The <math>\gamma</math> parameter determines by how much we update the atomic positions along the search direction, and is allowed to change between iterations. The procedure is detailed below.
-=== Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization ===
+=== Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borwein step optimization ===
 In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search. During the backtracking line search, we start by (over)estimating the position update according to the user provided [[max_opt_step]] (default 0.1 Angstrom), <math>\delta x_\text{ṃax}</math>:

← Older revision		Revision as of 07:53, 1 November 2021
Line 34:		Line 34:
	\gamma_{n+1} = \frac{\|(\textbf{x}_{n+1} - \textbf{x}_n) \cdot (\textbf{F}_{n+1} - \textbf{F}_n)\|}{(\textbf{F}_{n+1} - \textbf{F}_n)^2}.		\gamma_{n+1} = \frac{\|(\textbf{x}_{n+1} - \textbf{x}_n) \cdot (\textbf{F}_{n+1} - \textbf{F}_n)\|}{(\textbf{F}_{n+1} - \textbf{F}_n)^2}.
	</math>		</math>
		+
		+	=== Example input file ===
		+
		+	Note: [[energy minimization]] is invoked with the <code>[[turbogap md]]</code> command.
		+
		+	[[optimize]] = "gd" ! Do gradient descent minimization
		+	[[e_tol]] = 1.e-6 ! Energy threshold for convergence
		+	[[md_nsteps]] = 1000 ! Maximum number of iterations (it will break earlier if convergence to e_tol is reached)
		+	[[max_opt_step]] = 0.1 ! Angstrom

@@ Line 5: / Line 5: @@
 </math>
-until we reach the criterion for convergence (set with the <code>[[e_tol]]</code> keyword), <math>|E_{n+1} - E_n| < E_\text{tol}</math>. The <math>\gamma</math> parameter determines by how much we update the atomic positions along the search direction, and is allowed to change between iterations. In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search.
+until we reach the criterion for convergence (set with the <code>[[e_tol]]</code> keyword), <math>|E_{n+1} - E_n| < E_\text{tol}</math>. The <math>\gamma</math> parameter determines by how much we update the atomic positions along the search direction, and is allowed to change between iterations. The procedure is detailed below.
-During the backtracking line search, we start by (over)estimating the position update according to the user provided [[max_opt_step]] (default 0.1 <math>\AA</math>), <math>\delta x_\text{ṃax}</math>:
+== Gradient descent with Armijo-Goldstein backtracking line search and Barzilai-Borweing step optimization ==
 <math>

← Older revision		Revision as of 17:35, 31 October 2021
Line 7:		Line 7:
	until we reach the criterion for convergence (set with the <code>[[e_tol]]</code> keyword), <math>\|E_{n+1} - E_n\| < E_\text{tol}</math>. The <math>\gamma</math> parameter determines by how much we update the atomic positions along the search direction, and is allowed to change between iterations. In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search.		until we reach the criterion for convergence (set with the <code>[[e_tol]]</code> keyword), <math>\|E_{n+1} - E_n\| < E_\text{tol}</math>. The <math>\gamma</math> parameter determines by how much we update the atomic positions along the search direction, and is allowed to change between iterations. In '''TurboGAP''', the initial <math>\gamma</math> is chosen by specifying the maximum allowed atomic displacement in the first optimization step, [[max_opt_step]], followed by an automated backtracking line search.

−	'''~~Under construction~~'''	+	During the backtracking line search, we start by (over)estimating the position update according to the user provided [[max_opt_step]] (default 0.1 <math>\AA</math>), <math>\delta x_\text{ṃax}</math>:
		+
		+	<math>
		+	\gamma_0 = \frac{\delta x_\text{ṃax}}{F_\text{max}},
		+	</math>
		+
		+	where <math>F_\text{max}</math> is the maximum force acting on any given atom in the system. Then, we enforce the Armijo-Goldstein condition for accepting this step size:
		+
		+	<math>
		+	E_{n+1} \le E_n - \gamma_n c \textbf{F} \cdot \textbf{F},
		+	</math>
		+
		+	where <math>c \in (0,1)</math> (hardcoded in '''TurboGAP''' to <math>c = 0.5</math>). If the condition is not met, then we reduce <math>\gamma</math> at each time step:
		+
		+	<math>
		+	\gamma_{n+1} = \tau \gamma_n,
		+	</math>
		+
		+	with <math>\tau \in (0,1)</math> (hardcoded in '''TurboGAP''' to <math>\tau = 0.5</math>), until the Armijo-Goldstein condition is met ("''backtracking''").
		+
		+	When this line search is over, we switch to using the Barzilai–Borwein method for finding <math>\gamma</math>:
		+
		+	<math>
		+	\gamma = \frac{\|(\textbf{x}_{n+1} - \textbf{x}_n) \cdot (\textbf{F}_{n+1} - \textbf{F}_n)\|}{(\textbf{F}_{n+1} - \textbf{F}_n)^2}.
		+	</math>.