Pontryagin's maximum principle

Pontryagin's maximum principle is used in optimal control theory to find the best possible control for taking a dynamical system from one state to another, especially in the presence of constraints for the state or input controls.[1] It states that it is necessary for any optimal control along with the optimal state trajectory to solve the so-called Hamiltonian system, which is a two-point boundary value problem, plus a maximum condition of the Hamiltonian.[lower-alpha 1] These necessary conditions become sufficient under certain convexity conditions on the objective and constraint functions.[2][3]

The maximum principle was formulated in 1956 by the Russian mathematician Lev Pontryagin and his students,[4][5] and its initial application was to the maximization of the terminal speed of a rocket.[6] The result was derived using ideas from the classical calculus of variations.[7] After a slight perturbation of the optimal control, one considers the first-order term of a Taylor expansion with respect to the perturbation; sending the perturbation to zero leads to a variational inequality from which the maximum principle follows.[8]

Widely regarded as a milestone in optimal control theory,[1] the significance of the maximum principle lies in the fact that maximizing the Hamiltonian is much easier than the original infinite-dimensional control problem; rather than maximizing over a function space, the problem is converted to a pointwise optimization.[9] A similar logic leads to Bellman's principle of optimality, a related approach to optimal control problems which states that the optimal trajectory remains optimal at intermediate points in time.[10] The resulting Hamilton–Jacobi–Bellman equation provides a necessary and sufficient condition for an optimum, and admits a straightforward extension to stochastic optimal control problems, whereas the maximum principle does not.[8] However in contrast to the Hamilton–Jacobi–Bellman equation, which needs to hold over the entire state space to be valid, Pontryagin's Maximum Principle is potentially more computationally efficient in that the conditions which it specifies only need to hold over a particular trajectory.[1]

Notation

In what follows we will be making use of the following notation.

\Psi _{T}(x(T))=\left.{\frac {\partial \Psi (x)}{\partial T}}\right|_{x=x(T)}\,

\Psi _{x}(x(T))={\begin{bmatrix}\left.{\frac {\partial \Psi (x)}{\partial x_{1}}}\right|_{x=x(T)}&\cdots &\left.{\frac {\partial \Psi (x)}{\partial x_{n}}}\right|_{x=x(T)}\end{bmatrix}}

H_{x}(x^{*},u^{*},\lambda ^{*},t)={\begin{bmatrix}\left.{\frac {\partial H}{\partial x_{1}}}\right|_{x=x^{*},u=u^{*},\lambda =\lambda ^{*}}&\cdots &\left.{\frac {\partial H}{\partial x_{n}}}\right|_{x=x^{*},u=u^{*},\lambda =\lambda ^{*}}\end{bmatrix}}

L_{x}(x^{*},u^{*})={\begin{bmatrix}\left.{\frac {\partial L}{\partial x_{1}}}\right|_{x=x^{*},u=u^{*}}&\cdots &\left.{\frac {\partial L}{\partial x_{n}}}\right|_{x=x^{*},u=u^{*}}\end{bmatrix}}

f_{x}(x^{*},u^{*})={\begin{bmatrix}\left.{\frac {\partial f_{1}}{\partial x_{1}}}\right|_{x=x^{*},u=u^{*}}&\cdots &\left.{\frac {\partial f_{1}}{\partial x_{n}}}\right|_{x=x^{*},u=u^{*}}\\\vdots &\ddots &\vdots \\\left.{\frac {\partial f_{n}}{\partial x_{1}}}\right|_{x=x^{*},u=u^{*}}&\ldots &\left.{\frac {\partial f_{n}}{\partial x_{n}}}\right|_{x=x^{*},u=u^{*}}\end{bmatrix}}

Formal statement of necessary conditions for minimization problem

Here the necessary conditions are shown for minimization of a functional. Take $x$ to be the state of the dynamical system with input $u$ , such that

{\dot {x}}=f(x,u),\quad x(0)=x_{0},\quad u(t)\in {\mathcal {U}},\quad t\in [0,T]

where ${\mathcal {U}}$ is the set of admissible controls and $T$ is the terminal (i.e., final) time of the system. The control $u\in {\mathcal {U}}$ must be chosen for all $t\in [0,T]$ to minimize the objective functional $J$ which is defined by the application and can be abstracted as

J=\Psi (x(T))+\int _{0}^{T}L(x(t),u(t))\,dt

The constraints on the system dynamics can be adjoined to the Lagrangian $L$ by introducing time-varying Lagrange multiplier vector $\lambda$ , whose elements are called the costates of the system. This motivates the construction of the Hamiltonian $H$ defined for all $t\in [0,T]$ by:

H(x(t),u(t),\lambda (t),t)=\lambda ^{\rm {T}}(t)f(x(t),u(t))+L(x(t),u(t))\,

where $\lambda ^{\rm {T}}$ is the transpose of $\lambda$ .

Pontryagin's minimum principle states that the optimal state trajectory $x^{*}$ , optimal control $u^{*}$ , and corresponding Lagrange multiplier vector $\lambda ^{*}$ must minimize the Hamiltonian $H$ so that

(1)\qquad H(x^{*}(t),u^{*}(t),\lambda ^{*}(t),t)\leq H(x^{*}(t),u,\lambda ^{*}(t),t)\,

for all time $t\in [0,T]$ and for all permissible control inputs $u\in {\mathcal {U}}$ . It must also be the case that

(2)\qquad \Psi _{T}(x(T))+H(T)=0\,

Additionally, the costate equations

(3)\qquad -{\dot {\lambda }}^{\rm {T}}(t)=H_{x}(x^{*}(t),u^{*}(t),\lambda (t),t)=\lambda ^{\rm {T}}(t)f_{x}(x^{*}(t),u^{*}(t))+L_{x}(x^{*}(t),u^{*}(t))

must be satisfied. If the final state $x(T)$ is not fixed (i.e., its differential variation is not zero), it must also be that the terminal costates are such that

(4)\qquad \lambda ^{\rm {T}}(T)=\Psi _{x}(x(T))\,

These four conditions in (1)-(4) are the necessary conditions for an optimal control. Note that (4) only applies when $x(T)$ is free. If it is fixed, then this condition is not necessary for an optimum.

gollark: I wonder if someone will end up making a third-party case extension or something to make it more tractable.

gollark: It is somewhat hard to remember.

gollark: Probably wouldn't really work as ranks for people.

gollark: "crude, basic, grand, rare, arcane, heroic, unique, celestial, and divine"

gollark: Wait, there's a rarity scale for skills and items and such in ToH, right? Maybe it could be based on that.

Notes

Whether the extreme value is maximum or minimum depends both on the problem and on the sign convention used for defining the Hamiltonian. The normal convention leads to a maximum hence maximum principle.

References

Ross, Isaac (2015). A primer on Pontryagin's principle in optimal control. San Francisco: Collegiate Publishers. ISBN 978-0-9843571-0-9. OCLC 625106088.CS1 maint: date and year (link)
Mangasarian, O. L. (1966). "Sufficient Conditions for the Optimal Control of Nonlinear Systems". SIAM Journal on Control. 4 (1): 139–152. doi:10.1137/0304013.
Kamien, Morton I.; Schwartz, Nancy L. (1971). "Sufficient Conditions in Optimal Control Theory". Journal of Economic Theory. 3 (2): 207–214. doi:10.1016/0022-0531(71)90018-4.
Boltyanski, V.; Martini, H.; Soltan, V. (1998). "The Maximum Principle – How it came to be?". Geometric Methods and Optimization Problems. New York: Springer. pp. 204–227. ISBN 0-7923-5454-0.
Gamkrelidze, R. V. (1999). "Discovery of the Maximum Principle". Journal of Dynamical and Control Systems. 5 (4): 437–451. doi:10.1023/A:1021783020548. Reprinted in Bolibruch, A. A.; et al., eds. (2006). Mathematical Events of the Twentieth Century. Berlin: Springer. pp. 85–99. ISBN 3-540-23235-4.
For first published works, see references in Fuller, A. T. (1963). "Bibliography of Pontryagin's Maximum Principle". J. Electronics & Control. 15 (5): 513–517. doi:10.1080/00207216308937602.
McShane, E. J. (1989). "The Calculus of Variations from the Beginning Through Optimal Control Theory". SIAM J. Control Optim. 27 (5): 916–939. doi:10.1137/0327049.
Yong, J.; Zhou, X. Y. (1999). "Maximum Principle and Stochastic Hamiltonian Systems". Stochastic Controls: Hamiltonian Systems and HJB Equations. New York: Springer. pp. 101–156. ISBN 0-387-98723-1.
Sastry, Shankar (March 29, 2009). "Lecture Notes 8. Optimal Control and Dynamic Games" (PDF).
Zhou, X. Y. (1990). "Maximum Principle, Dynamic Programming, and their Connection in Deterministic Control". Journal of Optimization Theory and Applications. 65 (2): 363–373. doi:10.1007/BF01102352.

External links

"Pontryagin maximum principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[2] Whether the extreme value is maximum or minimum depends both on the problem and on the sign convention used for defining the Hamiltonian. The normal convention leads to a maximum hence maximum principle.

[:0-1] Ross, Isaac (2015). A primer on Pontryagin's principle in optimal control. San Francisco: Collegiate Publishers. ISBN 978-0-9843571-0-9. OCLC 625106088.CS1 maint: date and year (link)

[3] Mangasarian, O. L. (1966). "Sufficient Conditions for the Optimal Control of Nonlinear Systems". SIAM Journal on Control. 4 (1): 139–152. doi:10.1137/0304013.

[4] Kamien, Morton I.; Schwartz, Nancy L. (1971). "Sufficient Conditions in Optimal Control Theory". Journal of Economic Theory. 3 (2): 207–214. doi:10.1016/0022-0531(71)90018-4.

[5] Boltyanski, V.; Martini, H.; Soltan, V. (1998). "The Maximum Principle – How it came to be?". Geometric Methods and Optimization Problems. New York: Springer. pp. 204–227. ISBN 0-7923-5454-0.

[6] Gamkrelidze, R. V. (1999). "Discovery of the Maximum Principle". Journal of Dynamical and Control Systems. 5 (4): 437–451. doi:10.1023/A:1021783020548. Reprinted in Bolibruch, A. A.; et al., eds. (2006). Mathematical Events of the Twentieth Century. Berlin: Springer. pp. 85–99. ISBN 3-540-23235-4.

[7] For first published works, see references in Fuller, A. T. (1963). "Bibliography of Pontryagin's Maximum Principle". J. Electronics & Control. 15 (5): 513–517. doi:10.1080/00207216308937602.

[8] McShane, E. J. (1989). "The Calculus of Variations from the Beginning Through Optimal Control Theory". SIAM J. Control Optim. 27 (5): 916–939. doi:10.1137/0327049.

[YongZhou-9] Yong, J.; Zhou, X. Y. (1999). "Maximum Principle and Stochastic Hamiltonian Systems". Stochastic Controls: Hamiltonian Systems and HJB Equations. New York: Springer. pp. 101–156. ISBN 0-387-98723-1.

[10] Sastry, Shankar (March 29, 2009). "Lecture Notes 8. Optimal Control and Dynamic Games" (PDF).

[11] Zhou, X. Y. (1990). "Maximum Principle, Dynamic Programming, and their Connection in Deterministic Control". Journal of Optimization Theory and Applications. 65 (2): 363–373. doi:10.1007/BF01102352.