Mass Transportation with LQ Cost Functions

We study the optimal transport problem in the Euclidean space where the cost function is given by the value function associated with a Linear Quadratic minimization problem. Under appropriate assumptions, we generalize Brenier’s Theorem proving existence and uniqueness of an optimal transport map. In the controllable case, we show that the optimal transport map has to be the gradient of a convex function up to a linear change of coordinates. We give regularity results and also investigate the non-controllable case.     

Average case complexity of linear multivariate problems I. Theory

We study the average case complexity of linear multivariate problems, that is, the approximation of continuous linear operators on functions of d variables. The function spaces are equipped with Gaussian measures. We consider two classes of information. The first class Λ^std consists of function values, and the second class Λ^all consists of all continuous linear functionals. Tractability of a linear multivariate problem means that the average case complexity of computing an ε-approximation is O((1/)^p) with p independent of d. The smallest such p is called the exponent of the problem. Under mild assumptions, we prove that tractability in Λ^all is equivalent to tractability in Λ^std and that the difference of the exponents is at most 2. The proof of this result is not constructive. We provide a simple condition to check tractability in Λ^all. We also address the issue of how to construct optimal (or nearly optimal) sample points for linear multivariate problems. We use relations between average case and worst case settings. These relations reduce the study of the average case to the worst case for a different class of functions. In this way we show how optimal sample points from the worst case setting can be used in the average case. In Part II we shall apply the theoretical results to obtain optimal or almost optimal sample points, optimal algorithms, and average case complexity functions for linear multivariate problems equipped with the folded Wiener sheet measure. Of particular interest will be the multivariate function approximation problem.     

The smallest point of a polytope

This note suggests new ways for calculating the point of smallest Euclidean norm in the convex hull of a given set of points inR ⁿ . It is shown that the problem can be formulated as a linear least-square problem with nonnegative variables or as a least-distance problem. Numerical experiments illustrate that the least-square problem is solved efficiently by the active set method. The advantage of the new approach lies in the solution of large sparse problems. In this case, the new formulation permits the use of row relaxation methods. In particular, the least-distance problem can be solved by Hildreth's method.     

Minimax observers of full and reduced order

We consider the problem of optimal observation of unmeasurable variables in linear dynamical systems with the use of observers of full and reduced order. For the observation performance characteristic to be minimized, we take the initial perturbation damping level in the observation error equation defined as the maximum ratio of the L ₂-norm of the error to the Euclidean norm of the corresponding initial state. Conditions for the existence of such minimax observers and their synthesis are stated in the form of linear matrix inequalities.     

The inverse optimal value problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.Mathematics Subject Classification (1999):49N45, 90C05, 90C25, 90C26, 90C31, 90C60Acknowledgement This research has been supported in part by the National Science Foundation under CAREER Award DMII-0133943. The authors thank two anonymous reviewers for valuable comments.     

On two geometric problems related to the travelling salesman problem

The degree-K Minimum Spanning Tree (MST) problem asks for the minimum length spanning tree that has no vertex of degree greater than K. The Euclidean degree-K MST problem is known to be tractable for K ? 5; the degree-2 MST is simply the Euclidean path-TSP, which is NP-complete. It is proved that the Euclidean degree-3 MST problem is also NP-complete, thus leaving open only the case for K = 4. Among the most illustrious approximation algorithms is the heuristic for the Euclidean TSP due to Christofides. It is proved that implementing the “shortcutting phase” of Christofides' algorithm optimally is NP-hard (even so, Christofides' algorithm guarantees a tour which is no more than 50% longer than the optimal one).     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

Improved pedagogy for linear differential equations by reconsidering how we measure the size of solutions

For over 50 years, the learning of teaching of a priori bounds on solutions to linear differential equations has involved a Euclidean approach to measuring the size of a solution. While the Euclidean approach to a priori bounds on solutions is somewhat manageable in the learning and teaching of the proofs involving second-order, linear problems with constant co-efficients, we believe it is not pedagogically optimal. Moreover, the Euclidean method becomes pedagogically unwieldy in the proofs involving higher-order cases. The purpose of this work is to propose a simpler pedagogical approach to establish a priori bounds on solutions by considering a different way of measuring the size of a solution to linear problems, which we refer to as the Uber size. The Uber form enables a simplification of pedagogy from the literature and the ideas are accessible to learners who have an understanding of the Fundamental Theorem of Calculus and the exponential function, both usually seen in a first course in calculus. We believe that this work will be of mathematical and pedagogical interest to those who are learning and teaching in the area of differential equations or in any of the numerous disciplines where linear differential equations are used.     

Bounds on the Optimal Location to the Weber Problem under Conditions of Uncertainty

Optimal and Heuristic bounds are given for the optimal location to the Weber problem when the locations of demand points are not deterministic but may be within given circles. Rectilinear, Euclidean and square Euclidean types of distance measure are discussed. The exact shape of all possible optimal points is given in the rectilinear and square Euclidean cases. A heuristic method for the computation of the region of possible optimal points is developed in the case of Euclidean distance problem. The maximal distance between a possible optimal point and the deterministic solution is also computed heuristically.     

Asymptotic optimization of nonlinear singularly perturbed systems with control constrained by a hypersphere

We consider a terminal control problem for a nonlinear singularly perturbed system with constraints imposed on the right endpoint of the trajectories. The values of the multidimensional controls are bounded in the Euclidean norm. We suggest an algorithm for an approximate (in the asymptotic sense) solution of this problem. The key advantage of the algorithm is the following: the original problem splits into two optimal control problems of lower dimension, one of which is linear.     

Robust Mean-Squared Error Estimation of Multiple Signals in Linear Systems Affected by Model and Noise Uncertainties

This paper is a continuation of the work in [11] and [2] on the problem of estimating by a linear estimator, N unobservable input vectors, undergoing the same linear transformation, from noise-corrupted observable output vectors. Whereas in the aforementioned papers, only the matrix representing the linear transformation was assumed uncertain, here we are concerned with the case in which the second order statistics of the noise vectors (i.e., their covariance matrices) are also subjected to uncertainty. We seek a robust mean-squared error estimator immuned against both sources of uncertainty. We show that the optimal robust mean-squared error estimator has a special form represented by an elementary block circulant matrix, and moreover when the uncertainty sets are ellipsoidal-like, the problem of finding the optimal estimator matrix can be reduced to solving an explicit semidefinite programming problem, whose size is independent of N. The research was partially supported by BSF grant #2002038     

Uniqueness and transport density in Monge's mass transportation problem

Monge's problem refers to the classical problem of optimally transporting mass: given Borel probability measures on , find the measure preserving map s(x) between them which minimizes the average distance transported. Here distance can be induced by the Euclidean norm, or any other uniformly convex and smooth norm on . Although the solution is never unique, we give a geometrical monotonicity condition singling out a particular optimal map s(x). Furthermore, a local definition is given for the transport cost density associated to each optimal map. All optimal maps are then shown to lead to the same transport density . Received: 18 December 2000 / Accepted: 11 May 2001 / Published online: 19 October 2001     

General Linear Quadratic Optimal Stochastic Control Problem Driven by a Brownian Motion and a Poisson Random Martingale Measure with Random Coefficients

In this article, we consider a linear-quadratic optimal control problem (LQ problem) for a controlled linear stochastic differential equation driven by a multidimensional Browinan motion and a Poisson random martingale measure in the general case, where the coefficients are allowed to be predictable processes or random matrices. By the duality technique, the dual characterization of the optimal control is derived by the optimality system (so-called stochastic Hamilton system), which turns out to be a linear fully coupled forward-backward stochastic differential equation with jumps. Using a decoupling technique, the connection between the stochastic Hamilton system and the associated Riccati equation is established. As a result, the state feedback representation is obtained for the optimal control. As the coefficients for the LQ problem are random, here, the associated Riccati equation is a highly nonlinear backward stochastic differential equation (BSDE) with jumps, where the generator depends on the unknown variables K, L, and H in a quadratic way (see (5.9) herein). For the case where the generator is bounded and is linearly dependent on the unknown martingale terms L and H, the existence and uniqueness of the solution for the associated Riccati equation are established by Bellman's principle of quasi-linearization.     

Local convergence in a generalized Fermat-Weber problem

In the Fermat-Weber problem, the location of a source point in ^N is sought which minimizes the sum of weighted Euclidean distances to a set of destinations. A classical iterative algorithm known as the Weiszfeld procedure is used to find the optimal location. Kuhn proves global convergence except for a denumerable set of starting points, while Katz provides local convergence results for this algorithm. In this paper, we consider a generalized version of the Fermat-Weber problem, where distances are measured by anl _p norm and the parameterp takes on a value in the closed interval [1, 2]. This permits the choice of a continuum of distance measures from rectangular (p=1) to Euclidean (p=2). An extended version of the Weiszfeld procedure is presented and local convergence results obtained for the generalized problem. Linear asymptotic convergence rates are typically observed. However, in special cases where the optimal solution occurs at a singular point of the iteration functions, this rate can vary from sublinear to quadratic. It is also shown that for sufficiently large values ofp exceeding 2, convergence of the Weiszfeld algorithm will not occur in general.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Generalized Solution of Linear Systems and Image Restoration

Let n, m be positive integers; we consider m×n real linear systems. We define regularized solutions of a linear system as the minimizers of an optimization problem. The objective function of this optimization problem can be seen as the Tikhonov functional when the p-norm is considered instead of the Euclidean norm. The cases p=1 and p= are studied. This analysis is used to restore defocused synthetic images and real images with encouraging results.     

On the optimal reconstruction of a solution of the Poisson equation

We consider the problem of optimal reconstruction of a solution of the generalized Poisson equation in a bounded domain Q with homogeneous boundary conditions for the case in which the right-hand side of the equation is fuzzy. We assume that right-hand sides of the equations belong to generalized Sobolev classes and finitely many Fourier coefficients of the right-hand sides of the equations are known with some accuracy in the Euclidean metric. We find the optimal reconstruction error and construct a family of optimal reconstruction methods. The problem on the best choice of the coefficients to be measured is solved.     

Algorithms for flows with parametric capacities

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.     

Optical Tomography for Variable Refractive Index with Angularly Averaged Measurements

In optical tomography one seeks to use near-infrared light to determine the optical absorption and scattering properties of a medium X ? ? ⁿ . If the refractive index is constant throughout the medium, the steady-state case is modeled by the stationary linear transport equation in terms of the Euclidean metric. In this work we consider the case of variable refractive index where the dynamics are modeled by writing the transport equation in terms of a Riemannian metric; in the absence of interaction, photons follow the geodesics of this metric. In particular we study the problem where our measurements allow the application of an in-going flux depending on both position and direction, but we allow only a weighted average measurement of the out-going flux. We show that making measurements on all of ? X determines the extinction coefficient and that once this is known, under additional assumptions, measurements at a single point on ? X determine the scattering kernel.     

Parametric versions of Hilbert’s fourth problem

LetH be the class of sufficiently smooth metrics defined on the Euclidean plane for which the geodesics are the usual Euclidean liens. The general problem is to describe all metrics fromH which at each point possess the length indicatrix from a prescribed parametric class of convex figures. As a tool, a differential equation is proposed derived from the “triangular deficit principle” formulated in an earlier paper of R. V. Ambartzumian. The paper demonstrates that for the case where the length indicatrix is segmental this equation leads to a complete solution. Also, there is a partial result stating that in the case of Riemann metrics the orientation of the ellipsi should necessarily be a harmonic function.