edu.mines.jtk.opt

Class QuadraticSolver

java.lang.Object

edu.mines.jtk.opt.QuadraticSolver

public class QuadraticSolver
extends java.lang.Object

Minimize a simple quadratic objective function. Finds the x that minimizes the quadratic function 0.5 x'Hx + b'x . Solves Hx + b = 0 for x (the Normal Equations of a least-squares problem) b is the gradient for x=0, and H is the hessian. The algorithm is a conjugate gradient. A is an approximate inverse Hessian, making AH more diagonal and improving convergence. A may also include a model-dependent conditioning to converge earlier on eigenfunction of most importance. The algorithm assumes that the application of H dominates the cost.

 x = p = u = 0;
 beta = 0;
 g = b;
 a = A g;
 q = H a;
 do {
 p = -a + beta p
 u = Hp = -q + beta u
 scalar = -p'g/p'u
 x = x + scalar p
 if (done) return x
 g = H x + b = g + scalar u
 a = A g
 q = H a
 beta = p'H A g / p'H p = p'q/p'u
 }
 

Also contains a solver for a least-squares inverse of a linear transform, using QuadraticTransform as a wrapper.

Constructor Summary

Constructors

Constructor and Description
QuadraticSolver(Quadratic quadratic) Implement the Quadratic interface and pass to this constructor.

Method Summary

Methods

Modifier and Type	Method and Description
Vect	solve(int numberIterations, Monitor monitor) Return a new solution after the number of conjugate gradient iterations.
static Vect	solve(VectConst data, VectConst referenceModel, LinearTransform linearTransform, boolean dampOnlyPerturbation, int conjugateGradIterations, Monitor monitor) Solve quadratic objective function for linear transform.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

QuadraticSolver

public QuadraticSolver(Quadratic quadratic)

Implement the Quadratic interface and pass to this constructor. Pass a vector b to the constructor (a copy is cloned internally). This solver calls Vect and Quadratic methods. Does not call Vect.multiplyInverseCovariance().

Parameters:

quadratic - Defines the Hessian quadratic term.

Method Detail

solve

public Vect solve(int numberIterations,
         Monitor monitor)

Return a new solution after the number of conjugate gradient iterations.

Parameters:

numberIterations - is the number of iterations to perform.

monitor - If non-null, then track all progress.

Returns:

Optimized solution

solve

public static Vect solve(VectConst data,
         VectConst referenceModel,
         LinearTransform linearTransform,
         boolean dampOnlyPerturbation,
         int conjugateGradIterations,
         Monitor monitor)

Solve quadratic objective function for linear transform. Minimizes

 [F(m+x)-data]'N[F(m+x)-data] + (m+x)'M(m+x)
 

if dampOnlyPerturbation is true and

 [F(m+x)-data]'N[F(m+x)-data] + (x)'M(x)
 

if dampOnlyPerturbation is false.

Parameters:

data - The data to be fit.

referenceModel - Initialize with this model.

linearTransform - Describes the linear transform.

dampOnlyPerturbation - If true then, only damp perturbations to reference model. If false, then damp the reference model plus the perturbation.

conjugateGradIterations - The specified number of conjugate gradient iterations.

monitor - Report progress here, if non-null.

Returns:

Result of optimization