Computational and Variational Inverse
Problems, Fall 2015
This is the 1994style web page for our class. Here you will find
everything you need (other than slick web design!).
Handouts:
 08/26/15: Class syllabus and other information
 08/26/15: Slides from course overview in the
first lecture (this is a 50Mb file, so make sure you have a fast
connection!)
 08/31/15: Notes on the prototype
deblurring inverse problem and regularization approaches
 09/02/15: Examples of spectrum of
inverse operators
 09/21/15: Properties of quadratic forms;
examples of convergence of steepest descent and Newton
 10/12/15: Brief notes on calculus of
variations and weak forms of boundary value problems
 10/14/15: Getting started
with FEniCS [Note: this document was updated on 11/03 to
include extensive
installation instructions for various operating systems.]
 10/14/15: A zip file
containing two IPython notebooks illustrating the use of
FEniCS for solution of a linear BVP and for minimization of the
nonquadratic energy functional discussed in class on 10/12; see
the enclosed README for instructions on running them. Update on
11/03: You can also obtain standalone python versions of the codes
in these two notebooks as well as static html versions of the
notebooks (which show the output when the notebooks are run)
from
this page created by Umberto Villa.
 10/28/15: An IPython
notebook illustrating the use of FEniCS for solving an inverse
problem for the coefficient field of a Poisson equation, using the
steepest descent method. Note that SD is a poor choice of
optimization method for this problem; it is provided here in order
to compare with Newton's method, which we'll be using later in the
class. Update on 11/03: You can also download the
code
PoissonDeterministicSD.py, which is just a standalone python
version of the code in the IPython notebook. Finally, if you are
having problems running the IPython notebook, you can view the
static html file
PoissonDeterministicSD.html, which shows you the output of
the notebook when you run it.
 11/03/15: Here
is
a page that contains all of Umberto's IPython notebooks for our
class. In addition to the notebooks, you can find standalone
python versions of the codes, as well as static html files that
show you what the IPython notebooks look like when you run them.
 11/03/15: Handwritten
notes on first and second order sensitivity analysis via direct,
adjoint, and Lagrangian methods for both discrete and
infinitedimensional systems.
 11/09/15:
Umberto has added an IPython notebook
to
his IPython notebook web page illustrating the use of FEniCS for
solving an inverse problem for the coefficient field of a Poisson
equation using the inexact Newton CG algorithm. As with other
IPython notebooks, there are .ipynb, .html, and .py versions
available for download.
 11/16/15: Umberto has added an IPython notebook
to
his IPython notebook web page demonstrating the use of
FEniCS/hIPPYlib to study spectral properties of the Hessian operator
for an advectiondiffusion source inverse problem (dependence of
Hessian spectrum on mesh size, diffusivity coefficient, and noise
level)
 12/02/15: A good, compact reference for the Bayesian approach to
inverse problems
is
"A Gentle Tutorial on Statistical Inversion using the Bayesian
Paradigm", by Tan
BuiThanh.
Assignments:

Assignment #1 (Due September 23)
You will need the following MATLAB functions and other files for
Assignment 1:

Assignment #2 (Due October 14)
 descent.m
and mycg.m. These are the Matlab codes that
implement the (exact) Newton method to minimize the Rosenbrock
function (i.e., the "banana" function); this was demoed in class on
Oct. 5. If you wish you can build on these for Assignment 2 (you
will have to add CG solution of the Newton system at each iteration
and incorporate early termination to enforce positive curvature and
to prevent "oversolving".)

Assignment #3 (Due November 2)
You will need the following files to solve Problems 2 and 3 using
FEniCS:
 circle.xml This file includes a finite
element mesh for the unit circle for Problem 2.
 tntv.py This file includes some starter
lines of python code for Problem 3 to define the mesh and finite
element space and to evaluate the true and noisy images at each
point of the mesh.
 unconstrainedMinimization.py
This file includes an implementation of inexact NewtonCG to solve
variational unconstrained minimization problems using
the EisenstatWalker termination condition and an Armijobased line
search (early termination due to negative curvature is not
necessary, since Problem 3 results in positive definite Hessians).
 energyMinimization.py
This file includes an example of how to use the inexact NewtonCG
nonlinear solver implemented in unconstrainedMinimization.py.
 image.dat This is the target image for
Problem 3 that is read into tntv.py.
 nb.py This includes some utilities to plot
functions on meshes. It's called by tntv.py. The default FEniCS
plotting function warps the mesh in the vertical direction
proportional to the magnitude of the field to be plotted, which
doesn't look good for the image functions.
Besides these files, general FEniCS resources you will find useful for
Problems 2 and 3 include the "Getting started with FEniCS" document
and the two python notebooks linked above under "Handouts" (and dated
10/14/15).

Assignment #4 (Due November 19)

Assignment #5 (Due December 14)
You will need the following files to solve Problem 2 using
FEniCS (in addition to the usual nb.py):
 cgsolver.py An implementation of
the standard conjugate gradient method (it will abort if it detects
negative curvature). This implementation is appropriate to use for
the GaussNewton approximation of the Hessian (which is guaranteed
to be positive definite).
 cgsolverSteihaug.py This is an
implementation of the conjugate gradient method that incorporates
the Steihaug termination criterion (for negative curvature). This is
required for the true Newton Hessian (which is not guaranteed to be
positive definite).
 PoissonInexactNewton.py
This is the driver for the solution of the Poisson inverse problem
using the inexact Newton method, with either the true Newton Hessian
or the GaussNewton approximation of the Hessian.
Instructions for using PoissonInexactNewton.py:
 To set the relative noise level and the regularization, you will
have to edit the variables "noise_level" and "beta" (lines 87 and 88).
 To change the forward problem from diffusion to
advectiondiffusion, you will have to change the bilinear form
"a_goal", which is used to generate the synthetic observations given
the true parameter field (line 94); you will also have to change
the bilinear forms "a_state" and "a_adj" for the forward and
adjoint problems and their incremental variants (lines 148 and
152).
 To switch between Newton and Gauss_Newton methods, you will have
to set the boolean flag "use_GaussNewton" in line 251. If the flag
"use_GaussNewton" is set to "False", the true Newton Hessian and
Steihaugenhanced CG will be used. If the flag "use_GaussNewton" is
set to "True", the Gauss Newton Hessian and standard CG will be
used.
Lectures (Mon/Wed 911am, GDC 6.202)
 08/26: Introduction to inverse problems
 08/31: Prototype inverse problem: image deblurring; filter
regularization, Tikhonov regularization
 09/02: Error analysis for TSVD and Tikhonov regularization;
choice of regularization parameter via Lcurve and Morozov
discrepancy principle
 09/09: Solutions of prototype image deblurring problem for
different regularization parameter, grid sizes, noise levels
 09/14: Unconstrained optimization: first and second order
optimality conditions; framework for a globally
convergent line search method
 09/21: Unconstrained optimization: Steepest descent method,
convergence and examples; properties of quadratic forms
 09/23: Unconstrained optimization: Newton's method and its
convergence rate; numerical examples
 09/28: Model PDEconstrained inverse problem and
structure/properties of its Hessian operator
 09/30: Unconstrained optimization: approximate Newton methods
(BFGS, limited memory BFGS, LevenbergMarquardt, modified Cholesky,
GaussNewton)
 10/05: Unconstrained optimization: Inexact Newtonconjugate
gradient method
 10/07: Introduction to variational calculus: linear elliptic
boundary value problem
 10/12: Introduction to variational calculus: nonlinear elliptic
boundary value problem; infinitedimensional Newton's method
 10/14: Introduction to the FEniCS library for finite element
solution of boundary value problems posed in weak form
 10/19: Discretization of functionals and weak forms by finite
elements; optimizethendiscretize vs. discretizethenoptimize
 10/21: No class
 10/26: Sensitivity analysis: computing the discrete gradient via
the direct, adjoint, and Lagrangian methods; computing the
infinitedimensional gradient via the direct and adjoint methods
 10/28: Sensitivity analysis: computing the infinitedimensional
gradient via the Lagrangian method; using hIPPYlib to solve inverse
problems governed by PDEs using steepest descent
 11/02: Sensitivity analysis: computing the discrete
Hessianvector product and infinite dimensional Hessian action via
the second order Lagrangian
 11/04: Discretization of inverse problems:
optimizethendiscretize and discretizethenoptimize
 11/09: Using hIPPYlib to solve inverse problems governed by PDEs
using inexact Newtonconjugate gradients (Poisson log conductivity
inversion example)
 11/11: Sensitivity analysis: Nonlinear forward problems, mixed
and inhomogeneous boundary conditions, boundary observations, and
boundary inversion parameters
 11/16: Use of FEniCS/hIPPYlib to study spectral properties of the
Hessian operator for an advectiondiffusion source inverse problem
(dependence of the Hessian spectrum on mesh size, diffusivity
coefficient, and noise level)
 11/18: No class
 11/23: Sensitivity analysis: Nonlinear forward problems, mixed
and inhomogeneous boundary conditions, boundary observations, and
boundary inversion parameters continued
 11/25: No class
 11/30: Sensitivity analysis: Time dependent advectiondiffusion
inverse problem
 12/02: Bayesian approach to inverse problems; illustration for
Antarctic ice sheet flow