{'fraction_non_alphanumeric': 0.05722932259720608, 'fraction_numerical': 0.017752438596017186, 'mean_word_length': 4.14957562265201, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Discrete Hamilton-Jacobi Theory

We develop a discrete analogue of Hamilton-Jacobi theory in the framework of discrete Hamiltonian mechanics. The resulting discrete Hamilton-Jacobi equation is discrete only in time. We describe a discrete analogue of Jacobi's solution and also prove a discrete version of the geometric Hamilton-Jacobi theorem. The theory applied to discrete linear Hamiltonian systems yields the discrete Riccati equation as a special case of the discrete Hamilton-Jacobi equation. We also apply the theory to discrete optimal control problems, and recover some well-known results, such as the Bellman equation (discrete-time HJB equation) of dynamic programming and its relation to the costate variable in the Pontryagin maximum principle. This relationship between the discrete Hamilton-Jacobi equation and Bellman equation is exploited to derive a generalized form of the Bellman equation that has controls at internal stages.


Introduction
1.1. Discrete Mechanics. Discrete mechanics is a reformulation of Lagrangian and Hamiltonian mechanics with discrete time, as opposed to a discretization of the equations in the continuoustime theory. It not only provides a systematic view of structure-preserving integrators, but also has interesting theoretical aspects analogous to continuous-time Lagrangian and Hamiltonian mechanics [see, e.g., 30; 33; 34]. The main feature of discrete mechanics is its use of discrete versions of variational principles. Namely, discrete mechanics assumes that the dynamics is defined at discrete times from the outset, formulates a discrete variational principle for such dynamics, and then derives a discrete analogue of the Euler-Lagrange or Hamilton's equations from it.
The advantage of this construction is that it naturally gives rise to discrete analogues of the concepts and ideas in continuous time that have the same or similar properties, such as symplectic forms, the Legendre transformation, momentum maps, and Noether's theorem [30]. This in turn provides us with the discrete ingredients that facilitate further theoretical developments, such as discrete analogues of the theories of complete integrability [see, e.g., 31; 33; 34] and also those of reduction and connections [20; 25; 28]. Whereas the main topic in discrete mechanics is the development of structure-preserving algorithms for Lagrangian and Hamiltonian systems [see, e.g., 30], the theoretical aspects of it are interesting in their own right, and furthermore provide insight into the numerical aspects as well.
Another notable feature of discrete mechanics, especially on the Hamiltonian side, is that it is a generalization of (nonsingular) discrete optimal control problems. In fact, as stated in Marsden and West [30], discrete mechanics is inspired by discrete formulations of optimal control problems (see, e.g., Jordan and Polak [21] and Cadzow [9]).

1.2.
Hamilton-Jacobi Theory. In classical mechanics [see, e.g., 3; 16; 24; 29], the Hamilton-Jacobi equation is first introduced as a partial differential equation that the action integral satisfies. Specifically, let Q be a configuration space and T * Q be its cotangent bundle; and let q ∈ Q and t > 0 be arbitrary and suppose that (q(s),p(s)) ∈ T * Q is a solution of Hamilton's equationṡ where we regard the resulting integral as a function of the endpoint (q, t) ∈ Q × R + with R + being the set of positive real numbers. Then by taking variation of the endpoint (q, t), one obtains a partial differential equation satisfied by S(q, t): This is the Hamilton-Jacobi equation.
Conversely, it is shown that if S(q, t) is a solution of the Hamilton-Jacobi equation then S(q, t) is a generating function for the family of canonical transformations (or symplectic flows) that describe the dynamics defined by Hamilton's equations. This result is the theoretical basis for the powerful technique of exact integration called separation of variables.

Connection with Optimal Control and The Hamilton-Jacobi-Bellman Equation.
The idea of Hamilton-Jacobi theory is also useful in optimal control theory (see, e.g., Jurdjevic [22] and Bertsekas [6]). Consider a typical optimal control problem where we introduced the costate p, and also defined the control Hamiltonian, H(q, p, u) := p · f (q, u) − C(q, u).
We also define the optimal cost-to-go function J(q, t) := Since this definition coincides with Eq. (1.2), the function S(q, t) = S * − J(q, t) satisfies the H-J equation (1.3); this reduces to the Hamilton-Jacobi-Bellman (HJB) equation for the optimal cost-to-go function J(q, t): It can also be shown that the costate p of the optimal solution is related to the solution of the HJB equation.
1.4. Discrete Hamilton-Jacobi Theory. The main objective of this paper is to present a discrete analogue of Hamilton-Jacobi theory within the framework of discrete Hamiltonian mechanics [23], and also to apply the theory to discrete optimal control problems.
There are some previous works on discrete-time analogues of the Hamilton-Jacobi equation, such as Elnatanov and Schiff [13] and Lall and West [23]. Specifically, Elnatanov and Schiff [13] derived an equation for a generating function of a coordinate transformation that trivializes the dynamics. This derivation is a discrete analogue of the conventional derivation of the continuoustime Hamilton-Jacobi equation [see, e.g., 24, Chapter VIII]. Lall and West [23] formulated a discrete Lagrangian analogue of the Hamilton-Jacobi equation as a separable optimization problem.
1.5. Main Results. Our work was inspired by the result of Elnatanov and Schiff [13] and starts from a reinterpretation of their result in the language of discrete mechanics. This paper further extends the result by developing discrete analogues of results in (continuous-time) Hamilton-Jacobi theory. Namely, we formulate a discrete analogue of Jacobi's solution, which relates the discrete action sum to a solution of the discrete Hamilton-Jacobi equation. This also provides a very simple derivation of the discrete Hamilton-Jacobi equation and exhibits a natural correspondence with the continuous-time theory. Another important result in this paper is a discrete analogue of the Hamilton-Jacobi theorem, which relates the solution of the discrete Hamilton-Jacobi equation with the solution of the discrete Hamilton's equations.
We also show that the discrete Hamilton-Jacobi equation is a generalization of the discrete Riccati equation and the Bellman equation (see Fig. 1). Specifically, we show that the discrete Hamilton-Jacobi equation applied to linear discrete Hamiltonian systems and discrete optimal control problems reduces to the discrete Riccati and Bellman equations, respectively. This is again a discrete analogue of the well-known results that the Hamilton-Jacobi equation applied to linear Hamiltonian systems and optimal control problems reduces to the Riccati (see, e.g., Jurdjevic [22, p. 421]) and HJB equations (see Section 1.3 above), respectively.
The link between the discrete Hamilton-Jacobi equation and the Bellman equation turns out to be useful in deriving a class of generalized Bellman equations that are higher-order approximations of the original continuous-time problem. Specifically, we use the idea of the Galerkin Hamiltonian variational integrator of Leok and Zhang [26] to derive discrete control Hamiltonians that yield higher-order approximations, and then show that the corresponding discrete Hamilton-Jacobi equation gives a class of Bellman equations with controls at internal stages.  1.6. Outline of the Paper. We first present a brief review of discrete Lagrangian and Hamiltonian mechanics in Section 2. In Section 3, we describe a reinterpretation of the result of Elnatanov and Schiff [13] in the language of discrete mechanics and a discrete analogue of Jacobi's solution to the discrete Hamilton-Jacobi equation. The remainder of Section 3 is devoted to more detailed studies of the discrete Hamilton-Jacobi equation: its left and right variants, more explicit forms of them, and also a digression on the Lagrangian side. In Section 4, we prove a discrete version of the Hamilton-Jacobi theorem. In Section 5, we apply the theory to linear discrete Hamiltonian systems, and show that the discrete Riccati equation follows from the discrete Hamilton-Jacobi equation. Section 6 establishes the link with discrete-time optimal control and interprets the results of the preceding sections in this setting. Section 7 further extends this idea to derive a class of Bellman equations with controls at internal stages.

Discrete Mechanics
This section briefly reviews some key results of discrete mechanics following Marsden and West [30] and Lall and West [23].

Discrete Lagrangian Mechanics.
A discrete Lagrangian flow {q k } N k=0 , on an n-dimensional differentiable manifold Q, can be described by the following discrete variational principle: Let S N d be the following action sum of the discrete Lagrangian L d : Q × Q → R: which is an approximation of the action integral as shown above. Consider discrete variations q k → q k + ε δq k , for k = 0, 1, . . . , N , with δq 0 = δq N = 0. Then, the discrete variational principle δS N d = 0 gives the discrete Euler-Lagrange equations: This determines the discrete flow F L d : Q × Q → Q × Q: Let us define the discrete Lagrangian symplectic one-forms Θ ± L d : Then, the discrete flow F L d preserves the discrete Lagrangian symplectic form

Discrete Hamiltonian
Mechanics. Introduce the right and left discrete Legendre trans- respectively. Then we find that the discrete Lagrangian symplectic forms Eq. (2.4) and (2.5) are pull-backs by these maps of the standard symplectic form on T * Q: , one can rewrite the discrete Euler-Lagrange equations (2.2) as follows: (2.7) Furthermore, define the discrete Hamiltonian mapF L d : Then, one may relate this map with the discrete Legendre transforms in Eq. (2.6) as follows: Furthermore, one can also show that this map is symplectic, i.e., This is the Hamiltonian description of the dynamics defined by the discrete Euler-Lagrange equation (2.2) introduced by Marsden and West [30]. Notice, however, that no discrete analogue of Hamilton's equations is introduced here, although the flow is now on the cotangent bundle T * Q. Lall and West [23] pushed this idea further to give discrete analogues of Hamilton's equations: From the point of view that a discrete Lagrangian is essentially a generating function of type one [16], we can apply Legendre transforms to the discrete Lagrangian to find the corresponding generating functions of type two or three [16]. In fact, they turn out to be a natural Hamiltonian counterpart to the discrete Lagrangian mechanics described above. Specifically, with the right discrete Legendre transform we can define the following right discrete Hamiltonian: Then, the discrete Hamiltonian mapF L d : (q k , p k ) → (q k+1 , p k+1 ) is defined implicitly by the right discrete Hamilton's equations which are precisely the characterization of a symplectic map in terms of a generating function, H + d , of type two. Similarly, with the left discrete Legendre transform we can define the following left discrete Hamiltonian: (2.14) Then, we have the left discrete Hamilton's equations which corresponds to a symplectic map expressed in terms of a generation function, H − d , of type three.
On the other hand, Leok and Zhang [26] demonstrate that discrete Hamiltonian mechanics can be obtained as a direct variational discretization of continuous Hamiltonian mechanics, instead of having to go via discrete Lagrangian mechanics. [13] derived a discrete Hamilton-Jacobi equation based on the idea that the Hamilton-Jacobi equation is an equation for a symplectic change of coordinates under which the dynamics becomes trivial. In this section, we would like to reinterpret their derivation in the framework of discrete Hamiltonian mechanics reviewed above.

Derivation by Elnatanov and Schiff. Elnatanov and Schiff
Theorem 3.1. Suppose that the discrete dynamics {(q k , p k )} N k=0 is governed by the right discrete Hamilton's equations (2.12). Consider the symplectic coordinate transformation (q k , p k ) → (q k ,p k ) that satisfies the following: (i) The old and new coordinates are related by the type-one generating function 1 S k : R n ×R n → R: Then, the set of functions {S k } N k=1 satisfies the discrete Hamilton-Jacobi equation: Proof.
The key ingredient in the proof is the right discrete Hamiltonian in the new coordinates, i.e., a functionĤ + d (q k ,p k+1 ) that satisfieŝ (3.4) or equivalently,p Let us first writeĤ + d in terms of the original right discrete Hamiltonian H + d and the generating function S k . For that purpose, first rewrite Eqs. (2.12) and (3.1) as follows: respectively. Then, using the above relations, we havê Thus, in view of Eq. (3.5), we obtain Now consider the choice of the new right discrete HamiltonianĤ + d that renders the dynamics trivial, i.e., (q k+1 ,p k+1 ) = (q k ,p k ). It is clear from Eq. (3.4) that we can set Then, Eq. (3.6) becomeŝ and sinceq k+1 =q k = · · · =q 0 , we have Eliminating p k+1 by using Eq. (3.1), we obtain Eq. (3.2).
Remark 3.2. What Elnatanov and Schiff [13] refer to as the Hamilton-Jacobi difference equation is the following: It is clear that this is equivalent to Eq. (3.2) in view of Eq. (2.12)

3.2.
Discrete Analogue of Jacobi's Solution. This section presents a discrete analogue of Jacobi's solution. This also gives an alternative derivation of the discrete Hamilton-Jacobi equation that is much simpler than the one shown above.
Theorem 3.3. Consider the action sums, Eq. (2.1), written in terms of the right discrete Hamiltonian, Eq. (2.11): evaluated along a solution of the right discrete Hamilton's equations (2.12); each S k d (q k ) is seen as a function of the end point coordinates q k and the discrete end time k. Then, these action sums satisfy the discrete Hamilton-Jacobi equation (3.3).
where p k+1 is considered to be a function of q k and q k+1 , i.e., p k+1 = p k+1 (q k , q k+1 ). Taking the derivative of both sides with respect to q k+1 , we have However, the terms in the brackets vanish because the right discrete Hamilton's equations (2.12) are assumed to be satisfied. Thus, we have  and hence the Hamilton-Jacobi equation In the above derivation of the discrete Hamilton-Jacobi equation (3.3), the difference in two action sums, Eq. (3.9), is a natural discrete analogue of the variation dS in Eq. (3.11). Notice also that Eq. (3.9) plays the same essential role as Eq. (3.11) does in deriving the Hamilton-Jacobi equation. Table 1 summarizes the correspondence between the ingredients in the continuous and discrete theories (see also Remark 3.4).

The Right and Left Discrete Hamilton-Jacobi Equations.
Recall that, in Eq. (3.8), we wrote the action sum, Eq. (2.1), in terms of the right discrete Hamiltonian, Eq. (2.11). We can also write it in terms of the left discrete Hamiltonian, Eq. (2.14), as follows: Then, we can proceed as in the proof of Theorem 3.3: First, we have (3.13) Table 1. Correspondence between ingredients in continuous and discrete theories; R ≥0 is the set of non-negative real numbers and N 0 is the set of non-negative integers.
Continuous Discrete where p k is considered to be a function of q k and q k+1 , i.e., p k = p k (q k , q k+1 ). Taking the derivative of both sides with respect to q k , we have However, the terms in the brackets vanish because the left discrete Hamilton's equations (2.15) are assumed to be satisfied. Thus, we have (3.14) Substituting this into Eq. (3.13) gives the discrete Hamilton-Jacobi equation with the left discrete Hamiltonian: We refer to Eqs. (3.3) and (3.15) as the right and left discrete Hamilton-Jacobi equations, respectively.
As mentioned above, Eqs. (3.8) and (3.12) are the same action sum, Eq. (2.1), expressed in different ways. Therefore we may summarize the above argument as follows:   (3.15) are implicit in the sense that they contain two spatial variables q k and q k+1 ; Theorem 3.3 suggests that one may consider q k and q k+1 to be related by the discrete Hamiltonian dynamics defined by either the right or left discrete Hamilton's equations (2.12) or (2.15), or equivalently, the discrete Hamiltonian map F L d : (q k , p k ) → (q k+1 , p k+1 ) defined in Eq. (2.8). More specifically, we may write q k+1 in terms of q k . This results in explicit forms of the discrete Hamilton-Jacobi equations, and we shall define the discrete Hamilton-Jacobi equations by the resulting explicit forms. We will see later in Section 6 that the explicit form is compatible with the formulation of the Bellman equation.
For the right discrete Hamilton-Jacobi equation (3.3), we first define the map f + k : Q → Q as follows: Replace p k+1 in Eq. (2.12a) by DS k+1 d (q k+1 ) as suggested by Eq. (3.10): Assuming this equation is solvable for q k+1 , we define f + k : We may now identify q k+1 with f + k (q k ) in the implicit form of the right Hamilton-Jacobi equation (3.3): where we suppressed the subscript k of q k since it is now clear that q k is an independent variable as opposed to a function of the discrete time k. We define Eq. (3.17) to be the right discrete Hamilton-Jacobi equation. Notice that these are differential-difference-functional equations defined on Q × N, with the spatial variable q and the discrete time k.
For the left discrete Hamilton-Jacobi equation (3.15), we define the map f − k : Q → Q as follows: where π Q : T * Q → Q is the cotangent bundle projection; equivalently, f − k is defined so that the diagram below commutes.
Notice also that, since the mapF L d : (q k , p k ) → (q k+1 , p k+1 ) is defined by Eq. (2.15), f − k is defined implicitly by In other words, replace p k in Eq. (2.15a) by DS k d (q k ) as suggested by Eq. (3.14), and define f − k (q k ) as the q k+1 in the resulting equation.
We may now identify q k+1 with f − k (q k ) in Eq. (3.15): where we again suppressed the subscript k of q k . We define Eqs. (3.17) and (3.20) to be the right and left discrete Hamilton-Jacobi equations, respectively.
Remark 3.6. Notice that the right discrete Hamilton-Jacobi equation (3.17) is more complicated than the left one (3.20), particularly because the map f + k appears more often than f − k does in the latter; notice here that, as shown in Eq. (3.18), the maps f ± k in the discrete Hamilton-Jacobi equations (3.17) and (3.20) depend on the function S k d , which is the unknown one has to solve for. However, it is possible to define an equally simple variant of the right discrete Hamilton-Jacobi equation by writing q k−1 in terms of q k : Let us first define g k : Q → Q by or so that the diagram below commutes.
where we again suppressed the subscript k of q k . This is as simple as the left discrete Hamilton-Jacobi equation (3.20). However the map g k is, being backward in time, rather unnatural compared to f k . Furthermore, as we shall see in Section 6, in the discrete optimal control setting, the map f k is defined by a given function and thus the formulation with f k will turn out to be more convenient.

The Discrete Hamilton-Jacobi Equation on the Lagrangian
(3.21) This is essentially the Lagrangian equivalent of the discrete Hamilton-Jacobi equation (3.17) as Lall and West [23] suggest. Let us apply the same argument as above to obtain the explicit form for Eq. (3.21). Taking the derivative of the above equation with respect to q k , we have , and hence from the definition of the left discrete Legendre transform, Eq. (2.6b), where we defined the map f L k : Q → Q as follows (see the commutative diagram below): where pr 2 : Q×Q → Q is the projection to the second factor, i.e., pr 2 (q 1 , q 2 ) = q 2 . Thus, eliminating q k+1 from Eq. (3.21) and then replacing q k by q, we obtain the discrete Hamilton-Jacobi equation on the Lagrangian side: The map f L k defined in Eq. (3.22) is identical to f − k defined above in Eq. (3.18) as the commutative diagram below demonstrates.
The commutativity of the square in the diagram defines the f − k as we saw earlier, whereas that of the right-angled triangle on the lower left defines the f L k in Eq. Then, the set of points is a solution of the right discrete Hamilton's equations (2.12).
Similarly, suppose that S k d satisfies the left discrete Hamilton-Jacobi equation (3.20), and let {c k } N k=0 ⊂ Q be a set of points that satisfy Furthermore, assume that the Jacobian Df − k is invertible at each point c k . Then, the set of points is a solution of the left discrete Hamilton's equations (2.15).
Proof. To prove the first assertion, first recall the implicit definition of f + k in Eq. (3.16): In particular, for q = c k , we have where we used Eq. (4.1) and (4.2). On the other hand, taking the derivative of Eq. (3.17) with respect to q, Using Eqs. (4.1) and (4.2), we obtain Eqs. (4.6) and (4.7) show that the sequence {(c k , p k )} satisfies the right discrete Hamilton's equations (2.12). Now, let us prove the latter assertion. First, recall the implicit definition of f − k in Eq. (3.19): In particular, for q = c k , we have where we used Eq. (4.3) and (4.4). On the other hand, taking the derivative of Eq. (3.17) with respect to q yields,

Discrete Linear Hamiltonian Systems and Matrix Riccati Equation.
Example 5.1 (Quadratic discrete Hamiltonian-discrete linear Hamiltonian systems). Consider a discrete Hamiltonian system on T * R n ∼ = R n × R n (the configuration space is Q = R n ) defined by the quadratic left discrete Hamiltonian where M , K, and L are real n × n matrices; we assume that M and L are invertible and also that M and K are symmetric. The left discrete Hamilton's equations (2.15) are and hence are a discrete linear Hamiltonian system (see Section A.1). Now, let us solve the left discrete Hamilton-Jacobi equation (3.20) for this system. For that purpose, we first generalize the problem to that with a set of initial points instead of a single initial point (q 0 , p 0 ). More specifically, consider the set of initial points that is a Lagrangian affine spacẽ L z 0 (see Definition A.2) which contains the point z 0 := (q 0 , p 0 ). Then, the dynamics is formally written as, for any discrete time k ∈ N, such thatL (k) = graph dS k d ; here A k are symmetric n × n matrices, b k are elements in R n , and c k are in R.
Now that we know the form of the solution, we substitute the above expression into the discrete Hamilton-Jacobi equation to find the equations for A k , b k , and c k . Notice first that the map f − k is given by the first half of Eq. (5.2) with p k replaced by DS k d (q): Then, substituting Eq. (5.3) into the left-hand side of the left discrete Hamilton-Jacobi equation (3.20) yields the following recurrence relations for A k , b k , and c k : where we assumed that I + A k M −1 is invertible.
Remark 5.2. For the A k+1 defined by Eq. (5.5a) to be symmetric, it is sufficient that A k is invertible; for if it is, then Eq. (5.5a) becomes A k+1 = L T (A −1 k + M −1 ) −1 L − K, and so A k , M , and K being symmetric implies that A k+1 is as well.
Remark 5.3. We can rewrite Eq. (5.5a) as follows: Notice the exact correspondence between the coefficients in the above equation and the matrix entries in the discrete linear Hamiltonian equations (5.2). In fact, this is the discrete Riccati equation that corresponds to the iteration defined by Eq. (5.2). See Ammar and Martin [2] for details on this correspondence.
To summarize the above observation, we have: In other words, the discrete Hamilton-Jacobi equation is a nonlinear generalization of the discrete Riccati equation.

Relation to the Bellman Equation
In this section, we apply the above results to the optimal control setting. We will show that the (right) discrete Hamilton-Jacobi equation (3.17) gives the Bellman equation (discrete-time HJB equation) as a special case. This result gives a discrete analogue of the relationship between the H-J and HJB equations discussed in Section 1.3. 6.1. Discrete Optimal Control Problem. Let q d := {q k } N k=0 be the state variables in a vector space V ∼ = R n with q 0 and q N fixed and u d := {u k } N −1 k=0 be controls in the set U ⊂ R m . With a given function C d : V × U → R, define the discrete cost functional Then, we formulate the Standard Discrete Optimal Control Problem as follows [see, e.g., 4; 9; 17; 21]: Problem 6.1 (Standard Discrete Optimal Control Problem). Minimize the discrete cost functional, i.e., subject to the constraint,

Necessary Condition for Optimality and the Bellman Equation.
We would like to formulate the necessary condition for optimality. First, introduce the augmented discrete cost functional:Ŝ where we introduced the costate p d := {p k } N k=1 with p k ∈ V * , and also defined the discrete control HamiltonianĤ Then, the optimality condition, Eq. (6.1), is restated as In particular, extremality with respect to the control u d implies Now, we assume thatĤ + d is sufficiently regular so that this equation uniquely determines the optimal control u * d := {u * k } N −1 k=0 ; and therefore, u * k is a function of q k and p k+1 , i.e., u * k = u * k (q k , p k+1 ). We then define (6.5) and also the optimal discrete cost-to-go function where S * d is the optimal discrete cost functional, i.e., The above action sum has exactly the same form as Eq. (3.8) formulated in the framework of discrete Hamiltonian mechanics. Therefore, our theory now directly applies to this case: The corresponding right discrete Hamilton's equations (2.12) are, using the expression in Eq. (6.5), . Therefore, Eq. (3.16) gives the implicit definition of f + k as follows: Hence, the (right) discrete Hamilton-Jacobi equation (3.17) applied to this case gives and again using the expression for the Hamiltonian in Eq. (6.5), this becomes which is the Bellman equation (see, e.g., Bellman [4,5] and Bertsekas [6]).
Remark 6.2. Notice that the discrete HJB equation (6.8) is much simpler than the discrete Hamilton-Jacobi equations (3.17) and (3.20) because of the special form of the control Hamiltonian Eq. (6.5). Also, notice that, as shown in Eq. (6.7), the term f + k (q k ) is written in terms of the given function f . See Remark 3.6 for comparison.

Relation between the Discrete H-J and Bellman Equations and its Consequences.
Summarizing the observation made above, we have This observation leads to the following well-known fact: be a solution to the Bellman equation (6.8). Then, the costate p k in the discrete maximum principle is given as follows: where c k+1 = f d (c k , u * k ) with the optimal control u * k .
Proof. Follows from a reinterpretation of Theorem 4.1 through Proposition 6.3 with the relation

Generalized Bellman Equation with Internal-Stage Controls
In the previous section, we showed that the discrete Hamilton-Jacobi equation recovers the Bellman equation if we apply our theory to the Hamiltonian formulation of the Standard Discrete Optimal Control Problem 6.1. In this section, we generalize the approach to derive what may be considered as higher-order discrete-time approximations of the HJB equation (1.4). Namely, we derive a class of discrete control Hamiltonians that use higher-order approximations (a more general version of Eq. (6.3)) by employing the technique of Galerkin Hamiltonian variational integrators introduced by Leok and Zhang [26]; and then, we apply our theory to obtain a class of generalized Bellman equations that have controls at internal stages. A Hamiltonian structure comes into play with the introduction of the augmented cost functional: where we introduced the costate p(t) ∈ V * , and also defined the control Hamiltonian, H(q, p, u) := p · f (q, u) − C(q, u).
where h is the time step; C 1 ([0, h], T * Q) is the set of continuously differentiable curves on T * Q over the time interval [0, h]; an extremum is achieved for the exact solution of Hamilton's equations (1.1) that satisfy the specified boundary conditions. Therefore, it requires the exact solution (q(t), p(t)) to evaluate the the above integral, and so the exact discrete Hamiltonian cannot be practically computed in general.
The key idea of Galerkin Hamiltonian variational integrators [26] is to replace the set of curves C 1 ([0, h], T * Q) by a certain finite-dimensional space so as to obtain a computable expression for a discrete Hamiltonian.

Galerkin Discrete Control Hamiltonian.
Here, we would like to apply the above idea to the control Hamiltonian, Eq. (7.1), to obtain a discrete control Hamiltonian.
Let C s d (V ) be a finite-dimensional space of curves defined by where τ ∈ [0, 1] and w i ∈ V for each i = 1, . . . , s.

2.
Integrateq d (t) over [0, τ h], to obtain the approximation for the position q, i.e., where we applied the boundary condition q d (0) = q 0 . Applying the boundary condition q d (h) = q 1 at the other endpoint yields dτ . Furthermore, we introduce the internal stages, Again this is practically not computable, and so we employ the following approximation: Use the numerical quadrature formula with constants (b i , c i ) and the finite-dimensional function space C s d (V ) to constructĤ + d (q 0 , p 1 , U ) as follows: where we set P i := p(c i h) and U i := u(c i h) and defined where we defined M i j := ψ j (c i ) and used the expression for the control Hamiltonian in Eq. (7.1); note that P i ∈ V * and w i ∈ V for each i = 1, . . . , s, and that f takes values in V . In order to obtain an expression for H + d (q 0 , p 1 , U ), we first compute the stationarity conditions for K(q 0 , w, P, U, p 1 ) under the fixed boundary condition (q 0 , p 1 ): for j = 1, . . . , s.

4.
By solving the 2s stationarity conditions (7.4), we can express the parameters w and P in terms of q 0 , p 1 , and U , i.e., w =w(q 0 , U ) and P =P (q 0 , p 1 , U ): In particular, assuming b j = 0 for each j = 1, . . . , s, Eq. (7.4b) gives w j M i j = f (Q i (w), U i ); this gives a set of ns nonlinear equations 2 satisfied by w =w(q 0 , U ). 3 Therefore, we have Notice that the internal-stage momenta, P i , disappear when we substitute w =w(q 0 , U ). Therefore, we obtain the following Galerkin discrete control Hamiltonian: and This is a generalized version of Eq. (6.3) with internal-stage controls {U i k } s i=1 as opposed to a single control u k per time step (see Fig. 2). Now assume that Then, we may apply the same argument as in Section 6: In particular, the right discrete Hamilton-Jacobi equation (3.17) applied to this case gives the following Bellman equation with internal-stage controls: Figure 2. Internal-stage controls {U i k } s i=1 in the discrete time intervals between k and k + 1.
The following example shows that the standard Bellman equation (6.8) follows as a special case: Then, we have B 1 = 1, A 1 1 = 0, and M 1 1 = 1. Hence, Eq. (7.3) gives Q 1 = q k (we set the endpoints (q 0 , q 1 ) to be (q k , q k+1 ) here), and Eq. (7.4b) gives w 1 = f (q k , U 1 k ). However, the control U 1 k is defined as follows (we shift the time intervals from [0, h] to [t k , t k + h] here):

Conclusion and Future Work
We developed a discrete-time analogue of Hamilton-Jacobi theory starting from the discrete variational Hamiltonian mechanics formulated by Lall and West [23]. We reinterpreted and extended the discrete Hamilton-Jacobi equation given by Elnatanov and Schiff [13] in the language of discrete mechanics. Furthermore, we showed that the discrete Hamilton-Jacobi equation reduces to the discrete Riccati equation with a quadratic Hamiltonian, and also that it specializes to the Bellman equation of dynamic programming if applied to standard discrete optimal control problems. These results are discrete analogues of the corresponding known results in the continuous-time theory. Application to discrete optimal control also revealed that the Discrete Hamilton-Jacobi Theorem 4.1 specializes to a well-known result in discrete optimal control theory. We also used a Galerkin-type approximation to derive Galerkin discrete control Hamiltonians. This technique gave an explicit formula for discrete control Hamiltonians in terms of the constructs in the original continuous-time optimal control problem. By viewing the Bellman equation as a special case of the discrete Hamilton-Jacobi equation, we could introduce the discretization technique for discrete Hamiltonian mechanics into the discrete optimal control setting; this lead us to a class of Bellman equations with controls at internal stages.
We are interested in the following topics for future work: • Application to integrable discrete systems: Theorem 4.1 gives a discrete analogue of the theory behind the technique of solution by separation of variables, i.e., the theorem relates a solution of the discrete Hamilton-Jacobi equations with that of the discrete Hamilton's equations. An interesting question then is whether or not separation of variables applies to integrable discrete systems, e.g., discrete rigid bodies of Moser and Veselov [31] and various others discussed by Suris [33,34]. • Development of numerical methods based on the discrete Hamilton-Jacobi equation: Hamilton-Jacobi equation has been used to develop structured integrators for Hamiltonian systems. Ge and Marsden [14] developed a numerical method that preserves momentum maps and Poisson brackets of Lie-Poisson systems by solving the Lie-Poisson Hamilton-Jacobi equation approximately. See also Channell and Scovel [11] (and references therein) for a survey of structured integrators based on the Hamilton-Jacobi equation. The present theory, being inherently discrete in time, potentially provides a variant of such numerical methods. • Extension to discrete nonholonomic and Dirac mechanics: The present work is concerned only with unconstrained systems. Extensions to nonholonomic and Dirac mechanics, more specifically discrete-time versions of the nonholonomic Hamilton-Jacobi theory [10; 12; 19; 32] and Dirac Hamilton-Jacobi theory [27], are another direction for future research. On the other hand, Proposition 5.4 suggests that the discrete Hamilton-Jacobi equation is a generalization of the Riccati equation. We are interested in exploring possible further links implied by the generalization. • Galerkin discrete optimal control problems: The Galerkin discrete control Hamiltonians may be considered to be a means of formulating discrete optimal control problems with higher-order of approximation to a continuous-time optimal control problem. This idea generalizes the Runge-Kutta discretizations of optimal control problems (see, e.g., Hager [18] and references therein). In fact, Leok and Zhang [26] showed that their method recovers the SPRK (symplectic-partitioned Runge-Kutta) method. Therefore, this approach is expected to provide structure-preserving higher-order numerical methods for optimal control problems.
Proposition A.4. LetL b = b+L be a Lagrangian affine space of V and Φ : V → V be a symplectic transformation. Then Φ k (L b ) is also a Lagrangian affine space of V for any k ∈ N. More explicitly, we have Φ k (L b ) = Φ k b + Φ k (L).
Proof. Follows from a straightforward calculation.
A.3. Generating Functions. Now, consider the case where V = Q ⊕ Q * to apply the results from Section A.2 to the setting in Section A.1. This is a symplectic vector space with the symplectic form Ω : (Q ⊕ Q * ) × (Q ⊕ Q * ) → R defined by The key result here regarding Lagrangian subspaces on Q ⊕ Q * is the following: Proposition A.5. A Lagrangian subspace of Q ⊕ Q * that is transversal to {0} ⊕ Q * is the graph of an exact one-form on Q, i.e., L = graph dS for some function S : Q → R which has the form with some symmetric linear map A : Q → Q * and an arbitrary real scalar constant C. Moreover, the correspondence between the Lagrangian subspaces and such functions (modulo the constant term) is one-to-one.
Proof. First, recall that a Lagrangian submanifold of T * Q that projects diffeomorphically onto Q is the graph of a closed one-forms on Q (see Abraham and Marsden [1, Proposition 5.3.15 and the subsequent paragraph on p. 410]). In our case, Q is a vector space, and so the cotangent bundle T * Q is identified with the direct sum Q ⊕ Q * . Now, a Lagrangian subspace of Q ⊕ Q * that is transversal to {0} ⊕ Q * projects diffeomorphically onto Q, and so is the graph of a closed one-form. Then, by the Poincaré lemma, it follows that any such Lagrangian subspace L is identified with the graph of an exact one-form dS with some function S on Q, i.e., L = graph dS. However, as shown in, e.g., Jurdjevic [22, Theorem 3 on p. 233], the space of Lagrangian subspaces that are transversal to {0} ⊕ Q * is in one-to-one correspondence with the space of all symmetric maps A : Q → Q * , with the correspondence given by L = graph A. Hence, graph dS = graph A, or more specifically, dS(q) = A ij q j dq i . This implies that S has the form S(q) = 1 2 A ij q i q j + C, with an arbitrary real scalar constant C.