Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 38 · Getting Started

Your First Solvers: Grid Search and Newton

Build three simple solvers from scratch: grid search, bisection on the derivative and Newton's method. Compare their speed and learn when each one works.

You now know that a minimum of a smooth one-variable function has a zero derivative. That turns optimization into root finding: find x where f'(x) = 0. In this lesson you build three solvers from scratch and compare how many function evaluations each needs. They are tiny, but they preview ideas used by every serious optimizer.

Our test problem: f(x) = eˣ - 3x. Its derivative is f'(x) = eˣ - 3, which is zero at x = ln 3 ≈ 1.0986. The second derivative eˣ is always positive, so the function is convex and this point is the global minimum.

Grid search tries evenly spaced candidates and keeps the best. It needs no derivatives, but accuracy costs a lot: halving the spacing doubles the work in one variable, and in n variables the number of points explodes like kⁿ.

Python Grid search

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error shrinks, but slowly, and every digit of accuracy costs ten times more points.

Solver 2: bisection on the derivative

Because f is convex, f' is increasing. If f'(a) < 0 and f'(b) > 0, the root lies between them. Check the midpoint: its derivative sign tells you which half still contains the root. Each step halves the interval, so the error after k steps is at most (b - a) / 2ᵏ.

Python Bisection

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Forty derivative evaluations give around twelve correct digits: much better than the grid. Bisection is slow-but-sure ("linear convergence": the error shrinks by a constant factor each step).

Solver 3: Newton's method

Newton's method replaces the function near the current point with a parabola (using f' and f'') and jumps to the parabola's minimum. In one variable the update is

Text
x_new = x - f'(x) / f''(x)

This is the same as applying the classic tangent-line root finder to f'. When you start close enough, the number of correct digits roughly doubles each step ("quadratic convergence").

Python Newton's method

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After about six or seven steps it reaches machine precision, far fewer evaluations than bisection. The price: Newton needs the second derivative, and it can fail when started far from the answer or where f'' ≤ 0.

When Newton misbehaves

Newton's jump is only as good as its parabola. Where the curvature f'' is tiny, the parabola is nearly flat and the jump can be enormous. Where f'' is negative, the "parabola" opens downward and Newton heads for a maximum. Practical solvers add safeguards, such as a line search or a trust region, that shrink steps when they are too bold. You will meet the line search in the step size lesson.

Method Needs Speed Risk
Grid search only f very slow cost explodes with dimension
Bisection f', a bracket steady (linear) needs a bracket
Newton f', f'' very fast near the answer can overshoot or diverge
flowchart LR
    A["Grid search<br/>slow, robust"] --> B["Bisection<br/>steady, needs bracket"]
    B --> C["Newton<br/>fast, needs f'' and a good start"]

Faster methods use more information about the function.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why does bisection work on the derivative of a convex function?

    For convex f, f' increases, so f'(mid) < 0 means the minimum lies to the right and vice versa.
  2. 2. After k bisection steps starting from an interval of length L, the interval length is

    Each step halves the interval.
  3. 3. The Newton update for minimizing f in one variable is

    It jumps to the minimum of the local quadratic model, which uses f' and f''.
  4. 4. A main weakness of grid search in many dimensions is that

    k points per axis in n dimensions means kⁿ points in total.

Summary

  • A smooth convex minimum is a root of the derivative.
  • Grid search is simple but scales badly; bisection halves the error each step; Newton roughly doubles the correct digits each step near the answer.
  • More information (derivatives, curvature) buys faster convergence but adds risk, so safeguards matter.

Next: Convex Sets