文档介绍：Dynamic Programming and Optimal Control
SECOND EDITION
Dimitri P. Bertsekas
Massachusetts Institute of Technology
Selected Theoretical Problem Solutions
Last Updated 3/25/2006
Athena Scientific, Belmont, Mass.
k information and orders
/
1
NOTE
This solution set is meant to be a significant extension of the scope and coverage of the book. It
includes solutions to all of the book’s exercises marked with the symbol www .
The solutions are continuously updated and improved, and additional material, including new prob-
lems and their solutions are being added. Please ments, and suggestions for additions and
improvements to the author at ******@
The solutions may be reproduced and distributed for personal or educational uses.
2
Solutions Vol. I, Chapter 1
www
We first show the result given in the hint. We have for all µ ∈ M
max G0(w)+G1 f(w),µ(f(w)) ≥ max G0(w) + min G1 f(w),u
w∈W w∈W u∈U
and, taking min over µ ∈ M we obtain
min max G0(w)+G1 f(w),µ(f(w)) ≥ max G0(w) + min G1 f(w),u . (1)
µ∈M w∈W w∈W u∈U
We must therefore show the reverse inequality. For any >0, let µ ∈ M be such that
G1 f(w),µ(f(w)) ≤ min G1 f(w),u + , ∀ w ∈ W
u∈U
(Such a µ exists because of the assumption that minu∈U G1 f(w),u > −∞.) Then
min max G0(w)+G1 f(w),µ(f(w)) ≤ max G0(w)+G1 f(w),µ(f(w))
µ∈M w∈W w∈W
.
≤ max G0(w) + min G1 f(w),u +
w∈W u∈U
Since >0 can be taken arbitrarily small we obtain the reverse inequality to Eq. (1), and thus the desired
result.
To see how this result can fail without the condition minu∈U G1 f(w),u > −∞ for all w, let u
be a real number, let w =(w1,w2) be a two-dimensional vector, let there be no constraints on u and w
(U = , W = ×, where is the real line), let G0(w)=w1, f(w)=w2, and G1[f(w),u]=f(w)+u.
Then
max G0(w)+G1 f(w),µ(f(w)) = max w1 + w2 + µ(w2) = ∞, ∀µ ∈ M,
w∈W w1∈,w2∈
so that