  Golden-section search and bisection search are the two main principled
algorithms for 1d minimization of quasiconvex (unimodal) functions. The first
one only uses function queries, while the second one also uses gradient
queries. Other algorithms exist under much stronger assumptions, such as
Newton's method. However, to the best of our knowledge, there is no principled
exact line search algorithm for general convex functions -- including
piecewise-linear and max-compositions of convex functions -- that takes
advantage of convexity. We propose two such algorithms: $\Delta$-Bisection is a
variant of bisection search that uses (sub)gradient information and convexity
to speed up convergence, while $\Delta$-Secant is a variant of golden-section
search and uses only function queries.
  While bisection search reduces the $x$ interval by a factor 2 at every
iteration, $\Delta$-Bisection reduces the (sometimes much) smaller $x^*$-gap
$\Delta^x$ (the $x$ coordinates of $\Delta$) by at least a factor 2 at every
iteration. Similarly, $\Delta$-Secant also reduces the $x^*$-gap by at least a
factor 2 every second function query. Moreover, the $y^*$-gap $\Delta^y$ (the
$y$ coordinates of $\Delta$) also provides a refined stopping criterion, which
can also be used with other algorithms. Experiments on a few convex functions
confirm that our algorithms are always faster than their quasiconvex
counterparts, often by more than a factor 2.
  We further design a quasi-exact line search algorithm based on
$\Delta$-Secant. It can be used with gradient descent as a replacement for
backtracking line search, for which some parameters can be finicky to tune --
and we provide examples to this effect, on strongly-convex and smooth
functions. We provide convergence guarantees, and confirm the efficiency of
quasi-exact line search on a few single- and multivariate convex functions.
