Skip to content

Gradient and Direct Search, Generalized Inversion, SVD and Global Optimization

CSIR NET geophysics: steepest descent, Gauss-Newton, Marquardt, simplex and grid search, SVD and generalized inverse, resolution, simulated annealing, GA.

  • 21 min read
  • Updated
On this page · 14 sections
  1. Prerequisites
  2. The Hook: A Landscape with Many Valleys
  3. The Objective Function
  4. Gradient Methods
  5. Direct Search Methods
  6. Generalized Inversion and the SVD
  7. Global Optimization
  8. Memory Tricks
  9. Don’t Confuse
  10. Common Mistakes
  11. Practice
  12. Quick Revision Table
  13. Key Takeaways
  14. What’s Next

Prerequisites

The Hook: A Landscape with Many Valleys

The Objective Function

Inversion minimises an objective (misfit, cost) function \( \phi(\mathbf{m}) \), typically

$$\phi(\mathbf{m}) = \tfrac{1}{2}\lVert \mathbf{r}(\mathbf{m}) \rVert^2, \qquad \mathbf{r} = \mathbf{d} - g(\mathbf{m}),$$

plus a regularisation term if the problem is ill-posed. Near a point \( \mathbf{m} \), a quadratic model describes it:

$$\phi(\mathbf{m} + \Delta\mathbf{m}) \approx \phi(\mathbf{m}) + \mathbf{g}^{\mathsf T}\Delta\mathbf{m} + \tfrac{1}{2}\Delta\mathbf{m}^{\mathsf T}H\,\Delta\mathbf{m},$$

with gradient \( \mathbf{g} = \nabla\phi \) and Hessian \( H = \nabla^2\phi \). For the least-squares objective with Jacobian \( J = \partial g/\partial\mathbf{m} \):

$$\mathbf{g} = -J^{\mathsf T}\mathbf{r}, \qquad H = J^{\mathsf T}J - \sum_i r_i \nabla^2 g_i \approx J^{\mathsf T}J.$$

Dropping the second-derivative term is the Gauss–Newton approximation. It is good when residuals are small or the problem is nearly linear.

graph TD
    A["Minimise misfit phi(m)"] --> B{"Derivatives available and misfit smooth?"}
    B -->|Yes| C["Gradient methods: steepest descent, Newton, Gauss-Newton, Marquardt, conjugate gradient"]
    B -->|No, few parameters| D["Direct search: grid, simplex, pattern search"]
    A --> E{"Many local minima?"}
    E -->|Yes| F["Global methods: Monte Carlo, simulated annealing, genetic algorithms"]
    F --> G["Refine the best model with a local method"]
    C --> H["Assess resolution and uncertainty (SVD)"]
    G --> H

Gradient Methods

Steepest descent

Move downhill along the negative gradient:

$$\mathbf{m}_{k+1} = \mathbf{m}_k - \alpha_k\,\mathbf{g}_k.$$

For a quadratic with Hessian \( H \), the exact line-search step is \( \alpha = \frac{\mathbf{g}^{\mathsf T}\mathbf{g}}{\mathbf{g}^{\mathsf T}H\mathbf{g}} \). Each step goes as far as possible along a direction, so the next gradient is perpendicular to the last: the path zig-zags. Convergence is linear and becomes very slow in long narrow valleys (high condition number of \( H \)).

Newton’s method

Minimise the quadratic model exactly:

$$\boxed{H\,\Delta\mathbf{m} = -\mathbf{g}}$$
  • Converges in one step on a quadratic and quadratically near a minimum in general.
  • Needs second derivatives and a linear solve; can head for a maximum or saddle if \( H \) is not positive definite; can overshoot far from the minimum.

Gauss–Newton

Newton with \( H \approx J^{\mathsf T}J \):

$$\boxed{J^{\mathsf T}J\,\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r}}$$

Each step is a linear least-squares problem for the update. Only first derivatives are needed.

Levenberg–Marquardt

Damp the Gauss–Newton step:

$$\boxed{(J^{\mathsf T}J + \lambda I)\,\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r}}$$
\( \lambda \)Behaviour
\( \lambda \to 0 \)Gauss–Newton step: fast near the minimum
\( \lambda \) large\( \Delta\mathbf{m} \approx \frac{1}{\lambda}J^{\mathsf T}\mathbf{r} \): a short steepest-descent step, safe far from the minimum

The rule: if a step lowers the misfit, accept it and decrease \( \lambda \); if it raises the misfit, reject it and increase \( \lambda \). It is the same algebra as damped least squares on the previous page, now used to control step size in a non-linear iteration. Geophysical texts often call it simply the Marquardt method; statisticians know the same damped normal equations as ridge regression.

Conjugate gradients

Choose each new search direction to be conjugate (\( H \)-orthogonal) to the previous ones. On a quadratic in \( M \) unknowns, the method reaches the exact minimum in at most \( M \) steps (in exact arithmetic), and it needs only products of \( G \) or \( G^{\mathsf T} \) with vectors, never \( G^{\mathsf T}G \) itself. That makes conjugate-gradient-type solvers (such as LSQR) the standard choice for large sparse tomography systems with many thousands of cells.

Direct Search Methods

Direct search uses only values of \( \phi \), never derivatives. Use it when derivatives are unavailable, expensive or unreliable (noisy or discontinuous misfit), and the number of parameters is small.

MethodHow it worksStrengthWeakness
Grid (exhaustive) searchevaluate \( \phi \) at every node of a regular gridfinds the global minimum on the grid; maps the whole misfit surfacecost \( n^M \) grows explosively with \( M \)
Coordinate (one-at-a-time) searchvary one parameter at a timevery simpleslow when parameters trade off (diagonal valleys)
Pattern search (Hooke–Jeeves type)exploratory moves, then a jump along the improving patternhandles diagonal valleys betterlocal only
Nelder–Mead downhill simplexa simplex of \( M + 1 \) points; reflect the worst point through the centroid of the rest, then expand, contract or shrinkrobust, derivative-free, widely used for small \( M \)local; slow for many parameters

Generalized Inversion and the SVD

The singular value decomposition

Any real \( N \times M \) matrix can be factorised as

$$\boxed{G = U\Lambda V^{\mathsf T}}$$
  • \( U \) (\( N \times N \)): orthonormal data eigenvectors, \( U^{\mathsf T}U = I \).
  • \( V \) (\( M \times M \)): orthonormal model eigenvectors, \( V^{\mathsf T}V = I \).
  • \( \Lambda \) (\( N \times M \)): diagonal, holding the singular values \( \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_p > 0 \), then zeros. The number of non-zero singular values \( p \) is the rank of \( G \).
  • \( \sigma_i^2 \) are the non-zero eigenvalues of both \( G^{\mathsf T}G \) and \( GG^{\mathsf T} \); the columns of \( V \) and \( U \) are their eigenvectors.

Keep only the \( p \) non-zero values: \( G = U_p\Lambda_pV_p^{\mathsf T} \). The discarded columns span two null spaces:

SpaceSpanned byMeaning
Model null space\( V_0 \) (columns of \( V \) beyond \( p \))model changes with \( G\mathbf{m}_0 = 0 \): invisible to the data, the source of non-uniqueness
Data null space\( U_0 \) (columns of \( U \) beyond \( p \))data components no model can produce: they end up in the misfit

The generalized (Lanczos) inverse

$$\boxed{G^{\dagger} = V_p\Lambda_p^{-1}U_p^{\mathsf T}} \qquad \mathbf{m}_{\text{est}} = G^{\dagger}\mathbf{d} = \sum_{i=1}^{p}\frac{\mathbf{u}_i^{\mathsf T}\mathbf{d}}{\sigma_i}\,\mathbf{v}_i$$

This is the Moore–Penrose pseudo-inverse. It does three jobs at once:

  • If \( V_0 \) is empty (full column rank), it gives the least-squares solution.
  • If \( U_0 \) is empty (full row rank), it gives the minimum-norm exact solution.
  • In general (mixed-determined) it gives the minimum-norm least-squares solution: it fits what can be fitted and adds nothing from the model null space.

The sum shows the danger: each component is divided by \( \sigma_i \), so noise in directions with small singular values is hugely amplified.

Resolution and covariance

MatrixDefinitionPerfect caseReading it
Model resolution\( R = G^{\dagger}G = V_pV_p^{\mathsf T} \)\( R = I \)\( \mathbf{m}_{\text{est}} = R\,\mathbf{m}_{\text{true}} \): each estimated parameter is a weighted average of the true ones; rows are averaging kernels
Data resolution (information density)\( N = GG^{\dagger} = U_pU_p^{\mathsf T} \)\( N = I \)\( \mathbf{d}_{\text{pred}} = N\mathbf{d} \); a diagonal entry is the importance of that datum
Model covariance (data variance \( \sigma_d^2 \))\( C_m = \sigma_d^2V_p\Lambda_p^{-2}V_p^{\mathsf T} \)small \( \sigma_i \) give large variances

Both resolution matrices have trace \( p \). Keeping more singular values improves resolution (\( R \to I \)) but inflates the variance through the \( \frac{1}{\sigma_i^2} \) terms. This resolution–variance trade-off is the central compromise of inversion.

Taming small singular values

ApproachFilter applied to the \( i \)th componentEffect
Truncated SVD1 if \( \sigma_i \) is kept, 0 if discardeddrop components whose \( \sigma_i \) are below the noise level
Damped least squares\( \frac{\sigma_i^2}{\sigma_i^2 + \varepsilon^2} \)smooth roll-off: components with \( \sigma_i \gg \varepsilon \) pass, those with \( \sigma_i \ll \varepsilon \) are suppressed

Both reduce variance at the cost of resolution. A practical rule: keep components while the noise they would amplify, about \( \frac{\text{noise level}}{\sigma_i} \), stays small compared with the signal.

For continuous (function-space) problems, the Backus–Gilbert approach asks the same question differently: it builds, for each point, the most compact averaging kernel the data allow, and reports the trade-off between kernel width and estimate variance.

Global Optimization

Local methods find the minimum of the valley they start in. When the misfit surface is multimodal (many local minima), as in waveform fitting with cycle skipping, residual statics, or layered-Earth inversions with strong trade-offs, use methods that explore the whole model space.

Draw models at random from prior ranges, compute the misfit for each, keep those that fit acceptably. Simple, embarrassingly parallel and free of derivatives, but inefficient: most samples land in poor regions. The ensemble of acceptable models is itself useful, because it shows the range of models the data permit. In the Bayesian view, Markov chain Monte Carlo sampling draws models in proportion to the posterior probability (likelihood times prior), giving uncertainties directly.

Simulated annealing

The analogy is slow cooling of a melt: cooled slowly, atoms find the minimum-energy crystal; quenched, they freeze in a glassy, higher-energy state. Treat the misfit as an energy \( E \) and introduce a control parameter, the temperature \( T \).

  1. Perturb the current model at random; compute \( \Delta E = E_{\text{new}} - E_{\text{old}} \).
  2. Metropolis criterion: if \( \Delta E \le 0 \), accept. If \( \Delta E > 0 \), accept with probability $$\boxed{P = e^{-\Delta E/T}}$$
  3. Lower \( T \) slowly according to a cooling schedule (for example \( T_{k+1} = aT_k \) with \( a \) slightly below 1) and repeat.

At high \( T \) the search wanders freely and can climb out of local minima; at low \( T \) it settles into the deepest basin it has found. Cool too fast and it freezes in a local minimum.

Genetic algorithms

Borrow from natural selection, working on a population of models rather than one.

  1. Encode each model as a string (classically binary; real-valued codings are also used).
  2. Fitness: evaluate each model (fitness is high where misfit is low).
  3. Selection: fitter models are more likely to become parents.
  4. Crossover: exchange segments of two parent strings to make offspring.
  5. Mutation: flip occasional bits at random, preserving diversity.
  6. Replace the population and repeat for many generations.

With \( n \) bits a parameter takes \( 2^n \) values over its range, so its resolution is \( \frac{\text{range}}{2^n - 1} \).

Comparing the families

Local gradient (GN, Marquardt, CG)Direct search (grid, simplex)Global stochastic (MC, SA, GA)
Needs derivativesyesnono
Forward models neededfew (tens)many; grid grows as \( n^M \)very many (thousands to millions)
Finds global minimumonly if started in its basingrid: yes (on the grid); simplex: nolikely, not guaranteed
Best forsmooth, near-linear problems; large \( M \) with good startfew parameters, noisy misfitfew to moderate parameters, multimodal misfit, cheap forward model

A common practical recipe is hybrid: a global method to locate the right basin, then a gradient method to converge quickly, then the SVD or a Monte Carlo ensemble to report resolution and uncertainty.

Memory Tricks

Don’t Confuse

ThisvsThat
Newton: full Hessian, second derivativesGauss–Newton: \( H \approx J^{\mathsf T}J \), first derivatives only
Marquardt \( \lambda \) (step control in a non-linear iteration)Damping \( \varepsilon^2 \) in a linear inverse (regularisation); same algebra, different purpose
Nelder–Mead simplex (direct search, non-linear minimisation)Simplex method of linear programming (L1 fitting, constraints)
Model resolution \( R = V_pV_p^{\mathsf T} \)Data resolution \( N = U_pU_p^{\mathsf T} \)
Model null space: does not change the dataData null space: cannot be predicted by any model
Truncated SVD: sharp cut-offDamped LS: smooth filter \( \sigma^2/(\sigma^2 + \varepsilon^2) \)
Simulated annealing: one model, random walk with Metropolis acceptanceGenetic algorithm: a population evolving by selection, crossover and mutation

Common Mistakes

Practice

All questions below are original practice questions written for this page. They are not from any CSIR NET paper.

Level 1: Foundation

  1. Write the Gauss–Newton equation for the model update.
  2. How many vertices does the Nelder–Mead simplex have for a problem with 4 parameters?
  3. Write the Metropolis acceptance probability for an uphill move in simulated annealing.
Answers
  1. \( J^{\mathsf T}J\,\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r} \), with \( \mathbf{r} = \mathbf{d} - g(\mathbf{m}) \).
  2. 5 (\( M + 1 \)).
  3. \( P = e^{-\Delta E/T} \) for \( \Delta E > 0 \).

Level 2: Part B Style

Practice Q1. The forward model is \( g(m) = m^2 \) and the observed datum is 4. Starting from \( m_0 = 1 \), the first Gauss–Newton iterate is:

(a) 1.5 (b) 2.0 (c) 2.5 (d) 4.0

Answer: (c) 2.5

\( r = 4 - 1 = 3 \), \( J = 2m = 2 \), \( \Delta m = \frac{Jr}{J^2} = \frac{3}{2} = 1.5 \). New \( m = 2.5 \). Option (a) is the step, not the new model.

Practice Q2. In simulated annealing at temperature \( T = 1 \), a trial model increases the misfit by 2 units. The probability of accepting it is about:

(a) 0.02 (b) 0.14 (c) 0.50 (d) 0.61

Answer: (b) 0.14

\( P = e^{-2/1} = 0.135 \). Option (d) is the value at \( T = 4 \); option (a) at \( T = 0.5 \).

Practice Q3. A genetic algorithm codes a velocity between 2000 and 6000 m/s in binary. The smallest number of bits giving a resolution of 1 m/s or better is:

(a) 10 (b) 11 (c) 12 (d) 13

Answer: (c) 12

Range 4000 m/s. With \( n \) bits the resolution is \( \frac{4000}{2^n - 1} \). \( n = 11 \): \( \frac{4000}{2047} \approx 1.95 \) m/s, too coarse. \( n = 12 \): \( \frac{4000}{4095} \approx 0.98 \) m/s. So 12 bits.

Practice Q4. In the Levenberg–Marquardt method, a trial step increases the misfit. The usual response is to:

(a) accept the step and decrease \( \lambda \) (b) reject the step and increase \( \lambda \) (c) reject the step and set \( \lambda = 0 \) (d) accept the step and increase \( \lambda \)

Answer: (b)

A failed step means the Gauss–Newton quadratic model is not trusted this far out. Increasing \( \lambda \) shortens the step and turns it towards the steepest-descent direction. Setting \( \lambda = 0 \) would give the pure Gauss–Newton step that just failed.

Level 3: Part C Style

Practice Q5. For \( G = \begin{pmatrix} 3 & 0 \\ 4 & 0 \end{pmatrix} \) and \( \mathbf{d} = (6,\ 9) \), the generalized-inverse (minimum-norm least-squares) estimate and the model resolution matrix are:

(a) \( (2.16,\ 0) \) and \( \mathrm{diag}(1, 0) \) (b) \( (2,\ 0) \) and \( \mathrm{diag}(1, 1) \) (c) \( (2.16,\ 2.16) \) and \( \mathrm{diag}(1, 0) \) (d) \( (2.25,\ 0) \) and \( \mathrm{diag}(0.36, 0.64) \)

Answer: (a)

\( \sigma_1 = 5 \) (from \( G^{\mathsf T}G = \mathrm{diag}(25, 0) \)), \( \mathbf{v}_1 = (1, 0) \), \( \mathbf{u}_1 = (0.6, 0.8) \).

\( \mathbf{m} = \frac{\mathbf{u}_1^{\mathsf T}\mathbf{d}}{\sigma_1}\mathbf{v}_1 = \frac{0.6(6) + 0.8(9)}{5}(1, 0) = \frac{10.8}{5}(1, 0) = (2.16,\ 0) \).

\( R = \mathbf{v}_1\mathbf{v}_1^{\mathsf T} = \mathrm{diag}(1, 0) \). The values 0.36 and 0.64 in (d) are the diagonal of the data resolution matrix; 2.25 is \( 9/4 \), from using the second datum alone.

Practice Q6. For a linear inverse problem \( \mathbf{d} = G\mathbf{m} \) with SVD \( G = U_p\Lambda_pV_p^{\mathsf T} \), consider:

  1. The squared singular values are the non-zero eigenvalues of \( G^{\mathsf T}G \).
  2. The model resolution matrix equals \( U_pU_p^{\mathsf T} \).
  3. Adding a vector from the model null space to the estimate changes the predicted data.
  4. The trace of the model resolution matrix equals the rank \( p \).

Which are correct?

(a) 1 and 4 only (b) 1, 2 and 4 only (c) 2 and 3 only (d) 1, 3 and 4 only

Answer: (a) 1 and 4 only
  1. True.
  2. False: \( R = V_pV_p^{\mathsf T} \); \( U_pU_p^{\mathsf T} \) is the data resolution matrix.
  3. False: by definition \( G\mathbf{m}_0 = 0 \) for \( \mathbf{m}_0 \) in the model null space, so the predictions do not change. That is exactly why such components cannot be resolved.
  4. True: \( \mathrm{tr}(V_pV_p^{\mathsf T}) = \mathrm{tr}(V_p^{\mathsf T}V_p) = \mathrm{tr}(I_p) = p \).

Practice Q7. A tomography kernel has singular values 5, 0.5 and 0.005. The noise component of the data along each data eigenvector is about 0.01. Which truncation is most sensible?

(a) Keep all three; the inverse is exact. (b) Keep \( \sigma_1 \) and \( \sigma_2 \), drop \( \sigma_3 \). (c) Keep only \( \sigma_1 \). (d) Keep only \( \sigma_3 \), since it is the most sensitive.

Answer: (b)

Each kept component adds model noise of about \( \frac{0.01}{\sigma_i} \): 0.002, 0.02 and 2. The third component would contribute an error of order 2, swamping any signal, so drop it. The second adds only 0.02 and brings real resolution, so keep it. (c) throws away usable information; (d) keeps only the worst-conditioned direction.

Quick Revision Table

IdeaFormula or fact
LS gradient, Gauss–Newton Hessian\( \mathbf{g} = -J^{\mathsf T}\mathbf{r} \), \( H \approx J^{\mathsf T}J \)
Steepest descent\( \mathbf{m} \leftarrow \mathbf{m} - \alpha\mathbf{g} \); zig-zags, linear convergence
Newton\( H\Delta\mathbf{m} = -\mathbf{g} \); one step on a quadratic
Gauss–Newton\( J^{\mathsf T}J\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r} \)
Levenberg–Marquardt\( (J^{\mathsf T}J + \lambda I)\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r} \); success: \( \lambda \downarrow \)
Conjugate gradientat most \( M \) steps on a quadratic; matrix–vector products only
Grid search cost\( n^M \) forward models
Nelder–Mead\( M + 1 \) vertices; reflect, expand, contract, shrink
SVD\( G = U\Lambda V^{\mathsf T} \); \( \sigma_i^2 \) = eigenvalues of \( G^{\mathsf T}G \); rank = number of non-zero \( \sigma \)
Generalized inverse\( G^{\dagger} = V_p\Lambda_p^{-1}U_p^{\mathsf T} \)
Resolution\( R = V_pV_p^{\mathsf T} \), \( N = U_pU_p^{\mathsf T} \), traces \( = p \)
Covariance\( \sigma_d^2V_p\Lambda_p^{-2}V_p^{\mathsf T} \)
Damping filter\( \sigma_i^2/(\sigma_i^2 + \varepsilon^2) \)
Metropolisaccept uphill with \( e^{-\Delta E/T} \)
GA resolutionrange / \( (2^n - 1) \)

Key Takeaways

What’s Next

Advertisement
Advertisement