Elliptic optimal control problems with <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-control cost and applications for the placement of control devices

Elliptic optimal control problems with L ¹-control cost are analyzed. Due to the nonsmooth objective functional the optimal controls are identically zero on large parts of the control domain. For applications, in which one cannot put control devices (or actuators) all over the control domain, this provides information about where it is most efficient to put them. We analyze structural properties of L ¹-control cost solutions. For solving the non-differentiable optimal control problem we propose a semismooth Newton method that can be stated and analyzed in function space and converges locally with a superlinear rate. Numerical tests on model problems show the usefulness of the approach for the location of control devices and the efficiency of our algorithm.     

On the complexity of the multivariate Sturm–Liouville eigenvalue problem

We study the complexity of approximating the smallest eigenvalue of -Δ+q with Dirichlet boundary conditions on the d-dimensional unit cube. Here Δ is the Laplacian, and the function q is non-negative and has continuous first order partial derivatives. We consider deterministic and randomized classical algorithms, as well as quantum algorithms using quantum queries of two types: bit queries and power queries. We seek algorithms that solve the problem with accuracy . We exhibit lower and upper bounds for the problem complexity. The upper bounds follow from the cost of particular algorithms. The classical deterministic algorithm is optimal. Optimality is understood modulo constant factors that depend on d. The randomized algorithm uses an optimal number of function evaluations of q when d≤2. The classical algorithms have cost exponential in d since they need to solve an eigenvalue problem involving a matrix with size exponential in d. We show that the cost of quantum algorithms is not exponential in d, regardless of the type of queries they use. Power queries enjoy a clear advantage over bit queries and lead to an optimal complexity algorithm.     

Optimal and better transport plans

We consider the Monge-Kantorovich transport problem in a purely measure theoretic setting, i.e. without imposing continuity assumptions on the cost function. It is known that transport plans which are concentrated on c-monotone sets are optimal, provided the cost function c is either lower semi-continuous and finite, or continuous and may possibly attain the value ∞. We show that this is true in a more general setting, in particular for merely Borel measurable cost functions provided that {c=∞} is the union of a closed set and a negligible set. In a previous paper Schachermayer and Teichmann considered strongly c-monotone transport plans and proved that every strongly c-monotone transport plan is optimal. We establish that transport plans are strongly c-monotone if and only if they satisfy a “better” notion of optimality called robust optimality.     

Linear Transport Equations with μ-Monotone Coefficients

We introduce the concept of a μ-monotone function. It allows us to extend the existing theory for Filippov solutions to ODE, linear transport equations, and conservation laws for a wider range of transport velocities (A₁,…,A_d) and fluxes (f₁,…,f_d).     

A <Emphasis Type="Italic">d</Emphasis>-person Differential Game with State Space Constraints

We consider a network of d companies (insurance companies, for example) operating under a treaty to diversify risk. Internal and external borrowing are allowed to avert ruin of any member of the network. The amount borrowed to prevent ruin is viewed upon as control. Repayment of these loans entails a control cost in addition to the usual costs. Each company tries to minimize its repayment liability. This leads to a d -person differential game with state space constraints. If the companies are also in possible competition a Nash equilibrium is sought. Otherwise a utopian equilibrium is more appropriate. The corresponding systems of HJB equations and boundary conditions are derived. In the case of Nash equilibrium, the Hamiltonian can be discontinuous; there are d interlinked control problems with state constraints; each value function is a constrained viscosity solution to the appropriate discontinuous HJB equation. Uniqueness does not hold in general in this case. In the case of utopian equilibrium, each value function turns out to be the unique constrained viscosity solution to the appropriate HJB equation. Connection with Skorokhod problem is briefly discussed.     

Continuity of optimal transport maps and convexity of injectivity domains on small deformations of 𝕊2

Given a compact Riemannian manifold, we study the regularity of the optimal transport map between two probability measures with cost given by the squared Riemannian distance. Our strategy is to define a new form of the so‐called Ma‐Trudinger‐Wang condition and to show that this condition, together with the strict convexity on the nonfocal domains, implies the continuity of the optimal transport map. Moreover, our new condition, again combined with the strict convexity of the nonfocal domains, allows us to prove that all injectivity domains are strictly convex too. These results apply, for instance, on any small C⁴‐deformation of the 2‐sphere. © 2009 Wiley Periodicals, Inc.     

古诺竞争的选址模型研究

在Paul提出的圆环形城市模型基础上,通过引入成本分布函数,扩展了Pal和Matsushima的模型,建立了一个新的带有成本因子的选址与产量竞争的双寡头竞争模型.结果表明:如果成本分布函数是常数,那么两企业均衡地分布于圆环形城市将达到完美的纳什均衡;如果成本分布函数是严格凸函数,当运输系数较小时,企业将在产品成本分布函数最小点处集聚,并各自达到利润最大化.     

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.     

Renormalized solutions of some transport equations with partially <Emphasis Type="Italic">W</Emphasis><Superscript>1,1</Superscript> velocities and applications

We prove existence and uniqueness of renormalized solutions of some transport equations with a vector field that is not W^1,1 with respect to all variables but is of a particular form. Two specific applications of this new result are then treated, based upon the equivalence between transport equations and ordinary differential equations. The first one consists of a result about the dependance upon initial conditions for solutions of ODEs. The second one is related to some stochastic differential equations arising in the modelling of polymeric fluid flows.     

Mean–range based distribution-free procedures to minimize “overage” and “underage” costs

We discuss several mean–range based distribution-free decision procedures to minimize several “overage” and “underage” cost functions. For a general cost function, we identify the most favorable distribution and the least favorable distribution associated with the random variable of interest and determine the upper and lower bounds for the cost function. For the quadratic cost function, we recommend the min–max distribution-free decision. For the linear cost function, we identify the range of potential optimal decisions and recommend a hybrid distribution-free decision that has several desirable properties. We provide several numerical examples to demonstrate the robustness of the proposed distribution-free decisions.     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.     

The optimistic <Emphasis Type="Italic">TU</Emphasis> game in minimum cost spanning tree problems

We associate an optimistic TU game with each minimum cost spanning tree problem. We define the worth of a coalition S as the cost of connecting agents in S to the source assuming that agents in N\S are already connected to the source, and agents in S can connect through agents in N\S. We study the Shapley value of this new game. We thank Hervé Moulin, William Thomson, and two referees for helpful comments. Financial support from the Ministerio de Ciencia y Tecnologia and FEDER through grant SEJ2005-07637-c02-01 is gratefully acknowledged.     

NOAH'S NONCONCAVITY: ON THE EXISTENCE OF NONTRIVIAL INTERIOR SOLUTIONS TO THE PROBLEM OF COST‐EFFECTIVE CONSERVATION PLANNING

Abstract The idea that species loss diminishes future information flows is a cornerstone of arguments for conservation planning. In his seminal work entitled The Noah's Ark Problem, Weitzman [1998] examines the problem of cost‐effective conservation planning from a theoretical perspective accounting for the affect planning has on the expected size of the biosphere's informative potential. This paper extends Weitzman's analysis by examining how his conclusions are altered by the introduction of a conservation authority that considers the value of information contained in the biosphere. Introducing nonquasiconcave preferences for the information contained in each species substantially modifies the characterization of a cost‐effective conservation plan. In particular, I find that a cost‐effective plan generally includes partial funding for many species and funds no species completely. This investigation is motivated by theoretical contributions to the information economics literature, a la Radner and Stiglitz [1984] , showing that the value function for information tends to exhibit increasing returns.     

The estimation of stochastic cost-quantity frontiers for discretionary cost and budgeted-expenditure systems

Two alternative approximating functions for representing the unknown composite residual density function of a cost-quantity frontier are examined. The frontier is one in which cost is regarded as preselected. This is appropriate for public sector economics and discretionary cost situations. One function requires the estimation of a single distribution parameter, whereas the other makes no a priori assumption on the shape of the density function.     

Competitive evaluation of threshold functions in the priced information model

In Charikar et al. (J. Comput. Syst. Sci. 64(4):785–819, 2002) the authors proposed a new model for studying the function evaluation problem based on a variant of the classical decision tree problem for Boolean functions. In this variant each variable of the function to evaluate has an associated cost which has to be paid in order to read the value of the variable. Given a function f and an assignment σ to the variables of f, the performance of an algorithm for evaluating f is measured via the competitive ratio, i.e., the ratio of the total cost spent by the algorithm and the cost of the cheapest set of variables constituting a certificate for the value of the function on the given assignment.     

The Monge problem for supercritical Mañé potentials on compact manifolds

We prove the existence of optimal transport maps for the Monge problem when the cost is a Finsler distance on a compact manifold. Our point of view consists in considering the distance as a Mañé potential, and to rely on recent developments in the theory of viscosity solutions of the Hamilton-Jacobi equation.     

Embedding optimal transports in statistical manifolds

We consider Monge-Kantorovich optimal transport problems on ? ^d , d ≥ 1, with a convex cost function given by the cumulant generating function of a probability measure. Examples include theWasserstein-2 transport whose cost function is the square of the Euclidean distance and corresponds to the cumulant generating function of the multivariate standard normal distribution. The optimal coupling is usually described via an extended notion of convex/concave functions and their gradient maps. These extended notions are nonintuitive and do not satisfy useful inequalities such as Jensen’s inequality. Under mild regularity conditions, we show that all such extended gradient maps can be recovered as the usual supergradients of a nonnegative concave function on the space of probability distributions. This embedding provides a universal geometry for all such optimal transports and an unexpected connection with information geometry of exponential families of distributions.     

Optimal Control of an M/G/1/K Queueing System with Combined <Emphasis Type="Italic">F</Emphasis> Policy and Startup Time

We investigate the optimal management problem of an M/G/1/K queueing system with combined F policy and an exponential startup time. The F policy queueing problem investigates the most common issue of controlling the arrival to a queueing system. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in the system. The method is illustrated analytically for exponential service time distribution. A cost model is established to determine the optimal management F policy at minimum cost. We use an efficient Maple computer program to calculate the optimal value of F and some system performance measures. Sensitivity analysis is also investigated.     

A fast second‐order difference scheme for the space–time fractional equation

In this paper, a fast second‐order accurate difference scheme is proposed for solving the space–time fractional equation. The temporal Caputo derivative is approximated by ?L2 ‐1_σ formula which employs the sum‐of‐exponential approximation to the kernel function appeared in Caputo derivative. The second‐order linear spline approximation is applied to the spatial Riemann–Liouville derivative. At each time step, a fast algorithm, the preconditioned conjugate gradient normal residual method with a circulant preconditioner (PCGNR), is used to solve the resulting system that reduces the storage and computational cost significantly. The unique solvability and unconditional convergence of the difference scheme are shown by the discrete energy method. Numerical examples are given to verify numerical accuracy and efficiency of the difference schemes.