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
On this page · 14 sections
Prerequisites
- Well- and Ill-Posed Problems and Least Squares: the normal equations, minimum-norm and damped solutions, and linearisation with the Jacobian. This page builds directly on them.
- Eigenvalues, orthogonal matrices and the spectral theorem: Inner Product Spaces and Orthonormal Bases.
- Newton’s method for roots and its quadratic convergence: Numerical Analysis in Mathematical Sciences.
- Chapter map: Numerical Analysis and Inversion.
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 --> HGradient 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.
| Method | How it works | Strength | Weakness |
|---|---|---|---|
| Grid (exhaustive) search | evaluate \( \phi \) at every node of a regular grid | finds the global minimum on the grid; maps the whole misfit surface | cost \( n^M \) grows explosively with \( M \) |
| Coordinate (one-at-a-time) search | vary one parameter at a time | very simple | slow when parameters trade off (diagonal valleys) |
| Pattern search (Hooke–Jeeves type) | exploratory moves, then a jump along the improving pattern | handles diagonal valleys better | local only |
| Nelder–Mead downhill simplex | a simplex of \( M + 1 \) points; reflect the worst point through the centroid of the rest, then expand, contract or shrink | robust, 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:
| Space | Spanned by | Meaning |
|---|---|---|
| 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
| Matrix | Definition | Perfect case | Reading 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
| Approach | Filter applied to the \( i \)th component | Effect |
|---|---|---|
| Truncated SVD | 1 if \( \sigma_i \) is kept, 0 if discarded | drop 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.
Monte Carlo (random) search
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 \).
- Perturb the current model at random; compute \( \Delta E = E_{\text{new}} - E_{\text{old}} \).
- Metropolis criterion: if \( \Delta E \le 0 \), accept. If \( \Delta E > 0 \), accept with probability $$\boxed{P = e^{-\Delta E/T}}$$
- 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.
- Encode each model as a string (classically binary; real-valued codings are also used).
- Fitness: evaluate each model (fitness is high where misfit is low).
- Selection: fitter models are more likely to become parents.
- Crossover: exchange segments of two parent strings to make offspring.
- Mutation: flip occasional bits at random, preserving diversity.
- 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 derivatives | yes | no | no |
| Forward models needed | few (tens) | many; grid grows as \( n^M \) | very many (thousands to millions) |
| Finds global minimum | only if started in its basin | grid: yes (on the grid); simplex: no | likely, not guaranteed |
| Best for | smooth, near-linear problems; large \( M \) with good start | few parameters, noisy misfit | few 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
| This | vs | That |
|---|---|---|
| Newton: full Hessian, second derivatives | Gauss–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 data | Data null space: cannot be predicted by any model | |
| Truncated SVD: sharp cut-off | Damped LS: smooth filter \( \sigma^2/(\sigma^2 + \varepsilon^2) \) | |
| Simulated annealing: one model, random walk with Metropolis acceptance | Genetic 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
- Write the Gauss–Newton equation for the model update.
- How many vertices does the Nelder–Mead simplex have for a problem with 4 parameters?
- Write the Metropolis acceptance probability for an uphill move in simulated annealing.
Answers
- \( J^{\mathsf T}J\,\Delta\mathbf{m} = J^{\mathsf T}\mathbf{r} \), with \( \mathbf{r} = \mathbf{d} - g(\mathbf{m}) \).
- 5 (\( M + 1 \)).
- \( 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:
- The squared singular values are the non-zero eigenvalues of \( G^{\mathsf T}G \).
- The model resolution matrix equals \( U_pU_p^{\mathsf T} \).
- Adding a vector from the model null space to the estimate changes the predicted data.
- 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
- True.
- False: \( R = V_pV_p^{\mathsf T} \); \( U_pU_p^{\mathsf T} \) is the data resolution matrix.
- 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.
- 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
| Idea | Formula 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 gradient | at 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) \) |
| Metropolis | accept uphill with \( e^{-\Delta E/T} \) |
| GA resolution | range / \( (2^n - 1) \) |
Key Takeaways
What’s Next
- Numerical Analysis and Inversion: Quick Revision: the whole unit on one page.
- Revisit Well- and Ill-Posed Problems and Least Squares with the SVD in mind: every formula there is a filter on singular values.
- The deconvolution filters in Filters, Deconvolution and Fractal Analysis are least-squares inverse problems of exactly this kind.
- Back to the Earth Sciences overview.