6
$\begingroup$

One method to optimize the integral $$\int_{\mathcal T} L(t,x,\dot{x}) \; dt $$ of a functional over a curve is the calculus of variations, which leads to ordinary differential equations: the Euler-Lagrange equation $$-\frac{d}{dt} L_{\dot{x}}(t,x(t),\dot{x}(t)) + L_x(t,x(t),\dot{x}(t)) =0$$ or its generalization, Pontryagin's maximum principle. An alternative is Bellman's optimality principle, which leads to Hamilton-Jacobi-Bellman partial differential equations. Each of the methods has advantages and disadvantages depending on the application, and there are numerous technical differences between them, but in the cases when both are applicable the answers are broadly similar.

The calculus of variations can also be used to optimize a functional $$\int_{\mathcal X} L(x,u,p) \; dx $$ integrated over a multidimensional space. The resulting Euler-Lagrange equations $$-\frac{\partial}{\partial x} L_{p}(x,u(x),p(x)) + L_u(x,u(x),p(x))$$ are partial differential equations with the space coordinates as independent variables. Is an alternative approach using value functions, leading to optimality conditions along the lines of Bellman's optimality principle, known?

$\endgroup$
  • 1
    $\begingroup$ Wikipedia does mention Dynamic Programming as an alternative to Calculus of Variations. I suspect when you try to discretize the Euler-Lagrange equation (e.g. find a geodesic curve on your computer) the algorithm you use involves some type of memoization or technique to keep things in memory. I don't know of any deep or profound uses of this equality between Principle of Least Action and Dynamic Programming. $\endgroup$ – john mangual Mar 30 '16 at 13:42
  • $\begingroup$ Yes, dynamic programming is an alternative to the calculus of variations, but as far as I know only for those problems in which the independent variable is 1-dimensional. Finding geodesics is an example of those. I am interested in minimizing $\int_{\mathcal X} L(u,p,x) dx$ with ${\mathcal X}$ a subset of $R^n$, for example, in which case I am only aware of the Euler-Lagrange approach. $\endgroup$ – Pait Mar 30 '16 at 17:04
  • $\begingroup$ Perhaps a little confusion can arise at 1st glance from the fact that in the calculus of variations in several variables the letter $x$ is often used to denote the independent space variable ($u$ is often used for the dependent variable). Usually in dynamical programming the independent variable is time $t$, the dependent variable is state $x$, and in controls problems $u$ is the input. $\endgroup$ – Pait Apr 5 '16 at 9:09
  • $\begingroup$ Fascinating. If the papers suggested in the answers don't really solve the problem, perhaps I should assume that it is open. At least until the bounty expires ;-) $\endgroup$ – Pait Apr 11 '16 at 17:17
  • 1
    $\begingroup$ looking again at your question, there is nothing about discretization or dynamic programming except for Bellman's name. Perhaps I will read up and ask my own question 😯 $\endgroup$ – john mangual Apr 11 '16 at 18:14
2
+75
$\begingroup$

A. multi-dimensional state, one-dimensional time

Multi-dimensional extensions $x\in\mathbb{R}^n$ of the one-dimensional Hamilton-Jacobi-Bellman equations have been considered in Consistency of a Simple Multidimensional Scheme for Hamilton-Jacobi-Bellman Equations (2005).

We present an approximation scheme for second-order Hamilton–Jacobi–Bellman equations arising in stochastic optimal control. The scheme is based on a Markov chain approximation method to solve the nonlinear partial differential equations that govern the optimization problem. The scheme can be readily implemented in any dimension. The consistency of the scheme is proved, which guarantees its convergence.


B. multi-dimensional state, multi-dimensional time

For extensions where both state and time are multi-dimensional, $x\in\mathbb{R}^n$, $t\in\mathbb{R}_+^m$, see Multitime linear-quadratic regulator problem based on curvilinear integral (2009) (and several more recent papers on the multi-time Bellman principle by Constantin Udriste and co-workers).

We introduce a multitime dynamic programming method based on multitime Hamilton- Jacobi-Bellman PDEs. These PDEs are equivalent to multitime Hamilton PDEs system and the multitime maximum principle. The optimal control is characterized means of a multitime variant of the Riccati PDE that may be viewed as a feedback law.

$\endgroup$
  • 1
    $\begingroup$ The paper deals with a "garden-variety" HJB equation arising out of ordinary integral equations - the integration variable is one-dimensional time. I don't see a connection with the question. $\endgroup$ – Pait Apr 5 '16 at 9:02
  • 1
    $\begingroup$ thank you for the clarification, I have added the multi-dimensional time extension as well. $\endgroup$ – Carlo Beenakker Apr 5 '16 at 21:19
  • $\begingroup$ The multi-time paper is instructive. However the HJB equation is derived assuming knowledge of a specific path in multi-time - this key giveaway is that the Lagrangian integrated in the optimization goal is a 1-form. Path-independence is assumed via integrability conditions on the commutators of vector fields. I'd say these conditions are rather artificial in any real world situation. So the 2009 paper does not really generalize Bellman's method for the multidimensional case. The question is still open. Perhaps one of the dozens of references to work by the same group does it... $\endgroup$ – Pait Apr 7 '16 at 10:44
1
$\begingroup$

As I haven't noticed before, this one is a duplicate of the first answer: Riemannian optimal control and this author's further works

Theorem (Multitime maximum principle). Suppose u∗(·) is an optimal solution of the control problem and x∗(·) is the corresponding optimal state. Then there exists a costate tensor...

And maybe this article, I don't have full access ATM: The taxation principle and multi-time Hamilton-Jacobi equations

...Here, we propose an example of the contrary: every system of first order partial differential equations of a certain type can be solved by use of an economics principle. For the case of a single equation, our approach is in some sense dual to the usual optimal control method.

$\endgroup$
  • $\begingroup$ excuse me, isn't this the previous answer B ??? $\endgroup$ – Carlo Beenakker Apr 6 '16 at 14:35
  • $\begingroup$ Basically, it is. I'm sorry, I haven't seen your last link. $\endgroup$ – homocomputeris Apr 6 '16 at 15:15
  • $\begingroup$ OK, no problem. $\endgroup$ – Carlo Beenakker Apr 6 '16 at 15:17
  • $\begingroup$ The Riemannian optimal control paper derives a version of the Pontryagin maximum principle, which is an extension of the Euler-Lagrange equation of the calculus of variations. Thus it is not an extension of the Bellman method, which is quite different. My question remains open. $\endgroup$ – Pait Apr 7 '16 at 13:17
  • $\begingroup$ The idea that a class of partial differential equations might be solved using economics principles is epistemologically intriguing. I believe that the revelation principle and the taxation principle amount to assuming some form of commutativity and integrability conditions, which restrict the method's applicability to the cases where the answers were already known. $\endgroup$ – Pait Apr 7 '16 at 13:18
0
$\begingroup$

As far as I know a multidimensional version of Bellman's principle of optimality has not been found. The papers suggested in the answers above all refer to one-dimensional independent variables, or to cases that can be reduced, by introducing integrability assumptions, to optimization of a functional with a one-dimensional independent variable.

Finding a multivariable version of the dynamic programming method may be an open problem. Until it is solved, the classical Euler-Lagrange equations are the method we have.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.