Line search methods - Revision history

Yuhui Gu: /* Inexact Search */

2021-12-16T10:35:14Z

Inexact Search

← Older revision		Revision as of 06:35, 16 December 2021
Line 119:		Line 119:
	===Wolfe Conditions===		===Wolfe Conditions===
	This condition is proposed by Phillip Wolfe in 1969. <ref>P. Wolfe, "[https://epubs.siam.org/doi/abs/10.1137/1011036 Convergence Conditions for Ascent Methods]," ''SIAM Review'', vol. 11, no. 2, pp. 226–235, 1969.</ref> It provide an efficient way of choosing a step length that decreases the objective function sufficiently. It consists of two conditions: Armijo (sufficient decrease) condition and the curvature condition.		This condition is proposed by Phillip Wolfe in 1969. <ref>P. Wolfe, "[https://epubs.siam.org/doi/abs/10.1137/1011036 Convergence Conditions for Ascent Methods]," ''SIAM Review'', vol. 11, no. 2, pp. 226–235, 1969.</ref> It provide an efficient way of choosing a step length that decreases the objective function sufficiently. It consists of two conditions: Armijo (sufficient decrease) condition and the curvature condition.
	[[File:Armijo.png\|thumb\|upright=1.1\|'''Figure 2.''' Armijo Condition. <ref name="nocedal" />]]		[[File:Armijo.png\|thumb\|upright=1\|'''Figure 2.''' Armijo Condition. <ref name="nocedal" />]]

	====Armijo (Sufficient Decrease) Condition====		====Armijo (Sufficient Decrease) Condition====
Line 128:		Line 128:

	====Curvature Condition====		====Curvature Condition====
	[[File:Curvature condition.png\|thumb\|upright=1.1\|'''Figure 3.''' Curvature Condition. <ref name="nocedal" />]]		[[File:Curvature condition.png\|thumb\|upright=1\|'''Figure 3.''' Curvature Condition. <ref name="nocedal" />]]

	<math>\nabla{f(x_k + \alpha p_k)}^\top p_k \geq c_2 \nabla{f(x_k)}^\top p_k</math>,		<math>\nabla{f(x_k + \alpha p_k)}^\top p_k \geq c_2 \nabla{f(x_k)}^\top p_k</math>,
Line 143:		Line 143:

	The strong Wolfe curvature condition restricts the slope of <math>\phi(\alpha)</math> from getting too positive, hence excluding points far away from the stationary point of <math>\phi</math>.		The strong Wolfe curvature condition restricts the slope of <math>\phi(\alpha)</math> from getting too positive, hence excluding points far away from the stationary point of <math>\phi</math>.
	[[File:Goldstein.png\|thumb\|upright=1.1\|'''Figure 4.''' Goldstein Conditions. <ref name="nocedal" />]]		[[File:Goldstein.png\|thumb\|upright=1\|'''Figure 4.''' Goldstein Conditions. <ref name="nocedal" />]]

	===Goldstein Conditions===		===Goldstein Conditions===

Zhengyisui: /* Steepest Descent Method */

2021-12-16T04:41:47Z

Steepest Descent Method

← Older revision		Revision as of 00:41, 16 December 2021
Line 93:		Line 93:
	'''Return''' <math>x_{k}</math>, <math>f(x_{k})</math></blockquote>		'''Return''' <math>x_{k}</math>, <math>f(x_{k})</math></blockquote>

	[[File:Rosenbrock.png\|thumb\|upright=0.9\|'''Figure 1.''' Steepest descent does not produce convergence on the Rosenbrock function. <ref name="hauser" />]]		[[File:Rosenbrock.png\|thumb\|upright=0.8\|'''Figure 1.''' Steepest descent does not produce convergence on the Rosenbrock function. <ref name="hauser" />]]

	One advantage of the steepest descent method is the convergency. For a steepest descent method, it converges to a local minimum from any starting point. <ref name="hauser">R. Hauser, "[https://people.maths.ox.ac.uk/hauser/hauser_lecture2.pdf Line Search Methods for Unconstrained Optimization]," Oxford University Computing Laboratory, 2007. </ref>		One advantage of the steepest descent method is the convergency. For a steepest descent method, it converges to a local minimum from any starting point. <ref name="hauser">R. Hauser, "[https://people.maths.ox.ac.uk/hauser/hauser_lecture2.pdf Line Search Methods for Unconstrained Optimization]," Oxford University Computing Laboratory, 2007. </ref>

Zhengyisui: /* Steepest Descent Method */

2021-12-16T04:41:10Z

Steepest Descent Method

← Older revision		Revision as of 00:41, 16 December 2021
Line 93:		Line 93:
	'''Return''' <math>x_{k}</math>, <math>f(x_{k})</math></blockquote>		'''Return''' <math>x_{k}</math>, <math>f(x_{k})</math></blockquote>

	[[File:Rosenbrock.png\|thumb\|upright=1.2\|'''Figure 1.''' Steepest descent does not produce convergence on the Rosenbrock function. <ref name="hauser" />]]		[[File:Rosenbrock.png\|thumb\|upright=0.9\|'''Figure 1.''' Steepest descent does not produce convergence on the Rosenbrock function. <ref name="hauser" />]]

	One advantage of the steepest descent method is the convergency. For a steepest descent method, it converges to a local minimum from any starting point. <ref name="hauser">R. Hauser, "[https://people.maths.ox.ac.uk/hauser/hauser_lecture2.pdf Line Search Methods for Unconstrained Optimization]," Oxford University Computing Laboratory, 2007. </ref>		One advantage of the steepest descent method is the convergency. For a steepest descent method, it converges to a local minimum from any starting point. <ref name="hauser">R. Hauser, "[https://people.maths.ox.ac.uk/hauser/hauser_lecture2.pdf Line Search Methods for Unconstrained Optimization]," Oxford University Computing Laboratory, 2007. </ref>

Yuhui Gu: /* Numeric Example */

2021-12-15T20:27:26Z

Numeric Example

← Older revision		Revision as of 16:27, 15 December 2021
Line 232:		Line 232:
	<math>\|\| \nabla f(x_5)\|\|=\sqrt{(-0.04)^2+(-0.04)^2}=0.0565 </math>.		<math>\|\| \nabla f(x_5)\|\|=\sqrt{(-0.04)^2+(-0.04)^2}=0.0565 </math>.

	Since 0.0565 is relatively small and is close enough to zero, the line search is complete.		Since <math>0.0565</math> is relatively small and is close enough to zero, the line search is complete.

	The derived optimal solution is <math>x^*=\begin{bmatrix}-1\\1.48\end{bmatrix}</math>, and the optimal objective value is found to be <math>-1.25</math>.		The derived optimal solution is <math>x^*=\begin{bmatrix}-1\\1.48\end{bmatrix}</math>, and the optimal objective value is found to be <math>-1.25</math>.

Yuhui Gu: /* Numeric Example */

2021-12-15T20:26:59Z

Numeric Example

← Older revision		Revision as of 16:26, 15 December 2021
Line 234:		Line 234:
	Since 0.0565 is relatively small and is close enough to zero, the line search is complete.		Since 0.0565 is relatively small and is close enough to zero, the line search is complete.

	The derived optimal solution is <math>x^*=\begin{bmatrix}-1\\1.48\end{bmatrix}</math>, and the optimal objective value is found to be -1.25.		The derived optimal solution is <math>x^*=\begin{bmatrix}-1\\1.48\end{bmatrix}</math>, and the optimal objective value is found to be <math>-1.25</math>.

	==Applications==		==Applications==

Yuhui Gu: /* Curvature Condition */

2021-12-15T20:26:30Z

Curvature Condition

← Older revision		Revision as of 16:26, 15 December 2021
Line 132:		Line 132:
	<math>\nabla{f(x_k + \alpha p_k)}^\top p_k \geq c_2 \nabla{f(x_k)}^\top p_k</math>,		<math>\nabla{f(x_k + \alpha p_k)}^\top p_k \geq c_2 \nabla{f(x_k)}^\top p_k</math>,

	where <math>c_2\in(c_1,1)</math> is much greater than <math>c_1</math> and is typically on the order of 0.1. This condition ensures a sufficient increase of the gradient.		where <math>c_2\in(c_1,1)</math> is much greater than <math>c_1</math> and is typically on the order of <math>0.1</math>. This condition ensures a sufficient increase of the gradient.

	This left hand side of the curvature condition is simply the derivative of <math>\phi(\alpha)</math>, thus ensuring <math>\alpha_k</math> to be in the vicinity of a stationary point of <math>\phi(\alpha)</math>.		This left hand side of the curvature condition is simply the derivative of <math>\phi(\alpha)</math>, thus ensuring <math>\alpha_k</math> to be in the vicinity of a stationary point of <math>\phi(\alpha)</math>.

Yuhui Gu: /* Goldstein Conditions */

2021-12-15T20:25:49Z

Goldstein Conditions

← Older revision		Revision as of 16:25, 15 December 2021
Line 151:		Line 151:

	where <math>0 \leq c \leq 1/2</math>. The Goldstein condition is quite similar with the Wolfe condition in that, its second inequality ensures that the step length <math>\alpha</math> will decrease the objective function sufficiently and its first inequality keep <math>\alpha</math> from being too short. In comparison with Wolfe condition, one disadvantage of Goldstein condition is that the first inequality of the condition might exclude all minimizers of <math>\phi</math> function. However, usually it is not a fatal problem as long as the objective decreases in the direction of convergence. As a short conclusion, the Goldstein and Wolfe		where <math>0 \leq c \leq 1/2</math>. The Goldstein condition is quite similar with the Wolfe condition in that, its second inequality ensures that the step length <math>\alpha</math> will decrease the objective function sufficiently and its first inequality keep <math>\alpha</math> from being too short. In comparison with Wolfe condition, one disadvantage of Goldstein condition is that the first inequality of the condition might exclude all minimizers of <math>\phi</math> function. However, usually it is not a fatal problem as long as the objective decreases in the direction of convergence. As a short conclusion, the Goldstein and Wolfe
	conditions have quite similar convergence theories. Compared to the Wolfe conditions, the Goldstein conditions are often used in Newton-type methods but are not well suited for quasi-Newton methods that maintain a positive definite Hessian approximation.		conditions have quite similar convergence theories. Compared to the Wolfe conditions, the Goldstein conditions are often used in Newton-type methods but are not well-suited for quasi-Newton methods that maintain a positive definite Hessian approximation.

	===Backtracking Line Search===		===Backtracking Line Search===

Yuhui Gu: /* Numeric Example */

2021-12-15T20:17:45Z

Numeric Example

← Older revision		Revision as of 16:17, 15 December 2021
Line 176:		Line 176:
	Starting from <math>x_0=\begin{bmatrix} 0\\0 \end{bmatrix}</math> gives <math>-\nabla f(x_0)=\begin{bmatrix}-1\\1\end{bmatrix}</math>.		Starting from <math>x_0=\begin{bmatrix} 0\\0 \end{bmatrix}</math> gives <math>-\nabla f(x_0)=\begin{bmatrix}-1\\1\end{bmatrix}</math>.

	We then have <math>f~~\left~~(x_0-\alpha\nabla f(x_0))~~\right~~=f(-\alpha,\alpha)=\alpha^2-2\alpha</math>.		We then have <math>f(x_0-\alpha\nabla f(x_0))=f(-\alpha,\alpha)=\alpha^2-2\alpha</math>.

	Taking partial derivative of the above equation with respect to <math>\alpha</math> and set it to zero to find the minimizer		Taking partial derivative of the above equation with respect to <math>\alpha</math> and set it to zero to find the minimizer

Yuhui Gu: /* Numeric Example */

2021-12-15T20:17:30Z

Numeric Example

← Older revision		Revision as of 16:17, 15 December 2021
Line 176:		Line 176:
	Starting from <math>x_0=\begin{bmatrix} 0\\0 \end{bmatrix}</math> gives <math>-\nabla f(x_0)=\begin{bmatrix}-1\\1\end{bmatrix}</math>.		Starting from <math>x_0=\begin{bmatrix} 0\\0 \end{bmatrix}</math> gives <math>-\nabla f(x_0)=\begin{bmatrix}-1\\1\end{bmatrix}</math>.

	We then have <math>f(x_0-\alpha\nabla f(x_0))=f(-\alpha,\alpha)=\alpha^2-2\alpha</math>.		We then have <math>f\left(x_0-\alpha\nabla f(x_0))\right=f(-\alpha,\alpha)=\alpha^2-2\alpha</math>.

	Taking partial derivative of the above equation with respect to <math>\alpha</math> and set it to zero to find the minimizer		Taking partial derivative of the above equation with respect to <math>\alpha</math> and set it to zero to find the minimizer

Yuhui Gu: /* Strong Wolfe Curvature Condition */

2021-12-15T20:16:47Z

Strong Wolfe Curvature Condition

← Older revision		Revision as of 16:16, 15 December 2021
Line 138:		Line 138:
	====Strong Wolfe Curvature Condition====		====Strong Wolfe Curvature Condition====

	The (weak) Wolfe conditions can result in an <math>\alpha</math> value that is not close to the minimizer of <math>\phi(\alpha)</math>. The (weak) Wolfe conditions can be modified by using the following condition called Strong Wolfe condition, which writes the curvature condition in absolute values		The (weak) Wolfe conditions can result in an <math>\alpha</math> value that is not close to the minimizer of <math>\phi(\alpha)</math>. The (weak) Wolfe conditions can be modified by using the following condition called Strong Wolfe condition, which writes the curvature condition in absolute values:

	<math>\|p_k \nabla{f(x_k + \alpha p_k)\| \leq c_2 \|p^\top_k f(x_k)}\|</math>.		<math>\|p_k \nabla{f(x_k + \alpha p_k)\| \leq c_2 \|p^\top_k f(x_k)}\|</math>.