Average optimality inequality for continuous-time Markov decision processes in Polish spaces

In this paper, we study the average optimality for continuous-time controlled jump Markov processes in general state and action spaces. The criterion to be minimized is the average expected costs. Both the transition rates and the cost rates are allowed to be unbounded. We propose another set of conditions under which we first establish one average optimality inequality by using the well-known “vanishing discounting factor approach”. Then, when the cost (or reward) rates are nonnegative (or nonpositive), from the average optimality inequality we prove the existence of an average optimal stationary policy in all randomized history dependent policies by using the Dynkin formula and the Tauberian theorem. Finally, when the cost (or reward) rates have neither upper nor lower bounds, we also prove the existence of an average optimal policy in all (deterministic) stationary policies by constructing a “new” cost (or reward) rate. Research partially supported by the Natural Science Foundation of China (Grant No: 10626021) and the Natural Science Foundation of Guangdong Province (Grant No: 06300957).     

Continuous-Time Markov Decision Processes with Unbounded Transition and Discounted-Reward Rates

Abstract

In this article, we study continuous-time Markov decision processes in Polish spaces. The optimality criterion to be maximized is the expected discounted criterion. The transition rates may be unbounded, and the reward rates may have neither upper nor lower bounds. We provide conditions on the controlled system's primitive data under which we prove that the transition functions of possibly non-homogeneous continuous-time Markov processes are regular by using Feller's construction approach to such transition functions. Then, under continuity and compactness conditions we prove the existence of optimal stationary policies by using the technique of extended infinitesimal operators associated with the transition functions of possibly non-homogeneous continuous-time Markov processes, and also provide a recursive way to compute (or at least to approximate) the optimal reward values. The conditions provided in this paper are different from those used in the previous literature, and they are illustrated with an example.     

Variance minimization for continuous-time Markov decision processes: two approaches

This paper studies the limit average variance criterion for continuous-time Markov decision processes in Polish spaces. Based on two approaches, this paper proves not only the existence of solutions to the variance minimization optimality equation and the existence of a variance minimal policy that is canonical, but also the existence of solutions to the two variance minimization optimality inequalities and the existence of a variance minimal policy which may not be canonical. An example is given to illustrate all of our conditions.     

连续时间Markov决策过程的均值-方差优化问题

本文考虑连续时间Markov决策过程折扣模型的均值-方差优化问题.假设状态空间和行动空间均为Polish空间,转移率和报酬率函数均无界.本文的优化目标是在折扣最优平稳策略类里,选取相应方差最小的策略.本文致力于寻找Polish空间下Markov决策过程均值-方差最优策略存在的条件.利用首次进入分解方法,本文证明均值-方差优化问题可以转化为"等价"的期望折扣优化问题,进而得到关于均值-方差优化问题的"最优方程"和均值-方差最优策略的存在性以及它相应的特征.最后,本文给出若干例子说明折扣最优策略的不唯一性和均值-方差最优策略的存在性.     

New optimality conditions for average-payoff continuous-time Markov games in Polish spaces

This paper concerns two-person zero-sum games for a class of average-payoff continuous-time Markov processes in Polish spaces.The underlying processes are determined by transition rates that are allowed to be unbounded,and the payoff function may have neither upper nor lower bounds.We use two optimality inequalities to replace the so-called optimality equation in the previous literature.Under more general conditions,these optimality inequalities yield the existence of the value of the game and of a pair of ...     

Generalized semi-infinite optimization: A first order optimality condition and examples

We consider a generalized semi-infinite optimization problem (GSIP) of the form (GSIP) min{f(x)‖xεM}, where M={x∈ℝⁿ|h_i(x)=0i=l,...m, G(x,y)⩾0, y∈Y(x)} and all appearing functions are continuously differentiable. Furthermore, we assume that the setY(x) is compact for allx under consideration and the set-valued mappingY(.) is upper semi-continuous. The difference with a standard semi-infinite problem lies in thex-dependence of the index setY. We prove a first order necessary optimality condition of Fritz John type without assuming a constraint qualification or any kind of reduction approach. Moreover, we discuss some geometrical properties of the feasible setM. This work was partially supported by the “Deutsche Forschungsgemeinschaft” through the Graduiertenkolleg “Mathematische Optimierung” at the University of Trier.     

Calmness of Set-Valued Mappings Between Asplund Spaces and Application to Equilibrium Problems

The paper deals with the calmness of two classes of nonconvex set-valued mappings in Asplund spaces and its application to equilibrium problems. Its main part is devoted to establish new sufficient conditions for calmness, which are derived in terms of coderivatives and w* boundaries of normal cones to constraint sets. In order to achieve this goal, a new concept so-called “sequential normal smoothness” for the sets in Asplund spaces is introduced and compared with two well-known notions of convexity and semismoothness. Finally, the results are applied to prove necessary optimality conditions for nonparametric equilibrium problems under new weak constraint qualifications.     

Another set of conditions for Markov decision processes with average sample-path costs

This paper deals with discrete-time Markov decision processes with average sample-path costs (ASPC) in Borel spaces. The costs may have neither upper nor lower bounds. We propose new conditions for the existence of ε-ASPC-optimal (deterministic) stationary policies in the class of all randomized history-dependent policies. Our conditions are weaker than those in the previous literature. Moreover, some sufficient conditions for the existence of ASPC optimal stationary policies are imposed on the primitive data of the model. In particular, the stochastic monotonicity condition in this paper has first been used to study the ASPC criterion. Also, the approach provided here is slightly different from the “optimality equation approach” widely used in the previous literature. On the other hand, under mild assumptions we show that average expected cost optimality and ASPC-optimality are equivalent. Finally, we use a controlled queueing system to illustrate our results.     

Average optimality for continuous-time Markov decision processes with a policy iteration approach

This paper deals with the average expected reward criterion for continuous-time Markov decision processes in general state and action spaces. The transition rates of underlying continuous-time jump Markov processes are allowed to be unbounded, and the reward rates may have neither upper nor lower bounds. We give conditions on the system's primitive data and under which we prove the existence of the average reward optimality equation and an average optimal stationary policy. Also, under our conditions we ensure the existence of ?-average optimal stationary policies. Moreover, we study some properties of average optimal stationary policies. We not only establish another average optimality equation on an average optimal stationary policy, but also present an interesting “martingale characterization” of such a policy. The approach provided in this paper is based on the policy iteration algorithm. It should be noted that our way is rather different from both the usually “vanishing discounting factor approach” and the “optimality inequality approach” widely used in the previous literature.     

Hierarchic control

Distributed control is applied to a system modelled by a parabolic evolution equation. One considers situations where there are two cost (objective) functions. One possible way is to cut the control into 2 parts, one being thought of as “the leader” and the other one as “the follower”. This situation is studied in the paper, with one of the cost functions being of the controllability type. Existence and uniqueness is proven. The optimality system is given in the paper. Dedicated to the memory of Professor K G Ramanathan     

On Hardy spaces associated with Bessel operators

In this paper, we study Hardy spaces associated with two Bessel operators. Two different kind of Hardy spaces appear. These differences are transparent in the corresponding atomic decompositions. The first author was partially supported by MTM2004/05878. The second author was supported by the European Commission Marie Curie Host Fellowship for the Transfer of Knowledge “Harmonic Analysis, Nonlinear Analysis and Probability” MTKD-CT-2004-013389 and by Polish funds for science in years 2005–2008 (research project 1P03A03029).     

From Scalar to Vector Optimization

Initially, second-order necessary optimality conditions and sufficient optimality conditions in terms of Hadamard type derivatives for the unconstrained scalar optimization problem ϕ(x) → min, x ∈ ℝ ^m , are given. These conditions work with arbitrary functions ϕ: ℝ ^m → ℝ, but they show inconsistency with the classical derivatives. This is a base to pose the question whether the formulated optimality conditions remain true when the “inconsistent” Hadamard derivatives are replaced with the “consistent” Dini derivatives. It is shown that the answer is affirmative if ϕ is of class (i.e., differentiable with locally Lipschitz derivative). Further, considering functions, the discussion is raised to unconstrained vector optimization problems. Using the so called “oriented distance” from a point to a set, we generalize to an arbitrary ordering cone some second-order necessary conditions and sufficient conditions given by Liu, Neittaanmaki, Krizek for a polyhedral cone. Furthermore, we show that the conditions obtained are sufficient not only for efficiency but also for strict efficiency.     

Moduli for pairs of elliptic curves¶with isomorphic N-torsion

We study the moduli surface for pairs of elliptic curves together with an isomorphism between their N-torsion groups. The Weil pairing gives a “determinant” map from this moduli surface to (Z/N Z)^*; its fibers are the components of the surface. We define spaces of modular forms on these components and Hecke correspondences between them, and study how those spaces of modular forms behave as modules for the Hecke algebra. We discover that the component with determinant −1 is somehow the “dominant” one; we characterize the difference between its spaces of modular forms and the spaces of modular forms on the other components using forms with complex multiplication. In addition, we prove Atkin–Lehner-style results about these spaces of modular forms. Finally, we show some simplifications that arise when N is prime, including a complete determination of such CM-forms, and give numerical examples. Received: 20 September 2000 / Revised version: 7 February 2001     

Distribution results for lattices in SL(2,ℚ p )

In this paper we study the ergodic properties of the linear action of lattices Γ of SL(2,ℚ_p) on ℚ_p × ℚ_p and distribution results for orbits of Γ. Following Serre, one can define a “geodesic flow” for an associated tree (actually associated to GL(2,ℚ_p)). The approach we use is based on an extension of this approach to “frame flows” which are a natural compact group extension of the geodesic flow.     

N-Widths and Average Widths of Besov Classes in Sobolev Spaces

In this paper, we consider the n-widths and average widths of Besov classes in the usual Sobolev spaces. The weak asymptotic results concerning the Kolmogorov n-widths, the linear n-widths, the Gel＇fand n-widths, in the Sobolev spaces on T^d, and the infinite-dimensional widths and the average widths in the Sobolev spaces on Ra are obtained, respectively.     

Structural stability and robustness to bounded rationality for non-compact cases

We study the model M consisting of “general games” with noncompact action space, together with an associated abstract rationality function. We prove that M is structurally stable and robust to ϵ-equilibria for “almost all” parameters. As applications, we investigate structural stability and robustness to bounded rationality for noncooperative games, multiobjective optimizations and fixed point problems satisfying existence and some continuity conditions. Specifically, we introduce concrete rationality functions for such three kinds of problems with both payoffs and strategy sets, objective functions and domain spaces, and correspondence and domain spaces as parameters, respectively, and show the generic structural stability and robustness to bounded rationality for the corresponding model Ms.     

The Economic Lot Scheduling Problem without Capacity Constraints

This study presents a comprehensive analysis on the Economic Lot Scheduling Problem (ELSP) without capacity constraints. We explore the optimality structure of the ELSP without capacity constraints and discover that the curve for the optimal objective values is piecewise convex with repsect to B, i.e., the values of basic period. The theoretical properties of the junction points on the piecewise convex curve not only provides us the information on “which product i” to modify, but also on “where on the B-axis” to change the set of optimal multpliers in the search process. By making use of the junction points, we propose an effective search algorithm to secure a global optimal solution for the ELSP without capacity constraints. Also, we use random experiments to verify that the proposed algorithm is efficient. The results in this paper lay important foundation for deriving an efficient heuristic to solve the conventional ELSP with capacity constraints.     

Risk-sensitive average continuous-time Markov decision processes with unbounded rates

Abstract

In this paper we study the risk-sensitive average cost criterion for continuous-time Markov decision processes in the class of all randomized Markov policies. The state space is a denumerable set, and the cost and transition rates are allowed to be unbounded. Under the suitable conditions, we establish the optimality equation of the auxiliary risk-sensitive first passage optimization problem and obtain the properties of the corresponding optimal value function. Then by a technique of constructing the appropriate approximating sequences of the cost and transition rates and employing the results on the auxiliary optimization problem, we show the existence of a solution to the risk-sensitive average optimality inequality and develop a new approach called the risk-sensitive average optimality inequality approach to prove the existence of an optimal deterministic stationary policy. Furthermore, we give some sufficient conditions for the verification of the simultaneous Doeblin condition, use a controlled birth and death system to illustrate our conditions and provide an example for which the risk-sensitive average optimality strict inequality occurs.     

Prevalence of Multifractal Functions in S<Superscript>v</Superscript> Spaces

Spaces called S^v were introduced by Jaffard [16] as spaces of functions characterized by the number ≃ 2^ν(α)j of their wavelet coefficients having a size ≳ 2^−αj at scale j . They are Polish vector spaces for a natural distance. In those spaces we show that multifractal functions are prevalent (an infinite-dimensional “almost-every”). Their spectrum of singularities can be computed from ν, which justifies a new multifractal formalism, not limited to concave spectra.