Line search
In (unconstrained) optimization, the \'\'\'linesearch\'\'\' strategy is one of two basic iterative approaches to finding a local minimum Failed to parse (syntax error): {\displaystyle \\mathbf{x}^*} of an objective function Failed to parse (syntax error): {\displaystyle f:\\mathbb R^n\\to\\mathbb R} . The other method is that of trust regions.
Algorithm
- i) Set iteration counter , and make an initial guess, Failed to parse (syntax error): {\displaystyle \\mathbf{x}_0} for the minimum.
- ii) Compute a descent direction Failed to parse (syntax error): {\displaystyle \\mathbf{p}_k} .
- iii) Choose Failed to parse (syntax error): {\displaystyle \\alpha_k} to \'loosely\' minimize Failed to parse (syntax error): {\displaystyle \\phi(\\alpha)=f(\\mathbf{x}_k+\\alpha\\mathbf{p}_k)} over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \\alpha\\in\\mathbb R} .
- iv) Update Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \\mathbf{x}_{k+1}=\\mathbf{x}_k+\\alpha_k\\mathbf{p}_k}
, .
- If Failed to parse (syntax error): {\displaystyle \\|\\nabla f(\\mathbf{x}_k)\\|\\leq} tolerance, STOP.
- Else, goto ii).
In step iii) we can either \'\'exactly\'\' minimize Failed to parse (syntax error): {\displaystyle \\phi} , by solving Failed to parse (syntax error): {\displaystyle \\phi\'(\\alpha_k)=0} , or \'\'loosely\'\', by asking for a sufficient decrease in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \\phi} . The latter may be performed in a number of ways, perhaps by doing a backtracking linesearch or using the Wolfe conditions.
Like other optimization methods, line search may be combined with simulated annealing to allow it to jump over some local minima.
References
- N. I. M. Gould and S. Leyffer, An introduction to algorithms for nonlinear optimization. In J. F. Blowey, A. W. Craig, and T. Shardlow, Frontiers in Numerical Analysis, pages 109-197. Springer Verlag, Berlin, 2003.