View source for Maximum principle

<!--
m0631201.png
$#A+1 = 35 n = 0
$#C+1 = 35 : ~/encyclopedia/old_files/data/M063/M.0603120 Maximum principle,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''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|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|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|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|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 [[#References|[1]]]–[[#References|[5]]]).

If the optimal control problem for a linear discrete system is treated as a [[Linear programming|linear programming]] problem (see [[#References|[6]]], [[#References|[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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.-Ts. Fan,   Ch.-S. Wang,   "The discrete maximum principle" , Wiley  (1964)  {{MR|0165981}} {{ZBL|0143.42905}} {{ZBL|0128.14503}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.I. Propoi,   "Elements of the theory of optimal processes" , Moscow  (1973)  (In Russian)  {{MR|}} {{ZBL|}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  B.H. Pshenichnyi,   "Necessary conditions for an extremum" , M. Dekker  (1971)  (Translated from Russian)  {{MR|0276845}} {{ZBL|0764.90079}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  V.G. Boltyanskii,   "Optimal control of discrete systems" , Wiley  (1978)  (Translated from Russian)  {{MR|0528636}} {{MR|0514558}} {{ZBL|}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  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  {{MR|0215632}} {{ZBL|}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  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)  {{MR|286533}} {{ZBL|}} </TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  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  {{MR|}} {{ZBL|0233.90015}} </TD></TR></table>

====Comments====
For the maximum principle for analytic functions see [[Maximum-modulus principle|Maximum-modulus principle]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.E. Bryson,   Y.-C. Ho,   "Applied optimal control" , Ginn  (1969)  {{MR|0446628}} {{ZBL|}} </TD></TR></table>