Editing Line search (section)

=== Zero-order methods ===
Zero-order methods use only function evaluations (i.e., a [[value oracle]]) - not derivatives:<ref name=":0" />{{Rp|location=sec.5}}
* [[Ternary search]]: pick some two points ''b,c'' such that ''a''<''b''<''c''<''z''. If f(''b'')≤f(''c''), then x* must be in [''a'',''c'']; if f(''b'')≥f(''c''), then x* must be in [''b'',''z'']. In both cases, we can replace the search interval with a smaller one. If we pick ''b'',''c'' very close to the interval center, then the interval shrinks by ~1/2 at each iteration, but we need two function evaluations per iteration. Therefore, the method has [[linear convergence]] with rate <math>\sqrt{0.5}\approx 0.71</math>. If we pick b,c such that the partition a,b,c,z has three equal-length intervals, then the interval shrinks by 2/3 at each iteration, so the method has [[linear convergence]] with rate <math>\sqrt{2/3}\approx 0.82</math>.
* Fibonacci search: This is a variant of ternary search in which the points ''b'',''c'' are selected based on the [[Fibonacci sequence]]. At each iteration, only one function evaluation is needed, since the other point was already an endpoint of a previous interval. Therefore, the method has linear convergence with rate <math>1/ \varphi  \approx 0.618</math> .
* [[Golden-section search]]: This is a variant in which the points ''b'',''c'' are selected based on the [[golden ratio]]. Again, only one function evaluation is needed in each iteration, and the method has linear convergence with rate <math>1/ \varphi  \approx 0.618</math> . This ratio is optimal among the zero-order methods.
Zero-order methods are very general - they do not assume differentiability or even continuity.