Root Finding and Optimization

Newton's method xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ) converges quadratically (the number of correct digits doubles each step) near a simple root; bisection is slower but always converges when the root is bracketed.

Concept

Root of one equation f(x) = 0 fzero(@f, x0) or with a bracket [a b] Roots of a polynomial Minimum on an interval fminbnd(@f, a, b)

Unconstrained minimum, several variables fminsearch (Nelder–Mead, no derivatives); fminunc (Optimization Toolbox)

fmincon, linprog, quadprog, ga (toolboxes) fsolve (Optimization Toolbox) Nonlinear least squares

lsqcurvefit, lsqnonlin (toolbox), or fminsearch on the squared error

Newton's method xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ) converges quadratically (the number of correct digits doubles each step) near a simple root; bisection is slower but always converges when the root is bracketed. fzero combines both ideas.

Options are set with optimset (or optimoptions for toolbox solvers): TolX, TolFun, MaxIter, Display.

Why It Matters

Operating points of nonlinear circuits, parameter identification (fitting models to test data), optimal designs (minimum weight, cost or energy) and controller tuning are optimization problems.

Syntax

x = fzero(@(x) x^3 - 2*x - 5, 2);
[x, fval] = fminsearch(@(p) sum((model(p, t) - y).^2), p0);

Example

24.1 fzero, Newton's method, fminbnd, fminsearch and model fitting

% root of a nonlinear equation: diode-like current balance
g = @(v) 1e-12 * (exp(v / 0.025) - 1) - (5 - v) / 1000;
vd = fzero(g, [0 1]);
fprintf('fzero: operating voltage %.5f V, residual %.2e\n', vd, g(vd))

% Newton's method by hand
fn = @(x) x ^ 3 - 2 * x - 5;
dfn = @(x) 3 * x ^ 2 - 2;
x = 2;
for k = 1:6
    x = x - fn(x) / dfn(x);
    fprintf('Newton iteration %d: x = %.12f\n', k, x)
end

% minimum of a one-variable function on an interval
cost = @(d) 2 * pi * (d / 2) ^ 2 + 4 * 1000 / d;            % can surface area for V = 250*pi... simplified
[dopt, cmin] = fminbnd(cost, 1, 50);
fprintf('fminbnd: optimum d = %.4f, cost %.4f\n', dopt, cmin)

% unconstrained multivariable minimum (Nelder-Mead)
rosen = @(p) (1 - p(1)) ^ 2 + 100 * (p(2) - p(1) ^ 2) ^ 2;
[pmin, fmin] = fminsearch(rosen, [-1.2 1], optimset('TolX', 1e-8, 'TolFun', 1e-10, 'MaxFunEvals', 5000, 'MaxIter', 5000));
fprintf('fminsearch on Rosenbrock: minimum at [%.5f %.5f], f = %.2e\n', pmin, fmin)

% fitting a model by minimizing squared error
tdata = 0:0.5:3;
ydata = [5.0 3.1 1.9 1.1 0.72 0.43 0.27];
model = @(p, t) p(1) * exp(-p(2) * t);
sse = @(p) sum((model(p, tdata) - ydata) .^ 2);
p = fminsearch(sse, [4 1]);
fprin
…

Expected Result

fzero found the diode operating point with a residual near zero.

Newton's method reached full double precision in about four iterations: the correct digits roughly doubled each step (quadratic convergence).

fminsearch found the Rosenbrock minimum at (1, 1) without derivatives.

The exponential model was fitted to data by minimizing the sum of squared errors.

fzero: operating voltage 0.55537 V, residual 5.20e-18
Newton iteration 1: x = 2.100000000000
Newton iteration 2: x = 2.094568121104
Newton iteration 3: x = 2.094551481698
Newton iteration 4: x = 2.094551481542
Newton iteration 5: x = 2.094551481542
Newton iteration 6: x = 2.094551481542
fminbnd: optimum d = 10.8385, cost 553.5810
fminsearch on Rosenbrock: minimum at [1.00000 1.00000], f = 4.47e-18
fitted y = 5.0128 * exp(-0.9792 t), SSE 0.00434

Common Mistakes

A poor starting guess (Newton and fminsearch can converge to the wrong root/minimum or diverge).

fzero bracket [a b] where f(a) and f(b) have the same sign.

Parameters of very different scale in fminsearch (rescale them).

Trusting a single run for a problem with many local minima.

Best Practices

Plot the function first to choose brackets and starting points.

Check the exit flag and the final function value.

Scale variables to similar magnitudes; tighten tolerances when needed.

Interview Relevance

Medium: "how do you find the root of a nonlinear equation?", "Newton vs bisection?", "how do you fit a nonlinear model to data?", "local vs global minimum?".

Practice Questions

Find where cos(x) = x with fzero.

Find the radius that minimizes the surface area of a 1-litre can with fminbnd.

Implement bisection and count iterations for 1e-10 accuracy.

Fit a first-order step response K·(1 − e^(−t/τ)) to noisy data with fminsearch.

Quick Quiz

Q1. (Multiple choice) Which function minimizes a multivariable function without derivatives in core MATLAB? A) fzero B) fminbnd C) fminsearch D) roots Answer: C.

Q2. (Predict the output) Newton's method on x³ − 2x − 5 from x = 2 converges to?

Answer: ≈ 2.094551481542 (verified).

Q3. (True/False) fminsearch always finds the global minimum.

Answer: False. It finds a local minimum near the starting point.

Q4. (Find the bug) fzero(@(x) x^2 + 1, [0 2]) errors.

Answer: The function doesn't change sign on the bracket (x² + 1 has no real root).

Coding Challenge

Use fzero to find the time at which the RC voltage 5·(1 − e^(−t)) reaches 4 V, and compare with the exact value −ln(0.2).

v = @(t) 5 * (1 - exp(-t));
t4 = fzero(@(t) v(t) - 4, 1);
fprintf('reaches 4 V at t = %.6f s (exact %.6f s)\n', t4, -log(0.2))