Dynamic Programming And Its Application To Optimal Control

Dynamic Programming and Its Application to Optimal Control This is Volume 81 in MATHEMATICS IN SCIENCE AND ENGINEERING A series of monographs and textbooks Edited by RICHARD BELLMAN, University of Southern California A partial list of the books in this series appears at the end of this volume. A complete listing is available from the Publisher upon request. DYNAMIC PROGRAMMING AND ITS APPLICATION TO OPTIMAL CONTROL R. Boudarel INTERNATIONAL COMPANY FOR INFORMATION TECHNOLOGY LOUVECIENNES, FRANCE J. Delmas CENTER FOR STUDY AND RESEARCH IN AUTOMATION TOULOUSE, FRANCE P. Guichet INTERNATIONAL COMPANY FOR INFORMATION TECHNOLOGY LOUVECIENNES. FRANCE Translated by R. N . McDonough DEPARTMENT OF ELECTRICAL ENGINEERING UNIVERSITY OF DELAWARE NEWARK, DELAWARE W A C A D E M I C PRESS New York and London 1971 COPYRIGHT 0 1971, BY ACADEMIC PRESS, INC. ALL RIGHTS RESERVED NO PART O F THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM T H E PUBLISHERS. Originally published in the French language under the title “Comrnande Optimale des Processus,” Tome 3, “Programmation Dynamique e t ses Applications,” and copyrighted in 1968 by Dunod, Paris. ACADEMIC PRESS, INC. 1 1 1 Fifth Avenue, New York, New York lp003 United Kingdom Edition published b y ACADEMIC PRESS. INC. (LONDON)’ LTD. Berkeley Square House, London W l X 6BA LiBRARY OF CONGRESS CATALOG CARD NUMBER:79-154364 AMS (MOS) 1970 Subject Classification: 49C05 PRINTED IN THE UNITED STATES O F AMERICA ASIN: B0043EJNNE Contents Foreword Preface xi xiii PART 1 DISCRETE DETERMINISTIC PROCESSES Chapter 1 The Principles of Dynamic Programming 1.1 General Description of the Method 1.2 Example of the General Method 1.3 Sequential Decision Problems and the Principle of Optimality 1.4 An Example of Application of the Principle of Optimality 1.5 Remarks Chapter 2 Processes with Bounded Horizon 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Definition of a Discrete Process Statement of the Problem Application of the Principle of Optimality Direct Derivation of the Recurrence Equation Analog Interpretation of the Recurrence Equation Practical Application of the Recurrence Equation Additive Constraints Sensitivity of the Solution 9 10 10 11 12 13 16 19 Chapter 3 Processes with Infinite or Unspecified Horizon 3.1 3.2 3.3 3.4 Processes with Infinite Horizon Processes with Unspecified Horizon Structure and Stability of a System with Infinite Horizon Calculation of the Solution of the Optimality Equation 21 21 22 24 Chapter 4 Practical Solution of the Optimal Recurrence Relation 4.1 4.2 4.3 4.4 Search for an Optimum The Problem of Dimensionality Domain of Definition of the Return Function Solution by Successive Approximations V 30 31 33 37 vi 4.5 4.6 4.7 4.8 C0N TEN TS The Use of Legendre Polynomials Linear Systems with Quadratic Costs Linearization Reduction of the Dimensionality 40 46 52 52 PART 2 DISCRETE RANDOM PROCESSES Chapter 5 5. I 5.2 5.3 5.4 5.5 General Theory Optimal Control of Stochastic Processes Processes with Bounded Horizon and Measurable State Processes with Random Horizon and Measurable State Processes with a State Not Completely Measurable Conclusions 57 59 64 66 69 Chapter 6 Processes with Discrete States 6.1 Fundamentals 6.2 Terminal Problems 6.3 Optimization of a Return Function 6.4 Discrete Stochastic Processes with Discrete States Which Are Not Completely Measurable 71 74 79 87 PART 3 NUMERICAL SYNTHESIS OF THE