A viability theorem for set-valued states in a Hilbert space

Applications in robust control problems and shape evolution motivate the mathematical interest in control problems whose states are compact (possibly non-convex) sets rather than vectors. This leads to evolutions in a basic set which can be supplied with a metric (like the well-established Pompeiu–Hausdorff distance), but it does not have an obvious linear structure. This article extends differential inclusions with state constraints to compact-valued states in a separable Hilbert space H. The focus is on sufficient conditions such that a given constraint set (of compact subsets) is viable a.k.a. weakly invariant. Our main result extends the tangential criterion in the well-known viability theorem (usually for differential inclusions in a vector space) to the metric space of non-empty compact subsets of H.     

Stochastic control and compatible subsets of constraints

Given a stochastic differential control system and a closed set K in Rn, we study the that, with probability one, the associated solution of the control system remains for ever in the set K. This set is called the viability kernel of K. If N is equal to the whole set K, K is said to be viable. We prove that, in the general case, the viability kernel itself is viable and we characterize it through some partial differential equations. We prove that, under suitable assumptions, also the boundary of N is viable. As an application, we give a new characterization of the value function of some optimal control problem.     

A Planning Problem Combining Calculus of Variations and Optimal Transport

We consider some variants of the classical optimal transport where not only one optimizes over couplings between some variables x and y but also over some control variables governing the evolutions of these variables with time. Such a situation is motivated by an assignment problem of tasks with workers whose characteristics can evolve with time (and be controlled). We distinguish between the coupled and decoupled case. The coupled case is a standard optimal transport with the value of some optimal control problem as cost. The decoupled case is more involved since it is nonlinear in the transport plan.     

Some new two-weight codes and strongly regular graphs

It is well known (and due to Delsarte [3]) that the three concepts (i) two-weight projective code, (ii) strongly regular graph defined by a difference set in a vector space, and (iii) subset X of a projective space such that |X∩H| takes only two values when H runs over all hyperplanes, are equivalent. Here we construct some new examples (formulated as in (iii)) by taking a quadric defined over a small field and cutting out a quadratic defined over a larger field.     

Regulation of births for viability of populations governed by age-structured problems

We assume that the evolution of the population is governed by a controlled McKendrick age-structured partial differential equation where the mortality rate and immigrated population levels are no longer known coefficients, but contingent regulation parameters chosen for a given purpose, for instance, for requiring that the population satisfies prescribed viability constraints depending on time and age. The Lotka renewal equation relating the boundary condition (number of births) to the integral with respect to age of the population is replaced by the introduction of another regulation parameter in the boundary condition, regarded as a natality policy. We may control it by its derivative, regarded as a natality decision. We then construct a regulation map, associating with the population level, the time and the age the subset of natality policies, a mortality rates and an immigration levels needed for governing viable evolutions of the population.     

Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms

This paper treats with K-shortest viable path problem in a transportation network including multiple modes. The considered modes are metro, rapid-bus, private and walking. In this network, a viable path is one that the number of mode changes is limited and the traverse time and also the walking, metro and private usage are restricted subjected to some constraints. The traverse time is defined dependent on congestion level. Because constrained shortest path is NP-hard, we extend two metaheuristic algorithms namely GASA and BACS for the given problem. GASA is a Greedy Algorithm Simulated Annealing and BACS is a bi-direction searching Ant Colony System made by two colonies of ants. We evaluate the validation of these algorithms applying several multimodal random networks. In addition, their results are compared with CPLEX 12.1. We find that GASA is appropriate for small networks and BACS has better performance in median and large-scale networks. Our results on Tehran network also demonstrate that BACS provides better objective values than BACS ones because Tehran public transportation is sparse.     

Average boundary conditions in Cauchy problems

We consider the general Cauchy problem with initial data in a Hilbert space and with a formal dissipative linear generator. A complete parametrization is known of the (abstract) boundary conditions which make this problem well set. We exhibit a distinguished subset $\text{B}$_E of the set $\text{B}$ of boundary conditions and demonstrate explicitly that the evolution associated with each B in $\text{B}$ can be represented as a (time independent) average over the evolutions associated with B′ in $\text{B}$_E. Applications are discussed to Schrödinger equations in bounded regions or with singular potentials.     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

Anisotropic propagation of weak discontinuities in flows of thermally conducting and dissociating gases

The object of the present investigation is to study the anisotropic propagation of weak discontinuities in flows of thermally conducting and dissociating gases. The velocity of propagation of the wave frcnt is determined. A set of differential equations governing the growth and decay of weak discontinuities are obtained and solved. It is found that if the sonic wave is a compressive wave of order 1, then it terminates into a shock wave after a critical timet _c which has been determined. It is also observed that the effects of heat conduction and dissociation are to decrease the duration of time by which a weak discontinuity will generate into a shock wave.     

Nonzero-sum constrained discrete-time Markov games: the case of unbounded costs

In this paper, we consider discrete-time \(N\) -person constrained stochastic games with discounted cost criteria. The state space is denumerable and the action space is a Borel set, while the cost functions are admitted to be unbounded from below and above. Under suitable conditions weaker than those in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006) for bounded cost functions, we also show the existence of a Nash equilibrium for the constrained games by introducing two approximations. The first one, which is as in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006), is to construct a sequence of finite games to approximate a (constrained) auxiliary game with an initial distribution that is concentrated on a finite set. However, without hypotheses of bounded costs as in (Alvarez-Mena and Hernández-Lerma, Math Methods Oper Res 63:261–285, 2006), we also establish the existence of a Nash equilibrium for the auxiliary game with unbounded costs by developing more shaper error bounds of the approximation. The second one, which is new, is to construct a sequence of the auxiliary-type games above and prove that the limit of the sequence of Nash equilibria for the auxiliary-type games is a Nash equilibrium for the original constrained games. Our results are illustrated by a controlled queueing system.     

Constrained core solutions for totally positive games with ordered players

In many applications of cooperative game theory to economic allocation problems, such as river-, polluted river- and sequencing games, the game is totally positive (i.e., all dividends are nonnegative), and there is some ordering on the set of the players. A totally positive game has a nonempty core. In this paper we introduce constrained core solutions for totally positive games with ordered players which assign to every such a game a subset of the core. These solutions are based on the distribution of dividends taking into account the hierarchical ordering of the players. The Harsanyi constrained core of a totally positive game with ordered players is a subset of the core of the game and contains the Shapley value. For special orderings it coincides with the core or the Shapley value. The selectope constrained core is defined for acyclic orderings and yields a subset of the Harsanyi constrained core. We provide a characterization for both solutions.     

The Duckworth-Lewis-Stern method: extending the Duckworth-Lewis methodology to deal with modern scoring rates

The famous (and occasionally infamous) Duckworth-Lewis methodology for dealing with interruptions in limited overs cricket matches made its international debut in early 1997. For nearly 20 years, it has set the standard for target adjustment at nearly all levels of the game. In that time, though, it has not been static. In 2003, the Professional Edition of the method was introduced to handle changes to scoring patterns that were becoming apparent in modern cricket. We here introduce the Duckworth-Lewis-Stern (DLS) method, designed to deal with the now common extreme scoring rates seen in limited overs matches, particularly Twenty20. In addition, we outline key principles governing the structure and properties of target adjustment methods and compare DLS with other proposed procedures.     

Geometry and entropy of generalized rotation sets

For a continuous map f on a compact metric space we study the geometry and entropy of the generalized rotation set Rot(Φ). Here Φ = (?₁, ..., ? _m ) is a m-dimensional continuous potential and Rot(Φ) is the set of all µ-integrals of Φ and µ runs over all f-invariant probability measures. It is easy to see that the rotation set is a compact and convex subset of ? ^m . We study the question if every compact and convex set is attained as a rotation set of a particular set of potentials within a particular class of dynamical systems. We give a positive answer in the case of subshifts of finite type by constructing for every compact and convex set K in ? ^m a potential Φ = Φ(K) with Rot(Φ) = K. Next, we study the relation between Rot(Φ) and the set of all statistical limits Rot _Pt (Φ). We show that in general these sets differ but also provide criteria that guarantee Rot(Φ) = Rot _Pt (Φ). Finally, we study the entropy function w ? H(w),w ∈ Rot(Φ). We establish a variational principle for the entropy function and show that for certain non-uniformly hyperbolic systems H(w) is determined by the growth rate of those hyperbolic periodic orbits whose Φ-integrals are close to w. We also show that for systems with strong thermodynamic properties (sub-shifts of finite type, hyperbolic systems and expansive homeomorphisms with specification, etc.) the entropy function w ? H(w) is real-analytic in the interior of the rotation set.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

Abstract convex optimal antiderivatives

Having studied families of antiderivatives and their envelopes in the setting of classical convex analysis, we now extend and apply these notions and results in settings of abstract convex analysis. Given partial data regarding a c-subdifferential, we consider the set of all c-convex c-antiderivatives that comply with the given data. Under a certain assumption, this set is not empty and contains both its lower and upper envelopes. We represent these optimal antiderivatives by explicit formulae. Some well known functions are, in fact, optimal c-convex c-antiderivatives. In one application, we point out a natural minimality property of the Fitzpatrick function of a c-monotone mapping, namely that it is a minimal antiderivative. In another application, in metric spaces, a constrained Lipschitz extension problem fits naturally the convexity notions we discuss here. It turns out that the optimal Lipschitz extensions are precisely the optimal antiderivatives. This approach yields explicit formulae for these extensions, the most particular case of which recovers the well known extensions due to McShane and Whitney.     

Fast fully polynomial approximation schemes for minimizing completion time variance

We present fully polynomial approximation schemes (FPASs) for the problem of minimizing completion time variance (CTV) of a set of n jobs on a single machine. The fastest of these schemes runs in time O(n²/ε) and thus improves on all fully polynomial approximation schemes presented in the literature.     

Semiconcavity results for constrained optimal control problems in a half-space

In this paper we give semiconcavity results for the value function of some constrained optimal control problems with infinite horizon in a half-space. In particular, we assume that the control space is the l¹-ball or the l^∞-ball in Rn.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

Decay Rates to Equilibrium for Nonlinear Plate Equations with Degenerate, Geometrically-Constrained Damping

We analyze the convergence to equilibrium of solutions to the nonlinear Berger plate evolution equation in the presence of localized interior damping (also referred to as geometrically constrained damping). Utilizing the results in (Geredeli et al. in J. Differ. Equ. 254:1193–1229, 2013), we have that any trajectory converges to the set of stationary points $\mathcal{N}$ . Employing standard assumptions from the theory of nonlinear unstable dynamics on the set $\mathcal{N}$ , we obtain the rate of convergence to an equilibrium. The critical issue in the proof of convergence to equilibria is a unique continuation property (which we prove for the Berger evolution) that provides a gradient structure for the dynamics. We also consider the more involved von Karman evolution, and show that the same results hold assuming a unique continuation property for solutions, which is presently a challenging open problem.     

Fluctuation between Subsets of Evolutions Governed by Chaotic Systems

Some issues on fluctuation of solutions to Lorenz and Rossler systems, for instance, are related to viability kernels of subsets under continuous time systems, or in the case of Julia sets, for instance, under discrete time systems. It happens that viability kernels of subsets, capture basins of targets and the combination of the twos provide tools for the analysis of the local behavior around equilibria (local stable and unstable manifolds), the asymptotic behavior and the functuation of evolutions between two areas of a domain, etc. Since algorithms and softwares do exist for computing the viability kernels and the capture basins, as well as evolutions viable in the viability kernel until they converge to a target infinite time, we are able to localize fluctuation basins.