Overcoming the Computational Intractability of Optimal Control

54 concepts59 papers1 proposal

Optimal control theory provides the mathematical foundation for guiding dynamical systems—whether they are autonomous quadrotors, chemical reactors, or fluid-cooled battery packs—along trajectories that minimize costs like time, energy, or error. At the apex of this theory sits the Hamilton-Jacobi-Bellman (HJB) equation, a partial differential equation (PDE) whose solution yields the globally optimal value function and feedback policy.

Yet, for decades, a massive chasm has existed between this theoretical gold standard and practical engineering. For most real-world systems, the HJB equation is notoriously intractable. This article explores why optimal control is so computationally punishing and details the modern paradigms researchers are using to break through this mathematical bottleneck.

The Fundamental Bottleneck: Why Control is Hard

To understand why optimal control equations defy simple computation, consider the two primary ways control problems are framed: indirect methods (which solve for individual trajectories) and direct value-function methods (which solve for the entire state space). Both approaches quickly run into severe mathematical roadblocks.

The Curse of Dimensionality in Value Functions

Direct methods attempt to solve the HJB equation across the entire state space. If you know the optimal value from any given state, generating the control signal is trivial: you simply move in the direction of the steepest descent of the value function.

However, solving this PDE traditionally requires discretizing the state space into a grid. If a system has $d$ dimensions and we place $N$ grid points along each dimension, the total number of points scales as $N^d$. For a simple 6-degree-of-freedom robot (12 dimensions including velocity), a modest grid of 100 points per dimension requires $10^{24}$ states—an astronomical number that makes numerical grid-based methods impossible. As noted by Mukherjee et al. and Zhao et al., analytical solutions are virtually nonexistent for nonlinear dynamics, leaving engineers stranded when scaling to complex physical systems.

The Sensitivity of Trajectory Optimization

To avoid solving a PDE across the entire state space, indirect methods like Pontryagin’s Maximum Principle (PMP) focus on finding a single optimal trajectory from a specific starting point. This shifts the mathematical burden from a PDE to a set of ordinary differential equations (ODEs).

However, PMP introduces an "adjoint" or co-state variable for every state variable, representing the marginal value of changing that state. This formulation results in a Two-Point Boundary Value Problem (TPBVP): you know the initial position of the system, but you only know the terminal conditions of the co-states.

State Equations:    x(0) is known  ------------->  x(T) is free/constrained
Co-state Equations:  λ(0) is unknown <-------------  λ(T) is known

As highlighted by Wang et al. and Khazaeni et al., integrating these coupled, bidirectional differential equations is highly sensitive to initial parameters and computationally prohibitive for real-time applications. Even in deterministic settings, nonholonomic constraints (like those governing wheeled robots) can cause these trajectory equations to yield mathematically intractable elliptic functions, as shown by Murray. When adversarial elements or environmental noise are introduced, the problem escalates to the Hamilton-Jacobi-Isaacs (HJI) equation, rendering standard numerical solvers completely useless (Pereira et al., Thijssen et al.).

To bypass these bottlenecks, modern research splits into three main strategies: convex relaxations, mesh-free neural approximations, and temporal parallelization.

Convexifying the Problem via Occupation Measures

One elegant way to bypass non-convex, nonlinear differential equations is to change our perspective entirely: instead of looking at individual trajectories, we look at probability distributions of trajectories. This is the core intuition behind the occupation measure framework.

Imagine trying to find the optimal path through a complex maze of nonlinear dynamics. Tracking a single point is a highly non-convex optimization problem because the dynamics can twist and bend the feasible space. Instead, imagine pouring water into the maze and tracking how the fluid spreads. The behavior of the fluid is governed by linear conservation laws (the continuity or Liouville equation), even if the maze walls themselves are highly nonlinear.

An occupation measure formalizes this fluid analogy. It measures the total time a system trajectory spends in a given region of the state-action space. By rephrasing the optimal control problem in terms of these measures, the objective function and the system dynamics become completely linear.

Nonlinear Trajectory Space (Non-Convex)  --->  Lifting to Measure Space (Convex)
   Minimize ∫ c(x,u) dt                           Minimize ∫ c(x,u) dμ(x,u)
   subject to ẋ = f(x,u)                          subject to div(f·μ) = μ_init - μ_term

Lasserre et al. and Lasserre et al. demonstrated that if the system's dynamics and costs are polynomial, this infinite-dimensional linear program can be approximated using a sequence of finite-dimensional Semidefinite Programming (SDP) relaxations, known as the Sum-of-Squares (SOS) hierarchy. As Korda et al. explain, this "lifting" mechanism allows engineers to compute actual rational feedback controllers with guaranteed upper bounds on performance, providing a mathematically rigorous bridge over the non-convexity of traditional HJB formulations.

Mesh-Free Approximations with Physics-Informed Neural Networks

While convex relaxations work beautifully for polynomial systems, the size of the resulting semidefinite matrices scales poorly as the degree of the polynomial increases. To break the curse of dimensionality for general, high-dimensional systems, researchers have turned to deep learning.

The core insight is that deep neural networks are exceptional mesh-free function approximators. Instead of discretizing a state space into a rigid grid, a neural network can learn a continuous representation of the value function across high-dimensional spaces. However, purely data-driven reinforcement learning (RL) requires millions of random trials to discover the underlying physics of an environment.

To accelerate this, Physics-Informed Neural Networks (PINNs) inject the HJB equation directly into the network's loss function. Instead of just learning from rewards, the network is penalized whenever its outputs violate the fundamental PDE of optimal control.

Loss = Data_Loss + α · || HJB_Residual ||²
where HJB_Residual = ∂V/∂t + min_u [ c(x,u) + ∇V · f(x,u) ]

For instance, Mukherjee et al. introduced HJBPPO, an algorithm where the actor-critic architecture forces the critic network to satisfy the continuous-time HJB equation. Similarly, Meng et al. developed a PINN-based policy iteration framework that provides rigorous convergence and verification guarantees. By evaluating the HJB residual on a set of randomly sampled points rather than a fixed grid, Verma et al. showed that these physics-heavy models achieve high accuracy with up to 20 times fewer simulations than standard model-free RL algorithms.

Bypassing Grids via Forward-Backward SDEs

For stochastic systems or robust "min-max" control problems (where an agent optimizes performance against a worst-case adversarial disturbance), solving the resulting Hamilton-Jacobi-Isaacs PDE is even more daunting.

To circumvent this, Pereira et al. leverage a deep learning approach based on Forward-Backward Stochastic Differential Equations (FBSDEs). Through a mathematical link known as the non-linear Feynman-Kac formula, a class of second-order HJB PDEs can be represented as a coupled system of stochastic differential equations:

  1. A forward SDE simulates the system's state trajectory through time.
  2. A backward SDE propagates the gradient of the value function (the co-states) backward from the terminal cost.

By training neural networks (such as LSTMs) to act as the gradient of the value function along these sampled trajectories, the authors bypass grid-based methods entirely. The network only learns the value function in the regions of the state space that the system actually visits, making high-dimensional min-max control computationally viable.

Temporal Parallelization and Hybrid Planning

A final dimension of intractability stems from time itself. Solving the HJB equation or running dynamic programming algorithms inherently requires marching backward in time from a terminal state, resulting in a sequential time complexity of $O(T)$.

Breaking the Sequential Time Barrier

To unlock the massive parallel processing power of modern GPUs, Särkkä et al. introduced a framework to parallelize the HJB equation across the time domain. They achieved this by defining an associative combination operator for "conditional value functions."

Instead of computing the value function sequentially from $T$ back to $0$, the time horizon is divided into hundreds of isolated sub-intervals. Each sub-interval computes its own local conditional value function in parallel. Because the combination operator is associative, these local solutions can be merged using a parallel scan algorithm (similar to a binary tree merge), reducing the temporal computational complexity from linear $O(T)$ to logarithmic $O(\log T)$.

Sequential (O(T)):  [0] <--- [1] <--- [2] <--- [3] <--- [4] <--- [5] <--- [6] <--- [7]

Parallel (O(log T)): [0 <--- 1]    [2 <--- 3]    [4 <--- 5]    [6 <--- 7]
                        \            /              \            /
                         [0 <------- 3]              [4 <------- 7]
                                 \                        /
                                  [0 <------------------- 7]

Decoupling Global and Local Control

In practical robotics, when exact real-time trajectory optimization is too slow to prevent a vehicle from crashing, engineers often decouple global path planning from local kinodynamic execution.

Sivaramakrishnan et al. demonstrate a hybrid architecture where a deep reinforcement learning controller is trained offline in an obstacle-free environment to handle the complex, low-level physics of a vehicle (local goal-reaching). Online, a sampling-based global planner treats this learned controller as a reliable primitive, steering the robot through complex environments without ever needing to solve expensive two-point boundary value problems on the fly.

This approach grounds the theoretical insights established by the authors of this work, who proved that sampling directly in the control space can yield asymptotically optimal trajectories for Lipschitz continuous systems without requiring an explicit, computationally intractable analytical steering function.

Conclusion

The computational intractability of the Hamilton-Jacobi-Bellman equation is no longer an impassable barrier for nonlinear, high-dimensional control. By shifting from non-convex trajectories to convex occupation measures, replacing rigid numerical grids with physics-informed neural networks, and breaking temporal dependencies via parallelization, modern control theory has turned a mathematical nightmare into a suite of tractable, scalable engineering tools.

Key Foundational Work

Nonholonomic motion planning: steering using sinusoids (1993) — contributed 1 concept elements to this direction.
Is There Any Need for Domain-Dependent Control Information?: A Reply (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hamilton_jacobi_bellman_intractability_fcb74bb5,
  title = {Hamilton-Jacobi-Bellman intractability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hamilton-jacobi-bellman-intractability/rdr_fcb74bb525b44ed2aa812903cfee9441},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_hamilton_jacobi_bellman_intractability_fcb74bb5_v1,
  title = {Hamilton-Jacobi-Bellman intractability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hamilton-jacobi-bellman-intractability/rdr_fcb74bb525b44ed2aa812903cfee9441/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake