2
$\begingroup$

I wanted to clarify the idea of the exact line search in steepest descent method.

An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search direction $(d)$ and iteratively shrinking the step size until a decrease of the objective function is observed. Is this correct? I.e. the only condition suppose to be satisfied is: $f(x_{k+1})<f(x_k)$, where $x_{k+1} = x_k + \alpha_kd_k$

In exact line search the step size $\alpha$ is not necessary to be fixed. Is this true?

If this is true then what is the difference of the exact line search from the backtracking line search? I know that backtracking line search is based on Armijo-Gooldstein condition or Wolfe's condition.

$\endgroup$
  • 3
    $\begingroup$ What you have described is not an exact line search. See math.stackexchange.com/questions/1153655/… . $\endgroup$ – Mark L. Stone Mar 28 '16 at 16:30
  • $\begingroup$ An exact line search chooses $\alpha_k$ as $\min_\alpha f(x_k+\alpha d_k)$. Needless to say, this is only feasible for a very limited class of $f$ (such as quadratic functions). $\endgroup$ – Christian Clason Mar 28 '16 at 21:52
  • 1
    $\begingroup$ @Christian Clason , an exact line search is actually feasible (but not necessarily computationally desirable) for a much broader class of functions, because in this case, "exact" line search really means approximately exact, in the sense in which any numerical optimization problem is only solved to within some numerical tolerance (approximation) to the exact solution. That is still very different than an approximate line search which stops when an Armijo-Gooldstein condition or Wolfe condition is first met. $\endgroup$ – Mark L. Stone Mar 28 '16 at 23:16
  • $\begingroup$ @MarkL.Stone That's not how I have seen the term used in optimization ("approximately exact" is an oxymoron); note that in the answer you linked to, the exact line search is in fact applied to a quadratic problem -- namely a Taylor approximation of the original problem. If this is what you had in mind (a.k.a. "Newton's method with exact line search"), then we are in agreement. $\endgroup$ – Christian Clason Mar 29 '16 at 7:04
  • $\begingroup$ @Christian Clason , even quadratics are not solved exactly. Perhaps we can agree to disagree. $\endgroup$ – Mark L. Stone Mar 29 '16 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.