NUMERICAL OPTIMIZATION FOR TRANSPORT AND REGISTRATION PROBLEMS Open Access

Abstract

NUMERICAL OPTIMIZATION FOR TRANSPORT AND REGISTRATION PROBLEMS

by
Raya Horesh

In this thesis we develop numerical methods for the solution of large-scale PDE-based constrained optimization problems. Overall three studies
are presented; the first two are application driven, addressing volume preserving image registration and optimal mass transport problems. The third
study is more generic and embarks at the development of a new inexact sequential quadratic programming framework. Image registration aims at
finding a plausible transformation which aligns images taken at different times, different view-points or by different modalities. This problem is ill-
posed and therefore, regularization is required. In that study, elastic regularizer is considered along with volume preserving constraint. A numerical
framework based on augmented Lagrangian along with geometrical multi-grid preconditioner was devised. The proposed algorithm was tested with
real data. The optimal mass transport seeks for an optimal way to move a pile of soil from one site to another using minimal energy, while preserving
the overall mass. In that study, a fluid dynamics formulation was considered. This formulation introduces an artificial time stepping, which on the
one hand transforms the non-convex problem to a convex one, but on the other hand increases the dimensionality of the problem. A Schur comple-
ment and algebraic multigrid formed a preconditioner within a sequential quadratic programming scheme. Results for both three and four dimensional
problems were presented. Inside each step of nonlinear optimization, solution for an ill-conditioned, indefinite linear system, known as a KKT system
is required. As problem size increases, linear iterative solvers become the bottleneck of the optimization scheme. In the third study, a new approach
for inexact step computation is proposed. The general idea is to reduce the number of linear iteration while still maintaining convergence of the overall
scheme. This is done, by the embedment of a filter inside a linear solver.

Table of Contents

1 Introduction 8

1 Image Registration - Problem Statement . . . . . . . . . . . . 9

1.1 An Image . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Distance Measure . . . . . . . . . . . . . . . . . . . . . 9

1.3 Feasible Transformation . . . . . . . . . . . . . . . . . 10

2 Optimal Mass Transport . . . . . . . . . . . . . . . . . . . . . 15

2.1 Monge-Kantorovich Problem . . . . . . . . . . . . . . . 15

2.2 Fluid Dynamics Framework for the Monge-

Kantorovich Problem . . . . . . . . . . . . . . . . . . . 17

3 Inexact Sequential Quadratic Programming . . . . . . . . . . 18

4 Contributions of this Thesis . . . . . . . . . . . . . . . . . . . 22

2 Background for Relevant Numerical Tools 25

1 Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Constrained Optimization Problem - De nition . . . . . . . . 26

3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Optimality Conditions for Equality Constrained Optimization 28

5 Optimality Conditions for Inequality Constrained Optimization 29

6 Sequential Quadratic Programming . . . . . . . . . . . . . . . 30

7 Line Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

8 Log-Barrier Method . . . . . . . . . . . . . . . . . . . . . . . . 33

1

9 Augmented Lagrangian Method . . . . . . . . . . . . . . . . . 33

10 Stationary Linear Solvers . . . . . . . . . . . . . . . . . . . . . 35

10.1 Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

10.2 Gauss - Seidel . . . . . . . . . . . . . . . . . . . . . . . 35

11 Non-stationary Iterative Methods - Krylov Subspace Methods 36

11.1 Conjugate Directions . . . . . . . . . . . . . . . . . . . 37

11.2 Conjugate Gradient (CG) . . . . . . . . . . . . . . . . 39

11.3 Generalized Minimal Residual Method (GMRES) . . . 40

12 Multi-grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3 Volume Preserving Image Registration 45

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2 Mathematical Formulation and Discretization . . . . . . . . . 47

2.1 Continuous Formulation . . . . . . . . . . . . . . . . . 47

2.2 Discretization . . . . . . . . . . . . . . . . . . . . . . . 49

3 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.1 Augmented Lagrangian Method . . . . . . . . . . . . . 53

3.2 Minimization of the Augmented Lagrangian . . . . . . 54

4 Multi-grid Solver . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.1 Smoother . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2 Prolongation and Restriction Operators . . . . . . . . . 57

4.3 Coarse Grid Solver . . . . . . . . . . . . . . . . . . . . 57

4.4 Discretization Properties . . . . . . . . . . . . . . . . . 57

5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . 61

6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4 Mass Preserving Image Registration 71

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

2 Problem Reformulation . . . . . . . . . . . . . . . . . . . . . . 74

3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . 83

6 Conclusions and Summary . . . . . . . . . . . . . . . . . . . . 89

5 Filter-Based Inexact SQP Method 91

1 Background and Motivation . . . . . . . . . . . . . . . . . . . 91

2 Filter Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3 Constrained Optimization Framework . . . . . . . . . . . . . . 97

4 Inexact SQP Framework . . . . . . . . . . . . . . . . . . . . . 98

5 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . 101

5.1 Generalized Laplace Inverse Problem . . . . . . . . . . 101

5.2 Optimal Mass Transport . . . . . . . . . . . . . . . . . 103

5.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . 104

6 Summary and Future Work 106

Bibliography 110

Index 121

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Keyword	Numerical Optimization
Committee Chair / Thesis Advisor	Haber, Eldad, Emory University
Committee Members	Veneziani, Alessandro, Emory University Nagy, James, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	NUMERICAL OPTIMIZATION FOR TRANSPORT AND REGISTRATION PROBLEMS ()	2018-08-28 12:49:21 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions