Wolfe conditions


Wolfe conditions

In (unconstrained) optimization, the Wolfe conditions are a set of inequalities for performing inexact linesearch, especially in quasi-Newton methods. Inexact line searches provide an efficient way of computing an acceptable step length alpha that reduces the cost 'sufficiently', rather than minimizing the cost over alphainmathbb R exactly.

Let f:mathbb R^n omathbb R be a smooth objective function, and mathbf{p}_k be a given search direction. A step length alpha_k is said to satisfy the "Wolfe conditions" if the following two inequalities hold.

:i) f(mathbf{x}_k+alpha_kmathbf{p}_k)leq f(mathbf{x}_k)+c_1alpha_kmathbf{p}_k^{mathrm T} abla f(mathbf{x}_k),:ii) mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k+alpha_kmathbf{p}_k)geq c_2mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k),

with 0. Inequality i) is known as the Armijo rule and ii) as the curvature condition; i) ensures that alpha_k decreases f 'sufficiently', and ii) ensures that the slope of the function phi(alpha)=f(mathbf{x}_k+alphamathbf{p}_k) at alpha_k is greater than c_2 times that at alpha = 0.

The Wolfe conditions, however, can result in a value for the step length that is not close to a minimizer of phi. If we modify the curvature condition to the following,

:iia) ig|mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k+alpha_kmathbf{p}_k)ig|leq c_2ig|mathbf{p}_k^{mathrm T} abla f(mathbf{x}_k)ig|

then i) and iia) together form the so-called strong Wolfe conditions, and force alpha_k to lie close to a critical point of phi.

The Goldstein conditions are similar but more commonly used with Newton methods (as opposed to quasi-Newton methods).

References

* J. Nocedal and S. J. Wright, Numerical optimization. Springer Verlag, New York, NY, 1999.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Wolfe Ranch — is located in Arches National Park near Moab, Utah, U.S.John Wesley Wolf settled in the location in the later 1800s with his oldest son Fred. A nagging leg injury from the Civil War prompted Wolf to move west from Ohio, looking for a drier… …   Wikipedia

  • Wolfe, Nathan — ▪ 2009 born Aug. 24, 1970, Detroit, Mich.       At a meeting sponsored by the American Association for the Advancement of Science in February 2008, American virologist and epidemiologist Nathan Wolfe announced his plans for a Global Viral… …   Universalium

  • Criteres de Wolfe — Critères de Wolfe En optimisation non contrainte, les critères de Wolfe sont un ensemble d inégalités permettant d optimiser la méthode de recherche linéaire ; plus précisément, cela permet de sélectionner un pas adéquat pour la recherche… …   Wikipédia en Français

  • Critères De Wolfe — En optimisation non contrainte, les critères de Wolfe sont un ensemble d inégalités permettant d optimiser la méthode de recherche linéaire ; plus précisément, cela permet de sélectionner un pas adéquat pour la recherche linéaire. Soit une… …   Wikipédia en Français

  • Critères de wolfe — En optimisation non contrainte, les critères de Wolfe sont un ensemble d inégalités permettant d optimiser la méthode de recherche linéaire ; plus précisément, cela permet de sélectionner un pas adéquat pour la recherche linéaire. Soit une… …   Wikipédia en Français

  • Critères de Wolfe — En optimisation non contrainte, les critères de Wolfe sont un ensemble d inégalités permettant d optimiser la méthode de recherche linéaire ; plus précisément, cela permet de sélectionner un pas adéquat pour la recherche linéaire. Soit une… …   Wikipédia en Français

  • Effet sachs-wolfe — Fond diffus cosmologique, photographié par le satellite WMAP. Les zones bleu de grande taille, apparaissant plus froides, sont en réalité des zones plus chaudes que les autres, mais sujettes à un décalage vers le rouge gravitationnel : c est …   Wikipédia en Français

  • Louise Dahl-Wolfe — Louise Emma Augusta Dahl (November 19, 1895 in San Francisco, California – December 11, 1989) was a photographer, known primarily for her work for Harper s Bazaar with fashion editor Diana Vreeland.Born to Norwegian parents, Dahl Wolfe was known… …   Wikipedia

  • Effet Sachs-Wolfe — Fond diffus cosmologique, photographié par le satellite WMAP. Les zones bleu de grande taille, apparaissant plus froides, sont en réalité des zones plus chaudes que les autres, mais sujettes à un décalage vers le rouge gravitationnel : c est …   Wikipédia en Français

  • James Wolfe Ripley — Infobox Military Person name= James Wolfe Ripley born= birth date|1794|12|10 died= death date and age|1870|3|16|1794|12|10 caption= nickname= placeofbirth= Windham County, Connecticut placeofdeath= Hartford, Connecticut placeofburial= allegiance …   Wikipedia