For my doctoral research, I developed new numerical methods for optimal transportation. Numerical optimal transportation is application-focused. It requires a solid understanding of numerical partial differential equation methods, network flow techniques, and ways the two can be combined and extended.
Optimal transportation is applicable to a wide range of problems in a variety of fields. Studying such versatile techniques gives me all the excuse I need to explore and enjoy new topics, mathematical and otherwise.
A brief history of numerical optimal transport, the algorithms I have developed, mathematical contributions, numerical results, and objectives for future research.
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation with Luca Dieci of the Georgia Institute of Technology. [arXiv:1702.03517] Spring 2018.
Abstract. We introduce a new technique, which we call the boundary method, for solving semi-discrete optimal transport problems with a wide range of cost functions. The boundary method reduces the effective dimension of the problem, thus improving complexity. For cost functions equal to a p-norm with p ∈ (1,∞), we provide mathematical justification, convergence analysis, and algorithmic development. Our testing supports the boundary method with these p-norms, as well as other, more general cost functions.
- Uniqueness of optimal solutions for semi-discrete transport with p-norm cost functions. Summer 2017. [arXiv:1705.09383]
Abstract. Semi-discrete transport can be characterized in terms of real-valued shifts. Often, but not always, the solution to the shift-characterized problem partitions the continuous region. This paper gives examples of when partitioning fails, and offers a large class of semi-discrete transport problems where the shift-characterized solution is always a partition.
- General auction method for real-valued optimal transport with Luca Dieci of the Georgia Institute of Technology. [arXiv:1705.06379] Summer 2016.
Abstract. The auction method developed by Bertsekas in the late 1970s is a relaxation technique for solving integer-valued assignment problems. It resembles a competitive bidding process, where unsatisfied persons (bidders) attempt to claim the objects (lots) offering the best value. By transforming integer-valued transport problems into assignment problems, the auction method can be extended to compute optimal transport solutions. We propose a more general auction method that can be applied directly to real-valued transport problems. We prove termination and provide a priori error bounds for the general auction method. Our numerical results indicate that the complexity of the general auction is roughly comparable to that of the original auction method, when the latter is applicable.
- Successive Subdivision Methods for transportation networks of images and other grid graphs with Michael Muskulus of the Norwegian University of Science and Technology. Spring 2017.
Abstract. A variety of methods already exist for computing solutions to discrete optimal transport problems, but all of those methods are designed to work on abstract networks. We propose a new optimal transport technique, the method of successive subdivision, or SSD, as a way of leveraging known positional information to reduce computation time and complexity. We then compare the performance of a specific, multigrid-style SSD against some standard methods, and consider the scaling behavior of our software in order to acquire information about the method’s average complexity. Our results show that multigrid-style SSD is significantly faster than standard solution methods, especially for large transport problems. We therefore conclude that the SSD approach offers a promising way of using the structure of the embedding space to solve optimal transport problems more efficiently.
- Topological models for 3-configurations with Arthur White of Western Michigan University. Fall 2014.
Abstract. Models of geometries are desirable for verifying properties of consistency, completeness, and independence of axiom systems. We consider 3-configurations of order v (for 3 ≤ v ≤ 100) and replication number r, with necessarily v ≥ 2r + 1 and 3 | vr. For each of the 1345 such pairs (v, r), we find a topological model for one corresponding 3-configuration, focusing on Steiner Triple Systems and partially balanced incomplete block designs where possible.
- “A real-valued auction algorithm for optimal transport.” 2018 Conference on Data Analysis poster presentation. March 2018.
Abstract. Optimal transportation theory is an area of mathematics with real-world applications in fields ranging from economics to optimal control to machine learning. We propose a new algorithm for solving discrete transport (network flow) problems, based on classical auction methods. In commerce, auctions are a time-tested method of obtaining optimal object prices from a group of competing bidders. During the 1970s, Dimitri Bertsekas developed an auction-based algorithm, as an alternative to the Hungarian method for the assignment problem. He and David Castañón later published an auction algorithm for integer-valued optimal transport that solves by converting transport problems into assignment problems. The general transport auction method we propose works directly on real-valued transport problems. Our results prove termination, bound the transport error, and relate our algorithm to the algorithm of Bertsekas and Castañón.
- “An auction algorithm for real-valued optimal transport.” Georgia Institute of Technology 10 to 60 celebration talk. December 2017.
Abstract. In commerce, auctions are a time-tested method of obtaining optimal object prices from a group of competing bidders. In the 1970s, Dimitri Bertsekas developed an auction-based algorithm, as an alternative to the Hungarian method for the assignment problem. He and David Castañón later published an auction algorithm for integer-valued optimal transport that solves by converting transport problems into assignment problems. We propose a more general auction algorithm that works directly on real-valued transport problems and describe its connection to the algorithm of Bertsekas and Castañón.
- “The boundary method for optimal mass transportation and Wasserstein distance computation.” Georgia Institute of Technology Mathematics and Applications Portal Working Group for Problems in Transport and Related Topics in Graphs talk. May 2017.
Abstract. Numerical optimal transport is an important area of research, but many problems are too large and complex for easy computation. Because continuous transport problems are generally solved by conversion to semi-discrete forms, we developed the boundary method for semi-discrete transport. The boundary method works with unaltered ground cost functions. It rapidly identifies region boundaries: locations in the continuous space where transport destinations change. Because the method concentrates computation over those boundaries, rather than the entire continuous space, it reduces the effective dimension of the discretization. The boundary method is an effective mesh generation method, able to solve many transport problems that are intractable using other approaches. Even where other numerical methods exist, our tests indicate that the boundary method's performance will compare favorably.
- “The boundary method for numerical optimal transport.” Georgia Institute of Technology Applied and Computational Mathematics seminar talk. November 2016.
Abstract. The boundary method is a new algorithm for solving semi-discrete transport problems involving a variety of ground cost functions. By reformulating a transport problem as an optimal coupling problem, one can construct a partition of its continuous space whose boundaries allow accurate determination of the transport map and its associated Wasserstein distance. The boundary method approximates region boundaries using the general auction algorithm, controlling problem size with a localized refinement approach. This talk describes numerical and mathematical results obtained when the ground cost is a convex combination of lp norms, and shares preliminary work involving other ground cost functions.
- “Numerical methods for optimal coupling.” Georgia Institute of Technology College of Sciences School Visits talk. April 2016.
- “Blending continuous and discrete methods to compute optimal transport partitions.” Hale Conference: Dynamics of Evolution Equations poster presentation. March 2016.
Abstract. Optimal transportation can be used to partition a continuous region based on a set of discrete points, but such partitions are difficult to determine exactly and they have been nearly as hard to approximate numerically. We propose a new numerical technique, combining discrete and continuous methods, that generates faster and more accurate results than existing techniques. By considering the optimal transportation problem as an optimal coupling problem, we developed a semi-stable descent method and combined that with a network technique that exploits region continuity to reduce complexity.
- “Computing Optimal Coupling Systems by Blending Continuous and Discrete Methods.” Georgia Scientific Computing Symposium poster presentation and short talk. February 2016.
National Science Foundation Awards
Other Awards and Activities
- Undergraduate Research and Creative Activities Award. Western Michigan University. 2012 recipient.
- Explorations in Science Research. University of California Berkeley multidisciplinary research experience for undergraduates. 2011 participant.
Explorations in Science Research is a seven day workshop for quantitatively-inclined undergraduates majoring in science, technology, engineering, or mathematics. Students are given the opportunity to work with large data sets of environmentally-relevant information. They are challenged to represent and interpret this data in ways that best communicate its implications to the public. Considering these challenges lets students see how science influences policymaking and general understanding. During the workshop, students gain a basic understanding of computing and visualization tools, and they develop their own data-driven, environmentally-conscious projects.