Programming and Optimal Control2.pdf

(8561 KB) Pobierz
Dynamic
Programming
and Optimal Control
Volume I
THIRD EDITION
P. Bertsekas
Massachusetts Institute of Technology
WWW site for book information and
http://www.athenasc.com
IiJ
Athena Scientific, Belmont,
Athena Scientific
Post Office Box
805
NH 03061-0805
U.S.A.
ErnaH: info@athenasc.com
WWW: http://www.athenasc.co:m
ABOUT THE AUTHOR
Dimitri Bertsekas studied Mechanical and Electrical Engineering at
the National Technical University of Athens, Greece, and obtained his
Ph.D. in system science from the Massachusetts Institute of Technology. He
has held faculty positions with the Engineering-Economic Systems Dept.,
Stanford University, and the Electrical Engineering Dept. of the Univer-
sity of Illinois, Urbana. Since 1979 he has been teaching at the Electrical
Engineering and Computer Science Department of the Massachusetts In-
stitute of Technology (M.LT.), where he is currently McAfee Professor of
Engineering.
His research spans several fields, including optimization, control, la,rge-
scale computation, and data communication networks, and is closely tied
to his teaching and book authoring activities. He has written llUInerous
research papers, and thirteen books, several of which are used as textbooks
in MIT classes. He consults regularly with private industry and has held
editorial positions in several journals.
Professor Bertsekas was awarded the INFORMS 1997 Prize for H,e-
search Excellence in the Interface Between Operations Research and Com-
puter Science for his book "Neuro-Dynamic Programming" (co-authored
with John Tsitsiklis), the 2000 Greek National Award for Operations Re-
search, and the 2001 ACC John R. Ragazzini Education Award. In 2001,
he was elected to the United States National Academy of Engineering.
Cover Design: Ann Gallager, www.gallagerdesign.com
©
2005, 2000, 1995 Dimitri P. Bertsekas
All rights reserved. No part of this book may be reproduced in any form
by
~1Il~
electronic or mechanical means (including photocopying, recording,
or mlormation storage and retrieval) without permission in writing from
the publisher.
Publisher's Cataloging-in-Publication Data
Bertsekas, Dimitri P.
Dynamic Programming and Optimal Control
Includes Bibliography and Index
1.
Mathematical Optimization. 2. Dynamic Programming. L Title.
QA402.5 .13465 2005
519.703
00-91281
ISBN 1-886529-26-4
ATHENA SCIENTIFIC
OPTIMIZATION AND COl\1PUTATION SERIES
1. Convex Analysis and Optimization, by Dimitri P. Bertsekas, with
Angelia Nedic and Asuman E. Ozdaglar, 2003, ISBN 1-886529-
45-0, 560 pages
2. Introduction to Probability, by Dimitri P. Bertsekas and John N.
Tsitsiklis, 2002, ISBN 1-886529-40-X, 430 pages
3.
Dynamic Programming and Optimal Control, Two-Volume Set,
by Dimitri P. Bertsekas, 2005, ISBN 1-886529-08-6, 840 pages
4.
Nonlinear Programming, 2nd Edition, by Dimitri P. Bertsekas,
1999, ISBN 1-886529-00-0, 791 pages
Contents
1.
The Dynamic Programming Algorithm
1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
1.7.
Introduction
. . . . . . . . .
The Basic Problem. . . . . . . . . .
The Dynamic Programming Algorithm .
State Augmentation and Other Reformulations
Some Mathematical Issues . . . . . . . .
Dynamic Prograrnming and Minimax Control
Notes, Sources, and Exercises . . . . . . .
p.
2
p.
12
p. 18
p.35
p.42
p.
46
p.51
5. Network Optimization: Continuous and Discrete Models, by Dim-
itri P. Bertsekas, 1998, ISBN 1-886529-02-7, 608 pages
6.
Network Flows and Monotropic Optimization, by R. Tyrrell Rock-
2. Deterministic Systems and the Shortest Path Probleln
2.1. Finite-State Systems and Shortest Paths
2.2. Some Shortest Path Applications
2.2.1. Critical Path Analysis
2.2.2. Hidden Markov Models and the Viterbi Algorithm
2.3. Shortest Path Algorithms . . . . . . . . . . .
2.3.1. Label Correcting Methods. . . . . . . .
2.3.2. Label Correcting Variations -
A
*
Algorithm
2.3.3. Branch-and-Bound . . . . . . . . . .
2.3.4. Constrained and Multiobjective Problems
2.4. Notes, Sources, and Exercises .
p.
64
p.
fl8
areUar, 1998, ISBN 1-886529-06-X, 634 pages
7. Introduction to Linear Optimization, by Dimitris Bertsimas and
John N. Tsitsiklis, 1997, ISBN 1-886529-19-1, 608 pages
8. Parallel and Distributed Computation: Numerical Methods, by
Dimitri P. Bertsekas and John N. Tsitsiklis, 1997, ISBN 1-886529-
01-9, 718 pages
9. Neuro-Dynamic Programming, by Dimitri P. Bertsekas and John
N. Tsitsiklis, 1996, ISBN 1-886529-10-8, 512 pages
10. Constra,ined Optimization and Lagrange Multiplier Methods, by
Dimitri P. Bertsekas, 1996, ISBN 1-88f1529-04-3, 410 pages
11. Stochastic Optirnal Control: The Discrete-Time Case, by Dimitri
P. Bertsekas and Steven E. Shreve, 1996, ISBN 1-886529-03-5,
330 pages
p.
68
p.70
p.77
p.
78
p.
87
p.88
p.91
p. 97
3. Deterministic Continuous-Time
3.1. Continuous-Time Optimal Control
3.2. The Hamilton-Jacobi-Bellman Equation
3.3. The Pontryagin Minimum Principle
3.3.1. An Informal Derivation Using the HJB Equation
3.3.2. A Derivation Based on Variational Ideas
3.3.3. Minimum Principle for Discrete-Time Problems
3.4. Extensions of the Minimum Principle
3.4.1. Fixed Terminal State
3.4.2. Free Initial State
p.106
p.109
p.115
p.115
p.
125
p.129
p.
131
p.131
p.135
vi
Contents
Contents
vii
p.
~366
3.4.3. Free Terminal Time . . . . .
~.L4.4.
Time-Varying System and Cost
3.4.5. Singular Problems . .
~~.5.
Notes, Sources, and Exercises . . . .
p.135
p.138
p.139
p.142
4. Problellls with Perfect State Information
4.1.
4.2.
L1.3.
4.4.
4.5.
4.6.
Linear Systems and Quadratic Cost
Inventory Control
Dynamic Portfolio Analysis . . . .
Optimal Stopping Problems . . . .
Scheduling and the Interchange Argument
Set-Membership Description of Uncertainty
4.6.1. Set-Membership Estimation . . . .
4.6.2. Control with Unknown-but-Bounded Disturbances
4.7. Notes, Sources, and Exercises . . . . . . . . . . . .
p.148
p. 162
p.170
p.176
p. 186
p.190
p.191
p.197
p.201
6.5. Model Predictive Control and Related Methods
6.5.1. Rolling Horizon Approximations . . . .
6.5.2. Stability Issues in Model Predictive Control
6.5.3. Restricted Structure Policies . .
6.6. Additional Topics in Approximate DP
6.6.1. Discretization . . . . . . . .
6.6.2. Other Approximation Approaches
6.7. Notes, Sources, and Exercises . . . . .
p.367
p.369
p.
~376
p. 382
p. 382
p.
38
L
1
p. 386
7. Introduction to Infinite Horizon Problems
7.1.
7.2.
7.3.
7.4.
7.5.
7.6.
An Overview . . . . . . . . .
Stochastic Shortest Path Problems
Discounted Problems . . . . . .
Average Cost per Stage Problems
Semi-Markov Problems . . .
Notes, Sources, and Exercises . .
p.402
p.405
p.417
p.421
p.435
p. 445
5. Problen'ls with Imperfect State Information
5.1.
5.2.
5.3.
5.4.
Reduction to the Perfect Information Case
Linear Systems and Quadratic Cost
Minimum Variance Control of Linear Systems
SufIicient Statistics and Finite-State Markov Chains
5.4.1. The Conditional State Distribution
5.4.2. Finite-State Systems .
5.5. Notes, Sources, and Exercises
p.218
p.229
p.236
p.251
p.252
p.258
p.270
Appendix A: Mathematical Review
A.1.
A.2.
A.3.
A.4.
A.5.
Sets
.
Euclidean Space.
Matrices . . . .
Analysis . . . .
Convex Sets and Functions
p.459
p.460
p.461
p. 465
p.467
6.
Control
6.1. Certainty Equivalent and Adaptive Control
G.l.l.
Caution, Probing, and Dual Control
6.1.2. Two-Phase Control and Identifiability
6.1.~1.
Certainty Equivalent Control and Identifiability
6.1.4. Self-Tuning Regulators
G.2. Open-Loop Feedback Control . . . . . . . . . "
t\.~3.
Limited Lookahead Policies . . . . . . . . . . . .
6.3.1. Performance Bounds for Limited Lookahead Policies
6.3.2. Computational Issues in Limited Lookahead . . .
G.3.3. Problem Approximation - Enforced Decomposition
6.3.4. Aggregation . . . . . . . . . . . .
6.3.5. Parametric Cost-to-Go Approximation
6.4. Rollout Algorithms. . . . . . . . . .
6.4.1. Discrete Deterministic Problems .
6.4.2. Q-Factors Evaluated by Simulation
6.4.3. Q-Factor Approximation
p. 283
p. 289
p. 291
p. 293
p. 298
p. 300
p. 304
p. 305
p. 310
p. 312
p. 319
p. 325
p. 335
p. 342
p.361
p. 363
Appendix B: On Optimization Theory
B.1. Optimal Solutions . . . . . . .
B.2. Optimality Conditions . . . . .
B.3. Minimization of Quadratic J:iorms
p.468
p.470
p.471
Appendix C: On Probability Theory
C.l. Probability Spaces. . .
C.2. Random Variables
C.3.
Conditional Probability
p.472
p.
47~i
p.
475
Appendix D: On Finite-State Markov Chains
D.l.
D.2.
D.3.
D.4.
Stationary Markov Chains
Classification of States
Limiting Probabilities
First Passage Times .
p.477
p.478
p.479
p.480
viii
P'C'A.a'LIU.lI..
Contents
Contents
E: Kalman Filtering
p.481
p.483
p.491
p.496
p.499
p.501
COl\fTENTS OF VOLUIVIE II
1.
Infinite Horizon - Discounted Problems
E.l. Least-Squares Estimation .
E.2. Linear Least-Squares Estimation
E.~1.
State Estimation
Kalman Filter
E.4. Stability Aspects . . . . . . .
E.5. Gauss-Markov Estimators
E.6. Deterministic Least-Squares Estimation
Appendix F: lVIodeling of Stochastic Linear Systems
F .1. Linear Systems with Stochastic Inputs
F.2. Processes with Rational Spectrum
F
.~1.
The ARMAX Model . . . . . .
p. 503
p.
504
p.
506
1.1. Minimization of Total Cost Introduction
1.2. Discounted Problems with Bounded Cost per Stage
1.3. Finite-State Systems - Computational Methods
1.3.1. Value Iteration and Error Bounds
1.3.2. Policy Iteration
1.3.3. Adaptive Aggregation
1.3.4. Linear Programming
1.3.5. Limited Lookahead Policies
1.4. The Role of Contraction Mappings
1.5. Scheduling and Multiarmed Bandit Problems
1.6. Notes, Sources, and Exereises
2. Stochastic Shortest Path Problems
G: Forrnulating Problems of Decision Under Uncer-
G.l. T'he Problem of Decision Under Uncertainty
G.2. Expected Utility Theory and Risk . .
G.3. Stoehastic Optimal Control Problems
References
Index . . .
p.
507
p.511
p.524
p.529
p.541
2.1. Main Results
2.2. Computational Methods
2.2.1. Value Iteration
2.2.2. Policy Iteration
2.3. Simulation-Based Methods
2.3.1. Policy Evaluation by Monte-Carlo Simulation
2.3.2. Q-Learning
2.3.3. Approximations
2.3.4. Extensions to Discounted Problems
2.3.5. The Role of Parallel Computation
2.4. Notes, Sources, and Exereises
3. Undiscounted Problems
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
Unbounded Costs per Stage
Linear Systems and Quadratic Cost
Inventory Control
Optimal Stopping
Optimal Gambling Strategies
Nonstationary and Periodic Problems
Notes, Sourees, and Exercises
4. Average Cost per Stage Problems
4.1. Preliminary Analysis
4.2. Optimality Conditions
4.3. Computational Methods
4.3.1. Value Iteration

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin