Computational and Variational Inverse
Problems, Fall 2015
This is the 1994-style 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
non-quadratic 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
PoissonDeterministic-SD.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
PoissonDeterministic-SD.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
infinite-dimensional 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 advection-diffusion 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
Bui-Thanh.
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 demo-ed 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 "over-solving".)
-
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 Newton-CG to solve
variational unconstrained minimization problems using
the Eisenstat-Walker termination condition and an Armijo-based 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 Newton-CG
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 Gauss-Newton 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).
- Poisson-InexactNewton.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 Gauss-Newton approximation of the Hessian.
Instructions for using Poisson-InexactNewton.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
advection-diffusion, 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
Steihaug-enhanced 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 9-11am, 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 L-curve 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 PDE-constrained inverse problem and
structure/properties of its Hessian operator
- 09/30: Unconstrained optimization: approximate Newton methods
(BFGS, limited memory BFGS, Levenberg-Marquardt, modified Cholesky,
Gauss-Newton)
- 10/05: Unconstrained optimization: Inexact Newton-conjugate
gradient method
- 10/07: Introduction to variational calculus: linear elliptic
boundary value problem
- 10/12: Introduction to variational calculus: nonlinear elliptic
boundary value problem; infinite-dimensional 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; optimize-then-discretize vs. discretize-then-optimize
- 10/21: No class
- 10/26: Sensitivity analysis: computing the discrete gradient via
the direct, adjoint, and Lagrangian methods; computing the
infinite-dimensional gradient via the direct and adjoint methods
- 10/28: Sensitivity analysis: computing the infinite-dimensional
gradient via the Lagrangian method; using hIPPYlib to solve inverse
problems governed by PDEs using steepest descent
- 11/02: Sensitivity analysis: computing the discrete
Hessian-vector product and infinite dimensional Hessian action via
the second order Lagrangian
- 11/04: Discretization of inverse problems:
optimize-then-discretize and discretize-then-optimize
- 11/09: Using hIPPYlib to solve inverse problems governed by PDEs
using inexact Newton-conjugate 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 advection-diffusion 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 advection-diffusion
inverse problem
- 12/02: Bayesian approach to inverse problems; illustration for
Antarctic ice sheet flow
