next up previous [pdf]

Next: Formulation Up: Linear Programming Previous: Theory

Mapping Optimization Problems to Linear Programming

This maps to our conventional model-fitting treatment using optimization theory according to the following:

$\displaystyle x_i$ $\displaystyle \xrightarrow[$parameter space$\displaystyle ]{}$ model space (6)
$\displaystyle c_i$ $\displaystyle \xrightarrow[$objective function$\displaystyle ]{}$ regularization (7)
$\displaystyle a_{ij}$ $\displaystyle \xrightarrow[$constraint functions$\displaystyle ]{}$ forward operator (8)
$\displaystyle b_j$ $\displaystyle \xrightarrow[$constraint vector$\displaystyle ]{}$ data space (9)

with $ i=1..$(model size) and $ j=1..$(data size) Conveniently, this allows a direct representation of geophysical data fitting, including regularization on the model space. This linear programming setup can be represented in matrix form, as follows:


$\displaystyle {\bf c}^T {\bf x} = Z$     (10)
$\displaystyle {\bf A x \leq b}$     (11)

I have introduced the scalar, $ Z$, which is the value of the objective. This will be either minimized or maximized depending on the particular geophysical problem. Effectively, this means finding a value for $ \bf {x}$ that optimally aligns with the model-fitting and data-fitting goals.

Correspondingly, for a simple $ 2\times3$ example:

$\displaystyle \begin{bmatrix}c_1& c_2\end{bmatrix} \begin{bmatrix}x_1 \ x_2 \end{bmatrix} = Z$ (12)

$\displaystyle \begin{bmatrix}a_{11} & a_{12} \ a_{21} & a_{22} \ a_{31} & a_{...
...ix}x_1 \ x_2 \end{bmatrix} \leq \begin{bmatrix}b_1 \ b_2 \ b_3 \end{bmatrix}$ (13)

To solve according to the $ L_1$ norm, we need to take account of the absolute value in the definition of the $ L_1$ error criteria, noting that the $ i^{th}$ element of the residual is defined as an absolute value of the error term:

$\displaystyle r_i = \vert {\bf L m - d} \vert$ (14)

To account for this, we extend the linear programming matrix representation to augmented form. This requires an extension of the $ {\bf x}$ vector. The approach is not entirely dissimilar to the placement of a regularization in the model vector in a conventional setup, in that it is reformulating the equations to provide us with a fit in compliance with our a priori geophyiscal knowledge.

The augmented representation is written in matrix form as

$\displaystyle \begin{bmatrix}{\bf 1} & -{\bf c}^T & {\bf0} \ {\bf0} & {\bf A} ...
... x} \ {\bf x_s} \end{bmatrix} = \begin{bmatrix}{\bf0} \ {\bf b} \end{bmatrix}$ (15)

The first row of the augmented form results in the optimization criteria:

$\displaystyle Z - {\bf c}^T{\bf x} = 0$ (16)

A large value of Z maximizes the original objective function, subject to the constraints in the $ {\bf c}$ matrix. The goal is to put as much ``energy'' in the Z (objective function) with as little energy in all other rows of the augmented matrix; this is accomplished with the Simplex Algorithm, simultaneously satisfying the minimization of the pure $ L_1$ norm criteria.


next up previous [pdf]

Next: Formulation Up: Linear Programming Previous: Theory

2009-10-19