Search

We formulate and study the infinite dimensional linear programming (LP) problem associated with the deterministic discrete time long-run average criterion optimal control problem. Along with its du...

International audience; In this paper, we study asymptotic properties of problems of control of stochastic discrete time systems with time averaging and time discounting optimality criteria, and we establish that the Cesàro and Abel limits of the optimal values in such problems can be estimated with the help of a certain infinite-dimensional (ID) linear programming (LP) problem and its dual.

We consider infinite horizon optimal control problems with time averaging and time discounting criteria and give estimates for the Cesàro and Abel limits of their optimal values in the case when they depend on the initial conditions. We establish that these limits are bounded from above by the optimal value of a certain infinite dimensional (ID) linear programming (LP) problem and that they are bounded from below by the optimal value of the corresponding dual problem. (These estimates imply, in particular, that the Cesàro and Abel limits exist and are equal to each other if there is no duality gap). In addition, we obtain IDLP-based optimality conditions for the long run average optimal control problem, and we illustrate these conditions by an example.

We consider stabilization of an equilibrium point via infinite horizon discounted optimal control in discrete-time. In addition to applications in economics and social sciences, discounted optimal control is a commonly used numerical technique guaranteeing solvability of certain classes of optimal control problems . In this paper, we present conditions based on strict dissipativity that ensure that the optimally controlled system is asymptotically stable or practically asymptotically stable. These conditions are shown to be complementary to recently proposed conditions based on a detectability property. Illustrative examples are provided.

The paper deals with a problem of control of a system characterized by the fact that the influence of controls on the dynamics of certain functions of state variables (called observables) is relatively weak and the rates of change of these observables are much slower than the rates of change of the state variables themselves. The contributions of the paper are twofold. Firstly, the averaged system whose solutions approximate the trajectories of the slow observables is introduced, and it is shown that the optimal value of the problem of optimal control with time discounting criterion considered on the solutions of the system with slow observables (this problem is referred to as perturbed) converges to the optimal value of the corresponding problem of optimal control of the averaged system. Secondly, a way how an asymptotically optimal control of the perturbed problem can be constructed on the basis of an optimal solution of the averaged problem is indicated, sufficient and necessary optimality conditions for the averaged problem are stated, and a way how a near optimal solution of the latter can be constructed numerically is outlined (the construction being illustrated with an example)., 40 pages, 4 figures

We study a non-zero sum game considered on the solutions of a hybrid dynamical system that evolves in continuous time and that is subjected to abrupt changes of parameters. The changes of the parameters are synchronized with (and determined by) the changes of the states/actions of two Markov decision processes, each of which is controlled by a player that aims at minimizing his or her objective function. The lengths of the time intervals between the " jumps " of the parameters are assumed to be small. We show that an asymptotic Nash equilibrium of such hybrid game can be constructed on the basis of a Nash equilibrium of a deterministic averaged dynamic game.

We formulate and study the infinite-dimensional linear programming problem associated with the deterministic long-run average cost control problem. Along with its dual, it allows one to characterize the optimal value of this control problem. The novelty of our approach is that we focus on the general case wherein the optimal value may depend on the initial condition of the system.

It has been recently established that a deterministic infinite horizon discounted optimal control problem in discrete time is closely related to a certain infinite dimensional linear programming problem and its dual. In the present paper, we use these results to establish necessary and sufficient optimality conditions for this optimal control problem and apply them to construct a near optimal control., 25 pages

This paper is devoted to a study of infinite horizon optimal control problems with time discounting and time averaging criteria in discrete time. We establish that these problems are related to certain infinite-dimensional linear programming (IDLP) problems. We also establish asymptotic relationships between the optimal values of problems with time discounting and long-run average criteria.

A problem of minimization of L1-penalized conditional value-at-risk (CVaR) is considered. It is shown that there exists a non-negative threshold value of the penalty parameter such that the optimal value of the penalized problem is unbounded if the penalty parameter is less than the threshold value, and it is bounded if the penalty parameter is greater or equal than this value. It is established that the threshold value can be found via the solution of a linear programming problem, and, therefore, readily computable. Theoretical results are illustrated by numerical examples. Refereed/Peer-reviewed

International audience; Linear programming formulations for the discounted and long-run average MDPs have evolved along separate trajectories. In 2006, E. Altman conjectured that the two linear programming formulations of discounted and long-run average MDPs are, most likely, a manifestation of general properties of singularly perturbed linear programs. In this note we demonstrate that this is, indeed, the case.

It has been established recently that, under mild conditions, deterministic long run average problems of optimal control are “asymptotically equivalent” to infinite-dimensional linear programming problems (LPPs) and that these LPPs can be approximated by finite-dimensional LPPs. In this paper we introduce the corresponding infinite- and finite-dimensional dual problems and study duality relationships. We also investigate the possibility of using solutions of finite-dimensional LPPs and their duals for numerical construction of the optimal controls in periodic optimization problems. The construction is illustrated with a numerical example.

Deterministic long run average problems of optimal control are ''asymptotically equivalent" to infinite-dimensional linear programming problems ( LPP ) and the latter are approximated by finite dimensional LPP. The solutions of this finite dimensional LPP can be used for numerical analysis of periodic optimization problems. In the present paper we establish the convergence of controls constructed on the basis of the solution of the finite dimensional LPP to the optimal control of a periodic optimization problem. Results are illustrated with a numerical example.

We provide a condition under which infinite horizon discounted optimal control problems can be used in order to obtain stabilizing controls for nonlinear systems. The paper gives a mathematical analysis of the problem as well as an illustration by a numerical example.

We show that necessary and sufficient conditions of optimality in periodic optimization problems can be stated in terms of a solution of the corresponding HJB inequality, the latter being equivalent to a max–min type variational problem considered on the space of continuously differentiable functions. We approximate the latter with a maximin problem on a finite dimensional subspace of the space of continuously differentiable functions and show that a solution of this problem (existing under natural controllability conditions) can be used for construction of near optimal controls. We illustrate the construction with a numerical example. Refereed/Peer-reviewed

The paper aims at the development of tools for analysis and construction of near optimal solutions of singularly perturbed (SP) optimal controls problems with long run average optimality criteria. The idea that we exploit is to first asymptotically approximate a given problem of optimal control of the SP system by a certain averaged optimal control problem, then reformulate this averaged problem as an infinite-dimensional (ID) linear programming (LP) problem, and then approximate the latter by semi-infinite LP problems. We show that the optimal solution of these semi-infinite LP problems and their duals (that can be found with the help of a modification of an available LP software) allow one to construct near optimal controls of the SP system. We demonstrate the construction with a numerical example., Comment: 36 pages, 4 figures. arXiv admin note: substantial text overlap with arXiv:1309.3734

We consider the problem of control for continuous time stochastic hybrid systems in finite time horizon. The systems considered are nonlinear: the state evolution is a nonlinear function of both the control and the state. The control parameters change at discrete times according to an underlying controlled Markov chain which has finite state and action spaces. The objective is to design a controller which would minimize an expected nonlinear cost of the state trajectory. We show using an averaging procedure, that the above minimization problem can be approximated by the solution of some deterministic optimal control problem. This paper generalizes our previous results obtained for systems whose state evolution is linear in the control.

The paper aims at the development of an apparatus for analysis and construction of near optimal solutions of singularly perturbed (SP) optimal controls problems (that is, problems of optimal control of SP systems) considered on the infinite time horizon. We mostly focus on problems with time discounting criteria but a possibility of the extension of results to periodic optimization problems is discussed as well. Our consideration is based on earlier results on averaging of SP control systems and on linear programming formulations of optimal control problems. The idea that we exploit is to first asymptotically approximate a given problem of optimal control of the SP system by a certain averaged optimal control problem, then reformulate this averaged problem as an infinite-dimensional (ID) linear programming (LP) problem, and then approximate the latter by semi-infinite LP problems. We show that the optimal solution of these semi-infinite LP problems and their duals (that can be found with the help of a modification of an available LP software) allow one to construct near optimal controls of the SP system. We demonstrate the construction with two numerical examples., 53 pages, 10 figures

A singularly perturbed zero-sum differential game with full information is considered. Upper and lower value functions of this game are shown to have limits as the singular perturbations parameter tends to zero. These limits are established to coincide with viscosity solutions of some Hamilton–Jacobi type equations. A special case and two examples are considered to illustrate the general results.

We consider a class of singularly perturbed optimal control problems which may not be approximated by the reduced problems constructed via the formal replacement of the fast variables by the states of equilibrium of the "fast" subsystem considered with "frozen" slow variables and controls. We construct a reduced optimal control problem which provides a true approximation for the problems under consideration and write down the necessary and sufficient optimality conditions for this reduced problem. >

We investigate the interaction between Transmission Control Protocol (TCP) and an Active Queue Management (AQM) router, that are designed to control congestion in the Internet. TCP controls the sending rate with which the data is injected into the network and AQM generates control signals based on the congestion level. For a given TCP version, we define the optimal strategy for the AQM router as a solution of a nonlinear periodic optimization problem, and we find this solution using a linear programming approach. We show that depending on the choice of the utility function for the sending rate, the optimal control is either periodic or steady state. Main attention is paid to a problem with a sigmoidal utility function, in which the evolution of the optimal sending rate resembles a “saw-tooth” behavior of the “instantaneous” TCP sending rate.

We study a class of optimal stochastic control problems involving two different time scales. The fast mode of the system is represented by deterministic state equations whereas the slow mode of the system corresponds to a jump disturbance process. Under a fundamental "ergodicity" property for a class of "infinitesimal control systems" associated with the fast mode, we show that there exists a limit problem which provides a good approximation to the optimal control of the perturbed system. Both the finite and infinite discounted horizon cases are considered. We show how an approximate optimal control law can be constructed from the solution of the limit control problem. In the particular case where the infinitesimal control systems possess the so-called turnpike property, i.e. are characterized by the existence of global attractors, the limit control problem can be given an interpretation related to a decomposition approach. Due to the constraints on page numbers all results are presented without proofs.

A dynamic flow-shop is considered consisting of one slow and one fast machine. Production capacities of both machines vary randomly according to a Markov chain whose transition rates are consistent with the time scale of the fast machine. The problem of minimization of a discounted cost of manufacturing is formulated. A conjecture is presented regarding the asymptotic behaviour of the value function for the above problem when the separation of slow and fast time scales becomes singular. Natural conditions are formulated under which the conjecture might be satisfied.

We provide a simple test for the convergence of a sequence of subsets in an infinite-dimensional space to a compact convex one. The test reduces, roughly, the convergence problem to finite dimensions. Applications are portrayed demonstrating how convexification phenomena established in finite dimensions are easily generalized to infinite dimensions.

We consider in this paper a continuous time stochastic hybrid control system with finite time horizon. The objective is to minimize a nonlinear function of the state trajectory. The state evolves according to a nonlinear dynamics. The parameters of the dynamics of the system may change at discrete times $l\epsilon$, $l=0,1,...$, according to a controlled Markov chain which has finite state and action spaces. Under the assumption that $\epsilon$ is a small parameter, we justify an averaging procedure allowing us to establish that our problem can be approximated by the solution of some deterministic optimal control problem.