Another Set of Conditions for Strong n (n = −1, 0) Discount Optimality in Markov Decision Processes

Abstract

In this paper we study discrete-time Markov decision processes with average expected costs (AEC) and discount-sensitive criteria in Borel state and action spaces. The costs may have neither upper nor lower bounds. We propose another set of conditions on the system's primitive data, and under which we prove (1) AEC optimality and strong ? 1-discount optimality are equivalent; (2) a condition equivalent to strong 0-discount optimal stationary policies; and (3) the existence of strong n (n = ?1, 0)-discount optimal stationary policies. Our conditions are weaker than those in the previous literature. In particular, the “stochastic monotonicity condition” in this paper has been first used to study strong n (n = ?1, 0)-discount optimality. Moreover, we provide a new approach to prove the existence of strong 0-discount optimal stationary policies. It should be noted that our way is slightly different from those in the previous literature. Finally, we apply our results to an inventory system and a controlled queueing system.     

Weak and Strong Optimality Conditions for Constrained Control Problems with Discontinuous Control

In recent years, sufficient optimality criteria and solution stability in optimal control have been investigated widely and used in the analysis of discrete numerical methods. These results were concerned mainly with weak local optima, whereas strong optimality has been considered often as a purely theoretical aspect. In this paper, we show via an example problem how weak the weak local optimality can be and derive new strong optimality conditions. The criteria are suitable for practical verification and can be applied to the case of discontinuous controls with changes in the set of active constraints.     

积分型总极值方法的最优性条件

郑权提出了求总极值问题的积分—水平集的概念性算法,同时给出了最优性条件.本文构造函数F(x),讨论了该函数的性质,证明求解原问题等价于求解方程F(c)=0的根.在文中给出了相应的总极值存在的最优性条件.     

Second-Order Optimality Conditions in Generalized Semi-Infinite Programming

This paper deals with generalized semi-infinite optimization problems where the (infinite) index set of inequality constraints depends on the state variables and all involved functions are twice continuously differentiable. Necessary and sufficient second-order optimality conditions for such problems are derived under assumptions which imply that the corresponding optimal value function is second-order (parabolically) directionally differentiable and second-order epiregular at the considered point. These sufficient conditions are, in particular, equivalent to the second-order growth condition.     

带消失约束的区间值优化问题的最优性条件与对偶定理

本文考虑一类带消失约束的非光滑区间值优化问题(IOPVC)。在一定的约束条件下得到了问题(IOPVC)的LU最优解的必要和充分性最优性条件,研究了其与Mond-Weir型对偶模型和Wolfe型对偶模型之间的弱对偶,强对偶和严格逆对偶定理,并给出了一些例子来阐述我们的结果。     

A Posteriori Verification of Optimality Conditions for Control Problems with Finite-Dimensional Control Space

In this article, we investigate non-convex optimal control problems. We are concerned with a posteriori verification of sufficient optimality conditions. If the proposed verification method confirms the fulfillment of the sufficient condition then a posteriori error estimates can be computed. A special ingredient of our method is an error analysis for the Hessian of the underlying optimization problem. We derive conditions under which positive definiteness of the Hessian of the discrete problem implies positive definiteness of the Hessian of the continuous problem. The article is complemented with numerical experiments.     

Optimality equations and sensitive optimality in bounded Markov decision processes 1

This paper consider Markov decision processes with countable state space, compact action spaces and a bounded reward function. Under some recurrence and connectedness condition, including the simultaneous Döblin condition, we prove the existence of bounded solutions of the optimality equations which arise for the multichain case in connection with the average reward criterion and sensitive optimality criteria, and we give a characterization of the sets of n-average optimal decision rules.     

A new strong optimality criterion for nonstationary Markov decision processes

This paper deals with a new optimality criterion consisting of the usual three average criteria and the canonical triplet (totally so-called strong average-canonical optimality criterion) and introduces the concept of a strong average-canonical policy for nonstationary Markov decision processes, which is an extension of the canonical policies of Herna′ndez-Lerma and Lasserre [16] (pages: 77) for the stationary Markov controlled processes. For the case of possibly non-uniformly bounded rewards and denumerable state space, we first construct, under some conditions, a solution to the optimality equations (OEs), and then prove that the Markov policies obtained from the OEs are not only optimal for the three average criteria but also optimal for all finite horizon criteria with a sequence of additional functions as their terminal rewards (i.e. strong average-canonical optimal). Also, some properties of optimal policies and optimal average value convergence are discussed. Moreover, the error bound in average reward between a rolling horizon policy and a strong average-canonical optimal policy is provided, and then a rolling horizon algorithm for computing strong average ε(>0)-optimal Markov policies is given.     

The Model for Two-dimensional Layout Optimization Problem with Performance Constraints and Its Optimality Function

This paper studies the two-dimensional layout optimization problem.An optimization model withperformance constraints is presented.The layout problem is partitioned into finite subproblems in terms ofgraph theory,in such a way of that each subproblem overcomes its on-off nature optimal variable.A minimaxproblem is constructed that is locally equivalent to each subproblem.By using this minimax problem,we presentthe optimality function for every subproblem and prove that the first order necessary optimality condition issatisfied at a point if and only if this point is a zero of optimality function.     

Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints

For the problem of maximizing a convex quadratic function under convex quadratic constraints, we derive conditions characterizing a globally optimal solution. The method consists in exploiting the global optimality conditions, expressed in terms of -subdifferentials of convex functions and -normal directions, to convex sets. By specializing the problem of maximizing a convex function over a convex set, we find explicit conditions for optimality.     

A note on asymptotics of discounted value function and strong 0-discount optimality

We consider a Markov decision process with a Borel state space, bounded rewards, and a bounded transition density satisfying a simultaneous Doeblin-Doob condition. An asymptotics for the discounted value function related to the existence of stationary strong 0-discount optimal policies is extended from the case of finite action sets to the case of compact action sets and continuous in action rewards and transition densities.Supported by NSF grant DMS-9404177     

Strong 0-discount optimal policies in a Markov decision process with a Borel state space

We consider a Markov decision process with a Borel state space, a countable action space, finite action sets, bounded rewards and a bounded transition density satisfying a simultaneous Doeblin condition. The existence of stationary strong 0-discount optimal polices is proved.Supported by NSF grant DMS-9404177.     

报酬无界的平均准则马氏决策过程

本文对可数状态集、非空决策集、报酬无界的平均准则马氏决策过程，提出了一组新的条件，在此条件下存在（ε）最优平稳策略，且当最优不等式中的和有定义时最优不等式也成立。     

Stability of Discrete Approximations and Necessary Optimality Conditions for Delay-Differential Inclusions

This paper is devoted to the study of optimization problems for dynamical systems governed by constrained delay-differential inclusions with generally nonsmooth and nonconvex data. We provide a variational analysis of the dynamic optimization problems based on their data perturbations that involve finite-difference approximations of time-derivatives matched with the corresponding perturbations of endpoint constraints. The key issue of such an analysis is the justification of an appropriate strong stability of optimal solutions under finite-dimensional discrete approximations. We establish the required pointwise convergence of optimal solutions and obtain necessary optimality conditions for delay-differential inclusions in intrinsic Euler–Lagrange and Hamiltonian forms involving nonconvex-valued subdifferentials and coderivatives of the initial data.     

Note on the optimal transportation of distributions

We extend our work on the optimal mapping of distributions in three directions: (a) we consider any set-valued mapping, not just diffeomorphisms; (b) we distinguish between weak and strong optimality, and identify strong optimality with cyclic monotonicity; and (c) we prove that, under some restrictions, a weakly optimal mapping has the subgradient property.     

On Optimality Conditions for Generalized Semi-Infinite Programming Problems

Generalized semi-infinite optimization problems (GSIP) are considered. We generalize the well-known optimality conditions for minimizers of order one in standard semi-infinite programming to the GSIP case. We give necessary and sufficient conditions for local minimizers of order one without the assumption of local reduction. The necessary conditions are derived along the same lines as the first-order necessary conditions for GSIP in a recent paper of Jongen, Rückmann, and Stein (Ref. 1) by assuming the so-called extended Mangasarian–Fromovitz constraint qualification. Using the ideas of a recent paper of Rückmann and Shapiro, we give short proofs of necessary and sufficient optimality conditions for minimizers of order one under the additional assumption of the Mangasarian–Fromovitz constraint qualification at all local minimizers of the so-called lower-level problem.     

Sufficient Optimality Conditions for Optimal Control Problems with State Constraints

It is well-known in optimal control theory that the maximum principle, in general, furnishes only necessary optimality conditions for an admissible process to be an optimal one. It is also well-known that if a process satisfies the maximum principle in a problem with convex data, the maximum principle turns to be likewise a sufficient condition. Here an invexity type condition for state constrained optimal control problems is defined and shown to be a sufficient optimality condition. Further, it is demonstrated that all optimal control problems where all extremal processes are optimal necessarily obey this invexity condition. Thus optimal control problems which satisfy such a condition constitute the most general class of problems where the maximum principle becomes automatically a set of sufficient optimality conditions.     

On First Order Optimality Conditions for Vector Optimization

We develop first order optimality conditions for constrained vector optimization. The partial orders for the objective and the constraints are induced by closed and convex cones with nonempty interior. After presenting some well known existence results for these problems, based on a scalarization approach, we establish necessity of the optimality conditions under a Slater-like constraint qualification, and then sufficiency for the K-convex case. We present two alternative sets of optimality conditions, with the same properties in connection with necessity and sufficiency, but which are different with respect to the dimension of the spaces to which the dual multipliers belong. We introduce a duality scheme, with a point-to-set dual objective, for which strong duality holds. Some examples and open problems for future research are also presented,