Engineering Optimization: Theory and Practice, Fourth Edition

9.9 Continuous Dynamic Programming 575

to the solution of continuous decision problems, consider the following simple (uncon-
strained) problem. Find the functiony(x)that minimizes the integral

f=

∫b

x=a

R

(

dy

dx

, y, x

)

dx (9.33)

subject to the known end conditionsy(x=a)=α, andy(x=b)=β. We shall see
how dynamic programming can be used to determiney(x)numerically. This approach
will not yield an analytical expression fory(x)but yields the value ofy(x)at a finite
number of points in the intervala≤x≤b. To start with, the interval (a,b) is divided
intonsegments each of lengthx(all the segments are assumed to be of equal length
only for convenience). The grid points defining the various segments are given by

x 1 = a, x 2 = a+x,... ,

xi =a+(i− 1 )x,... , xn+ 1 = a+nx=b

Ifxis small, the derivativedy/dxatxican be approximated by a forward difference
formula as
dy
dx

(xi)≃

yi+ 1 −yi

x

(9.34)

whereyi= y(xi) ,i= 1 , 2 ,... , n+1. The integral in Eq. (9.33) can be approxi-
mated as

f ≃

∑n

i= 1

R

[

dy

dx

(xi), y(xi), xi

]

x (9.35)

Thus the problem can be restated as

Findy(x 2 ),y(x 3 ) ,.. .,y(xn) which minimizes,

f≃x

∑n

i= 1

R

{

yi+ 1 −yi

x

, yi, xi

}

(9.36)

subject to the known conditionsy 1 = αandyn+ 1 =β.
This problem can be solved as a final value problem. Let

fi∗(θ )= min

yi+ 1 ,yi+ 2 ,...,yn

{n

∑

k= 1

R

(

yk+ 1 −yk

x

, yk, xk

)

x

}

(9.37)

whereθis a parameter representing the various values taken byyi. Thenfi∗(θ ) can
also be written as

fi∗(θ ) =min

yi+ 1

[

R

{

yi+ 1 −θ

x

, θ, xi

}

x+fi∗+ 1 (yi+ 1 )

]

(9.38)

This relation is valid fori= 1 , 2 ,... , n−1, and

fn∗(θ )=R

(

β−θ

x

, θ, xn

)

x (9.39)

Finally the desired minimum value is given byf 0 ∗(θ =α).