Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneral auction method for real-valued optimal transport
83
0
0.0
(
0
)
Added by
Joseph Walsh III
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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. Auction methods were originally developed as an alternative to the Hungarian method for the assignment problem, so the classic auction-based algorithms solve integer-valued optimal transport by converting such 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 classic algorithms of Bertsekas and Castanon.
rate research
Read More
A simple procedure to map two probability measures in $mathbb{R}^d$ is the so-called emph{Knothe-Rosenblatt rearrangement}, which consists in rearranging monotonically the marginal distributions of the last coordinate, and then the conditional distributions, iteratively. We show that this mapping is the limit of solutions to a class of Monge-Kantorovich mass transportation problems with quadratic costs, with the weights of the coordinates asymptotically dominating one another. This enables us to design a continuation method for numerically solving the optimal transport problem.
We consider shape optimization problems for general integral functionals of the calculus of variations, defined on a domain $Omega$ that varies over all subdomains of a given bounded domain $D$ of ${bf R}^d$. We show in a rather elementary way the existence of a solution that is in general a quasi open set. Under very mild conditions we show that the optimal domain is actually open and with finite perimeter. Some counterexamples show that in general this does not occur.
We consider a given region $Omega$ where the traffic flows according to two regimes: in a region $C$ we have a low congestion, where in the remaining part $Omegasetminus C$ the congestion is higher. The two congestion functions $H_1$ and $H_2$ are given, but the region $C$ has to be determined in an optimal way in order to minimize the total transportation cost. Various penalization terms on $C$ are considered and some numerical computations are shown.
We develop a novel optimization model to maximize the profit of a Demand-Side Platform (DSP) while ensuring that the budget utilization preferences of the DSPs advertiser clients are adequately met. Our model is highly flexible and can be applied in a Real-Time Bidding environment (RTB) with arbitrary auction types, e.g., both first and second price auctions. Our proposed formulation leads to a non-convex optimization problem due to the joint optimization over both impression allocation and bid price decisions. Using Fenchel duality theory, we construct a dual problem that is convex and can be solved efficiently to obtain feasible bidding prices and allocation variables that can be deployed in a RTB setting. With a few minimal additional assumptions on the properties of the auctions, we demonstrate theoretically that our computationally efficient procedure based on convex optimization principles is guaranteed to deliver a globally optimal solution. We conduct experiments using data from a real DSP to validate our theoretical findings and to demonstrate that our method successfully trades off between DSP profitability and budget utilization in a simulated online environment.
We investigate the problem of optimal transport in the so-called Kantorovich form, i.e. given two Radon measures on two compact sets, we seek an optimal transport plan which is another Radon measure on the product of the sets that has these two measures as marginals and minimizes a certain cost function. We consider quadratic regularization of the problem, which forces the optimal transport plan to be a square integrable function rather than a Radon measure. We derive the dual problem and show strong duality and existence of primal and dual solutions to the regularized problem. Then we derive two algorithms to solve the dual problem of the regularized problem: A Gauss-Seidel method and a semismooth quasi-Newton method and investigate both methods numerically. Our experiments show that the methods perform well even for small regularization parameters. Quadratic regularization is of interest since the resulting optimal transport plans are sparse, i.e. they have a small support (which is not the case for the often used entropic regularization where the optimal transport plan always has full measure).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
