Nonlinear Optimization, Interactively

0

The problem: where am I?

Setup

A robot sits at some unknown position. It can't see that position directly — it only knows the fixed positions of a few landmarks, and it can measure its (noisy) distance to each one. That's it. From those distances alone, it has to work out where it is.

If the robot knew its distance to a landmark exactly, all it would know is that it sits somewhere on a circle around that landmark. One landmark isn't enough. This is the classic trilateration problem — the same idea behind GPS, and it's nonlinear because distance involves a square root: distance = sqrt((x − Lx)² + (y − Ly)²). There's no algebra shortcut to solve for the robot's position directly once there's more than one noisy measurement — so instead, we turn it into something we can search for.

💡 The idea for the rest of this page: turn "where is the robot?" into "what position makes our measurements make the most sense?" — then find that position by taking small, smart steps downhill on a cost function. Every method below is a different rule for choosing that step.

1

Turning it into a cost function

Foundations

For each landmark i we define a residual: how wrong our current guess is, in measurement units.

r⁢(p) = ‖p − L⁢‖ − d⁢
  p = our current guess of the robot's position (x, y)
  L⁢ = the known position of landmark i
  d⁢ = the noisy distance we measured to landmark i

We can't just sum the residuals (positive and negative errors would cancel), so we square and sum them into one cost function — the thing we're going to minimize:

C(p) = ½ ∑ r⁢(p)²

Drag the slider below. It moves the robot's guessed position along a line past one landmark, and the chart on the right plots the cost at every point on that line. Notice the curve is a smooth bowl near the bottom, but not a perfect parabola — that's the "nonlinear" part. Our whole job for the rest of this page is: find the bottom of the bowl, without checking every possible point.

Robot's guessed x-position

2

The naive way: gradient descent

Method 1 of 4

🎯 Learning goal: a slope tells you which way is downhill, and roughly how steep — that's enough to take a step. No curvature, no matrix, just "go the other way from the slope."

The simplest strategy: look at the slope f'(x) at your current guess, and step a little in the downhill direction.

xₕ₊₁ = xₕ − α · f'(xₕ) (α = step size / "learning rate")

Pick a starting guess and a step size below, then click Step repeatedly (or Run) and watch it crawl toward the minimum. Try a step size that's too big — it can overshoot and bounce around, or even walk away from the minimum entirely. Too small, and it barely moves.

Click anywhere on the chart to set a new starting guess.

Step size α

⚠️ Weakness: gradient descent only ever asks "which way is down?" — never "how far until the bottom?" So it needs a well-tuned step size and often takes many small steps to converge.

3

Newton's method: using curvature

Method 2 of 4

🎯 Learning goal: the second derivative tells you how the slope is changing — the curvature. Fit a parabola that matches your point's height, slope, and curvature, and jump straight to its minimum instead of crawling.

At the current guess, approximate the cost with a parabola that matches its value, slope, and curvature (a second-order Taylor expansion). That parabola has an exact, known minimum — so jump straight there:

xₕ₊₁ = xₕ − f'(xₕ) / f''(xₕ)

Same cost curve as before. Step through it and compare: Newton usually needs far fewer steps than gradient descent to land on the minimum, because it's using more information (curvature, not just slope) at every step. The dashed curve is the local parabola it's currently trusting.

Click anywhere on the chart to set a new starting guess.

⚠️ Weakness: Newton's step trusts the local parabola completely. If the curvature f''(x) is near zero, tiny, or negative (the function is concave where you're standing — try starting far to one side), the "parabola's minimum" can be a wild overshoot, or point the wrong way entirely. No step-size safety net.

4

Into 2D: Newton-Raphson for the robot

Method 2, generalized

🎯 Learning goal: in 2D (or higher), "slope" becomes a gradient vector and "curvature" becomes a Hessian matrix. The update rule is the same idea, just with linear algebra doing the work.

∇C(p) = gradient (2×1 vector) H(p) = Hessian (2×2 matrix)
pₕ₊₁ = pₕ − H(pₕ)⁻¹ ∇C(pₕ)

Below is the cost surface C(x, y) for the robot, plotted as a 3D bowl — height and color both track cost, so you can rotate it to see the shape directly instead of squinting at a flat heatmap. This scenario deliberately uses only two landmarks, so there isn't one clean bowl: two positions can produce almost the same pair of distances, mirrored across the line through the landmarks. Drag to orbit, scroll to zoom, and click the surface to place a starting guess, then step. Watch what happens if you start on the "wrong" side.

Drag to orbit, scroll to zoom. Click the surface to set the robot's starting guess (blue). ★ marks the true position (hidden from the algorithm — it only sees noisy distances).

Newton path ★ true position ◆ landmark

⚠️ Weakness: the full Hessian needs the curvature of every residual (second derivatives), and with too few or poorly-placed landmarks it can be near-singular or indefinite — Newton's jump becomes unreliable exactly where you need it most.

5

Gauss-Newton: a shortcut built for least-squares

Method 3 of 4

🎯 Learning goal: our cost is specifically a sum of squared residuals — that special structure lets us approximate the Hessian without computing any second derivatives at all.

Write the residuals' first derivatives as a Jacobian matrix J (one row per landmark). It turns out the true Hessian splits into two parts:

H(p) = JᵀJ + ∑ r⁢ · (curvature of r⁢)

Gauss-Newton just drops the second term and uses JᵀJ as a stand-in for the Hessian:

pₕ₊₁ = pₕ − (JᵀJ)⁻¹ Jᵀr(pₕ)

That's a good approximation whenever the residuals themselves are small or nearly linear near the answer — true for most well-posed localization problems close to the solution. This scenario adds a third landmark, which removes the mirror-image ambiguity from the last step. Toggle the checkbox to overlay Newton's path for comparison — near the minimum they behave almost identically, but Gauss-Newton got there without ever touching a second derivative.

Drag to orbit, scroll to zoom. Click the surface to set the robot's starting guess.

Gauss-Newton path Newton path (for comparison)

Also show Newton's path

⚠️ Weakness: Gauss-Newton still takes the full step with no safety net. Start it somewhere the linear (Jacobian) approximation is poor, and it can overshoot or oscillate instead of settling in — try dragging the guess far from the landmarks.

6

Levenberg-Marquardt: the best of both

Method 4 of 4

🎯 Learning goal: blend gradient descent's caution with Gauss-Newton's speed using one dial, λ ("damping"), and adjust that dial automatically based on whether each step actually helped.

pₕ₊₁ = pₕ − (JᵀJ + λI)⁻¹ Jᵀr(pₕ)

When λ = 0 this is exactly Gauss-Newton. As λ → ∞ the step shrinks and turns into a plain (small) gradient-descent step. Levenberg-Marquardt adjusts λ after every step: if the step reduced the cost, accept it and lower λ (be bolder, trust the local model more); if the step made things worse, reject it and raise λ (be more cautious, fall back toward gradient descent). Same 3-landmark scenario as before — try a starting guess far from the landmarks, where plain Gauss-Newton struggled, and watch adaptive λ tame it.

Drag to orbit, scroll to zoom. Click the surface to set the robot's starting guess.

Adapt λ automatically

Fixed λ

💡 This is why Levenberg-Marquardt is the default choice for real robot localization, camera calibration, and bundle adjustment: it's almost as fast as Gauss-Newton near the answer, and about as reliable as gradient descent far from it.

7

Playground: race all four methods

Put it all together

One scenario, four landmarks, one starting guess — every method runs from the same spot at once. Watch the paths diverge and see the table fill in as each one converges (or doesn't).

Drag to orbit, scroll to zoom. Click the surface to set the shared starting guess.

Gradient descent Newton Gauss-Newton Levenberg-Marquardt

Method	Iters	Final error	Status

✓

Cheat sheet

Recap

Method	Update rule	Uses	Good when
Gradient descent	`p − α∇C`	Gradient only	Far from the answer, or curvature is unreliable — but slow
Newton	`p − H⁻¹∇C`	Gradient + full Hessian	Close to the answer with a well-behaved (positive-definite) Hessian — fast, but fragile
Gauss-Newton	`p − (JᵀJ)⁻¹Jᵀr`	Jacobian only — no 2nd derivatives	Least-squares problems where residuals are small near the answer — cheap and fast
Levenberg-Marquardt	`p − (JᵀJ + λI)⁻¹Jᵀr`	Jacobian + adaptive damping λ	Almost always — the practical default for nonlinear least-squares

All four methods answer the same question — which direction, and how far? — using progressively more information about the shape of the cost function. Gradient descent only asks "which way is down." Newton asks "down, and how curved is it here?" Gauss-Newton gets a cheap answer to the same question by exploiting the sum-of-squares structure. Levenberg-Marquardt hedges between the two automatically, which is why it's the one you'll actually find inside most robotics and computer-vision libraries (it's the workhorse under g2o, Ceres Solver, and most bundle-adjustment and SLAM back-ends).