The concept of duality gap function in infinite dimensional linear programming is considered in this paper. Basic properties of the function and two theorems on its behavior are obtained by using duality theorems with...
详细信息
The concept of duality gap function in infinite dimensional linear programming is considered in this paper. Basic properties of the function and two theorems on its behavior are obtained by using duality theorems with interior conditions. As illustrations for the results, we investigate the parametric versions of an example due to D. Gale and parametric linear programs on spaces of continuous functions. The notions of Riemann-Stieltjes integral and function of bounded variation have been shown to be very useful for our investigations. (C) 2015 Published by Elsevier Inc.
We consider linearprogramming (LP) problems in infinitedimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinitedimensional...
详细信息
We consider linearprogramming (LP) problems in infinitedimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinitedimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of randomized optimization and first-order methods, leading to a priori as well as a posteriori performance guarantees. We illustrate the generality and implications of our theoretical results in the special case of the long-run average cost and discounted cost optimal control problems in the context of Markov decision processes on Borel spaces. The applicability of the theoretical results is demonstrated through a fisheries management problem.
The classical problem of optimal transportation can be formulated as a linear optimization problem on a convex domain: among all joint measures with fixed marginals find the optimal one, where optimality is measured a...
详细信息
The classical problem of optimal transportation can be formulated as a linear optimization problem on a convex domain: among all joint measures with fixed marginals find the optimal one, where optimality is measured against a cost function. Here we consider a natural but largely unexplored variant of this problem by imposing a pointwise constraint on the joint (absolutely continuous) measures: among all joint densities with fixed marginals and which are dominated by a given density, find the optimal one. For this variant, we show that local non-degeneracy of the cost function implies every minimizer is extremal in the convex set of competitors, hence unique. An appendix develops rudiments of a duality theory for this problem, which allows us to compute several suggestive examples.
A variant of the classical optimal transportation problem is the following: among all joint measures with fixed marginals and that are dominated by a given density, find the optimal one. Existence and uniqueness of so...
详细信息
A variant of the classical optimal transportation problem is the following: among all joint measures with fixed marginals and that are dominated by a given density, find the optimal one. Existence and uniqueness of solutions to this variant were established by Korman and McCann. In the present article, we expose an unexpected symmetry leading to explicit examples in two and more dimensions. These are inspired in part by simulations in one dimension that display singularities and topology and in part by two further developments: the identification of all extreme points in the feasible set and an approach to uniqueness based on constructing feasible perturbations.
Given two densities on R^n with the same total mass, the Monge transport problem is to find a Borel map s : R^n → R^n rearranging the first distribution of mass onto the second, while minimizing the average distance ...
详细信息
Given two densities on R^n with the same total mass, the Monge transport problem is to find a Borel map s : R^n → R^n rearranging the first distribution of mass onto the second, while minimizing the average distance transported. Here distance is measured by a norm with a uniformly smooth and convex unit ball. This paper gives a complete proof of the existence of optimal maps under the technical hypothesis that the distributions of mass be compactly supported. The maps are not generally unique. The approach developed here is new, and based on a geometrical change-of-variables technique offering considerably more flexibility than existing approaches.
Up to this time, the only known method to solve the discrete-time mixed sensitivity minimization problem in l1 has been to use a certain infinite-dimensionallinearprogramming approach, presented by Dahleh and Pearso...
详细信息
Up to this time, the only known method to solve the discrete-time mixed sensitivity minimization problem in l1 has been to use a certain infinite-dimensionallinearprogramming approach, presented by Dahleh and Pearson in 1988 and later modified by Mendlovitz. That approach does not give in general true optimal solutions;only suboptimal ones are obtained. Here, for the first time, the true l1-optimal solutions are found for some mixed sensitivity minimization problems. In particular, Dahleh and Pearson construct an 11th order suboptimal compensator for a certain second-order plant with first-order weight functions;it is shown that the unique optimal compensator for that problem is rational and of order two. The author discovered this fact when trying out a new scheme of solving the infinite-dimensionallinearprogramming system. This scheme is of independent interest, because when it is combined with the Dahleh-Pearson-Mendlovitz scheme, it gives both an upper bound and a lower bound on the optimal performance;hence, it provides the missing error bound that enables one to truncate the solution. Of course, truncation is appropriate only if the order of the optimal compensator is too high. This may indeed be the case, as is shown with an example where the order of the optimal compensator can be arbitrarily high.
A new, simple, constraint qualification for infinitedimensional programs with linearprogramming type constraints is used to derive the dual program; see Theorem 3.1. Applications include a proof of the explicit solu...
详细信息
A new, simple, constraint qualification for infinitedimensional programs with linearprogramming type constraints is used to derive the dual program; see Theorem 3.1. Applications include a proof of the explicit solution of the best interpolation problem presented in [8].
暂无评论