  In this paper, we develop algorithms to overcome the curse of dimensionality
in possibly non-convex state-dependent Hamilton-Jacobi equations (HJ PDEs)
arising from optimal control and differential game problems. The subproblems
are independent and can be implemented in an embarrassingly parallel fashion.
This is an ideal setup for perfect scaling in parallel computing. The algorithm
is proposed to overcome the curse of dimensionality [1, 2] when solving HJ PDE.
The major contribution of the paper is to change an optimization problem over a
space of curves to an optimization problem of a single vector, which goes
beyond [23]. We extend [5, 6, 8], and conjecture a (Lax-type) minimization
principle when the Hamiltonian is convex, as well as a (Hopf-type) maximization
principle when the Hamiltonian is non-convex. The conjectured Hopf-type
maximization principle is a generalization of the well-known Hopf formula [11,
16, 30]. We validated formula under restricted assumptions, and bring our
readers to [57] which validates that our conjectures in a more general setting
after a previous version of our paper. We conjectured the weakest assumption is
a psuedoconvexity assumption similar to [46]. The optimization problems are of
the same dimension as that of the HJ PDE. We suggest a coordinate descent
method for the minimization procedure in the generalized Lax/Hopf formula, and
numerical differentiation is used to compute the derivatives. This method is
preferable since the evaluation of the function value itself requires some
computational effort, especially when we handle high dimensional optimization
problem. The use of multiple initial guesses and a certificate of correctness
are suggested to overcome possibly multiple local extrema since the
optimization process is no longer convex. Our method is expected to have
application in control theory and differential game problems, and elsewhere.
