当前位置：网站首页>Basic recursive equation of DP

Basic recursive equation of DP

2022-07-26 11:22:00 【AutoGalaxy】

One . Give the teacher's first PPT

Two . I mean , Four pages PPT, The basic recurrence equation of dynamic programming can be summarized

Here, push it with your own hand , To record

The targeted system looks like this ：

$\left\{\begin{equation} x(k+1)=f(x(k),u(k),k) \\ x(0)=0 \end{equation}\right.$

Our goal is ： Permissive u^*(k)(k=0,1,2,...,N-1) , Minimize the following performance index functions

$J_{N}=\sum_{k=0}^{N-1}L[x(k),u(k),k]$

Here is from u(0) At the beginning , Therefore, the performance index function can be expressed as J[x(0),u]

Here's one more sentence , In order to generalize the problem , Value is starting from any state x(k) , Then the performance index function can be written as J[x(k),k] , meanwhile The meaning is as follows ： By state x(k) To the end of the process , By any sequence u The resulting cost .

Then the optimal performance index （ The following notation ）：

J^*[x(k),u]=J[x(k),u^*]=J^*[x(k)]

because x(k) There is still N-k level , So here we use $J^*_{N-k}[x(k)]$ Indicates that the initial state is x(k), There is still N-k The best performance index of level .

Next, we will further deduce $J^*_{N-k}[x(k)]$

$\begin{aligned} J^*_{N-k}[x(k)] &=\min_{u(k),u(k+1),...,u(N-1)}\sum_{j=k}^{N-1} L[x(j),u(j),j]\\ &= \min_{u(k),u(k+1),...,u(N-1)}(L[x(k),u(k),k]+\sum_{j=k+1}^{N-1} L[x(j),u(j),j]) \\ \end{aligned}$

To sum up , It's a system , A target performance index function , A derivation （ The goal of derivation is to find out the relationship between the current state and the next state ）

Finally, let's move to a practical example

For the above performance index function , There is no end value

Then from the above recursion, we can get about x[N] The formula of