Next: Synthetic Example
Up: Witten: Optimization
Previous: Introduction
The general form of the problem examined by Kim et al. (submitted) is
 
(1) 
where is the model, is an operator relating the
model to the data and is the model
value at point .
In this paper a very similar problem, of the form,
 
(2) 
will be explored. Here is a vector whose components range over vertical
travel time depth and whose values are the interval velocity
squared v^{2}_{int} and is the data vector which has the same
range as , but whose values are the scaled rootmean squared (RMS) velocities squared,
, where is the index on
the time axis. is the casual integration operator, and is a weight matrix which is proportional to
our confidence in the RMS velocities. As well, and are the first order
finitedifference derivatives along the midpoint and traveltime axis,
respectively, and and are
the regularization parameters that control the importance of the two
model residuals, effectively controlling the smoothing.
This problem can be transformed to a convex quadratic problem with
linear inequality constraints,
 

 
 (3) 
where serve to remove the absolute value from the
problem. The new problem (3) can be solved by interior
point methods (e.g. Wright (1997); Ye (1997)). With this goal in mind, we can
now construct
logarithmic barrier functions, which approximate an inequality
constraint by increasing to infinity as the point approaches the
constraint. For a simple problem,
 

 (4) 
the logarithmic barrier function is
 
(5) 
where t > 0 is a parameter the determines how closely you
approximate the constraint Boyd and Vandenberghe (2004).
For
the bound constraints in equation 3 the barrier functions are:
 
(6) 
and
 
(7) 
Now we can define the centering problem as,
 
(8) 
The centering problem is an equivalent representation to problem
(3) and has a unique
solution parametrized by t, called the central path which leads to
an optimal solution Boyd and Vandenberghe (2004). Newtons method can now be applied
to the centering problem, which involves solving a system on linear
equations,
 
(9) 
where is the Hessian and
is the gradient. Conjugate gradients is used to find an approximate
solution to this system. We differ from Kim et al. (submitted) by choosing
not to solve the whole system with conjugate gradients. Instead, and will be
solved analytically, decreasing the size of the system of equations
needed to be solved
solve from 3n to n, substantially reducing computational time.
`To solve for analytically, take the derivative of
with respect to , then solve for . This gives
 
(10) 
The same can be done for . We can also write the Hessian and gradient succinctly as,
 
(11) 
where
 
(12) 
where diag denotes a diagonal matrix with elements
.
The gradient can be written as
 

 (13) 
Since the Hessian is constructed from more than the linear operator (it
incorporates the barrier functions),
matrix multiplication is used to solve the system of equations in
the Newton system. Thus each step of the conjugate gradient is slow,
but time is saved by reducing the overall number of conjugate gradient
steps.
The final algorithm is:
given the update parameters for t, set the initial values
, , and .
repeat
1. Calculate and
2. Compute the search direction using conjugate gradients
3. Compute the step size s by backtracking line search
4. Update )
5. Calculate and update
6. Evaluate the duality gap and quit if appropriate (see Boyd and Vandenberghe (2004)
for more on Duality)
7. Update t
Next: Synthetic Example
Up: Witten: Optimization
Previous: Introduction
Stanford Exploration Project
5/6/2007