8
$\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?

Improve this question
$\endgroup$
5
  • 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
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 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
    Commented Apr 5, 2016 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
    Commented Apr 11, 2016 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
    Commented Apr 11, 2016 at 18:14

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Apr 5, 2016 at 9:02
  • 1
    $\begingroup$ thank you for the clarification, I have added the multi-dimensional time extension as well. $\endgroup$
    – Carlo Beenakker
    Commented Apr 5, 2016 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
    Commented Apr 7, 2016 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ excuse me, isn't this the previous answer B ??? $\endgroup$
    – Carlo Beenakker
    Commented Apr 6, 2016 at 14:35
  • $\begingroup$ Basically, it is. I'm sorry, I haven't seen your last link. $\endgroup$
    – homocomputeris
    Commented Apr 6, 2016 at 15:15
  • $\begingroup$ OK, no problem. $\endgroup$
    – Carlo Beenakker
    Commented Apr 6, 2016 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
    Commented Apr 7, 2016 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
    Commented Apr 7, 2016 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .