Answers to: Binary Line Searchhttp://www.or-exchange.com/questions/3898/binary-line-search<p>It seems that one thing that could be done to minimize a convex function of one variable would be to start at a point x where the gradient is negative and then check point x'. If the gradient has reversed direction, then we choose the midpoint between x,x' and continue. </p>
<p>However, I've never seen such a method used anywhere. Does it not perform well in practice compared to ordinary gradient descent?</p>enThu, 27 Oct 2011 11:57:58 -0400Comment by Ehsan on Matthew Saltzman's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3914<p>Required number of observation for binary search and golden section methods are given on page 355 of Bazaraa et al.'s Nonlinear Programming - Theory and Algorithms, 3rd edition.</p>EhsanThu, 27 Oct 2011 11:57:58 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3914Comment by Ehsan on Paul Rubin's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3913<p>Perhaps it's a matter of naming conventions, but some references like Bazaraa et al.'s Nonlinear Programming denote the derivative counterpart of binary search method as the Bisection search method.</p>EhsanThu, 27 Oct 2011 11:55:43 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3913Comment by Matthew Saltzman on Matthew Saltzman's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3905<p>So both converge linearly. But golden section reuses some function evaluations that can't be reused in bisection, so the overall number of function evaluations is smaller. That matters if function evaluations are costly. (I guess I really should look this up...)</p>Matthew SaltzmanWed, 26 Oct 2011 22:32:11 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3905Comment by Paul Rubin on Matthew Saltzman's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3904<p>Once you've restricted the search to a finite interval, bisection reduces the interval 50% per iteration compared to roughly 40% with golden section.</p>Paul RubinWed, 26 Oct 2011 22:23:24 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3904Answer by Matthew Saltzmanhttp://www.or-exchange.com/questions/3898/binary-line-search/3903<p>Bisection search usually applies to the problem of finding a root. Start with a point with positive value and a point with negative value. Take the midpoint, determine its value, and replace the endpoint with the same sign with the midpoint. If the function is continuous, you will eventually converge on a root.</p>
<p>One could use bisection search with the derivative of the function of interest, which is essentially what Opt proposes, but I think other methods are generally considered superior. (I'd have to go back to an NLP text to recover the convergence rate proofs, but they are in any standard text.) The usual line searches for differentiable functions are based on Newton's method (which has quadratic local convergence), but modified to guarantee global convergence.</p>
<p>Paul's suggestion is relevant for continuous functions that may not be differentiable. IIRC, Golden section search minimizes the number of function evaluations compared to other interval search techniques like midpoint. (I haven't taught NLP in a little while, so take this all with a grain of salt.)</p>Matthew SaltzmanWed, 26 Oct 2011 22:06:30 -0400http://www.or-exchange.com/questions/3898/binary-line-search/3903Comment by Paul Rubin on Paul Rubin's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3902<p>Not that I know of. The closest I can come are some "hill-climbing" methods, one of which is due to Nelder and Mead and (rather confusingly) called the "simplex" algorithm. (Search using the authors' names to avoid many, many irrelevant results.)</p>Paul RubinWed, 26 Oct 2011 18:43:31 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3902Comment by Opt on Paul Rubin's answerhttp://www.or-exchange.com/questions/3898/binary-line-search#3901<p>Thanks for the answer. Are there multivariate generalization of the bisection and/or golden section methods?</p>OptWed, 26 Oct 2011 18:28:51 -0400http://www.or-exchange.com/questions/3898/binary-line-search#3901Answer by Paul Rubinhttp://www.or-exchange.com/questions/3898/binary-line-search/3900<p>Bisection search is certainly taught as a ”standard” method of line search (along with golden section search and some others that I'm forgetting at the moment). I don't know what's popular with vendors of NLP solvers. I used to favor golden section when I wrote my own code because (a) derivative computations are sometimes expensive and (b) not every convex function is differentiable; but that's just a personal preference.</p>Paul RubinWed, 26 Oct 2011 18:12:59 -0400http://www.or-exchange.com/questions/3898/binary-line-search/3900