Maximum principle

discrete

The Pontryagin maximum principle for discrete-time control processes. For such a process the maximum principle need not be satisfied, even if the Pontryagin maximum principle is valid for its continuous analogue, obtained by replacing the finite difference operator $ x _ {t+1} - x _ {t} $ by the differential $ d x / d t $. For example, consider the optimal control problem

$$ \tag{1 } \max J ( x _ {T+1} ) , $$

$$ \tag{2 } x _ {t+1} = f _ {t} ( x _ {t} , u _ {t} ) , $$

$$ \tag{3 } u _ {t} \in U ,\ t = 0 \dots T , $$

$$ \tag{4 } x _ {0} = a . $$

This can be treated as a standard problem on an extremum in the presence of constraints. Then the condition for optimality of a trajectory $ \{ x _ {t} ^ {*} , u _ {t} ^ {*} \} $ can be obtained with the help of the Lagrange function

$$ L = J ( x _ {T+1} ) + \sum _ { t= 0} ^ { T } ( p _ {t+1} f _ {t} ( x _ {t} , u _ {t} ) - p _ {t+1} x _ {t+1} ) . $$

Here

$$ p _ {t+1} f _ {t} ( x _ {t} , u _ {t} ) = \ H _ {t} , $$

by analogy with the continuous case, is called the Hamilton function. Let $ J $, $ f _ {t} $, $ t = 0 \dots T $, be differentiable functions with respect to all variables and let $ U $ be a bounded closed set. Then for a solution $ \{ x _ {t} ^ {*} , u _ {t} ^ {*} \} $ of (1)–(4) to be optimal it is necessary that there exist Lagrange multipliers $ \{ p _ {t+1} ^ {*} \} $ such that $ ( x _ {t} ^ {*} , u _ {t} ^ {*} , p _ {t+1} ^ {*} ) $ is a stationary point of the Lagrange function, that is, at this point

$$ \frac{\partial L }{\partial x } = 0 ; \ \ \frac{\partial L }{\partial p } = 0 ; \ \ \delta _ {n} L = \ \frac{\partial L }{\partial u } \delta u \leq 0 $$

for all admissible variations of the control $ \delta u $. The first condition leads to the dynamical equations of the discrete process (2) and the initial condition (4). The second leads to the boundary condition and the conjugate system for the impulses $ \{ p _ {t+1} \} $:

$$ p _ {T+1} = \ \frac{\partial J }{\partial x _ {T+1} } , $$

$$ p _ {t} = p _ {t+1} \frac{\partial f }{\partial x _ {t} } ,\ t = T \dots 0 . $$

The third condition leads to a condition on the first variation of the Hamilton function:

$$ \tag{5 } \delta _ {n} H _ {t} = \ \frac{\partial H _ {t} }{\partial u _ {t} } \delta u _ {t} \leq 0 . $$

However, (5) does not imply that the Hamilton function attains its maximum at the optimal control,

$$ H _ {1} ( x _ {t} ^ {*} , u _ {t} ^ {*} , p _ {t+1} ^ {*} ) = \ \max _ {u \in U } \ H _ {t} ( x _ {t} ^ {*} , u _ {t} ^ {*} , p _ {t+1} ^ {*} ), $$

over all controls satisfying the constraint (3); it shows that $ u _ {t} ^ {*} $ is a stationary point of the Hamilton function. If the first variation of the Hamilton function, $ ( \partial H _ {t} / \partial u _ {t} ) \delta u _ {t} $, is zero (this holds, in particular, when $ u _ {t} ^ {*} $ is an interior point or when there are admissible variations $ \delta u _ {t} $ of the control at $ u _ {t} ^ {*} $ orthogonal to $ \partial H _ {t} / \partial u _ {t} $), then the nature of the stationary point is determined by the successive terms in the expansion:

$$ H _ {t} ( u _ {t} ^ {*} + \epsilon \delta u _ {t} ) - H _ {t} ( u _ {t} ^ {*} ) = \epsilon \frac{\partial H _ {t} }{\partial u _ {t} } \delta u _ {t} < 0 . $$

Examples have been constructed in which $ u _ {t} ^ {*} $ is a local maximum, a local minimum and even a saddle point of the Hamilton function. Therefore, in general, the maximum principle does not hold for discrete systems.

For systems which are linear in the phase variables,

$$ x _ {t+1} = A ( u _ {t} ) x _ {t} + \phi ( u _ {t} ), $$

or in the controls,

$$ x _ {t+1} = g ( x _ {t} ) + B ( x _ {t} ) u _ {t} , $$

under the additional condition of linearity of the objective $ J = c _ {T+1} x _ {T+1} $ in the first case, or convexity of $ U $ in the second case, the maximum principle is satisfied (see [1]–[5]).

If the optimal control problem for a linear discrete system is treated as a linear programming problem (see [6], [7]), then its dual discrete-time dynamical problem may be obtained. The conjugate system for the impulses gives the dynamical equation for the dual problem. On an optimal trajectory not only the objective but also the Hamilton functions of dual dynamical systems coincide.

References

[1]	L.-Ts. Fan, Ch.-S. Wang, "The discrete maximum principle" , Wiley (1964) MR0165981 Zbl 0143.42905 Zbl 0128.14503
[2]	A.I. Propoi, "Elements of the theory of optimal processes" , Moscow (1973) (In Russian)
[3]	B.H. Pshenichnyi, "Necessary conditions for an extremum" , M. Dekker (1971) (Translated from Russian) MR0276845 Zbl 0764.90079
[4]	V.G. Boltyanskii, "Optimal control of discrete systems" , Wiley (1978) (Translated from Russian) MR0528636 MR0514558
[5]	R. Gabasov, F.M. Kirillova, "Extending L.S. Pontryagin's maximum principle to discrete systems" Automation and Remote Control , 27 (1966) pp. 1878–1882 Avtomatika i Telemekhanika , 11 (1966) pp. 46–51 MR0215632
[6]	Yu.P. Ivanilov, "Conjugate (dual) linear dynamic optimization problems and procedures for their computation" Prikl. Mat. i Programmirov. , 4 (1971) pp. 31–40 (In Russian) MR286533
[7]	Yu.P. Ivanilov, A.I. Propoi, "On linear dynamic programming problems" Soviet Math. Dokl. , 12 : 3 (1971) pp. 926–930 Dokl. Akad. Nauk SSSR , 198 : 5 (1971) pp. 1011–1014 Zbl 0233.90015

Comments

For the maximum principle for analytic functions see Maximum-modulus principle.

References

[a1]	A.E. Bryson, Y.-C. Ho, "Applied optimal control" , Ginn (1969) MR0446628