Convex Optimization

A problem is a convex optimization problem if it has the form

$$\begin{eqnarray} \mbox{minimize } f_0(x)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \nonumber\ \mbox{subject to } f_i(x) \leq b_i,\mbox{ } i=1,\ldots,m \end{eqnarray}$$ (3)

where $f_0,\ldots,f_m$ and $b_1,\ldots,b_m$ are convex functions and x exists in a convex set, $\bf S$ Boyd and Vandenberghe (2004). Convex optimization problems have many attractive features including the guarantee of local minima to be global and strong optimality, feasibility, and sensitivity information. As well, there are reliable and efficient numerical algorithms to solve these problems. Since this Dix formulation is a least-squares problem, which is already convex, it seems natural to try convex optimization techniques to find the solution.

The data fitting goal, equation (1), can be rewritten in optimization notation as

$$\mbox{minimize } \Vert \bf{W(Cu-d)}\Vert _2$$ (4)

where $\Vert \cdot \Vert _2$ means the least-squares norm. When necessary regularization terms are added the full set of goals, equation (2) becomes  

$$\mbox{minimize } \Vert\bf{W(Cu-d)}\Vert _2+\Vert\bf \epsilon_{\tau} D_{\tau}u\Vert _i+\Vert\bf \epsilon_{x} D_{\tau} u\Vert _i$$ (5)

in optimization notation. If i is 2 then an $\ell_2$ regularization is used and a smooth model is obtained. If i is 1 then an $\ell_1$ regularization is used and the result is a blocky model, instead.

Even after inversion, there may be points in the model space which do not make geological sense, usually due to picking errors caused by poor resolution. Convex optimization allows for bound constraints to be imposed on the solution, which can correct for such inconsistencies. If we constrain the solution then we have

$$\begin{eqnarray} \mbox{minimize } \Vert\bf{W(Cu-d)}\Vert _2+\Vert\bf \epsilon_{\... ...~~~~~~~\nonumber \ u \geq v_{\rm{min}}, ~~~~~~~~~~~~~~~~~~~~~~~~~\end{eqnarray}$$ (6)

where $v_{\rm{max}}$ and $v_{\rm{min}}$ are the square of the maximum and minimum allowable velocity models, respectively.

To do the convex optimization, $\bf cvx$ Grant et al. (2006) will be used. $\bf cvx$ is a MATLAB based system for solving convex optimization problems. It allows constraints and objectives to be specified with common MATLAB syntax.