Introduction
The numerical solution of partial differential equations (PDEs) posed on high-dimensional state spaces is a central challenge in scientific computing, arising prominently in dynamic programming, where the value function of a d d d -dimensional optimal control problem satisfies a Hamilton–Jacobi–Bellman (HJB) equation over a subset of R d \mathbb{R}^{d} R d . Classical methods, such as finite differences [34 ] , finite elements [61 ] , and spectral methods [51 ] , are effective in low dimensions but typically require meshes, grids, or tensor-product approximation spaces whose cardinality grows exponentially with d d d , a phenomenon known as the curse of dimensionality [4 ] . Sparse grids [11 ] , reduced basis methods [44 ] , kernel-based approximation [58 ] , and deep learning [27 ] mitigate this growth with ansatze whose complexity is not tied to a grid in R d \mathbb{R}^{d} R d . For methods built on a dictionary of candidate features, their effectiveness relies on identifying which basis functions and training samples are most relevant to the solution at hand.
The prototypical problem motivating this work is the synthesis of optimal feedback laws for nonlinear dynamical systems. Consider a control-affine system with state y ( t ) ∈ R d \mathbf{y}(t) \in\mathbb{R}^{d} y ( t ) ∈ R d and control signal u ( t ) ∈ R m \mathbf{u}(t) \in\mathbb{R}^{m} u ( t ) ∈ R m , for which we seek a control minimizing an accumulated running cost over an infinite horizon:
min u ( ⋅ ) ∫ 0 ∞ ( ℓ ( y ( t ) ) + β ∥ u ( t ) ∥ 2 ) d t , β > 0 , subject to y ˙ ( t ) = f ( y ( t ) ) + q ( y ( t ) ) u ( t ) , y ( 0 ) = x . (1) \min_{\mathbf{u}(\cdot)} \int_{0}^{\infty} \left(\ell(\mathbf{y}(t))+\beta\lVert\mathbf{u}(t)\rVert^{2}\right)\,\mathrm{d}t,\qquad\beta>0,
\qquad\text{subject to}\quad\dot{\mathbf{y}}(t)=\mathbf{f}(\mathbf{y}(t))+\mathbf{q}(\mathbf{y}(t))\mathbf{u}(t),\qquad\mathbf{y}(0)=\mathbf{x}. \tag*{(1)} u ( ⋅ ) min ∫ 0 ∞ ( ℓ ( y ( t )) + β ∥ u ( t ) ∥ 2 ) d t , β > 0 , subject to y ˙ ( t ) = f ( y ( t )) + q ( y ( t )) u ( t ) , y ( 0 ) = x . (1)
2020 Mathematics Subject Classification. 49L12, 49L20, 49N35, 68T05, 93C20.
Key words and phrases. Optimal feedback control, Hamilton–Jacobi–Bellman equations, Adaptive basis selection, Greedy algorithms, Galerkin methods, Polynomial approximation.
The optimal cost of (1) , understood as a function of the initial state x \mathbf{x} x , defines the value function V ( x ) V(\mathbf{x}) V ( x ) of the control problem. Dynamic programming establishes that, wherever differentiable, the value function satisfies the stationary, first-order Hamilton–Jacobi–Bellman equation
0 = min u ∈ R m { ℓ ( x ) + β ∥ u ∥ 2 2 + ∇ V ( x ) T ( f ( x ) + q ( x ) u ) } . (2) 0 = \min_{\mathbf{u}\in\mathbb{R}^{m}} \left\{ \ell(\mathbf{x}) + \beta\lVert\mathbf{u}\rVert_2^2 + \nabla V(\mathbf{x})^{\mathsf{T}}\left(\mathbf{f}(\mathbf{x})+\mathbf{q}(\mathbf{x})\mathbf{u}\right) \right\}. \tag*{(2)} 0 = u ∈ R m min { ℓ ( x ) + β ∥ u ∥ 2 2 + ∇ V ( x ) T ( f ( x ) + q ( x ) u ) } . (2)
Once V V V is known, the optimal control is recovered in feedback form , u ∗ ( x ) = − 1 2 β q ( x ) T ∇ V ( x ) \mathbf{u}^{*}(\mathbf{x})=-\frac{1}{2\beta}\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla V(\mathbf{x}) u ∗ ( x ) = − 2 β 1 q ( x ) T ∇ V ( x ) , valid for every state x \mathbf{x} x . Inserting u ∗ \mathbf{u}^{*} u ∗ into (2) gives the fully nonlinear PDE L H J B ( V ) = 0 \mathcal{L}_{\mathrm{HJB}}(V)=0 L HJB ( V ) = 0 , with
L H J B ( V ) : = − 1 4 β ∇ V T q q T ∇ V + ∇ V T f + ℓ , \mathcal{L}_{\mathrm{HJB}}(V):=-\frac{1}{4\beta}\nabla V^{\mathsf{T}}\mathbf{q}\mathbf{q}^{\mathsf{T}}\nabla V+\nabla V^{\mathsf{T}}\mathbf{f}+\ell, L HJB ( V ) := − 4 β 1 ∇ V T q q T ∇ V + ∇ V T f + ℓ ,
cast over the state space of the dynamics, so that grid-based discretizations become unfeasible already for moderate values of d d d . The construction of numerical schemes for (2) which remain tractable in high dimensions is the main purpose of this paper. The methodology applies to a general class of first-order PDEs L ( V ) = 0 \mathcal{L}(V)=0 L ( V ) = 0 (see § 3 ), with the HJB equation as our leading example.
Sparse greedy approximation. To approximate the value function V V V , we introduce a large pool of globally defined candidate basis functions Φ Θ ( x ) = { ϕ j ( x ) : j ∈ Θ } \Phi_{\Theta}(\mathbf{x})=\{\phi_j(\mathbf{x}):j\in\Theta\} Φ Θ ( x ) = { ϕ j ( x ) : j ∈ Θ } , with ∣ Θ ∣ = P ≫ 1 |\Theta|=P\gg1 ∣Θ∣ = P ≫ 1 , such as multivariate polynomials, and consider approximations of the form
V ^ ( x ; c ) = ∑ j ∈ Γ c j ϕ j ( x ) = c T Φ Γ ( x ) . (3) \widehat{V}(\mathbf{x};\mathbf{c})=\sum_{j\in\Gamma}c_j\phi_j(\mathbf{x})=\mathbf{c}^{\mathsf{T}}\Phi_{\Gamma}(\mathbf{x}). \tag*{(3)} V ( x ; c ) = j ∈ Γ ∑ c j ϕ j ( x ) = c T Φ Γ ( x ) . (3)
where Γ ⊂ Θ \Gamma\subset\Theta Γ ⊂ Θ is the index set of active basis functions, Φ Γ ( x ) = [ ϕ j ( x ) ] j ∈ Γ T \Phi_{\Gamma}(\mathbf{x})=[\phi_j(\mathbf{x})]_{j\in\Gamma}^{\mathsf{T}} Φ Γ ( x ) = [ ϕ j ( x ) ] j ∈ Γ T is the vector of active basis functions, and c = [ c j ] j ∈ Γ T \mathbf{c}=[c_j]_{j\in\Gamma}^{\mathsf{T}} c = [ c j ] j ∈ Γ T is the coefficient vector. In practice only a relatively small subset of Φ Θ \Phi_{\Theta} Φ Θ contributes significantly to the approximation, while the cost of computing c \mathbf{c} c grows rapidly with n : = ∣ Γ ∣ n:=|\Gamma| n := ∣Γ∣ . Our aim is therefore to identify an accurate active set with n ≪ P n\ll P n ≪ P . We construct it greedily: starting from a small set Γ ( 1 ) \Gamma^{(1)} Γ ( 1 ) , at iteration k k k we compute the current approximation V ^ ( k ) = c ( k ) T Φ Γ ( k ) \widehat{V}^{(k)}=\mathbf{c}^{(k)\mathsf{T}}\Phi_{\Gamma^{(k)}} V ( k ) = c ( k ) T Φ Γ ( k ) , assign to each remaining candidate ϕ j \phi_j ϕ j , j ∈ Λ ( k ) : = Θ ∖ Γ ( k ) j\in\Lambda^{(k)}:=\Theta\setminus\Gamma^{(k)} j ∈ Λ ( k ) := Θ ∖ Γ ( k ) , an indicator e j ( k ) ≥ 0 e_j^{(k)}\ge0 e j ( k ) ≥ 0 that predicts the improvement obtained by adding ϕ j \phi_j ϕ j , and set
Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , j ∗ ∈ arg max j ∈ Λ ( k ) e j ( k ) , \Gamma^{(k+1)}=\Gamma^{(k)}\cup\{j^{*}\},\qquad j^{*}\in\operatorname*{arg\,max}_{j\in\Lambda^{(k)}}e_j^{(k)}, Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , j ∗ ∈ j ∈ Λ ( k ) arg max e j ( k ) ,
after which all coefficients are recomputed. The method is thus specified by how c ( k ) \mathbf{c}^{(k)} c ( k ) is computed and by the choice of e j ( k ) e_j^{(k)} e j ( k ) . We consider two complementary settings.
i) Model-based framework. When data are unavailable or expensive to obtain, we compute the coefficients by a Galerkin projection of the PDE and select basis functions with the residual-decay indicator
e j , P D E ( k ) = ∣ ⟨ L ( V ^ ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) ∣ ∥ L k ϕ j ∥ L 2 ( Ω ) , L k : = D L ( V ^ ( k ) ) . e_{j,\mathrm{PDE}}^{(k)}=\frac{\left|\left\langle\mathcal{L}(\widehat{V}^{(k)}),\mathcal{L}_k\phi_j\right\rangle_{L^2(\Omega)}\right|}{\lVert\mathcal{L}_k\phi_j\rVert_{L^2(\Omega)}},\qquad\mathcal{L}_k:=D\mathcal{L}(\widehat{V}^{(k)}). e j , PDE ( k ) = ∥ L k ϕ j ∥ L 2 ( Ω ) ⟨ L ( V ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) , L k := D L ( V ( k ) ) .
Its square, divided by two, is the largest decrease of the linearized residual functional α ↦ 1 2 ∥ L ( V ^ ( k ) ) + α L k ϕ j ∥ L 2 ( Ω ) 2 \alpha\mapsto\frac{1}{2}\lVert\mathcal{L}(\widehat{V}^{(k)})+\alpha\mathcal{L}_k\phi_j\rVert_{L^2(\Omega)}^2 α ↦ 2 1 ∥ L ( V ( k ) ) + α L k ϕ j ∥ L 2 ( Ω ) 2 along ϕ j \phi_j ϕ j . We derive it from the dual-weighted residual (DWR) framework by projecting the adjoint onto span { L k ϕ j } \operatorname{span}\{\mathcal{L}_k\phi_j\} span { L k ϕ j } , which makes it closed-form and adjoint-free: it requires only the current residual and the linearized operator, and no mesh.
ii) Data-driven framework. Following data-driven approaches to PDE approximation [47 ] , assume we are given a dataset D : = { ( x i , v i , g i ) } i = 1 N \mathcal{D}:=\{(\mathbf{x}_i,v_i,\mathbf{g}_i)\}_{i=1}^{N} D := {( x i , v i , g i ) } i = 1 N of function values v i = V ( x i ) v_i=V(\mathbf{x}_i) v i = V ( x i ) and gradients g i = ∇ V ( x i ) \mathbf{g}_i=\nabla V(\mathbf{x}_i) g i = ∇ V ( x i ) . For HJB equations, such data can be generated in a causality-free fashion by solving open-loop optimal control problems via Pontryagin’s Maximum Principle (PMP), see § 2 . We fit (3) by a gradient-augmented Lasso regression on an active subset of D D D . Given prescribed weights ω 1 , ω 2 > 0 \omega_1,\omega_2>0 ω 1 , ω 2 > 0 for the value and gradient errors, at each iteration we add both the sample with the largest misfit
ω 1 ∣ v i − V ^ ( k ) ( x i ) ∣ 2 + ω 2 ∥ g i − ∇ V ^ ( k ) ( x i ) ∥ 2 2 \omega_1\lvert v_i-\widehat{V}^{(k)}(\mathbf{x}_i)\rvert^2+\omega_2\lVert\mathbf{g}_i-\nabla\widehat{V}^{(k)}(\mathbf{x}_i)\rVert_2^2 ω 1 ∣ v i − V ( k ) ( x i ) ∣ 2 + ω 2 ∥ g i − ∇ V ( k ) ( x i ) ∥ 2 2
and the basis function with the largest supervised-loss indicator e j , S L ( k ) e_{\mathrm{j,SL}}^{(k)} e j , SL ( k ) , which measures the exact one-step decrease of the weighted gradient-augmented least-squares loss along ϕ j \phi_j ϕ j . In this way, only a small subset of the available samples is used.
Related literature. Two choices central to this paper are the selection of the approximation space and the states used to construct the approximation. Existing approaches to high-dimensional HJB equations address these choices through different numerical formulations. A first family determines the approximation from the PDE itself. Polynomial Galerkin schemes combined with policy iteration [30 ] , sparse-grid discretizations [8 , 25 ] , low-rank tensor formats [17 , 18 ] , and neural networks trained by minimizing the HJB residual, either pointwise as in physics-informed and Deep Galerkin methods [53 ] or over monotone finite-difference schemes [22 ] , fall into this class, as do backward SDE formulations [27 ] . In these methods the approximation space, that is, the polynomial degree, the grid level, the tensor format or the network architecture, is fixed before the solve, or is refined by local error indicators tied to a grid, as in adaptive sparse grids.
A second family avoids discretizing the state space by working at individual states or along optimal trajectories. Since optimal trajectories are characteristics of the HJB equation, solving open-loop optimal control problems via the PMP yields the value function and its gradient at individual states without a spatial grid [31 , 32 , 54 , 59 ] , and for certain Hamiltonians, Lax–Hopf formulas reduce such pointwise evaluations to convex optimization problems [16 ] . These samples are then used to fit a global approximation, such as a sparse polynomial [2 ] or a neural network trained with adaptive sampling [38 ] ; since each sample requires the solution of a two-point boundary value problem, the number of samples largely determines the cost. Related approaches regress on data from state-dependent Riccati equations [1 ] , train networks on the control objective with HJB penalties along trajectories [35 , 41 ] , apply symplectic networks to the PMP system [37 ] , or learn the feedback law directly [33 ] .
Adaptive strategies have been developed in several related contexts. In data-driven settings, [49 ] proposes a greedy point selection algorithm for kernel-based solutions of Dirichlet problems. In machine learning, [52 ] develops a greedy training algorithm for shallow neural networks that incrementally adds neurons (basis functions) to minimize empirical risk. In optimal control, [19 , 20 ] combine greedy selection of initial states for open-loop solves with greedy kernel approximation, including Hermite interpolation based on value and gradient data. Their subsequent work [21 ] introduces online enrichment driven by the HJB residual. In these kernel constructions, the approximation space is generated by kernel functions associated with the selected interpolation centers.
In model-based settings, adaptivity is often guided by a posteriori error estimation. A well-established framework is the DWR method, originally developed for finite element methods, which drives adaptive mesh refinement to achieve target accuracy in a prescribed quantity of interest (QoI) [3 , 10 , 26 , 28 , 40 ] . DWR provides a first-order error approximation for the QoI by weighting the primal residual with the solution of a (linearized) adjoint problem, typically computed with the same numerical scheme as the primal one, such as finite elements, discontinuous Galerkin [15 ] , finite volumes [13 ] , or feedforward neural networks [46 ] . It has been applied to many low-dimensional problems [29 , 45 , 57 ] and extended to neural networks [23 ] , reduced-order models [7 ] , multiscale [14 ] and virtual element methods [50 ] . However, these formulations remain mesh-based, and their effectiveness depends critically on the accuracy of the adjoint approximation [39 ] . The approach in [7 ] projects the adjoint onto a reduced subspace, but still requires solving a reduced adjoint system. Adjoint-based adaptivity for HJB equations has so far been demonstrated only in one- or two-dimensional settings [9 , 12 , 24 , 48 ] .
The proposed greedy enrichment is closely related to Orthogonal Matching Pursuit (OMP) [42 , 56 ] and, more broadly, to greedy dictionary approximation [6 , 36 ] . OMP selects the dictionary element with the largest normalized correlation with the current residual and then refits by least squares over the span of the selected elements. The supervised-loss indicator is a weighted OMP selection rule on the gradient-augmented feature matrix; our data-driven algorithm differs from OMP through the greedy selection of training data and the sparsity-promoting refit. The residual-decay indicator is an OMP-type rule in function space, with dictionary { L k ϕ j } \{\mathcal{L}_k\phi_j\} { L k ϕ j } , the PDE residual in place of the data residual, and a Galerkin refit.
Contributions. The main contributions of this paper are as follows.
We derive the closed-form residual-decay indicator e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) for model-based greedy basis enrichment, show that it predicts the first-order reduction of the PDE residual obtained by adding a single candidate basis function, and specialize it to the HJB operator. It is inspired by the goal-oriented DWR framework, but applies to high-dimensional, mesh-free settings while bypassing any adjoint solve. It also admits an empirical version computed from samples.
We develop a data-driven greedy algorithm for joint basis and training sample selection, which couples a weighted OMP step for the basis with a greedy selection of gradient-augmented training samples.
We demonstrate the proposed framework on benchmark PDEs and nonlinear optimal control problems in up to 35 dimensions. The numerical results show that the greedy strategies achieve comparable accuracy to nonadaptive baselines while using substantially fewer basis functions and, in the data-driven setting, fewer training samples.
The rest of the paper is organized as follows. Section 2 presents the finite-horizon optimal control problem, the associated HJB equation, its link with the PMP, and the large-horizon recovery of the infinite-horizon value function. Section 3 introduces the polynomial dictionaries and the Galerkin and supervised-learning schemes for the coefficients. Sections 4 and 5 develop the model-based and data-driven greedy algorithms, and Section 6 presents the numerical experiments.
Optimal control and Hamilton–Jacobi–Bellman PDEs
A primary motivation of this work is the approximation of nonlinear Hamilton-Jacobi-Bellman PDEs arising in optimal control, where the dimensionality make grid-based discretizations intractable. For an initial time t ∈ [ 0 , T ] t \in[0,T] t ∈ [ 0 , T ] and an initial state x ∈ R d \mathbf{x} \in\mathbb{R}^d x ∈ R d , we consider a deterministic nonlinear optimal control problem of the form
min u ( ⋅ ) ∈ L 2 ( T ; R m ) J ( u ; t , x ) : = ∫ t T ℓ ( y ( s ) ) + β ∥ u ( s ) ∥ 2 2 d s + ℓ T ( y ( T ) ) , β > 0 , (4) \min_{\mathbf{u}(\cdot)\in L^2(T;\mathbb{R}^m)} J(\mathbf{u};t,\mathbf{x}) := \int_t^T \ell(\mathbf{y}(s))+\beta\|\mathbf{u}(s)\|_2^2\,\mathrm{d}s+\ell_T(\mathbf{y}(T)), \qquad\beta>0, \tag*{(4)} u ( ⋅ ) ∈ L 2 ( T ; R m ) min J ( u ; t , x ) := ∫ t T ℓ ( y ( s )) + β ∥ u ( s ) ∥ 2 2 d s + ℓ T ( y ( T )) , β > 0 , (4)
subject to y ˙ ( s ) = f ( y ( s ) ) + q ( y ( s ) ) u ( s ) , y ( t ) = x \dot{\mathbf{y}}(s)=\mathbf{f}(\mathbf{y}(s))+\mathbf{q}(\mathbf{y}(s))\mathbf{u}(s), \quad\mathbf{y}(t)=\mathbf{x} y ˙ ( s ) = f ( y ( s )) + q ( y ( s )) u ( s ) , y ( t ) = x .
Assume that the running cost ℓ : R d → R \ell:\mathbb{R}^d\to\mathbb{R} ℓ : R d → R , the terminal penalty ℓ T : R d → R \ell_T:\mathbb{R}^d\to\mathbb{R} ℓ T : R d → R , the dynamics f : R d → R d \mathbf{f}:\mathbb{R}^d\to\mathbb{R}^d f : R d → R d , and the control-to-state-operator q : R d → R d × m \mathbf{q}:\mathbb{R}^d\to\mathbb{R}^{d\times m} q : R d → R d × m are continuously differentiable in R d \mathbb{R}^d R d .
The value function of (4) is defined as the optimal cost-to-go
V ( t , x ) : = min u ( ⋅ ) ∈ L 2 ( t , T ; R m ) J ( u ; t , x ) , ( t , x ) ∈ [ 0 , T ] × R d . V(t,x) := \min_{\mathbf{u}(\cdot)\in L^2(t,T;\mathbb{R}^m)} J(\mathbf{u};t,x), \qquad(t,x)\in[0,T]\times\mathbb{R}^d. V ( t , x ) := u ( ⋅ ) ∈ L 2 ( t , T ; R m ) min J ( u ; t , x ) , ( t , x ) ∈ [ 0 , T ] × R d .
By the Dynamic Programming Principle [5 ] , wherever V V V is differentiable it satisfies the time-dependent HJB equation
{ ∂ t V ( t , x ) + min u ∈ R m { ℓ ( x ) + β ∥ u ∥ 2 2 + ∇ V ( t , x ) T ( f ( x ) + q ( x ) u ) } = 0 , V ( T , x ) = ℓ T ( x ) . \begin{cases}
\partial_t V(t,x)+\min_{\mathbf{u}\in\mathbb{R}^m}\left\{\ell(x)+\beta\|\mathbf{u}\|_2^2+\nabla V(t,x)^{\mathsf T}(f(x)+q(x)\mathbf{u})\right\}=0,\\
V(T,x)=\ell_T(x).
\end{cases} { ∂ t V ( t , x ) + min u ∈ R m { ℓ ( x ) + β ∥ u ∥ 2 2 + ∇ V ( t , x ) T ( f ( x ) + q ( x ) u ) } = 0 , V ( T , x ) = ℓ T ( x ) .
from where the optimal control in feedback form is given by
u ∗ ( t , x ) = − 1 2 β q ( x ) T ∇ V ( t , x ) . \mathbf{u}^*(t,x)=-\frac{1}{2\beta}q(x)^{\mathsf T}\nabla V(t,x). u ∗ ( t , x ) = − 2 β 1 q ( x ) T ∇ V ( t , x ) .
yielding the equivalent HJB PDE
{ ∂ t V ( t , x ) + ∇ V ( t , x ) T f ( x ) − 1 4 β ∥ q ( x ) T ∇ V ( t , x ) ∥ 2 2 + ℓ ( x ) = 0 , V ( T , x ) = ℓ T ( x ) . (5) \begin{cases}
\partial_t V(t,x)+\nabla V(t,x)^{\mathsf T}f(x)-\dfrac{1}{4\beta}\left\|q(x)^{\mathsf T}\nabla V(t,x)\right\|_2^2+\ell(x)=0,\\
V(T,x)=\ell_T(x). \tag*{(5)}
\end{cases} ⎩ ⎨ ⎧ ∂ t V ( t , x ) + ∇ V ( t , x ) T f ( x ) − 4 β 1 q ( x ) T ∇ V ( t , x ) 2 2 + ℓ ( x ) = 0 , V ( T , x ) = ℓ T ( x ) . (5)
An alternative solution to the optimal control problem (4) follows Pontryagin’s Maximum Principle, corresponding to first-order necessary optimality conditions in the form of a two-point boundary-value problem (TPBVP) coupling the optimal state, adjoint, and control ( y ∗ ( s ) , p ∗ ( s ) , u ∗ ( s ) ) (\mathbf{y}^*(s),\mathbf{p}^*(s),\mathbf{u}^*(s)) ( y ∗ ( s ) , p ∗ ( s ) , u ∗ ( s )) over s ∈ ( t , T ) s\in(t,T) s ∈ ( t , T ) :
{ d d s y ∗ ( s ) = f ( y ∗ ( s ) ) + q ( y ∗ ( s ) ) u ∗ ( s ) , y ∗ ( t ) = x , − d d s p ∗ ( s ) = ∂ y ( f ( y ∗ ( s ) ) + q ( y ∗ ( s ) ) u ∗ ( s ) ) T p ∗ ( s ) + ∂ y ℓ ( y ∗ ( s ) ) , p ∗ ( T ) = ∇ ℓ T ( y ∗ ( T ) ) , \begin{cases}
\dfrac{d}{ds}\mathbf{y}^*(s)=f(\mathbf{y}^*(s))+q(\mathbf{y}^*(s))\mathbf{u}^*(s),\\
\mathbf{y}^*(t)=x,\\
-\dfrac{d}{ds}\mathbf{p}^*(s)=\partial_y\left(f(\mathbf{y}^*(s))+q(\mathbf{y}^*(s))\mathbf{u}^*(s)\right)^{\mathsf T}\mathbf{p}^*(s)+\partial_y\ell(\mathbf{y}^*(s)),\\
\mathbf{p}^*(T)=\nabla\ell_T(\mathbf{y}^*(T)),
\end{cases} ⎩ ⎨ ⎧ d s d y ∗ ( s ) = f ( y ∗ ( s )) + q ( y ∗ ( s )) u ∗ ( s ) , y ∗ ( t ) = x , − d s d p ∗ ( s ) = ∂ y ( f ( y ∗ ( s )) + q ( y ∗ ( s )) u ∗ ( s ) ) T p ∗ ( s ) + ∂ y ℓ ( y ∗ ( s )) , p ∗ ( T ) = ∇ ℓ T ( y ∗ ( T )) ,
closed via the optimal control
u ∗ ( s ) = − 1 2 β q ( y ∗ ( s ) ) T p ∗ ( s ) , ∀ s ∈ ( t , T ) . \mathbf{u}^*(s)=-\frac{1}{2\beta}q(\mathbf{y}^*(s))^{\mathsf T}\mathbf{p}^*(s),\qquad\forall s\in(t,T). u ∗ ( s ) = − 2 β 1 q ( y ∗ ( s ) ) T p ∗ ( s ) , ∀ s ∈ ( t , T ) .
Under the regularity assumption V ∈ C 1 V\in C^1 V ∈ C 1 , the PMP forward–backward dynamics act as characteristic curves of the HJB equation [43 , 54 , 60 ] . Thus, the value function at ( t , x ) (t,x) ( t , x ) can be computed by solving the TPBVP and evaluating the optimal cost (4) along the resulting optimal trajectory, while its gradient is identified as the adjoint, ∇ V ( t , x ) = p ∗ ( t ) \nabla V(t,x)=\mathbf{p}^*(t) ∇ V ( t , x ) = p ∗ ( t ) . Consequently, the data-driven approach developed in [2 ] , which constitutes one of the building blocks of the present work, approximates the solution of (5) by first generating a gradient-augmented dataset using a characteristic-based, causality-free method derived from solving the TPBVP via PMP, and then applies sparse regression to recover the value function using a polynomial basis. Building upon this framework, we introduce greedy selection strategies for both basis functions and data points. Instead of prescribing a fixed basis and dataset, we iteratively enrich the approximation subspace by selecting the most informative basis functions and sampling data points. This adaptive strategy provides accurate approximations of value functions while improving computational efficiency.
We conclude this section by connecting the finite-horizon problem (4) to the infinite-horizon problem (1) and its stationary HJB equation (2) . Note that (1) cannot be treated as the instance T = ∞ T=\infty T = ∞ of (4) : without additional admissibility assumptions on the class of controls, the resulting problem is ill-posed. Instead, we exploit the fact that, for stabilizable dynamics and a coercive running cost, the finite-horizon value function becomes approximately stationary sufficiently far away from the terminal time, and the influence of the terminal penalty ℓ T \ell_T ℓ T on V ( 0 , ⋅ ) V(0,\cdot) V ( 0 , ⋅ ) fades as T T T grows. Hence, for T T T sufficiently large, the stationary value function V ( x ) V(\mathbf{x}) V ( x ) and the associated feedback law u ∗ ( x ) \mathbf{u}^{*}(\mathbf{x}) u ∗ ( x ) are recovered from their time-dependent counterparts through
V ( x ) ≈ V ( 0 , x ) , u ∗ ( x ) ≈ u ∗ ( 0 , x ) . V(\mathbf{x}) \approx V(0,\mathbf{x}), \qquad\mathbf{u}^{*}(\mathbf{x}) \approx\mathbf{u}^{*}(0,\mathbf{x}). V ( x ) ≈ V ( 0 , x ) , u ∗ ( x ) ≈ u ∗ ( 0 , x ) .
This large-horizon approximation is the route followed throughout the paper: in the model-based setting, the time-dependent HJB equation (5) is integrated backwards from the terminal condition and V ( 0 , ⋅ ) V(0,\cdot) V ( 0 , ⋅ ) is retained, while in the data-driven setting, PMP-based samples of V ( 0 , ⋅ ) V(0,\cdot) V ( 0 , ⋅ ) and ∇ V ( 0 , ⋅ ) \nabla V(0,\cdot) ∇ V ( 0 , ⋅ ) are used as training data.
Polynomial models and approximation of HJB PDEs
The adaptive strategies developed in this paper apply to general stationary problems of the form
( L V ) ( x ) : = H ( x , V ( x ) , ∇ V ( x ) ) = 0 , x ∈ Ω , (6) (\mathcal{L}V)(\mathbf{x}) := \mathcal{H}(\mathbf{x}, V(\mathbf{x}), \nabla V(\mathbf{x})) = 0, \qquad\mathbf{x} \in\Omega, \tag*{(6)} ( L V ) ( x ) := H ( x , V ( x ) , ∇ V ( x )) = 0 , x ∈ Ω , (6)
where Ω ⊂ R d \Omega\subset\mathbb{R}^{d} Ω ⊂ R d is a compact domain, V \mathcal{V} V is a Hilbert space continuously embedded in H 1 ( Ω ) H^{1}(\Omega) H 1 ( Ω ) , and L : V → L 2 ( Ω ) \mathcal{L} : \mathcal{V} \to L^{2}(\Omega) L : V → L 2 ( Ω ) is the (possibly nonlinear) first-order differential operator induced by the Hamiltonian H : Ω × R × R d → R \mathcal{H} : \Omega\times\mathbb{R} \times\mathbb{R}^{d} \to\mathbb{R} H : Ω × R × R d → R . Our leading example is the stationary HJB equation (2) , for which H \mathcal{H} H is the control Hamiltonian obtained upon minimization over u \mathbf{u} u , and L \mathcal{L} L is the stationary HJB operator made precise in § 4.4 . Recall that we use V V V to denote the solution of (6) , and denote its approximation by V ^ \widehat{V} V .
In this section, we introduce the construction of the candidate basis set Φ Θ \Phi_{\Theta} Φ Θ and present two complementary numerical schemes for the approximation of the PDE (6) . In the model-based setting, the coefficients are computed by a Galerkin projection of the PDE operator L \mathcal{L} L . In the data-driven setting, the coefficients are obtained by supervised learning from gradient-augmented samples of the value function.
Sparse polynomial ansatz
Let Ω = ∏ i = 1 d Ω i \Omega= \prod_{i=1}^{d} \Omega_i Ω = ∏ i = 1 d Ω i be a bounded domain, where Ω i ⊂ R \Omega_i \subset\mathbb{R} Ω i ⊂ R . For i = 1 , … , d i = 1,\ldots,d i = 1 , … , d , let { ϕ m ( i ) } m ∈ N 0 \{\phi_m^{(i)}\}_{m\in\mathbb{N}_0} { ϕ m ( i ) } m ∈ N 0 be a one-dimensional orthonormal basis of L 2 ( Ω i ) L^{2}(\Omega_i) L 2 ( Ω i ) . Typical choices include orthonormal polynomial basis, such as Legendre and orthonormal trigonometric basis. Then for j = ( j 1 , j 2 , … , j d ) ∈ N 0 d \mathbf{j} = (j_1,j_2,\ldots,j_d) \in\mathbb{N}_0^d j = ( j 1 , j 2 , … , j d ) ∈ N 0 d , we define the corresponding tensor-product basis function by
ϕ j ( x ) = ∏ i = 1 d ϕ j i ( i ) ( x i ) , j = ( j 1 , j 2 , … , j d ) ∈ N 0 d . \phi_{\mathbf{j}}(\mathbf{x}) = \prod_{i=1}^{d}\phi_{j_i}^{(i)}(x_i), \qquad\mathbf{j} = (j_1,j_2,\ldots,j_d) \in\mathbb{N}_0^d. ϕ j ( x ) = i = 1 ∏ d ϕ j i ( i ) ( x i ) , j = ( j 1 , j 2 , … , j d ) ∈ N 0 d .
To manage complexity in high dimensions, we use the total degree index set
(Total degree) Θ T D ( M ) : = { j ∈ N 0 d : ∑ i = 1 d j i ≤ M } , \text{(Total degree)} \qquad\Theta^{\mathrm{TD}}(M) := \left\{\mathbf{j} \in\mathbb{N}_0^d : \sum_{i=1}^{d}j_i \le M\right\}, (Total degree) Θ TD ( M ) := { j ∈ N 0 d : i = 1 ∑ d j i ≤ M } ,
and the hyperbolic cross index set
(Hyperbolic cross) Θ H C ( J ~ ) : = { j ∈ N 0 d : ∏ i = 1 d ( j i + 1 ) ≤ 2 J ~ + 1 } , \text{(Hyperbolic cross)} \qquad\Theta^{\mathrm{HC}}(\widetilde{J}) := \left\{\mathbf{j} \in\mathbb{N}_0^d : \prod_{i=1}^{d}(j_i+1) \le2^{\widetilde{J}+1}\right\}, (Hyperbolic cross) Θ HC ( J ) := { j ∈ N 0 d : i = 1 ∏ d ( j i + 1 ) ≤ 2 J + 1 } ,
where M , J ~ ∈ N M,\widetilde{J} \in\mathbb{N} M , J ∈ N . For comparison, the full tensor index set
(Full tensor) Θ F U L L ( S ) : = { j ∈ N 0 d : max i = 1 , … , d j i ≤ S } \text{(Full tensor)} \qquad\Theta^{\mathrm{FULL}}(S) := \left\{\mathbf{j} \in\mathbb{N}_0^d : \max_{i=1,\ldots,d} j_i \le S\right\} (Full tensor) Θ FULL ( S ) := { j ∈ N 0 d : i = 1 , … , d max j i ≤ S }
with S ∈ N S \in\mathbb{N} S ∈ N has cardinality ∣ Θ F U L L ( S ) ∣ = ( S + 1 ) d |\Theta^{\mathrm{FULL}}(S)| = (S+1)^d ∣ Θ FULL ( S ) ∣ = ( S + 1 ) d , which grows exponentially with d d d . By contrast, the total-degree index set has cardinality ∣ Θ T D ( M ) ∣ = ∑ m = 0 M ( d + m − 1 m ) |\Theta^{\mathrm{TD}}(M)| = \sum_{m=0}^{M}\binom{d+m-1}{m} ∣ Θ TD ( M ) ∣ = ∑ m = 0 M ( m d + m − 1 ) , which grows combinatorially with M M M and d d d . The hyperbolic cross set provides a further reduction and thus scales better for high-dimensional problems, with cardinality satisfying ∣ Θ H C ( J ) ∣ ≤ min { 2 3 J + 1 4 d , e 2 ( 4 d ) } |\Theta^{\mathrm{HC}}(J)| \le\min\{2^{3J+1}4^d, e^{2(4d)}\} ∣ Θ HC ( J ) ∣ ≤ min { 2 3 J + 1 4 d , e 2 ( 4 d ) } [2 ] .
Model-based schemes: Galerkin projection
Given a selected basis index set Γ ⊂ Θ \Gamma\subset\Theta Γ ⊂ Θ with ∣ Γ ∣ = n |\Gamma| = n ∣Γ∣ = n , we define the n n n -dimensional approximation subspace
V n : = span { ϕ j : j ∈ Γ } ⊂ V . \mathcal{V}_n := \operatorname{span}\{\phi_j : j \in\Gamma\} \subset\mathcal{V}. V n := span { ϕ j : j ∈ Γ } ⊂ V .
Writing V ^ = Φ Γ T c \widehat{V} = \Phi_\Gamma^{\mathsf{T}}\mathbf{c} V = Φ Γ T c with c = [ c j ] j ∈ Γ ∈ R n \mathbf{c} = [c_j]_{j\in\Gamma} \in\mathbb{R}^n c = [ c j ] j ∈ Γ ∈ R n , the Galerkin approximation of (6) in V n \mathcal{V}_n V n is determined by the n n n equations
H ( c ) = 0 , H i ( c ) : = ⟨ L ( Φ Γ T c ) , ϕ i ⟩ L 2 ( Ω ) , i ∈ Γ . (7) \mathbf{H}(\mathbf{c}) = 0,\qquad H_i(\mathbf{c}) := \left\langle\mathcal{L}(\Phi_\Gamma^{\mathsf{T}}\mathbf{c}),\phi_i\right\rangle_{L^2(\Omega)},\qquad i\in\Gamma. \tag*{(7)} H ( c ) = 0 , H i ( c ) := ⟨ L ( Φ Γ T c ) , ϕ i ⟩ L 2 ( Ω ) , i ∈ Γ. (7)
When L \mathcal{L} L is affine, (7) is a linear system for c \mathbf{c} c ; this is the case of the benchmark in § 6.1 . The ansatz and the projection (7) are formulated for a stationary PDE. The HJB equation (5) associated with the control problem of § 2 , however, is time-dependent: we approximate its solution V ( t , ⋅ ) V(t,\cdot) V ( t , ⋅ ) on [ 0 , T ] [0,T] [ 0 , T ] and retain V ( 0 , ⋅ ) V(0,\cdot) V ( 0 , ⋅ ) , which approximates the stationary value function for large T T T . We therefore extend the ansatz to time-dependent functions by keeping the spatial basis fixed and letting the coefficients depend on time. Projecting in space as in (7) then yields a system of ordinary differential equations for the coefficients, which we now derive.
A time-dependent Galerkin scheme for HJB equations
The value function of the finite-horizon problem (4) satisfies (5) , which in terms of the stationary HJB operator L H J B \mathcal{L}_{\mathrm{HJB}} L HJB of (19) reads ∂ t V + L H J B V = 0 \partial_t V + \mathcal{L}_{\mathrm{HJB}}V = 0 ∂ t V + L HJB V = 0 with V ( T , ⋅ ) = ℓ T V(T,\cdot) = \ell_T V ( T , ⋅ ) = ℓ T . As in (3) , we approximate the value function by
V ^ ( t , x ) = ∑ j ∈ Γ c j ( t ) ϕ j ( x ) = Φ Γ ( x ) T c ( t ) , \widehat{V}(t,\mathbf{x}) = \sum_{j\in\Gamma} c_j(t)\phi_j(\mathbf{x}) = \Phi_\Gamma(\mathbf{x})^{\mathsf{T}}\mathbf{c}(t), V ( t , x ) = j ∈ Γ ∑ c j ( t ) ϕ j ( x ) = Φ Γ ( x ) T c ( t ) ,
where c ( t ) = [ c j ( t ) ] j ∈ Γ T \mathbf{c}(t) = [c_j(t)]_{j\in\Gamma}^{\mathsf{T}} c ( t ) = [ c j ( t ) ] j ∈ Γ T is the vector of time-dependent coefficients. Projecting the HJB equation onto the span of { ϕ i } i ∈ Γ \{\phi_i\}_{i\in\Gamma} { ϕ i } i ∈ Γ , for each i ∈ Γ i\in\Gamma i ∈ Γ , we solve for c ( t ) \mathbf{c}(t) c ( t ) such that
⟨ ∂ t V ( t , x ) + ∇ V ( t , x ) T f ( x ) − 1 4 β ∥ q ( x ) T ∇ V ( t , x ) ∥ 2 2 + ℓ ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) = 0. \left\langle\partial_t V(t,\mathbf{x}) + \nabla V(t,\mathbf{x})^{\mathsf{T}}\mathbf{f}(\mathbf{x}) - \frac{1}{4\beta}\left\|\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla V(t,\mathbf{x})\right\|_2^2 + \ell(\mathbf{x}),\phi_i(\mathbf{x})\right\rangle_{L^2(\Omega)} = 0. ⟨ ∂ t V ( t , x ) + ∇ V ( t , x ) T f ( x ) − 4 β 1 q ( x ) T ∇ V ( t , x ) 2 2 + ℓ ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) = 0.
Substituting V ^ \widehat{V} V into the above equation, we obtain
⟨ ∑ j ∈ Γ c ˙ j ( t ) ϕ j ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) + ⟨ ∑ j ∈ Γ c j ( t ) ∇ ϕ j ( x ) T f ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) − 1 4 β ⟨ ∥ q ( x ) T ( ∑ j ∈ Γ c j ( t ) ∇ ϕ j ( x ) ) ∥ 2 2 , ϕ i ( x ) ⟩ L 2 ( Ω ) + ⟨ ℓ ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) = 0. (8) \begin{aligned}
&\left\langle\sum_{j\in\Gamma}\dot{c}_j(t)\phi_j(\mathbf{x}),\phi_i(\mathbf{x})\right\rangle_{L^2(\Omega)}
+\left\langle\sum_{j\in\Gamma}c_j(t)\nabla\phi_j(\mathbf{x})^{\mathsf{T}}\mathbf{f}(\mathbf{x}),\phi_i(\mathbf{x})\right\rangle_{L^2(\Omega)}\\
&\quad-\frac{1}{4\beta}\left\langle\left\|\mathbf{q}(\mathbf{x})^{\mathsf{T}}\left(\sum_{j\in\Gamma}c_j(t)\nabla\phi_j(\mathbf{x})\right)\right\|_2^2,\phi_i(\mathbf{x})\right\rangle_{L^2(\Omega)}
+\left\langle\ell(\mathbf{x}),\phi_i(\mathbf{x})\right\rangle_{L^2(\Omega)}=0. \tag*{(8)}
\end{aligned} ⟨ j ∈ Γ ∑ c ˙ j ( t ) ϕ j ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) + ⟨ j ∈ Γ ∑ c j ( t ) ∇ ϕ j ( x ) T f ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) − 4 β 1 ⟨ q ( x ) T j ∈ Γ ∑ c j ( t ) ∇ ϕ j ( x ) 2 2 , ϕ i ( x ) ⟩ L 2 ( Ω ) + ⟨ ℓ ( x ) , ϕ i ( x ) ⟩ L 2 ( Ω ) = 0. (8)
This motivates the definition of the following matrices and vectors:
M ∈ R n × n with M i j = ∫ Ω ϕ i ( x ) ϕ j ( x ) d x , K ∈ R n × n with K i j = ∫ Ω ϕ i ( x ) ∇ ϕ j ( x ) T f ( x ) d x , L ∈ R n with L i = ∫ Ω ϕ i ( x ) ℓ ( x ) d x , L T ∈ R n with ( L T ) i = ∫ Ω ϕ i ( x ) ℓ T ( x ) d x , Q ( c ) ∈ R n with Q i ( c ) = ∫ Ω ϕ i ( x ) ∥ q ( x ) T ( ∑ j ∈ Γ c j ∇ ϕ j ( x ) ) ∥ 2 2 d x . \begin{aligned}
\mathbf{M} &\in\mathbb{R}^{n \times n} \quad\text{with} \quad M_{ij} = \int_{\Omega} \phi_i(\mathbf{x})\phi_j(\mathbf{x})\,\mathrm{d}\mathbf{x},\\
\mathbf{K} &\in\mathbb{R}^{n \times n} \quad\text{with} \quad K_{ij} = \int_{\Omega} \phi_i(\mathbf{x})\nabla\phi_j(\mathbf{x})^{\mathsf{T}}\mathbf{f}(\mathbf{x})\,\mathrm{d}\mathbf{x},\\
\mathbf{L} &\in\mathbb{R}^{n} \quad\text{with} \quad L_i = \int_{\Omega} \phi_i(\mathbf{x})\ell(\mathbf{x})\,\mathrm{d}\mathbf{x},\\
\mathbf{L}_{T} &\in\mathbb{R}^{n} \quad\text{with} \quad(\mathbf{L}_{T})_i = \int_{\Omega} \phi_i(\mathbf{x})\ell_T(\mathbf{x})\,\mathrm{d}\mathbf{x},\\
\mathbf{Q}(\mathbf{c}) &\in\mathbb{R}^{n} \quad\text{with} \quad Q_i(\mathbf{c}) = \int_{\Omega} \phi_i(\mathbf{x})\left\|\mathbf{q}(\mathbf{x})^{\mathsf{T}}\left(\sum_{j\in\Gamma}c_j\nabla\phi_j(\mathbf{x})\right)\right\|_2^2\,\mathrm{d}\mathbf{x}.
\end{aligned} M K L L T Q ( c ) ∈ R n × n with M ij = ∫ Ω ϕ i ( x ) ϕ j ( x ) d x , ∈ R n × n with K ij = ∫ Ω ϕ i ( x ) ∇ ϕ j ( x ) T f ( x ) d x , ∈ R n with L i = ∫ Ω ϕ i ( x ) ℓ ( x ) d x , ∈ R n with ( L T ) i = ∫ Ω ϕ i ( x ) ℓ T ( x ) d x , ∈ R n with Q i ( c ) = ∫ Ω ϕ i ( x ) q ( x ) T j ∈ Γ ∑ c j ∇ ϕ j ( x ) 2 2 d x .
Since ∂ t V ^ ( t , x ) = ∑ j ∈ Γ c ˙ j ( t ) ϕ j ( x ) \partial_t\widehat{V}(t,\mathbf{x})=\sum_{j\in\Gamma}\dot{c}_j(t)\phi_j(\mathbf{x}) ∂ t V ( t , x ) = ∑ j ∈ Γ c ˙ j ( t ) ϕ j ( x ) , we have
⟨ ∂ t V ^ , ϕ i ⟩ L 2 ( Ω ) = ∑ j ∈ Γ c ˙ j ( t ) ⟨ ϕ j , ϕ i ⟩ L 2 ( Ω ) = [ M c ˙ ( t ) ] i . \left\langle\partial_t\widehat{V},\phi_i\right\rangle_{L^2(\Omega)}
=\sum_{j\in\Gamma}\dot{c}_j(t)\left\langle\phi_j,\phi_i\right\rangle_{L^2(\Omega)}
=[\mathbf{M}\dot{\mathbf{c}}(t)]_i. ⟨ ∂ t V , ϕ i ⟩ L 2 ( Ω ) = j ∈ Γ ∑ c ˙ j ( t ) ⟨ ϕ j , ϕ i ⟩ L 2 ( Ω ) = [ M c ˙ ( t ) ] i .
Finally, we obtain the system
c ˙ ( t ) = M − 1 ( − K c ( t ) + 1 4 β Q ( c ( t ) ) − L ) . (9) \dot{\mathbf{c}}(t)=\mathbf{M}^{-1}\left(-\mathbf{K}\mathbf{c}(t)+\frac{1}{4\beta}\mathbf{Q}(\mathbf{c}(t))-\mathbf{L}\right). \tag*{(9)} c ˙ ( t ) = M − 1 ( − Kc ( t ) + 4 β 1 Q ( c ( t )) − L ) . (9)
We solve (9) backward in time on [ 0 , T ] [0,T] [ 0 , T ] with terminal condition M c ( T ) = L T \mathbf{M}\mathbf{c}(T)=\mathbf{L}_T Mc ( T ) = L T , i.e., V ^ ( T , ⋅ ) \widehat{V}(T,\cdot) V ( T , ⋅ ) is the L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) projection of ℓ T \ell_T ℓ T onto V n \mathcal{V}_n V n (in particular, c ( T ) = 0 \mathbf{c}(T)=0 c ( T ) = 0 when ℓ T ≡ 0 \ell_T\equiv0 ℓ T ≡ 0 ). Let F ( c ( t ) ) F(\mathbf{c}(t)) F ( c ( t )) denote the right-hand side of (9) . In an explicit Euler scheme for backward integration, we discretize [ 0 , T ] [0,T] [ 0 , T ] into N t N_t N t time steps of size Δ t = T / N t \Delta t=T/N_t Δ t = T / N t , and define the reversed time t n t = T − n t Δ t t_{n_t}=T-n_t\Delta t t n t = T − n t Δ t , where n t = 0 , … , N t n_t=0,\ldots,N_t n t = 0 , … , N t . Then, starting from c 0 = c ( T ) \mathbf{c}_0=\mathbf{c}(T) c 0 = c ( T ) , we update
c n t + 1 = c n t − Δ t F ( c n t ) , n t = 0 , … , N t − 1 , \mathbf{c}_{n_t+1}=\mathbf{c}_{n_t}-\Delta t\,F(\mathbf{c}_{n_t}),\qquad n_t=0,\ldots,N_t-1, c n t + 1 = c n t − Δ t F ( c n t ) , n t = 0 , … , N t − 1 ,
and the value function at time t = 0 t=0 t = 0 is approximated as
V ^ ( 0 , x ) ≈ ∑ j ∈ Γ c j ( 0 ) ϕ j ( x ) . \widehat{V}(0,\mathbf{x})\approx\sum_{j\in\Gamma}c_j(0)\phi_j(\mathbf{x}). V ( 0 , x ) ≈ j ∈ Γ ∑ c j ( 0 ) ϕ j ( x ) .
Data-driven schemes: supervised learning with gradient-augmented data
We consider a training dataset D = { ( x i , v i , g i ) } i = 1 N \mathcal{D}=\{(\mathbf{x}_i,v_i,\mathbf{g}_i)\}_{i=1}^{N} D = {( x i , v i , g i ) } i = 1 N and an active subset of the basis Φ Γ = { ϕ j } j ∈ Γ \Phi_{\Gamma}=\{\phi_j\}_{j\in\Gamma} Φ Γ = { ϕ j } j ∈ Γ , with ∣ Γ ∣ = n |\Gamma|=n ∣Γ∣ = n . For each sample x i \mathbf{x}_i x i , we define the feature row corresponding to function values as Φ Γ ( x i ) : = { ϕ j ( x i ) } j ∈ Γ ∈ R n \Phi_{\Gamma}(\mathbf{x}_i):=\{\phi_j(\mathbf{x}_i)\}_{j\in\Gamma}\in\mathbb{R}^{n} Φ Γ ( x i ) := { ϕ j ( x i ) } j ∈ Γ ∈ R n . For the gradient information, we define, for each coordinate k = 1 , … , d k=1,\ldots,d k = 1 , … , d ,
Φ Γ ( k ) ( x i ) : = { ∂ ϕ j ( x i ) ∂ x k } j ∈ Γ ∈ R n \Phi_{\Gamma}^{(k)}(\mathbf{x}_i):=\left\{\frac{\partial\phi_j(\mathbf{x}_i)}{\partial x_k}\right\}_{j\in\Gamma}\in\mathbb{R}^{n} Φ Γ ( k ) ( x i ) := { ∂ x k ∂ ϕ j ( x i ) } j ∈ Γ ∈ R n
and the full gradient feature matrix as
G ( x i ) = [ Φ Γ ( 1 ) ( x i ) Φ Γ ( 2 ) ( x i ) ⋮ Φ Γ ( d ) ( x i ) ] ∈ R d × n . \mathbf{G}(\mathbf{x}_i)=
\begin{bmatrix}
\Phi_{\Gamma}^{(1)}(\mathbf{x}_i)\\
\Phi_{\Gamma}^{(2)}(\mathbf{x}_i)\\
\vdots\\
\Phi_{\Gamma}^{(d)}(\mathbf{x}_i)
\end{bmatrix}
\in\mathbb{R}^{d\times n}. G ( x i ) = Φ Γ ( 1 ) ( x i ) Φ Γ ( 2 ) ( x i ) ⋮ Φ Γ ( d ) ( x i ) ∈ R d × n .
The complete feature matrix is then defined by
X = [ F ~ G ~ ] ∈ R N ( 1 + d ) × n , \mathbf{X}=\begin{bmatrix}\widetilde{\mathbf{F}}\\ \widetilde{\mathbf{G}}\end{bmatrix}\in\mathbb{R}^{N(1+d)\times n}, X = [ F G ] ∈ R N ( 1 + d ) × n ,
where
F ~ = [ Φ Γ ( x 1 ) Φ Γ ( x 2 ) ⋮ Φ Γ ( x N ) ] ∈ R N × n , G ~ = [ G ( x 1 ) G ( x 2 ) ⋮ G ( x N ) ] ∈ R N d × n . \widetilde{\mathbf{F}}=\begin{bmatrix}\Phi_{\Gamma}(\mathbf{x}_1)\\ \Phi_{\Gamma}(\mathbf{x}_2)\\ \vdots\\ \Phi_{\Gamma}(\mathbf{x}_N)\end{bmatrix}\in\mathbb{R}^{N\times n},\qquad\widetilde{\mathbf{G}}=\begin{bmatrix}\mathbf{G}(\mathbf{x}_1)\\ \mathbf{G}(\mathbf{x}_2)\\ \vdots\\ \mathbf{G}(\mathbf{x}_N)\end{bmatrix}\in\mathbb{R}^{Nd\times n}. F = Φ Γ ( x 1 ) Φ Γ ( x 2 ) ⋮ Φ Γ ( x N ) ∈ R N × n , G = G ( x 1 ) G ( x 2 ) ⋮ G ( x N ) ∈ R N d × n .
Similarly, the corresponding target vector b ∈ R N ( 1 + d ) \mathbf{b}\in\mathbb{R}^{N(1+d)} b ∈ R N ( 1 + d ) is constructed by concatenating the function values and gradients:
b = [ v g ] , v = ( v 1 , v 2 , ⋯ , v N ) T ∈ R N , g = ( g 1 T , ⋯ , g N T ) T ∈ R d N . \mathbf{b}=\begin{bmatrix}\mathbf{v}\\ \mathbf{g}\end{bmatrix},\qquad\mathbf{v}=(v_1,v_2,\cdots,v_N)^{\mathsf{T}}\in\mathbb{R}^{N},\qquad\mathbf{g}=\left(\mathbf{g}_1^{\mathsf{T}},\cdots,\mathbf{g}_N^{\mathsf{T}}\right)^{\mathsf{T}}\in\mathbb{R}^{dN}. b = [ v g ] , v = ( v 1 , v 2 , ⋯ , v N ) T ∈ R N , g = ( g 1 T , ⋯ , g N T ) T ∈ R d N .
The optimal coefficient vector c ∈ R n \mathbf{c}\in\mathbb{R}^{n} c ∈ R n is obtained by solving the following LASSO regression problem
c ∗ = argmin c ∈ R n { ∥ b − X c ∥ 2 2 + λ ∥ c ∥ 1 } , \mathbf{c}^{*}=\underset{\mathbf{c}\in\mathbb{R}^{n}}{\operatorname{argmin}}\left\{\lVert\mathbf{b}-\mathbf{X}\mathbf{c}\rVert_{2}^{2}+\lambda\lVert\mathbf{c}\rVert_{1}\right\}, c ∗ = c ∈ R n argmin { ∥ b − Xc ∥ 2 2 + λ ∥ c ∥ 1 } ,
where λ > 0 \lambda>0 λ > 0 is a regularization parameter that controls the sparsity in the solution.
Model-based adaptive basis selection
In this section, we develop a closed-form indicator that predicts the reduction in the PDE residual obtained by adding a single candidate basis function to the current approximation space. The indicator is inspired by the goal-oriented DWR framework for a suitable choice of QoI, while extending this idea to high-dimensional, mesh-free settings and bypassing any adjoint solve.
Recall that our goal is to solve (6) with an operator L : V → L 2 ( Ω ) \mathcal{L}:\mathcal{V}\to L^{2}(\Omega) L : V → L 2 ( Ω ) , where V \mathcal{V} V is a Hilbert space continuously embedded in H 1 ( Ω ) H^{1}(\Omega) H 1 ( Ω ) . For any g ∈ L 2 ( Ω ) g\in L^{2}(\Omega) g ∈ L 2 ( Ω ) and ϕ ∈ V \phi\in\mathcal{V} ϕ ∈ V , the embedding V ↪ L 2 ( Ω ) ↪ V ∗ \mathcal{V}\hookrightarrow L^{2}(\Omega)\hookrightarrow\mathcal{V}^{*} V ↪ L 2 ( Ω ) ↪ V ∗ allows us to identify the duality pairing ⟨ ⋅ , ⋅ ⟩ V ∗ , V \langle\cdot,\cdot\rangle_{\mathcal{V}^{*},\mathcal{V}} ⟨ ⋅ , ⋅ ⟩ V ∗ , V between V ∗ \mathcal{V}^{*} V ∗ and V \mathcal{V} V with the L 2 L^{2} L 2 inner product
⟨ g , ϕ ⟩ V ∗ , V : = ∫ Ω g ( x ) ϕ ( x ) d x = ⟨ g , ϕ ⟩ L 2 ( Ω ) . \langle g,\phi\rangle_{\mathcal{V}^{*},\mathcal{V}}:=\int_{\Omega}g(x)\phi(x)\,\mathrm{d}x=\langle g,\phi\rangle_{L^{2}(\Omega)}. ⟨ g , ϕ ⟩ V ∗ , V := ∫ Ω g ( x ) ϕ ( x ) d x = ⟨ g , ϕ ⟩ L 2 ( Ω ) .
At the k k k -th iteration, let V ^ ( k ) \widehat{V}^{(k)} V ( k ) denote the current approximation. We assume that (6) admits a solution V ∈ V V\in\mathcal{V} V ∈ V , which is fixed throughout as the target of the approximation, and that, for each iterate V ^ ( k ) \widehat{V}^{(k)} V ( k ) , the operator L \mathcal{L} L is Fréchet differentiable in an open neighborhood of V ^ ( k ) \widehat{V}^{(k)} V ( k ) . This differentiability is used only locally in the construction of the residual-based indicator below.
Index-set partition. At the k k k -th iteration, the prescribed basis pool Φ Θ \Phi_{\Theta} Φ Θ is partitioned as
Φ Θ ( x ) = Φ Γ ( k ) ( x ) ∪ Φ Λ ( k ) ( x ) , Γ ( k ) ∩ Λ ( k ) = ∅ , \Phi_{\Theta}(\mathbf{x})=\Phi_{\Gamma^{(k)}}(\mathbf{x})\cup\Phi_{\Lambda^{(k)}}(\mathbf{x}),\qquad\Gamma^{(k)}\cap\Lambda^{(k)}=\varnothing, Φ Θ ( x ) = Φ Γ ( k ) ( x ) ∪ Φ Λ ( k ) ( x ) , Γ ( k ) ∩ Λ ( k ) = ∅ ,
where Γ ( k ) ⊂ Θ \Gamma^{(k)}\subset\Theta Γ ( k ) ⊂ Θ denotes the index set of selected basis functions, n k : = ∣ Γ ( k ) ∣ n_k:=\lvert\Gamma^{(k)}\rvert n k := ∣ Γ ( k ) ∣ , and Λ ( k ) = Θ \ Γ ( k ) \Lambda^{(k)}=\Theta\backslash\Gamma^{(k)} Λ ( k ) = Θ\ Γ ( k ) is the index set of remaining candidates. We construct V ^ ( k + 1 ) \widehat{V}^{(k+1)} V ( k + 1 ) by greedily selecting a single basis function from the remaining candidates Λ ( k ) \Lambda^{(k)} Λ ( k ) and adding it to the active set Γ ( k ) \Gamma^{(k)} Γ ( k ) .
Given Γ ( k ) \Gamma^{(k)} Γ ( k ) , let V n k : = span { ϕ j : j ∈ Γ ( k ) } ⊂ V \mathcal{V}_{n_k}:=\operatorname{span}\{\phi_j:j\in\Gamma^{(k)}\}\subset\mathcal{V} V n k := span { ϕ j : j ∈ Γ ( k ) } ⊂ V and let V ^ ( k ) ∈ V n k \widehat{V}^{(k)}\in\mathcal{V}_{n_k} V ( k ) ∈ V n k be the current approximation. We define the PDE residual
R ( V ^ ( k ) ) : = L ( V ^ ( k ) ) ∈ L 2 ( Ω ) . (10) R\left(\widehat{V}^{(k)}\right):=\mathcal{L}\left(\widehat{V}^{(k)}\right)\in L^{2}(\Omega). \tag*{(10)} R ( V ( k ) ) := L ( V ( k ) ) ∈ L 2 ( Ω ) . (10)
Since L \mathcal{L} L is Fréchet differentiable at V ^ ( k ) \widehat{V}^{(k)} V ( k ) , its derivative L k : = D L ( V ^ ( k ) ) : V → L 2 ( Ω ) \mathcal{L}_k := D\mathcal{L}\left(\widehat{V}^{(k)}\right) : \mathcal{V} \to L^2(\Omega) L k := D L ( V ( k ) ) : V → L 2 ( Ω ) is a bounded linear operator. In particular, for all ψ ∈ V \psi\in\mathcal{V} ψ ∈ V , the directional derivative
D L ( V ^ ( k ) ) [ ψ ] = lim ε → 0 L ( V ^ ( k ) + ε ψ ) − L ( V ^ ( k ) ) ε D\mathcal{L}\left(\widehat{V}^{(k)}\right)[\psi] = \lim_{\varepsilon\to0} \frac{\mathcal{L}\left(\widehat{V}^{(k)}+\varepsilon\psi\right)-\mathcal{L}\left(\widehat{V}^{(k)}\right)}{\varepsilon} D L ( V ( k ) ) [ ψ ] = ε → 0 lim ε L ( V ( k ) + ε ψ ) − L ( V ( k ) )
exists and satisfies D L ( V ^ ( k ) ) [ ψ ] = L k ψ D\mathcal{L}\left(\widehat{V}^{(k)}\right)[\psi] = \mathcal{L}_k\psi D L ( V ( k ) ) [ ψ ] = L k ψ . Its adjoint L k ∗ : L 2 ( Ω ) → V ∗ \mathcal{L}_k^*: L^2(\Omega) \to\mathcal{V}^* L k ∗ : L 2 ( Ω ) → V ∗ is characterized by
⟨ L k ∗ w , v ⟩ V ∗ , V = ⟨ w , L k v ⟩ L 2 ( Ω ) , ∀ v ∈ V , w ∈ L 2 ( Ω ) . \left\langle\mathcal{L}_k^*w,v\right\rangle_{\mathcal{V}^*,\mathcal{V}} = \left\langle w,\mathcal{L}_kv\right\rangle_{L^2(\Omega)}, \qquad\forall v \in\mathcal{V},\ w \in L^2(\Omega). ⟨ L k ∗ w , v ⟩ V ∗ , V = ⟨ w , L k v ⟩ L 2 ( Ω ) , ∀ v ∈ V , w ∈ L 2 ( Ω ) .
Standard dual-weighted residual method
We first briefly recall the standard dual-weighted residual (DWR) method [3 ] , in which the error in a target quantity of interest (QoI) is approximated by weighting the primal residual with the solution of a linearized adjoint equation [7 Section 3.1] . This provides the conceptual starting point for our indicator. In the following, we replace the expensive adjoint solve with a computable projection tailored to adaptive basis selection.
We reformulate (6) as a PDE-constrained optimization problem
min V ∈ V Q ( V ) subject to L ( V ) = 0 , (11) \min_{V \in\mathcal{V}} Q(V) \quad\text{subject to} \quad\mathcal{L}(V)=0, \tag*{(11)} V ∈ V min Q ( V ) subject to L ( V ) = 0 , (11)
where Q : V → R Q:\mathcal{V}\to\mathbb{R} Q : V → R is a Fréchet differentiable functional that specifies the QoI but does not affect the PDE solution. The associated Lagrangian is defined by
L ( V , p ) : = Q ( V ) + ⟨ p , L ( V ) ⟩ L 2 ( Ω ) , \mathscr{L}(V,p) := Q(V) + \left\langle p,\mathcal{L}(V)\right\rangle_{L^2(\Omega)}, L ( V , p ) := Q ( V ) + ⟨ p , L ( V ) ⟩ L 2 ( Ω ) ,
with adjoint variable p ∈ L 2 ( Ω ) p \in L^2(\Omega) p ∈ L 2 ( Ω ) . First-order optimality conditions yield the adjoint equation
Q ′ ( V ) + D L ( V ) ∗ [ p ] = 0 in V ∗ . (12) Q'(V) + D\mathcal{L}(V)^*[p] = 0 \quad\text{in } \mathcal{V}^*. \tag*{(12)} Q ′ ( V ) + D L ( V ) ∗ [ p ] = 0 in V ∗ . (12)
At the current iterate we use the adjoint equation linearized at V ^ ( k ) \widehat{V}^{(k)} V ( k ) : let p k ∈ L 2 ( Ω ) p_k \in L^2(\Omega) p k ∈ L 2 ( Ω ) satisfy
L k ∗ p k = − Q ′ ( V ^ ( k ) ) in V ∗ . (13) \mathcal{L}_k^*p_k = -Q'\left(\widehat{V}^{(k)}\right) \quad\text{in } \mathcal{V}^*. \tag*{(13)} L k ∗ p k = − Q ′ ( V ( k ) ) in V ∗ . (13)
We denote by
r L ( h ) : = L ( V ^ ( k ) + h ) − L ( V ^ ( k ) ) − L k h , r_{\mathcal{L}}(h) := \mathcal{L}\left(\widehat{V}^{(k)}+h\right)-\mathcal{L}\left(\widehat{V}^{(k)}\right)-\mathcal{L}_kh, r L ( h ) := L ( V ( k ) + h ) − L ( V ( k ) ) − L k h ,
r Q ( h ) : = Q ( V ^ ( k ) + h ) − Q ( V ^ ( k ) ) − ⟨ Q ′ ( V ^ ( k ) ) , h ⟩ V ∗ , V , r_Q(h) := Q\left(\widehat{V}^{(k)}+h\right)-Q\left(\widehat{V}^{(k)}\right)-\left\langle Q'\left(\widehat{V}^{(k)}\right),h\right\rangle_{\mathcal{V}^*,\mathcal{V}}, r Q ( h ) := Q ( V ( k ) + h ) − Q ( V ( k ) ) − ⟨ Q ′ ( V ( k ) ) , h ⟩ V ∗ , V ,
the first-order Taylor remainders of L \mathcal{L} L and Q Q Q at V ^ ( k ) \widehat{V}^{(k)} V ( k ) , so that ∥ r L ( h ) ∥ L 2 ( Ω ) = o ( ∥ h ∥ V ) \lVert r_{\mathcal{L}}(h)\rVert_{L^2(\Omega)}=o(\lVert h\rVert_{\mathcal{V}}) ∥ r L ( h ) ∥ L 2 ( Ω ) = o (∥ h ∥ V ) and r Q ( h ) = o ( ∥ h ∥ V ) r_Q(h)=o(\lVert h\rVert_{\mathcal{V}}) r Q ( h ) = o (∥ h ∥ V ) as h → 0 h\to0 h → 0 in V \mathcal{V} V . The following lemma is the error representation underlying the DWR method.
Lemma 4.1 (DWR error representation). Let V ∈ V V\in\mathcal{V} V ∈ V solve (6) , let p k ∈ L 2 ( Ω ) p_k\in L^2(\Omega) p k ∈ L 2 ( Ω ) satisfy (13) , and set δ V : = V − V ^ ( k ) \delta V:=V-\widehat{V}^{(k)} δ V := V − V ( k ) . Then
Q ( V ) − Q ( V ^ ( k ) ) = ⟨ R ( V ^ ( k ) ) , p k ⟩ L 2 ( Ω ) + r Q ( δ V ) + ⟨ p k , r L ( δ V ) ⟩ L 2 ( Ω ) . (14) Q(V)-Q\left(\widehat{V}^{(k)}\right)=\left\langle R\left(\widehat{V}^{(k)}\right),p_k\right\rangle_{L^2(\Omega)}
+r_Q(\delta V)+\left\langle p_k,r_{\mathcal{L}}(\delta V)\right\rangle_{L^2(\Omega)}. \tag*{(14)} Q ( V ) − Q ( V ( k ) ) = ⟨ R ( V ( k ) ) , p k ⟩ L 2 ( Ω ) + r Q ( δ V ) + ⟨ p k , r L ( δ V ) ⟩ L 2 ( Ω ) . (14) In particular, the last two terms are o ( ∥ δ V ∥ V ) o(\lVert\delta V\rVert_{\mathcal{V}}) o (∥ δ V ∥ V ) , and they vanish if L \mathcal{L} L is affine and Q Q Q is linear.
Proof. Since L ( V ) = 0 \mathcal{L}(V)=0 L ( V ) = 0 , the definition of r L r_{\mathcal{L}} r L with h = δ V h=\delta V h = δ V gives L k δ V = − R ( V ^ ( k ) ) − r L ( δ V ) \mathcal{L}_k\delta V=-R(\widehat{V}^{(k)})-r_{\mathcal{L}}(\delta V) L k δ V = − R ( V ( k ) ) − r L ( δ V ) . Using the definition of r Q r_Q r Q , the adjoint equation (13) and the definition of L k ∗ \mathcal{L}_k^* L k ∗ , we obtain
Q ( V ) − Q ( V ^ ( k ) ) = ⟨ Q ′ ( V ^ ( k ) ) , δ V ⟩ V ∗ , V + r Q ( δ V ) = − ⟨ p k , L k δ V ⟩ L 2 ( Ω ) + r Q ( δ V ) = ⟨ p k , R ( V ^ ( k ) ) ⟩ L 2 ( Ω ) + ⟨ p k , r L ( δ V ) ⟩ L 2 ( Ω ) + r Q ( δ V ) . \begin{aligned}
Q(V)-Q(\widehat{V}^{(k)})&=\langle Q'(\widehat{V}^{(k)}),\delta V\rangle_{\mathcal{V}^*,\mathcal{V}}+r_Q(\delta V)\\
&=-\langle p_k,\mathcal{L}_k\delta V\rangle_{L^2(\Omega)}+r_Q(\delta V)\\
&=\langle p_k,R(\widehat{V}^{(k)})\rangle_{L^2(\Omega)}+\langle p_k,r_{\mathcal{L}}(\delta V)\rangle_{L^2(\Omega)}+r_Q(\delta V).
\end{aligned} Q ( V ) − Q ( V ( k ) ) = ⟨ Q ′ ( V ( k ) ) , δ V ⟩ V ∗ , V + r Q ( δ V ) = − ⟨ p k , L k δ V ⟩ L 2 ( Ω ) + r Q ( δ V ) = ⟨ p k , R ( V ( k ) ) ⟩ L 2 ( Ω ) + ⟨ p k , r L ( δ V ) ⟩ L 2 ( Ω ) + r Q ( δ V ) .
The final assertion follows from the bounds on r L r_{\mathcal{L}} r L and r Q r_Q r Q and the Cauchy–Schwarz inequality.
The leading term ⟨ R ( V ^ ( k ) ) , p k ⟩ L 2 ( Ω ) \langle R(\widehat{V}^{(k)}),p_k\rangle_{L^2(\Omega)} ⟨ R ( V ( k ) ) , p k ⟩ L 2 ( Ω ) in (14) is the standard goal-oriented DWR error estimate [3 , 55 ] . The adjoint p k p_k p k serves as a sensitivity kernel, quantifying the influence of the residual R ( V ^ ( k ) ) R(\widehat{V}^{(k)}) R ( V ( k ) ) on the functional error Q ( V ) − Q ( V ^ ( k ) ) Q(V)-Q(\widehat{V}^{(k)}) Q ( V ) − Q ( V ( k ) ) .
In the following, we introduce a computable indicator by projecting the adjoint p k p_k p k onto the linearized image of candidate directions.
Single-direction projected DWR indicator
Given Γ ( k ) \Gamma^{(k)} Γ ( k ) and V ^ ( k ) ∈ V n k \widehat{V}^{(k)}\in\mathcal{V}_{n_k} V ( k ) ∈ V n k , define V Λ ( k ) : = span { ϕ j : j ∈ Λ ( k ) } ⊂ V \mathcal{V}_{\Lambda^{(k)}}:=\operatorname{span}\{\phi_j:j\in\Lambda^{(k)}\}\subset\mathcal{V} V Λ ( k ) := span { ϕ j : j ∈ Λ ( k ) } ⊂ V and its linearized image
W Λ ( k ) : = span { w j : = L k ϕ j : j ∈ Λ ( k ) } ⊂ L 2 ( Ω ) . \mathcal{W}_{\Lambda^{(k)}}:=\operatorname{span}\{w_j:=\mathcal{L}_k\phi_j:j\in\Lambda^{(k)}\}\subset L^2(\Omega). W Λ ( k ) := span { w j := L k ϕ j : j ∈ Λ ( k ) } ⊂ L 2 ( Ω ) .
We project p k p_k p k onto the linearized image span { w j } ⊂ W Λ ( k ) \operatorname{span}\{w_j\}\subset\mathcal{W}_{\Lambda^{(k)}} span { w j } ⊂ W Λ ( k ) of a single candidate direction ϕ j \phi_j ϕ j . The next lemma shows that this projection can be computed without solving the adjoint equation.
Lemma 4.2 (Projected adjoint). Let j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) with w j = L k ϕ j ≠ 0 w_j=\mathcal{L}_k\phi_j\ne0 w j = L k ϕ j = 0 , and let p k ∈ L 2 ( Ω ) p_k\in L^2(\Omega) p k ∈ L 2 ( Ω ) satisfy (13) . Then the L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) -orthogonal projection of p k p_k p k onto span { w j } \operatorname{span}\{w_j\} span { w j } is
p k p r o j , j = ⟨ − Q ′ ( V ^ ( k ) ) , ϕ j ⟩ V ∗ , V ∥ w j ∥ L 2 ( Ω ) 2 w j . (15) p_k^{\mathrm{proj},j}=\frac{\langle-Q'(\widehat{V}^{(k)}),\phi_j\rangle_{\mathcal{V}^*,\mathcal{V}}}{\lVert w_j\rVert_{L^2(\Omega)}^2}w_j. \tag*{(15)} p k proj , j = ∥ w j ∥ L 2 ( Ω ) 2 ⟨ − Q ′ ( V ( k ) ) , ϕ j ⟩ V ∗ , V w j . (15)
Proof. In this proof, ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ denote the inner product and norm of L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) . The orthogonal projection onto span { w j } \operatorname{span}\{w_j\} span { w j } maps p p p to ⟨ p , w j ⟩ ∥ w j ∥ − 2 w j \langle p,w_j\rangle\lVert w_j\rVert^{-2}w_j ⟨ p , w j ⟩ ∥ w j ∥ − 2 w j . By the definition of L k ∗ \mathcal{L}_k^* L k ∗ and (13) ,
⟨ p k , w j ⟩ = ⟨ p k , L k ϕ j ⟩ = ⟨ L k ∗ p k , ϕ j ⟩ V ∗ , V = ⟨ − Q ′ ( V ^ ( k ) ) , ϕ j ⟩ V ∗ , V . \langle p_k,w_j\rangle=\langle p_k,\mathcal{L}_k\phi_j\rangle=\langle\mathcal{L}_k^*p_k,\phi_j\rangle_{\mathcal{V}^*,\mathcal{V}}=\langle-Q'(\widehat{V}^{(k)}),\phi_j\rangle_{\mathcal{V}^*,\mathcal{V}}. ⟨ p k , w j ⟩ = ⟨ p k , L k ϕ j ⟩ = ⟨ L k ∗ p k , ϕ j ⟩ V ∗ , V = ⟨ − Q ′ ( V ( k ) ) , ϕ j ⟩ V ∗ , V .
Replacing p k p_k p k with p k p r o j , j p_k^{\mathrm{proj},j} p k proj , j in the leading term of (14) gives the single-direction projected DWR indicator
E j p r o j : = ⟨ R ( V ^ ( k ) ) , p k p r o j , j ⟩ L 2 ( Ω ) = ⟨ − Q ′ ( V ^ ( k ) ) , ϕ j ⟩ V ∗ , V ⟨ R ( V ^ ( k ) ) , w j ⟩ L 2 ( Ω ) ∥ w j ∥ L 2 ( Ω ) 2 . (16) \mathcal{E}_j^{\mathrm{proj}}:=\langle R(\widehat{V}^{(k)}),p_k^{\mathrm{proj},j}\rangle_{L^2(\Omega)}=\frac{\langle-Q'(\widehat{V}^{(k)}),\phi_j\rangle_{\mathcal{V}^*,\mathcal{V}}\langle R(\widehat{V}^{(k)}),w_j\rangle_{L^2(\Omega)}}{\lVert w_j\rVert_{L^2(\Omega)}^2}. \tag*{(16)} E j proj := ⟨ R ( V ( k ) ) , p k proj , j ⟩ L 2 ( Ω ) = ∥ w j ∥ L 2 ( Ω ) 2 ⟨ − Q ′ ( V ( k ) ) , ϕ j ⟩ V ∗ , V ⟨ R ( V ( k ) ) , w j ⟩ L 2 ( Ω ) . (16)
This provides an adjoint-free, closed-form directional indicator predicting the first-order change in Q Q Q along the candidate direction ϕ j \phi_j ϕ j . It is, however, not intended to provide an accurate approximation of Q ( V ) − Q ( V ^ ( k ) ) Q(V)-Q(\widehat{V}^{(k)}) Q ( V ) − Q ( V ( k ) ) , but rather as an easy-to-compute score for selecting the next active basis function.
Residual-decay indicator
We now focus on the choice Q ( V ) : = 1 2 ∥ L ( V ) ∥ L 2 ( Ω ) 2 Q(V) := \frac{1}{2}\|\mathcal{L}(V)\|_{L^2(\Omega)}^2 Q ( V ) := 2 1 ∥ L ( V ) ∥ L 2 ( Ω ) 2 , which leads to the following indicator.
Definition 4.3 (Residual-decay indicator). Let V ^ ( k ) ∈ V n k \widehat{V}^{(k)} \in\mathbb{V}_{n_k} V ( k ) ∈ V n k , L k : = D L ( V ^ ( k ) ) \mathcal{L}_k := D\mathcal{L}(\widehat{V}^{(k)}) L k := D L ( V ( k ) ) and residual R ( V ^ ( k ) ) : = L ( V ^ ( k ) ) R(\widehat{V}^{(k)}) := \mathcal{L}(\widehat{V}^{(k)}) R ( V ( k ) ) := L ( V ( k ) ) . For each candidate ϕ j \phi_j ϕ j , j ∈ Λ ( k ) j \in\Lambda^{(k)} j ∈ Λ ( k ) , the residual-decay indicator is given by
e j , P D E ( k ) : = ∣ ⟨ R ( V ^ ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) ∣ ∥ L k ϕ j ∥ L 2 ( Ω ) . (17) e_{j,\mathrm{PDE}}^{(k)} := \frac{\left|\left\langle R(\widehat{V}^{(k)}),\mathcal{L}_k\phi_j\right\rangle_{L^2(\Omega)}\right|}{\|\mathcal{L}_k\phi_j\|_{L^2(\Omega)}}. \tag*{(17)} e j , PDE ( k ) := ∥ L k ϕ j ∥ L 2 ( Ω ) ⟨ R ( V ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) . (17) We set e j , P D E ( k ) = 0 e_{j,\mathrm{PDE}}^{(k)} = 0 e j , PDE ( k ) = 0 whenever ∥ L k ϕ j ∥ L 2 ( Ω ) = 0 \|\mathcal{L}_k\phi_j\|_{L^2(\Omega)} = 0 ∥ L k ϕ j ∥ L 2 ( Ω ) = 0 .
To interpret the indicator, consider for each j ∈ Λ ( k ) j \in\Lambda^{(k)} j ∈ Λ ( k ) the single-basis enrichment V ^ ( k ) + α ϕ j \widehat{V}^{(k)} + \alpha\phi_j V ( k ) + α ϕ j , α ∈ R \alpha\in\mathbb{R} α ∈ R , and the quadratic model of the residual functional obtained by linearizing L \mathcal{L} L at V ^ ( k ) \widehat{V}^{(k)} V ( k ) ,
m j ( α ) : = 1 2 ∥ R ( V ^ ( k ) ) + α L k ϕ j ∥ L 2 ( Ω ) 2 , α ∈ R . (18) m_j(\alpha) := \frac{1}{2}\left\|R(\widehat{V}^{(k)})+\alpha\mathcal{L}_k\phi_j\right\|_{L^2(\Omega)}^2,\qquad\alpha\in\mathbb{R}. \tag*{(18)} m j ( α ) := 2 1 R ( V ( k ) ) + α L k ϕ j L 2 ( Ω ) 2 , α ∈ R . (18)
The next proposition shows that e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) is, up to sign and a square, the projected DWR indicator (16) , and that it measures the largest reduction of the model m j m_j m j achievable along ϕ j \phi_j ϕ j .
Proposition 4.4 (Residual-decay indicator as predicted reduction). Let Q ( V ) = 1 2 ∥ L ( V ) ∥ L 2 ( Ω ) 2 Q(V)=\frac{1}{2}\|\mathcal{L}(V)\|_{L^2(\Omega)}^2 Q ( V ) = 2 1 ∥ L ( V ) ∥ L 2 ( Ω ) 2 and let j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) with L k ϕ j ≠ 0 \mathcal{L}_k\phi_j\ne0 L k ϕ j = 0 . Then the following hold.
(i) E j p r o j = − ( e j , P D E ( k ) ) 2 E_j^{\mathrm{proj}}=-\left(e_{j,\mathrm{PDE}}^{(k)}\right)^2 E j proj = − ( e j , PDE ( k ) ) 2 .
(ii) Q ( V ^ ( k ) + α ϕ j ) = m j ( α ) + o ( ∣ α ∣ ) Q(\widehat{V}^{(k)}+\alpha\phi_j)=m_j(\alpha)+o(|\alpha|) Q ( V ( k ) + α ϕ j ) = m j ( α ) + o ( ∣ α ∣ ) as α → 0 \alpha\to0 α → 0 .
(iii) The model m j m_j m j has the unique minimizer
α j ∗ = − ⟨ R ( V ^ ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) ∥ L k ϕ j ∥ L 2 ( Ω ) 2 , \alpha_j^*=-\frac{\left\langle R(\widehat{V}^{(k)}),\mathcal{L}_k\phi_j\right\rangle_{L^2(\Omega)}}{\|\mathcal{L}_k\phi_j\|_{L^2(\Omega)}^2}, α j ∗ = − ∥ L k ϕ j ∥ L 2 ( Ω ) 2 ⟨ R ( V ( k ) ) , L k ϕ j ⟩ L 2 ( Ω ) , and Q ( V ^ ( k ) ) − m j ( α j ∗ ) = 1 2 ( e j , P D E ( k ) ) 2 Q(\widehat{V}^{(k)})-m_j(\alpha_j^*)=\frac{1}{2}\left(e_{j,\mathrm{PDE}}^{(k)}\right)^2 Q ( V ( k ) ) − m j ( α j ∗ ) = 2 1 ( e j , PDE ( k ) ) 2 .
(iv) e j , P D E ( k ) = ∥ Π j R ( V ^ ( k ) ) ∥ L 2 ( Ω ) e_{j,\mathrm{PDE}}^{(k)}=\|\Pi_jR(\widehat{V}^{(k)})\|_{L^2(\Omega)} e j , PDE ( k ) = ∥ Π j R ( V ( k ) ) ∥ L 2 ( Ω ) , where Π j \Pi_j Π j denotes the L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) -orthogonal projection onto span { L k ϕ j } \operatorname{span}\{\mathcal{L}_k\phi_j\} span { L k ϕ j } . In particular, e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) is unchanged if ϕ j \phi_j ϕ j is replaced by s ϕ j s\phi_j s ϕ j with s ≠ 0 s\ne0 s = 0 .
Proof. Write R : = R ( V ^ ( k ) ) R:=R(\widehat{V}^{(k)}) R := R ( V ( k ) ) and w j : = L k ϕ j w_j:=\mathcal{L}_k\phi_j w j := L k ϕ j , and let ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ denote the inner product and norm of L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) .
(i) By the chain rule, ⟨ Q ′ ( V ^ ( k ) ) , ψ ⟩ V ∗ , V = ⟨ R , L k ψ ⟩ \langle Q'(\widehat{V}^{(k)}),\psi\rangle_{\mathbb{V}^*,\mathbb{V}}=\langle R,\mathcal{L}_k\psi\rangle ⟨ Q ′ ( V ( k ) ) , ψ ⟩ V ∗ , V = ⟨ R , L k ψ ⟩ for all ψ ∈ V \psi\in\mathbb{V} ψ ∈ V . Taking ψ = ϕ j \psi=\phi_j ψ = ϕ j in (16) gives E j p r o j = − ⟨ R , w j ⟩ 2 / ∥ w j ∥ 2 E_j^{\mathrm{proj}}=-\langle R,w_j\rangle^2/\|w_j\|^2 E j proj = − ⟨ R , w j ⟩ 2 /∥ w j ∥ 2 .
(ii) With the remainder r L r_{\mathcal{L}} r L introduced before Lemma 4.1 , L ( V ^ ( k ) + α ϕ j ) = R + α w j + r L ( α ϕ j ) \mathcal{L}(\widehat{V}^{(k)}+\alpha\phi_j)=R+\alpha w_j+r_{\mathcal{L}}(\alpha\phi_j) L ( V ( k ) + α ϕ j ) = R + α w j + r L ( α ϕ j ) , hence
Q ( V ^ ( k ) + α ϕ j ) − m j ( α ) = ⟨ R + α w j , r L ( α ϕ j ) ⟩ + 1 2 ∥ r L ( α ϕ j ) ∥ 2 . Q(\widehat{V}^{(k)}+\alpha\phi_j)-m_j(\alpha)=\left\langle R+\alpha w_j,r_{\mathcal{L}}(\alpha\phi_j)\right\rangle+\frac{1}{2}\|r_{\mathcal{L}}(\alpha\phi_j)\|^2. Q ( V ( k ) + α ϕ j ) − m j ( α ) = ⟨ R + α w j , r L ( α ϕ j ) ⟩ + 2 1 ∥ r L ( α ϕ j ) ∥ 2 .
Since ∥ r L ( α ϕ j ) ∥ = o ( ∣ α ∣ ∥ ϕ j ∥ V ) \|r_{\mathcal{L}}(\alpha\phi_j)\|=o(|\alpha|\|\phi_j\|_{\mathbb{V}}) ∥ r L ( α ϕ j ) ∥ = o ( ∣ α ∣∥ ϕ j ∥ V ) , the right-hand side is o ( ∣ α ∣ ) o(|\alpha|) o ( ∣ α ∣ ) .
(iii) Expanding the square, m j ( α ) = 1 2 ∥ R ∥ 2 + α ⟨ R , w j ⟩ + 1 2 α 2 ∥ w j ∥ 2 m_j(\alpha)=\frac{1}{2}\|R\|^2+\alpha\langle R,w_j\rangle+\frac{1}{2}\alpha^2\|w_j\|^2 m j ( α ) = 2 1 ∥ R ∥ 2 + α ⟨ R , w j ⟩ + 2 1 α 2 ∥ w j ∥ 2 , a strictly convex quadratic since w j ≠ 0 w_j\ne0 w j = 0 . Its derivative vanishes only at α j ∗ \alpha_j^* α j ∗ , and substitution gives m j ( α j ∗ ) = 1 2 ∥ R ∥ 2 − 1 2 ⟨ R , w j ⟩ 2 / ∥ w j ∥ 2 m_j(\alpha_j^*)=\frac{1}{2}\|R\|^2-\frac{1}{2}\langle R,w_j\rangle^2/\|w_j\|^2 m j ( α j ∗ ) = 2 1 ∥ R ∥ 2 − 2 1 ⟨ R , w j ⟩ 2 /∥ w j ∥ 2 . The claim follows from m j ( 0 ) = Q ( V ^ ( k ) ) m_j(0)=Q(\widehat{V}^{(k)}) m j ( 0 ) = Q ( V ( k ) ) .
(iv) We have Π j R = ⟨ R , w j ⟩ ∥ w j ∥ − 2 w j \Pi_jR=\langle R,w_j\rangle\|w_j\|^{-2}w_j Π j R = ⟨ R , w j ⟩ ∥ w j ∥ − 2 w j , whose norm is e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) . Since L k \mathcal{L}_k L k is linear, replacing ϕ j \phi_j ϕ j by s ϕ j s\phi_j s ϕ j replaces w j w_j w j by s w j sw_j s w j , which leaves span { w j } \operatorname{span}\{w_j\} span { w j } and hence Π j \Pi_j Π j unchanged. □
By Proposition 4.4 (iii), selecting ϕ j \phi_j ϕ j with the largest value of e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) maximizes the reduction of the residual functional Q \mathcal{Q} Q predicted by the linearized model m j m_j m j . Part (ii) only shows that m j m_j m j is accurate to first order in α \alpha α ; the indicator is therefore a ranking criterion rather than a guaranteed decrease of Q \mathcal{Q} Q .
Greedy selection of basis. At the k k k -th iteration, among all candidates { ϕ j : j ∈ Λ ( k ) } \{\phi_j:j\in\Lambda^{(k)}\} { ϕ j : j ∈ Λ ( k ) } , the next basis function is then chosen as
j ∗ : = argmax j ∈ Λ ( k ) e j , P D E ( k ) . j^* := \underset{j\in\Lambda^{(k)}}{\operatorname{argmax}}\ e_{j,\mathrm{PDE}}^{(k)}. j ∗ := j ∈ Λ ( k ) argmax e j , PDE ( k ) .
The active and candidate index sets are then updated as
Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ } . \Gamma^{(k+1)}=\Gamma^{(k)}\cup\{j^*\},\qquad\Lambda^{(k+1)}=\Lambda^{(k)}\setminus\{j^*\}. Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ } .
In practice, after adding a new basis function ϕ j ∗ \phi_{j^*} ϕ j ∗ , we re-optimize all coefficients over V n k + 1 \mathcal{V}_{n_{k+1}} V n k + 1 , so that V ^ ( k + 1 ) \widehat{V}^{(k+1)} V ( k + 1 ) is not exactly V ^ ( k ) + α j ∗ ∗ ϕ j ∗ \widehat{V}^{(k)}+\alpha_{j^*}^*\phi_{j^*} V ( k ) + α j ∗ ∗ ϕ j ∗ . Nevertheless, by Proposition 4.4 (iv), e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) is the L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) -norm of the projection of the current residual onto the one-dimensional space spanned by L k ϕ j \mathcal{L}_k\phi_j L k ϕ j . It therefore selects the candidate whose linearized image L k ϕ j \mathcal{L}_k\phi_j L k ϕ j captures the largest component of the current residual, providing an effectively computable indicator for basis selection.
The stationary HJB equation
We apply the residual-decay indicator settings to the stationary HJB equation (2) associated with the infinite-horizon problem (1) . Since the basis functions depend only on the state, and the finite-horizon value function at t = 0 t=0 t = 0 approximates the stationary one for large T T T (§ 2 ), we score candidate basis functions with the stationary HJB residual. By the Dynamic Programming Principle, the optimal feedback control is given by
u ∗ ( x ) = − 1 2 β q ( x ) T ∇ V ( x ) . \mathbf{u}^*(\mathbf{x})=-\frac{1}{2\beta}\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla V(\mathbf{x}). u ∗ ( x ) = − 2 β 1 q ( x ) T ∇ V ( x ) .
Substituting u ∗ \mathbf{u}^* u ∗ into (2) gives the stationary HJB operator L H J B : V → L 2 ( Ω ) \mathcal{L}_{\mathrm{HJB}}:\mathcal{V}\to L^2(\Omega) L HJB : V → L 2 ( Ω ) :
( L H J B V ) ( x ) : = − 1 4 β ∇ V ( x ) T q ( x ) q ( x ) T ∇ V ( x ) + ∇ V ( x ) T f ( x ) + ℓ ( x ) , (19) (\mathcal{L}_{\mathrm{HJB}}V)(\mathbf{x}):=-\frac{1}{4\beta}\nabla V(\mathbf{x})^{\mathsf{T}}\mathbf{q}(\mathbf{x})\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla V(\mathbf{x})+\nabla V(\mathbf{x})^{\mathsf{T}}\mathbf{f}(\mathbf{x})+\ell(\mathbf{x}), \tag*{(19)} ( L HJB V ) ( x ) := − 4 β 1 ∇ V ( x ) T q ( x ) q ( x ) T ∇ V ( x ) + ∇ V ( x ) T f ( x ) + ℓ ( x ) , (19)
for any x ∈ Ω \mathbf{x}\in\Omega x ∈ Ω . Let V ^ ( k ) ∈ V n k \widehat{V}^{(k)}\in\mathcal{V}_{n_k} V ( k ) ∈ V n k denote the k k k -th approximation of the value function, with index set Γ ( k ) \Gamma^{(k)} Γ ( k ) satisfying ∣ Γ ( k ) ∣ = n k |\Gamma^{(k)}|=n_k ∣ Γ ( k ) ∣ = n k . The associated HJB residual is defined as R ( V ^ ( k ) ) ( x ) : = ( L H J B V ^ ( k ) ) ( x ) R(\widehat{V}^{(k)})(\mathbf{x}):=(\mathcal{L}_{\mathrm{HJB}}\widehat{V}^{(k)})(\mathbf{x}) R ( V ( k ) ) ( x ) := ( L HJB V ( k ) ) ( x ) . Since L H J B \mathcal{L}_{\mathrm{HJB}} L HJB is quadratic in ∇ V \nabla V ∇ V , its expansion around V ^ ( k ) \widehat{V}^{(k)} V ( k ) terminates at second order. This gives the linearized operator explicitly.
Lemma 4.5 (Linearization of the HJB operator). Let V ^ ( k ) ∈ V n k \widehat{V}^{(k)}\in\mathcal{V}_{n_k} V ( k ) ∈ V n k and a k ( x ) : = f ( x ) − 1 2 β q ( x ) q ( x ) T ∇ V ^ ( k ) ( x ) \mathbf{a}_k(\mathbf{x}):=\mathbf{f}(\mathbf{x})-\frac{1}{2\beta}\mathbf{q}(\mathbf{x})\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla\widehat{V}^{(k)}(\mathbf{x}) a k ( x ) := f ( x ) − 2 β 1 q ( x ) q ( x ) T ∇ V ( k ) ( x ) . For every ψ ∈ V \psi\in\mathcal{V} ψ ∈ V , ε ∈ R \varepsilon\in\mathbb{R} ε ∈ R and x ∈ Ω \mathbf{x}\in\Omega x ∈ Ω ,
L H J B ( V ^ ( k ) + ε ψ ) ( x ) = R ( V ^ ( k ) ) ( x ) + ε a k ( x ) T ∇ ψ ( x ) − ε 2 4 β ∥ q ( x ) T ∇ ψ ( x ) ∥ 2 2 . (20) \mathcal{L}_{\mathrm{HJB}}(\widehat{V}^{(k)}+\varepsilon\psi)(\mathbf{x})=R(\widehat{V}^{(k)})(\mathbf{x})+\varepsilon\mathbf{a}_k(\mathbf{x})^{\mathsf{T}}\nabla\psi(\mathbf{x})-\frac{\varepsilon^2}{4\beta}\left\lVert\mathbf{q}(\mathbf{x})^{\mathsf{T}}\nabla\psi(\mathbf{x})\right\rVert_2^2. \tag*{(20)} L HJB ( V ( k ) + ε ψ ) ( x ) = R ( V ( k ) ) ( x ) + ε a k ( x ) T ∇ ψ ( x ) − 4 β ε 2 q ( x ) T ∇ ψ ( x ) 2 2 . (20)
Consequently, the linearized HJB operator L H J B , k : V → L 2 ( Ω ) \mathcal{L}_{\mathrm{HJB},k}:\mathcal{V}\to L^2(\Omega) L HJB , k : V → L 2 ( Ω ) at V ^ ( k ) \widehat{V}^{(k)} V ( k ) is
( L H J B , k ψ ) ( x ) : = D L H J B ( V ^ ( k ) ) [ ψ ] ( x ) = a k ( x ) T ∇ ψ ( x ) . (21) (\mathcal{L}_{\mathrm{HJB},k}\psi)(\mathbf{x}):=D\mathcal{L}_{\mathrm{HJB}}(\widehat{V}^{(k)})[\psi](\mathbf{x})=\mathbf{a}_k(\mathbf{x})^{\mathsf{T}}\nabla\psi(\mathbf{x}). \tag*{(21)} ( L HJB , k ψ ) ( x ) := D L HJB ( V ( k ) ) [ ψ ] ( x ) = a k ( x ) T ∇ ψ ( x ) . (21)
Proof. Fix x ∈ Ω \mathbf{x}\in\Omega x ∈ Ω and write p : = ∇ V ^ ( k ) ( x ) \mathbf{p}:=\nabla\widehat{V}^{(k)}(\mathbf{x}) p := ∇ V ( k ) ( x ) , g : = ∇ ψ ( x ) \mathbf{g}:=\nabla\psi(\mathbf{x}) g := ∇ ψ ( x ) and B : = q ( x ) q ( x ) T \mathbf{B}:=\mathbf{q}(\mathbf{x})\mathbf{q}(\mathbf{x})^{\mathsf{T}} B := q ( x ) q ( x ) T , which is symmetric. Then
( p + ε g ) T B ( p + ε g ) = p T B p + 2 ε g T B p + ε 2 ∥ q ( x ) T g ∥ 2 2 . (\mathbf{p}+\varepsilon\mathbf{g})^{\mathsf{T}}\mathbf{B}(\mathbf{p}+\varepsilon\mathbf{g})=\mathbf{p}^{\mathsf{T}}\mathbf{B}\mathbf{p}+2\varepsilon\mathbf{g}^{\mathsf{T}}\mathbf{B}\mathbf{p}+\varepsilon^2\lVert\mathbf{q}(\mathbf{x})^{\mathsf{T}}\mathbf{g}\rVert_2^2. ( p + ε g ) T B ( p + ε g ) = p T Bp + 2 ε g T Bp + ε 2 ∥ q ( x ) T g ∥ 2 2 .
Inserting this into (19) and collecting the terms linear in ε \varepsilon ε gives ε g T ( f ( x ) − 1 2 β B p ) = ε a k ( x ) T g \varepsilon\mathbf{g}^{\mathsf{T}}(\mathbf{f}(\mathbf{x})-\frac{1}{2\beta}\mathbf{B}\mathbf{p})=\varepsilon\mathbf{a}_k(\mathbf{x})^{\mathsf{T}}\mathbf{g} ε g T ( f ( x ) − 2 β 1 Bp ) = ε a k ( x ) T g , which proves (20) . Dividing by ε \varepsilon ε and letting ε → 0 \varepsilon\to0 ε → 0 in (20) identifies the derivative of L H J B \mathcal{L}_{\mathrm{HJB}} L HJB at V ^ ( k ) \widehat{V}^{(k)} V ( k ) in the direction ψ \psi ψ , yielding (21) .
By (20) , the linearized residual R ( V ^ ( k ) ) + α L H J B , k ϕ j R(\widehat{V}^{(k)})+\alpha\mathcal{L}_{\mathrm{HJB},k}\phi_j R ( V ( k ) ) + α L HJB , k ϕ j used in the model (18) differs from the exact residual L H J B ( V ^ ( k ) + α ϕ j ) \mathcal{L}_{\mathrm{HJB}}(\widehat{V}^{(k)}+\alpha\phi_j) L HJB ( V ( k ) + α ϕ j ) only by the term − α 2 4 β ∥ q ⊤ ∇ ϕ j ∥ 2 2 -\frac{\alpha^2}{4\beta}\lVert\mathbf{q}^{\top}\nabla\phi_j\rVert_2^2 − 4 β α 2 ∥ q ⊤ ∇ ϕ j ∥ 2 2 , which is small when the control acts weakly in the direction of ∇ ϕ j \nabla\phi_j ∇ ϕ j . We now define a stationary HJB residual-decay indicator.
Definition 4.6 (Stationary HJB residual-decay indicator). For the infinite-horizon problem (1) , let L H J B \mathcal{L}_{\mathrm{HJB}} L HJB be given by (19) and its associated residual R ( V ^ ( k ) ) R(\widehat{V}^{(k)}) R ( V ( k ) ) . For V ^ ( k ) ∈ V n k \widehat{V}^{(k)}\in\mathcal{V}_{n_k} V ( k ) ∈ V n k , let \mathbf{a}_k be as in Lemma 4.5. For each candidate basis function \phi_j$ with index j ∈ Λ ( k ) : = Θ ∖ Γ ( k ) j\in\Lambda^{(k)}:=\Theta\setminus\Gamma^{(k)} j ∈ Λ ( k ) := Θ ∖ Γ ( k ) , the stationary HJB residual-decay indicator is defined by
e j , H J B ( k ) : = ∣ ∫ Ω R ( V ^ ( k ) ) ( x ) ( a k ( x ) ⊤ ∇ ϕ j ( x ) ) d x ∣ ( ∫ Ω ∣ a k ( x ) ⊤ ∇ ϕ j ( x ) ∣ 2 d x ) 1 / 2 . (22) e_{j,\mathrm{HJB}}^{(k)}:=\frac{\left|\int_{\Omega}R\left(\widehat{V}^{(k)}\right)(\mathbf{x})\left(\mathbf{a}_k(\mathbf{x})^{\top}\nabla\phi_j(\mathbf{x})\right)\,\mathrm{d}\mathbf{x}\right|}{\left(\int_{\Omega}\left|\mathbf{a}_k(\mathbf{x})^{\top}\nabla\phi_j(\mathbf{x})\right|^2\,\mathrm{d}\mathbf{x}\right)^{1/2}}. \tag*{(22)} e j , HJB ( k ) := ( ∫ Ω ∣ a k ( x ) ⊤ ∇ ϕ j ( x ) ∣ 2 d x ) 1/2 ∫ Ω R ( V ( k ) ) ( x ) ( a k ( x ) ⊤ ∇ ϕ j ( x ) ) d x . (22)
We set e j , H J B ( k ) = 0 e_{j,\mathrm{HJB}}^{(k)}=0 e j , HJB ( k ) = 0 whenever the denominator in (22) vanishes.
Remark 4.7 (Constant basis functions). The indicator e j , H J B ( k ) e_{j,\mathrm{HJB}}^{(k)} e j , HJB ( k ) depends only on ∇ ϕ j \nabla\phi_j ∇ ϕ j and is therefore “blind” to constant basis functions. This is consistent with the fact that the undiscounted stationary HJB equation (2) determines V V V only up to additive constants: the indicator effectively learns only the shape of V V V , i.e., its gradient. Since the operator is used solely to select basis functions, and not to solve the stationary problem, we handle this by requiring the initial active set Γ ( 1 ) \Gamma^{(1)} Γ ( 1 ) to contain a constant basis function.
Model-based greedy algorithm
After introducing the indicator for adaptive basis selection, we now define a validation error used to analyze the approximation error throughout the iterative procedure. Let the validation dataset be D v a l = { ( x v a l , i , v v a l , i , g v a l , i ) } i = 1 N v a l \mathcal{D}_{\mathrm{val}}=\{(\mathbf{x}_{\mathrm{val},i},v_{\mathrm{val},i},\mathbf{g}_{\mathrm{val},i})\}_{i=1}^{N_{\mathrm{val}}} D val = {( x val , i , v val , i , g val , i ) } i = 1 N val with N v a l N_{\mathrm{val}} N val points. The relative L 2 L^2 L 2 - and H 1 H^1 H 1 -validation errors of V ^ ( k ) \widehat{V}^{(k)} V ( k ) at the k k k -th iteration are computed as
Error L 2 ( V ^ ( k ) ) = ( ∑ i = 1 N v a l ∣ V ^ ( k ) ( x v a l , i ) − v v a l , i ∣ 2 ∑ i = 1 N v a l ∣ v v a l , i ∣ 2 ) 1 / 2 , Error H 1 ( V ^ ( k ) ) = ( ∑ i = 1 N v a l ∥ ∇ V ^ ( k ) ( x v a l , i ) − g v a l , i ∥ 2 2 ∑ i = 1 N v a l ∥ g v a l , i ∥ 2 2 ) 1 / 2 . (23) \begin{aligned}
\operatorname{Error}_{L^2}\left(\widehat{V}^{(k)}\right)&=\left(\frac{\sum_{i=1}^{N_{\mathrm{val}}}\left|\widehat{V}^{(k)}(\mathbf{x}_{\mathrm{val},i})-v_{\mathrm{val},i}\right|^2}{\sum_{i=1}^{N_{\mathrm{val}}}|v_{\mathrm{val},i}|^2}\right)^{1/2},\\
\operatorname{Error}_{H^1}\left(\widehat{V}^{(k)}\right)&=\left(\frac{\sum_{i=1}^{N_{\mathrm{val}}}\left\|\nabla\widehat{V}^{(k)}(\mathbf{x}_{\mathrm{val},i})-\mathbf{g}_{\mathrm{val},i}\right\|_2^2}{\sum_{i=1}^{N_{\mathrm{val}}}\|\mathbf{g}_{\mathrm{val},i}\|_2^2}\right)^{1/2}. \tag*{(23)}
\end{aligned} Error L 2 ( V ( k ) ) Error H 1 ( V ( k ) ) = ∑ i = 1 N val ∣ v val , i ∣ 2 ∑ i = 1 N val V ( k ) ( x val , i ) − v val , i 2 1/2 , = ∑ i = 1 N val ∥ g val , i ∥ 2 2 ∑ i = 1 N val ∇ V ( k ) ( x val , i ) − g val , i 2 2 1/2 . (23)
With both the selection criterion and error measures established, we are now ready to present the model-based greedy algorithm.
Algorithm 1 describes the model-based greedy algorithm for solving the PDE (6) by Galerkin methods, where the basis selection is guided by the residual-decay indicator. Starting from an initial basis index set, the algorithm iteratively selects the candidate with the largest value of the indicator. At each iteration, the Galerkin system is solved in the updated basis subspace, and relative validation errors are computed. The procedure terminates either when the prescribed iteration budget k max k_{\max} k m a x is reached or when all remaining indicator values fall below the tolerance ε \varepsilon ε , i.e., max j ∈ Λ ( k ) e j , P D E ( k ) < ε \max_{j\in\Lambda^{(k)}}e_{j,\mathrm{PDE}}^{(k)}<\varepsilon max j ∈ Λ ( k ) e j , PDE ( k ) < ε .
Algorithm 1 Model-based greedy algorithm
Input: Candidate basis set Φ Θ \Phi_{\Theta} Φ Θ , validation dataset D v a l \mathcal{D}_{\mathrm{val}} D val , iteration budget k max k_{\max} k m a x , early stop tolerance ε \varepsilon ε
Initialize active basis index set Γ ( 1 ) \Gamma^{(1)} Γ ( 1 ) with cardinality 1 ≤ ∣ Γ ( 1 ) ∣ ≪ P 1 \leq\lvert\Gamma^{(1)}\rvert\ll P 1 ≤ ∣ Γ ( 1 ) ∣ ≪ P , and candidate set Λ ( 1 ) = Θ ∖ Γ ( 1 ) \Lambda^{(1)} = \Theta\setminus\Gamma^{(1)} Λ ( 1 ) = Θ ∖ Γ ( 1 )
Solve for coefficients c ( 1 ) \mathbf{c}^{(1)} c ( 1 ) by Galerkin methods on Φ Γ ( 1 ) : = { ϕ j : j ∈ Γ ( 1 ) } \Phi_{\Gamma^{(1)}} := \{\phi_j : j \in\Gamma^{(1)}\} Φ Γ ( 1 ) := { ϕ j : j ∈ Γ ( 1 ) }
Set V ^ ( 1 ) ( x ) = Φ Γ ( 1 ) ( x ) T c ( 1 ) \widehat{V}^{(1)}(\mathbf{x}) = \Phi_{\Gamma^{(1)}}(\mathbf{x})^{\mathsf{T}}\mathbf{c}^{(1)} V ( 1 ) ( x ) = Φ Γ ( 1 ) ( x ) T c ( 1 )
for k = 1 , 2 , … , k max k = 1, 2, \ldots, k_{\max} k = 1 , 2 , … , k m a x do
Compute e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) for j ∈ Λ ( k ) j \in\Lambda^{(k)} j ∈ Λ ( k )
if max j ∈ Λ ( k ) e j , P D E ( k ) < ε \max_{j \in\Lambda^{(k)}} e_{j,\mathrm{PDE}}^{(k)} < \varepsilon max j ∈ Λ ( k ) e j , PDE ( k ) < ε then
break
end if
j ∗ ← argmax j ∈ Λ ( k ) e j , P D E ( k ) j^{*} \leftarrow\operatorname*{argmax}_{j \in\Lambda^{(k)}} e_{j,\mathrm{PDE}}^{(k)} j ∗ ← argmax j ∈ Λ ( k ) e j , PDE ( k )
Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } \Gamma^{(k+1)} = \Gamma^{(k)} \cup\{j^{*}\} Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } and Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ } \Lambda^{(k+1)} = \Lambda^{(k)} \setminus\{j^{*}\} Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ }
Solve for c ( k + 1 ) \mathbf{c}^{(k+1)} c ( k + 1 ) on Φ Γ ( k + 1 ) \Phi_{\Gamma^{(k+1)}} Φ Γ ( k + 1 ) and set V ^ ( k + 1 ) = Φ Γ ( k + 1 ) T c ( k + 1 ) \widehat{V}^{(k+1)} = \Phi_{\Gamma^{(k+1)}}^{\mathsf{T}}\mathbf{c}^{(k+1)} V ( k + 1 ) = Φ Γ ( k + 1 ) T c ( k + 1 )
Compute Error L 2 ( V ^ ( k + 1 ) ) \operatorname{Error}_{L_2}(\widehat{V}^{(k+1)}) Error L 2 ( V ( k + 1 ) ) and Error H 1 ( V ^ ( k + 1 ) ) \operatorname{Error}_{H_1}(\widehat{V}^{(k+1)}) Error H 1 ( V ( k + 1 ) ) on D v a l \mathcal{D}_{\mathrm{val}} D val
end for
Remark 4.8 (Computational cost). At each iteration of Algorithm 1 we compute e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) for all j ∈ Λ ( k ) j \in\Lambda^{(k)} j ∈ Λ ( k ) and then re-solve the Galerkin system on the enlarged subspace. Using quadrature with N q N_q N q nodes, the computation of all candidate indicators costs O ( N q ∣ Λ ( k ) ∣ d ) O(N_q\lvert\Lambda^{(k)}\rvert d) O ( N q ∣ Λ ( k ) ∣ d ) operations. This step uses the current residual values and projects them against the linearized candidate directions. The Galerkin problem is then re-solved only on the active subspace of dimension n k ≪ P n_k \ll P n k ≪ P .
The cumulative cost of the linear-algebra component over n n n greedy iterations is ∑ k = 1 n O ( n k 3 ) \sum_{k=1}^{n} O(n_k^3) ∑ k = 1 n O ( n k 3 ) , in contrast, solving the full non-adaptive Galerkin model with all P P P basis functions has cost typically of order O ( P 3 ) O(P^3) O ( P 3 ) . For large P P P , the reduced Galerkin solves can provide substantial computational savings.
Finally, as discussed in § 5 , when training data are available, e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) can be approximated directly from data, further reducing the cost of the selection step and making the method particularly attractive in data-driven settings.
Data-driven adaptive basis and data selection
Given a training dataset D = { ( x i , v i , g i ) } i = 1 N \mathcal{D} = \{(\mathbf{x}_i, v_i, \mathbf{g}_i)\}_{i=1}^{N} D = {( x i , v i , g i ) } i = 1 N , we introduce an analogous partition of the data in
I ( k ) ∪ J ( k ) = { 1 , ⋯ , N } , I ( k ) ∩ J ( k ) = ∅ , \mathcal{I}^{(k)} \cup\mathcal{J}^{(k)} = \{1,\cdots,N\}, \qquad\mathcal{I}^{(k)} \cap\mathcal{J}^{(k)} = \emptyset, I ( k ) ∪ J ( k ) = { 1 , ⋯ , N } , I ( k ) ∩ J ( k ) = ∅ ,
where I ( k ) ⊂ { 1 , ⋯ , N } \mathcal{I}^{(k)} \subset\{1,\cdots,N\} I ( k ) ⊂ { 1 , ⋯ , N } indexes the active training data,
D I ( k ) = { ( x i , v i , g i ) } i ∈ I ( k ) , \mathcal{D}_{\mathcal{I}^{(k)}} = \{(\mathbf{x}_i,v_i,\mathbf{g}_i)\}_{i \in\mathcal{I}^{(k)}}, D I ( k ) = {( x i , v i , g i ) } i ∈ I ( k ) ,
used to fit V ^ ( k ) \widehat{V}^{(k)} V ( k ) , with cardinality m k : = ∣ I ( k ) ∣ m_k := \lvert\mathcal{I}^{(k)}\rvert m k := ∣ I ( k ) ∣ . The set J ( k ) = { 1 , ⋯ , N } ∖ I ( k ) \mathcal{J}^{(k)} = \{1,\cdots,N\} \setminus\mathcal{I}^{(k)} J ( k ) = { 1 , ⋯ , N } ∖ I ( k ) indexes the remaining data D J ( k ) = D ∖ D I ( k ) \mathcal{D}_{\mathcal{J}^{(k)}} = \mathcal{D} \setminus\mathcal{D}_{\mathcal{I}^{(k)}} D J ( k ) = D ∖ D I ( k ) , which are used for residual estimation and adaptive data selection.
We introduce data-driven criteria for adaptive basis and data selection within the supervised learning framework presented in § 3.3 . At each iteration, the most informative data points and basis functions are selected according to their predicted contribution to reducing the supervised loss.
Supervised-loss basis indicator
To quantify the potential improvement obtained by adding a single candidate basis function, we use the predicted one-step decrease of the gradient-augmented supervised loss. The construction is analogous to the single-direction projected indicator in § 4.2 . In the model-based setting, the PDE residual is tested against the linearized image L k ϕ j \mathcal{L}_k\phi_j L k ϕ j of a candidate basis direction. In the supervised setting, the PDE residual is replaced by the empirical residual on the active training set, and the linearized image is replaced by the corresponding feature vector generated by ϕ j \phi_j ϕ j and ∇ ϕ j \nabla\phi_j ∇ ϕ j . Thus, in both cases, each candidate basis function is assessed by the improvement it can produce along its own direction.
For the active dataset D I ( k ) \mathcal{D}_{\mathcal{I}^{(k)}} D I ( k ) , let h ( k ) \mathbf{h}^{(k)} h ( k ) denote the weighted residual vector associated with the current approximation on the active training set I ( k ) \mathcal{I}^{(k)} I ( k ) , collecting both function value and gradient residuals:
h ( k ) = [ { ω 1 μ i ( v i − V ^ ( k ) ( x i ) ) } i ∈ I ( k ) { ω 2 μ i ( g i − ∇ V ^ ( k ) ( x i ) ) } i ∈ I ( k ) ] ∈ R ( 1 + d ) m k , \mathbf{h}^{(k)}=
\begin{bmatrix}
\left\{\sqrt{\omega_1\mu_i}\left(v_i-\widehat{V}^{(k)}(x_i)\right)\right\}_{i\in\mathcal{I}^{(k)}}\\
\left\{\sqrt{\omega_2\mu_i}\left(\mathbf{g}_i-\nabla\widehat{V}^{(k)}(x_i)\right)\right\}_{i\in\mathcal{I}^{(k)}}
\end{bmatrix}
\in\mathbb{R}^{(1+d)m_k}, h ( k ) = { ω 1 μ i ( v i − V ( k ) ( x i ) ) } i ∈ I ( k ) { ω 2 μ i ( g i − ∇ V ( k ) ( x i ) ) } i ∈ I ( k ) ∈ R ( 1 + d ) m k ,
where μ i > 0 \mu_i>0 μ i > 0 denotes the sampling weight (for uniformly sampled data one may take μ i = 1 / m k \mu_i=1/m_k μ i = 1/ m k or μ i = 1 \mu_i=1 μ i = 1 ), and ω 1 , ω 2 > 0 \omega_1,\omega_2>0 ω 1 , ω 2 > 0 weight the function-value and gradient residuals, respectively. Similarly, for each candidate ϕ j \phi_j ϕ j , j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) , define the weighted feature vector
z j ( k ) = [ { ω 1 μ i ϕ j ( x i ) } i ∈ I ( k ) { ω 2 μ i ∇ ϕ j ( x i ) } i ∈ I ( k ) ] ∈ R ( 1 + d ) m k . \mathbf{z}_j^{(k)}=
\begin{bmatrix}
\left\{\sqrt{\omega_1\mu_i}\phi_j(x_i)\right\}_{i\in\mathcal{I}^{(k)}}\\
\left\{\sqrt{\omega_2\mu_i}\nabla\phi_j(x_i)\right\}_{i\in\mathcal{I}^{(k)}}
\end{bmatrix}
\in\mathbb{R}^{(1+d)m_k}. z j ( k ) = [ { ω 1 μ i ϕ j ( x i ) } i ∈ I ( k ) { ω 2 μ i ∇ ϕ j ( x i ) } i ∈ I ( k ) ] ∈ R ( 1 + d ) m k .
For each candidate basis function ϕ j \phi_j ϕ j , j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) , we consider the one-direction enrichment V ^ ( k ) + α ϕ j \widehat{V}^{(k)}+\alpha\phi_j V ( k ) + α ϕ j , α ∈ R \alpha\in\mathbb{R} α ∈ R . The supervised loss on the active training set, restricted to this enrichment, is
Q S L , j ( k ) ( α ) : = 1 2 ∥ h ( k ) − α z j ( k ) ∥ 2 2 , α ∈ R , \mathcal{Q}_{\mathrm{SL},j}^{(k)}(\alpha):=\frac{1}{2}\left\|\mathbf{h}^{(k)}-\alpha\mathbf{z}_j^{(k)}\right\|_2^2,\qquad\alpha\in\mathbb{R}, Q SL , j ( k ) ( α ) := 2 1 h ( k ) − α z j ( k ) 2 2 , α ∈ R ,
so that Q S L , j ( k ) ( 0 ) \mathcal{Q}_{\mathrm{SL},j}^{(k)}(0) Q SL , j ( k ) ( 0 ) is the current supervised loss. We define the supervised-loss basis indicator
e j , S L ( k ) : = ∣ ( z j ( k ) ) T h ( k ) ∣ ∥ z j ( k ) ∥ 2 = ( ∑ i ∈ I ( k ) μ i [ ω 1 ∣ ϕ j ( x i ) ∣ 2 + ω 2 ∥ ∇ ϕ j ( x i ) ∥ 2 2 ] ) − 1 / 2 ∣ ∑ i ∈ I ( k ) μ i [ ω 1 ( v i − V ^ ( k ) ( x i ) ) ϕ j ( x i ) + ω 2 ( g i − ∇ V ^ ( k ) ( x i ) ) T ∇ ϕ j ( x i ) ] ∣ , (24) \begin{aligned}
e_{j,\mathrm{SL}}^{(k)}:=\frac{\left|\left(\mathbf{z}_j^{(k)}\right)^{\mathsf{T}}\mathbf{h}^{(k)}\right|}{\left\|\mathbf{z}_j^{(k)}\right\|_2} \\
&=\left(\sum_{i\in\mathcal{I}^{(k)}}\mu_i\left[\omega_1|\phi_j(x_i)|^2+\omega_2\|\nabla\phi_j(x_i)\|_2^2\right]\right)^{-1/2}
\left|\sum_{i\in\mathcal{I}^{(k)}}\mu_i\left[\omega_1\left(v_i-\widehat{V}^{(k)}(x_i)\right)\phi_j(x_i)+\omega_2\left(\mathbf{g}_i-\nabla\widehat{V}^{(k)}(x_i)\right)^{\mathsf{T}}\nabla\phi_j(x_i)\right]\right|, \tag*{(24)}
\end{aligned} e j , SL ( k ) := z j ( k ) 2 ( z j ( k ) ) T h ( k ) = i ∈ I ( k ) ∑ μ i [ ω 1 ∣ ϕ j ( x i ) ∣ 2 + ω 2 ∥∇ ϕ j ( x i ) ∥ 2 2 ] − 1/2 i ∈ I ( k ) ∑ μ i [ ω 1 ( v i − V ( k ) ( x i ) ) ϕ j ( x i ) + ω 2 ( g i − ∇ V ( k ) ( x i ) ) T ∇ ϕ j ( x i ) ] , (24)
with e j , S L ( k ) : = 0 e_{j,\mathrm{SL}}^{(k)}:=0 e j , SL ( k ) := 0 whenever z j ( k ) = 0 \mathbf{z}_j^{(k)}=0 z j ( k ) = 0 . It is the data-driven counterpart of the residual-decay indicator, as the following proposition shows.
To compare with OMP, let r ( k ) \mathbf{r}^{(k)} r ( k ) and a j \mathbf{a}_j a j denote the vectors h ( k ) \mathbf{h}^{(k)} h ( k ) and z j ( k ) \mathbf{z}_j^{(k)} z j ( k ) computed with ω 1 = ω 2 = μ i = 1 \omega_1=\omega_2=\mu_i=1 ω 1 = ω 2 = μ i = 1 , that is, the unweighted residual vector and the unweighted gradient-augmented column of ϕ j \phi_j ϕ j on the active data. Applied to the dictionary { a j } j ∈ Λ ( k ) \{\mathbf{a}_j\}_{j\in\Lambda^{(k)}} { a j } j ∈ Λ ( k ) with residual r ( k ) \mathbf{r}^{(k)} r ( k ) , the selection step of OMP chooses
j O M P ∗ ∈ argmax j ∈ Λ ( k ) ∣ a j T r ( k ) ∣ ∥ a j ∥ 2 . (25) j_{\mathrm{OMP}}^*\in\underset{j\in\Lambda^{(k)}}{\operatorname{argmax}}\frac{\left|\mathbf{a}_j^{\mathsf{T}}\mathbf{r}^{(k)}\right|}{\|\mathbf{a}_j\|_2}. \tag*{(25)} j OMP ∗ ∈ j ∈ Λ ( k ) argmax ∥ a j ∥ 2 a j T r ( k ) . (25)
Proposition 5.1 (Supervised-loss indicator). Let j ∈ Λ ( k ) j \in\Lambda^{(k)} j ∈ Λ ( k ) with z j ( k ) ≠ 0 \mathbf{z}_{j}^{(k)} \ne0 z j ( k ) = 0 . Then the following hold.
(i) Q S L , j ( k ) Q_{\mathrm{SL},j}^{(k)} Q SL , j ( k ) has the unique minimizer α j ∗ = ( z j ( k ) ) T h ( k ) ∥ z j ( k ) ∥ 2 2 \alpha_j^* = \frac{(\mathbf{z}_{j}^{(k)})^\mathsf{T}\mathbf{h}^{(k)}}{\lVert\mathbf{z}_{j}^{(k)}\rVert_2^2} α j ∗ = ∥ z j ( k ) ∥ 2 2 ( z j ( k ) ) T h ( k ) , and Q S L , j ( k ) ( 0 ) − Q S L , j ( k ) ( α j ∗ ) = 1 2 ( e j , S L ( k ) ) 2 Q_{\mathrm{SL},j}^{(k)}(0) - Q_{\mathrm{SL},j}^{(k)}(\alpha_j^*) = \frac{1}{2}(e_{j,\mathrm{SL}}^{(k)})^2 Q SL , j ( k ) ( 0 ) − Q SL , j ( k ) ( α j ∗ ) = 2 1 ( e j , SL ( k ) ) 2 .
(ii) e j , S L ( k ) e_{j,\mathrm{SL}}^{(k)} e j , SL ( k ) is the Euclidean norm of the orthogonal projection of h ( k ) \mathbf{h}^{(k)} h ( k ) onto span { z j ( k ) } \operatorname{span}\{\mathbf{z}_{j}^{(k)}\} span { z j ( k ) } , and it is unchanged if ϕ j \phi_j ϕ j is replaced by s ϕ j s\phi_j s ϕ j with s ≠ 0 s \ne0 s = 0 .
(iii) If ω 1 = ω 2 \omega_1 = \omega_2 ω 1 = ω 2 and the weights μ i \mu_i μ i , i ∈ I ( k ) i \in\mathcal{I}^{(k)} i ∈ I ( k ) , are equal, then argmax j ∈ Λ ( k ) e j , S L ( k ) \operatorname*{argmax}_{j\in\Lambda^{(k)}} e_{j,\mathrm{SL}}^{(k)} argmax j ∈ Λ ( k ) e j , SL ( k ) coincides with the OMP selection rule (25) .
Proof. Parts (i) and (ii) follow as in Proposition 4.4(iii)–(iv), with L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) replaced by R ( 1 + d ) m k \mathbb{R}^{(1+d)m_k} R ( 1 + d ) m k with the Euclidean inner product, and R ( V ^ ( k ) ) R(\widehat{V}^{(k)}) R ( V ( k ) ) and L k ϕ j \mathcal{L}_k\phi_j L k ϕ j replaced by h ( k ) \mathbf{h}^{(k)} h ( k ) and − z j ( k ) -\mathbf{z}_{j}^{(k)} − z j ( k ) ; scale invariance holds because z j ( k ) \mathbf{z}_{j}^{(k)} z j ( k ) is linear in ϕ j \phi_j ϕ j . For (iii), if ω 1 = ω 2 = ω \omega_1 = \omega_2 = \omega ω 1 = ω 2 = ω and μ i = μ \mu_i = \mu μ i = μ , then h ( k ) = ω μ r ( k ) \mathbf{h}^{(k)} = \sqrt{\omega\mu}\,\mathbf{r}^{(k)} h ( k ) = ω μ r ( k ) and z j ( k ) = ω μ a j \mathbf{z}_{j}^{(k)} = \sqrt{\omega\mu}\,\mathbf{a}_j z j ( k ) = ω μ a j . Hence e j , S L ( k ) = ω μ ∣ a j T r ( k ) ∣ / ∥ a j ∥ 2 e_{j,\mathrm{SL}}^{(k)} = \sqrt{\omega\mu}\,\lvert\mathbf{a}_j^\mathsf{T}\mathbf{r}^{(k)}\rvert/\lVert\mathbf{a}_j\rVert_2 e j , SL ( k ) = ω μ ∣ a j T r ( k ) ∣ / ∥ a j ∥ 2 , and the common factor ω μ > 0 \sqrt{\omega\mu} > 0 ω μ > 0 does not affect the maximizer in (25) . □ □
By Proposition 5.1(i), selecting the candidate with the largest e j , S L ( k ) e_{j,\mathrm{SL}}^{(k)} e j , SL ( k ) selects the candidate that yields the largest one-step decrease of the supervised loss on the active data. Unlike Proposition 4.4(iii), this decrease is exact, since the supervised loss is quadratic in the coefficients. By Proposition 5.1(iii), the basis step of the data-driven algorithm differs from OMP only through the weights ω 1 , ω 2 \omega_1,\omega_2 ω 1 , ω 2 and the LASSO refit; the additional ingredient is the greedy selection of the training data in § 5.2 . The next basis function is chosen as
j ∗ = argmax j ∈ Λ ( k ) e j , S L ( k ) , j^* = \operatorname*{argmax}_{j\in\Lambda^{(k)}} e_{j,\mathrm{SL}}^{(k)}, j ∗ = j ∈ Λ ( k ) argmax e j , SL ( k ) ,
and the index sets are updated by
Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ } . \Gamma^{(k+1)} = \Gamma^{(k)} \cup\{j^*\}, \qquad\Lambda^{(k+1)} = \Lambda^{(k)} \setminus\{j^*\}. Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } , Λ ( k + 1 ) = Λ ( k ) ∖ { j ∗ } .
After each enrichment step, all coefficients are re-estimated on the enlarged active basis set. Alternatively, one may assemble the candidate columns Z ( k ) ∈ R ( 1 + d ) m k × ∣ Λ ( k ) ∣ \mathbf{Z}^{(k)} \in\mathbb{R}^{(1+d)m_k\times|\Lambda^{(k)}|} Z ( k ) ∈ R ( 1 + d ) m k × ∣ Λ ( k ) ∣ , and solve a regularized least-squares problem over the whole candidate space, in that case, the resulting coefficients should be interpreted as a proxy for multi-direction correction rather than as the exact one-step loss reduction with any individual candidate basis function.
Remark 5.2 (Data-driven residual-decay indicator). The residual-decay indicator of Definition 4.3 also has a data-driven version. Replacing the L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) inner product in (17) by the μ \mu μ -weighted discrete inner product on the active points { x i } i ∈ I ( k ) \{x_i\}_{i\in\mathcal{I}^{(k)}} { x i } i ∈ I ( k ) gives
e ~ j , P D E ( k ) : = ∣ ∑ i ∈ I ( k ) μ i R ( V ^ ( k ) ) ( x i ) L k ϕ j ( x i ) ∣ ( ∑ i ∈ I ( k ) μ i ∣ L k ϕ j ( x i ) ∣ 2 ) 1 / 2 . (26) \widetilde{e}_{j,\mathrm{PDE}}^{(k)} := \frac{\left\lvert\sum_{i\in\mathcal{I}^{(k)}} \mu_i R(\widehat{V}^{(k)})(x_i)\mathcal{L}_k\phi_j(x_i)\right\rvert}{\left(\sum_{i\in\mathcal{I}^{(k)}} \mu_i\left\lvert\mathcal{L}_k\phi_j(x_i)\right\rvert^2\right)^{1/2}}. \tag*{(26)} e j , PDE ( k ) := ( ∑ i ∈ I ( k ) μ i ∣ L k ϕ j ( x i ) ∣ 2 ) 1/2 ∑ i ∈ I ( k ) μ i R ( V ( k ) ) ( x i ) L k ϕ j ( x i ) . (26)
The analogues of Proposition 4.4(iii)–(iv) for e ~ j , P D E ( k ) \widetilde{e}_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) , with this inner product in place of that of L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) , hold by the same proof. This provides a practical way to use the DWR-type indicators in high-dimensional, data-driven settings.
Data score
In contrast to the basis-selection indicator, which estimates the loss decrease obtained by adding a candidate direction, the data score measures the current local contribution of each unselected sample to the supervised residual. For each candidate training data point ( x i , v i , g i ) ∈ D J ( k ) (x_i,v_i,\mathbf{g}_i) \in\mathcal{D}_{\mathcal{J}^{(k)}} ( x i , v i , g i ) ∈ D J ( k ) , we define the gradient-augmented data score in the same spirit as the supervised-loss basis indicator:
score i ( k ) = ω 1 ∣ v i − V ^ ( k ) ( x i ) ∣ 2 + ω 2 ∥ g i − ∇ V ^ ( k ) ( x i ) ∥ 2 2 . (27) \operatorname{score}_i^{(k)} = \omega_1\left|v_i-\widehat{V}^{(k)}(x_i)\right|^2+\omega_2\left\|\mathbf{g}_i-\nabla\widehat{V}^{(k)}(x_i)\right\|_2^2. \tag*{(27)} score i ( k ) = ω 1 v i − V ( k ) ( x i ) 2 + ω 2 g i − ∇ V ( k ) ( x i ) 2 2 . (27)
We then select the next data point as
i ∗ = argmax i ∈ J ( k ) score i ( k ) , i^*=\underset{i\in\mathcal{J}^{(k)}}{\operatorname{argmax}}\operatorname{score}_i^{(k)}, i ∗ = i ∈ J ( k ) argmax score i ( k ) ,
and update the data index sets
I ( k + 1 ) = I ( k ) ∪ { i ∗ } , J ( k + 1 ) = J ( k ) \ { i ∗ } . \mathcal{I}^{(k+1)}=\mathcal{I}^{(k)}\cup\{i^*\},\qquad\mathcal{J}^{(k+1)}=\mathcal{J}^{(k)}\backslash\{i^*\}. I ( k + 1 ) = I ( k ) ∪ { i ∗ } , J ( k + 1 ) = J ( k ) \ { i ∗ } .
Algorithm 2 Data-driven greedy algorithm
Input: Candidate basis set Φ Θ \Phi_{\Theta} Φ Θ , training dataset D \mathcal{D} D , validation dataset D v a l \mathcal{D}_{\mathrm{val}} D val , iteration budget k max k_{\max} k m a x , thresholds ε b a s i s \varepsilon_{\mathrm{basis}} ε basis and ε d a t a \varepsilon_{\mathrm{data}} ε data
Initialize active basis set Γ ( 1 ) \Gamma^{(1)} Γ ( 1 ) , candidate basis set Λ ( 1 ) = Θ \ Γ ( 1 ) \Lambda^{(1)}=\Theta\backslash\Gamma^{(1)} Λ ( 1 ) = Θ\ Γ ( 1 ) , active dataset I ( 1 ) \mathcal{I}^{(1)} I ( 1 ) , inactive dataset J ( 1 ) = { 1 , … , N } \ I ( 1 ) \mathcal{J}^{(1)}=\{1,\ldots,N\}\backslash\mathcal{I}^{(1)} J ( 1 ) = { 1 , … , N } \ I ( 1 ) , and basis_stop = FALSE, data_stop = FALSE
Solve for c ( 1 ) \mathbf{c}^{(1)} c ( 1 ) by supervised learning on D I ( 1 ) \mathcal{D}_{\mathcal{I}^{(1)}} D I ( 1 ) and Φ Γ ( 1 ) \Phi_{\Gamma^{(1)}} Φ Γ ( 1 ) , set V ^ ( 1 ) ( x ) = Φ Γ ( 1 ) ( x ) T c ( 1 ) \widehat{V}^{(1)}(\mathbf{x})=\Phi_{\Gamma^{(1)}}(\mathbf{x})^{\mathsf{T}}\mathbf{c}^{(1)} V ( 1 ) ( x ) = Φ Γ ( 1 ) ( x ) T c ( 1 )
for k = 1 , 2 , … , k max k=1,2,\ldots,k_{\max} k = 1 , 2 , … , k m a x do
Set I ( k + 1 ) ← I ( k ) \mathcal{I}^{(k+1)}\leftarrow\mathcal{I}^{(k)} I ( k + 1 ) ← I ( k ) , J ( k + 1 ) ← J ( k ) \mathcal{J}^{(k+1)}\leftarrow\mathcal{J}^{(k)} J ( k + 1 ) ← J ( k ) , Γ ( k + 1 ) ← Γ ( k ) \Gamma^{(k+1)}\leftarrow\Gamma^{(k)} Γ ( k + 1 ) ← Γ ( k ) , Λ ( k + 1 ) ← Λ ( k ) \Lambda^{(k+1)}\leftarrow\Lambda^{(k)} Λ ( k + 1 ) ← Λ ( k ) , and V ^ ( k + 1 / 2 ) ← V ^ ( k ) \widehat{V}^{(k+1/2)}\leftarrow\widehat{V}^{(k)} V ( k + 1/2 ) ← V ( k )
if data_stop = FALSE and J ( k ) ≠ ∅ \mathcal{J}^{(k)}\ne\varnothing J ( k ) = ∅ then
Compute score i ( k ) \operatorname{score}_i^{(k)} score i ( k ) for i ∈ J ( k ) i\in\mathcal{J}^{(k)} i ∈ J ( k )
if max i ∈ J ( k ) score i ( k ) ≥ ε d a t a \max_{i\in\mathcal{J}^{(k)}}\operatorname{score}_i^{(k)}\ge\varepsilon_{\mathrm{data}} max i ∈ J ( k ) score i ( k ) ≥ ε data then
i ∗ ← argmax i ∈ J ( k ) score i ( k ) i^*\leftarrow\operatorname{argmax}_{i\in\mathcal{J}^{(k)}}\operatorname{score}_i^{(k)} i ∗ ← argmax i ∈ J ( k ) score i ( k )
Update I ( k + 1 ) = I ( k ) ∪ { i ∗ } \mathcal{I}^{(k+1)}=\mathcal{I}^{(k)}\cup\{i^*\} I ( k + 1 ) = I ( k ) ∪ { i ∗ } and J ( k + 1 ) = J ( k ) \ { i ∗ } \mathcal{J}^{(k+1)}=\mathcal{J}^{(k)}\backslash\{i^*\} J ( k + 1 ) = J ( k ) \ { i ∗ }
Refit on D I ( k + 1 ) \mathcal{D}_{\mathcal{I}^{(k+1)}} D I ( k + 1 ) and Φ Γ ( k ) \Phi_{\Gamma^{(k)}} Φ Γ ( k ) to obtain c ( k + 1 / 2 ) \mathbf{c}^{(k+1/2)} c ( k + 1/2 ) and V ^ ( k + 1 / 2 ) \widehat{V}^{(k+1/2)} V ( k + 1/2 )
else
data_stop ← \leftarrow ← TRUE
end if
end if
Set V ^ ( k + 1 ) ← V ^ ( k + 1 / 2 ) \widehat{V}^{(k+1)}\leftarrow\widehat{V}^{(k+1/2)} V ( k + 1 ) ← V ( k + 1/2 )
if basis_stop = FALSE and Λ ( k ) ≠ ∅ \Lambda^{(k)}\ne\varnothing Λ ( k ) = ∅ then
Compute e j ( k ) e_j^{(k)} e j ( k ) for j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) using V ^ ( k + 1 / 2 ) \widehat{V}^{(k+1/2)} V ( k + 1/2 )
if max j ∈ Λ ( k ) e j ( k ) ≥ ε b a s i s \max_{j\in\Lambda^{(k)}}e_j^{(k)}\ge\varepsilon_{\mathrm{basis}} max j ∈ Λ ( k ) e j ( k ) ≥ ε basis then
j ∗ ← argmax j ∈ Λ ( k ) e j ( k ) j^*\leftarrow\operatorname{argmax}_{j\in\Lambda^{(k)}}e_j^{(k)} j ∗ ← argmax j ∈ Λ ( k ) e j ( k )
Update Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } \Gamma^{(k+1)}=\Gamma^{(k)}\cup\{j^*\} Γ ( k + 1 ) = Γ ( k ) ∪ { j ∗ } and Λ ( k + 1 ) = Λ ( k ) \ { j ∗ } \Lambda^{(k+1)}=\Lambda^{(k)}\backslash\{j^*\} Λ ( k + 1 ) = Λ ( k ) \ { j ∗ }
Refit on D I ( k + 1 ) \mathcal{D}_{\mathcal{I}^{(k+1)}} D I ( k + 1 ) and Φ Γ ( k + 1 ) \Phi_{\Gamma^{(k+1)}} Φ Γ ( k + 1 ) to obtain c ( k + 1 ) \mathbf{c}^{(k+1)} c ( k + 1 ) and V ^ ( k + 1 ) \widehat{V}^{(k+1)} V ( k + 1 )
else
basis_stop ← \leftarrow ← TRUE
end if
end if
Compute Error L 2 ( V ^ ( k + 1 ) ) \operatorname{Error}_{L_2}(\widehat{V}^{(k+1)}) Error L 2 ( V ( k + 1 ) ) and Error H 1 ( V ^ ( k + 1 ) ) \operatorname{Error}_{H_1}(\widehat{V}^{(k+1)}) Error H 1 ( V ( k + 1 ) ) on D v a l \mathcal{D}_{\mathrm{val}} D val
if basis_stop = TRUE and data_stop = TRUE then
break
end if
end for
Data-driven greedy algorithm
5.3. Data-driven greedy algorithm. Algorithm 2 extends the greedy strategy to the supervised learning framework with gradient-augmented data. At each iteration, data scores and basis indicators are evaluated and the relevant coefficients are refitted after any enrichment. Index sets and iterates are carried over unchanged when a step adds nothing, so that the intermediate iterate V ^ ( k + 1 / 2 ) \widehat{V}^{(k+1/2)} V ( k + 1/2 ) (after the data step) and V ^ ( k + 1 ) \widehat{V}^{(k+1)} V ( k + 1 ) (after the basis step) are defined at every iteration. The indicator e j ( k ) e_j^{(k)} e j ( k ) denotes either the supervised-loss basis indicator e j , S L ( k ) e_{j,\mathrm{SL}}^{(k)} e j , SL ( k ) or the empirical residual-decay indicator e ~ j , P D E ( k ) \widetilde{e}_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) . As in Algorithm 1, separate stopping criteria are imposed for data and basis selection, yielding further computational savings while preserving the desired approximation accuracy.
Numerical experiments
In this section, we present numerical experiments to assess the performance of the greedy selection strategies for basis and training samples introduced above. § 6.1 considers benchmark PDEs with closed-form solutions, while § 6.2 –§ 6.4 consider optimal control problems for which the value functions do not admit closed-form representations. The MATLAB code and data reproducing all numerical experiments in this paper is publicly available at: https://github.com/AmberYuyangHuang/Greedy-algorithm-for-HJB .
A benchmark for basis selection
We first consider the one-dimensional linear PDE
γ V ( x ) = r ( x ) + b ( x ) V ′ ( x ) , x ∈ Ω = [ − π , π ] , (28) \gamma V(x) = r(x) + b(x)V'(x), \qquad x \in\Omega= [-\pi,\pi], \tag*{(28)} γ V ( x ) = r ( x ) + b ( x ) V ′ ( x ) , x ∈ Ω = [ − π , π ] , (28)
with γ = 0.1 \gamma= 0.1 γ = 0.1 , b ( x ) = 0.05 sin ( x ) b(x) = 0.05\sin(x) b ( x ) = 0.05 sin ( x ) , and r r r chosen so that the exact solution is V ( x ) = cos ( x ) + cos ( 10 x ) V(x) = \cos(x) + \cos(10x) V ( x ) = cos ( x ) + cos ( 10 x ) . This is the affine case L ( V ) = A V − r \mathcal{L}(V) = AV-r L ( V ) = A V − r with ( A ϕ ) ( x ) = γ ϕ ( x ) − b ( x ) ϕ ′ ( x ) (A\phi)(x) = \gamma\phi(x)-b(x)\phi'(x) ( A ϕ ) ( x ) = γ ϕ ( x ) − b ( x ) ϕ ′ ( x ) , so the Galerkin system (7) is linear and L k = A \mathcal{L}_k=A L k = A for every k k k . We use the P = 101 P=101 P = 101 trigonometric basis functions
Φ Θ ( x ) = 1 π [ 1 2 , cos ( x ) , sin ( x ) , … , cos ( 50 x ) , sin ( 50 x ) ] T , \Phi_{\Theta}(x) = \frac{1}{\sqrt{\pi}}\left[\frac{1}{\sqrt{2}},\cos(x),\sin(x),\ldots,\cos(50x),\sin(50x)\right]^{\mathsf{T}}, Φ Θ ( x ) = π 1 [ 2 1 , cos ( x ) , sin ( x ) , … , cos ( 50 x ) , sin ( 50 x ) ] T ,
with Θ = { 1 , … , 101 } \Theta=\{1,\ldots,101\} Θ = { 1 , … , 101 } . In the data-driven setting, the training data are N = 60 N=60 N = 60 equispaced points in Ω \Omega Ω , and the validation set consists of N v a l = 100 N_{\mathrm{val}}=100 N val = 100 equispaced points shifted by half a training step.
Since V V V is supported on only two dictionary elements, ϕ 2 = π − 1 / 2 cos ( x ) \phi_2=\pi^{-1/2}\cos(x) ϕ 2 = π − 1/2 cos ( x ) and ϕ 20 = π − 1 / 2 cos ( 10 x ) \phi_{20}=\pi^{-1/2}\cos(10x) ϕ 20 = π − 1/2 cos ( 10 x ) , this benchmark tests basis identification. Table 1 reports the selected indices and the relative L 2 L^2 L 2 -validation errors for Algorithm 1 with e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) and Algorithm 2 with e j , S L ( k ) e_{j,\mathrm{SL}}^{(k)} e j , SL ( k ) , for the initializations Γ ( 1 ) = { 2 } \Gamma^{(1)}=\{2\} Γ ( 1 ) = { 2 } , { 20 } \{20\} { 20 } and the constant term { 1 } \{1\} { 1 } . In all cases, both indicators identify the exact support { 2 , 20 } \{2,20\} { 2 , 20 } within at most two iterations, after which the validation error drops to machine precision.
Table 1. Selection paths for the one-dimensional benchmark of (28) . For each initialization Γ ( 1 ) \Gamma^{(1)} Γ ( 1 ) we report the index j ∗ j^* j ∗ selected at iterations k = 1 , 2 k=1,2 k = 1 , 2 and the relative L 2 L^2 L 2 -validation error (23) after each refit. The exact support of V V V is { 2 , 20 } \{2,20\} { 2 , 20 } . Both the model-based indicator e j , P D E ( k ) e_{j,\mathrm{PDE}}^{(k)} e j , PDE ( k ) and the supervised-loss indicator e j , S L ( k ) e_{j,\mathrm{SL}}^{(k)} e j , SL ( k ) recover the exact support regardless of initialization.
Without prior knowledge of the solution, the initial index can also be chosen by the indicator itself: setting V ^ ( 0 ) = 0 \widehat{V}^{(0)}=0 V ( 0 ) = 0 , so that R ( V ^ ( 0 ) ) = − r R(\widehat{V}^{(0)})=-r R ( V ( 0 ) ) = − r , and taking Γ ( 1 ) = { j ∗ } \Gamma^{(1)}=\{j^*\} Γ ( 1 ) = { j ∗ } with j ∗ ∈ arg max j ∈ Θ e j , P D E ( 0 ) j^*\in\arg\max_{j\in\Theta}e_{j,\mathrm{PDE}}^{(0)} j ∗ ∈ arg max j ∈ Θ e j , PDE ( 0 ) selects j ∗ = 20 j^*=20 j ∗ = 20 , the dominant component cos ( 10 x ) \cos(10x) cos ( 10 x ) .
One-dimensional optimal control problem
We next consider the one-dimensional optimal control problem from [30 ]
min u ∈ L 2 ( 0 , T ) ∫ 0 T ( 1 4 ( y ( t ) 2 e y ( t ) + 2 y ( t ) e y ( t ) + 4 y ( t ) 3 ) 2 + u ( t ) 2 ) d t \min_{u\in L^2(0,T)}\int_0^T\left(\frac{1}{4}\left(y(t)^2e^{y(t)}+2y(t)e^{y(t)}+4y(t)^3\right)^2+u(t)^2\right)\,dt u ∈ L 2 ( 0 , T ) min ∫ 0 T ( 4 1 ( y ( t ) 2 e y ( t ) + 2 y ( t ) e y ( t ) + 4 y ( t ) 3 ) 2 + u ( t ) 2 ) d t
subject to
y ˙ ( t ) = u ( t ) , y ( 0 ) = x , \dot{y}(t)=u(t),\qquad y(0)=x, y ˙ ( t ) = u ( t ) , y ( 0 ) = x ,
that is, (4) with t = 0 t=0 t = 0 and no terminal penalty, ℓ T ≡ 0 \ell_T\equiv0 ℓ T ≡ 0 . The corresponding infinite-horizon stationary HJB equation has the exact solution V ( x ) = x 4 + x 2 e x V(x)=x^4+x^2e^x V ( x ) = x 4 + x 2 e x on Ω = [ − 1 , 1 ] \Omega=[-1,1] Ω = [ − 1 , 1 ] ; for the finite-horizon computation below, T T T is chosen large enough that V ( 0 , x ) V(0,x) V ( 0 , x ) is close to this stationary value function on the computational domain. According to Definition 4.6, given the current approximation V ^ ( k ) \widehat{V}^{(k)} V ( k ) , the selection indicator for each candidate basis function ϕ j ( x ) \phi_j(x) ϕ j ( x ) with index j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) is
e j , H J B ( k ) = ∣ ∫ − 1 1 R ( V ^ ( k ) ) ( x ) a k ( x ) ϕ j ′ ( x ) d x ∣ ( ∫ − 1 1 ∣ a k ( x ) ϕ j ′ ( x ) ∣ 2 d x ) 1 / 2 , a k ( x ) = − 1 2 ( V ^ ( k ) ) ′ ( x ) , (29) e_{j,\mathrm{HJB}}^{(k)}=\frac{\left|\int_{-1}^{1}R\left(\widehat{V}^{(k)}\right)(x)a_k(x)\phi_j'(x)\,dx\right|}{\left(\int_{-1}^{1}\left|a_k(x)\phi_j'(x)\right|^2\,dx\right)^{1/2}},\qquad a_k(x)=-\frac{1}{2}\left(\widehat{V}^{(k)}\right)'(x), \tag*{(29)} e j , HJB ( k ) = ( ∫ − 1 1 a k ( x ) ϕ j ′ ( x ) 2 d x ) 1/2 ∫ − 1 1 R ( V ( k ) ) ( x ) a k ( x ) ϕ j ′ ( x ) d x , a k ( x ) = − 2 1 ( V ( k ) ) ′ ( x ) , (29)
with residual
R ( V ^ ( k ) ) ( x ) = 1 4 ( ( x 2 e x + 2 x e x + 4 x 3 ) 2 − ( ( V ^ ( k ) ) ′ ( x ) ) 2 ) . R\left(\widehat{V}^{(k)}\right)(x)=\frac{1}{4}\left(\left(x^2e^x+2xe^x+4x^3\right)^2-\left(\left(\widehat{V}^{(k)}\right)'(x)\right)^2\right). R ( V ( k ) ) ( x ) = 4 1 ( ( x 2 e x + 2 x e x + 4 x 3 ) 2 − ( ( V ( k ) ) ′ ( x ) ) 2 ) .
By taking T = 10 T=10 T = 10 and considering a one-dimensional Legendre polynomial basis truncated at degree 10, we obtain the results reported in Figure 1 , where we observe that the accuracy of the greedy strategy improves rapidly once the basis size reaches six, while, by contrast, random selection attains the same accuracy only in the final stage.
Figure 1. Error decay of Algorithm 1 using the time-dependent Galerkin method for the one-dimensional optimal control problem, comparing random basis selection and greedy selection driven by the residual-decay indicator.
Van der Pol oscillator
We now consider the optimal control of the Van der Pol oscillator:
min u ∈ L 2 ( 0 , T ) ∫ 0 T ( y 1 ( t ) 2 + y 2 ( t ) 2 + β u ( t ) 2 ) d t \min_{u\in L^2(0,T)} \int_0^T \left(y_1(t)^2+y_2(t)^2+\beta u(t)^2\right)\,\mathrm{d}t u ∈ L 2 ( 0 , T ) min ∫ 0 T ( y 1 ( t ) 2 + y 2 ( t ) 2 + β u ( t ) 2 ) d t
subject to
{ y ˙ 1 ( t ) = y 2 ( t ) , y ˙ 2 ( t ) = − y 1 ( t ) + y 2 ( t ) ( 1 − y 1 ( t ) 2 ) + u ( t ) , ( y 1 ( 0 ) , y 2 ( 0 ) ) = ( x 1 , x 2 ) , \begin{cases}
\dot{y}_1(t)=y_2(t),\\
\dot{y}_2(t)=-y_1(t)+y_2(t)\left(1-y_1(t)^2\right)+u(t),\\
(y_1(0),y_2(0))=(x_1,x_2),
\end{cases} ⎩ ⎨ ⎧ y ˙ 1 ( t ) = y 2 ( t ) , y ˙ 2 ( t ) = − y 1 ( t ) + y 2 ( t ) ( 1 − y 1 ( t ) 2 ) + u ( t ) , ( y 1 ( 0 ) , y 2 ( 0 )) = ( x 1 , x 2 ) ,
where we set β = 0.1 \beta=0.1 β = 0.1 , T = 3 T=3 T = 3 , ℓ T ≡ 0 \ell_T\equiv0 ℓ T ≡ 0 , and the spatial domain Ω = [ − 3 , 3 ] 2 \Omega=[-3,3]^2 Ω = [ − 3 , 3 ] 2 .
Model-based setting. According to Definition 4.6, given the current approximation V ^ ( k ) \widehat{V}^{(k)} V ( k ) , for each candidate basis function ϕ j ( x ) \phi_j(\mathbf{x}) ϕ j ( x ) with index j ∈ Λ ( k ) j\in\Lambda^{(k)} j ∈ Λ ( k ) , the selection indicator e j , H J B ( k ) e_{j,\mathrm{HJB}}^{(k)} e j , HJB ( k ) is defined with
a k ( x ) = ( − x 1 + x 2 ( 1 − x 1 2 ) − 1 2 β ∂ x 2 V ^ ( k ) ( x ) , x 2 1 ) \mathbf{a}_k(\mathbf{x})=\left(-x_1+x_2\left(1-x_1^2\right)-\frac{1}{2\beta}\partial_{x_2}\widehat{V}^{(k)}(\mathbf{x}),\frac{x_2}{\phantom{1}}\right) a k ( x ) = ( − x 1 + x 2 ( 1 − x 1 2 ) − 2 β 1 ∂ x 2 V ( k ) ( x ) , 1 x 2 )
R ( V ^ ( k ) ) ( x ) = − 1 4 β ( ∂ x 2 V ^ ( k ) ( x ) ) 2 + ∂ x 1 V ^ ( k ) ( x ) x 2 + ∂ x 2 V ^ ( k ) ( x ) ( − x 1 + x 2 ( 1 − x 1 2 ) ) + x 1 2 + x 2 2 . R\left(\widehat{V}^{(k)}\right)(\mathbf{x})=-\frac{1}{4\beta}\left(\partial_{x_2}\widehat{V}^{(k)}(\mathbf{x})\right)^2+\partial_{x_1}\widehat{V}^{(k)}(\mathbf{x})x_2+\partial_{x_2}\widehat{V}^{(k)}(\mathbf{x})\left(-x_1+x_2\left(1-x_1^2\right)\right)+x_1^2+x_2^2. R ( V ( k ) ) ( x ) = − 4 β 1 ( ∂ x 2 V ( k ) ( x ) ) 2 + ∂ x 1 V ( k ) ( x ) x 2 + ∂ x 2 V ( k ) ( x ) ( − x 1 + x 2 ( 1 − x 1 2 ) ) + x 1 2 + x 2 2 .
We compare the performance of the time-dependent Galerkin method with two basis selection strategies: random selection and greedy selection using the residual-decay indicator. In both cases, we consider either a hyperbolic cross basis with index J = 4 \mathcal{J}=4 J = 4 (with a total of P = 52 P=52 P = 52 basis functions) or a total degree basis with maximum degree M = 8 M=8 M = 8 (with P = 45 P=45 P = 45 basis functions), both generated by Legendre polynomials. The initial basis function is selected as the constant basis. The results for random basis selection are averaged over 100 Monte Carlo simulations, while the greedy selection is deterministic when the initial basis is fixed. The validation error is computed over 1000 validation data points.
To study the error decay with respect to the number of selected basis functions, we set k max = P k_{\max}=P k m a x = P , which is the size of the whole candidate basis set. From Figure 2 , we observe that greedy selection
Figure 2. Error decay of Algorithm 1 (model-based basis selection, no data) using the time-dependent Galerkin method for the 2-dimensional Van der Pol oscillator optimal control problem, comparing random and adaptive basis selection strategies.
consistently outperforms random selection. Notably, greedy selection achieves the same accuracy level with substantially fewer basis functions, thus improving efficiency by preferentially selecting the most informative basis elements. With the hyperbolic cross basis, greedy selection reaches the accuracy of the full basis with only 16 of the 52 candidates, and with the total degree basis with 25 of the 45 candidates.
Data-driven setting. We now solve the same optimal control problem using the supervised learning framework. Here, training data are used both to fit the model and to compute the supervised loss guiding basis selection. We compare several strategies for jointly selecting data samples and basis functions.
All experiments are initialized with a single randomly selected basis function and data point. In Figure 3 , the bottom x x x -axis indicates the number of selected basis functions, while the top x x x -axis shows the number of selected training data points. We also take μ \mu μ to be the uniform empirical measure over the sample set.
Figure 3. Comparison of adaptive basis and data selection strategies using a hyperbolic cross basis with index J = 4 \mathcal{J}=4 J = 4 , generated by Legendre polynomials, k max = P = 52 k_{\max}=P=52 k m a x = P = 52 . Basis functions are selected using the supervised-loss basis indicator. LASSO regression with λ = 10 − 4 \lambda=10^{-4} λ = 1 0 − 4 is applied. Results are averaged over 100 independent runs. The shaded regions indicate one standard deviation around the mean validation error curves on a logarithmic scale.
The proposed adaptive basis and data selection strategy is particularly advantageous in the following scenarios: i) Expensive data generation. When obtaining new data points is costly (e.g., via high-fidelity simulations or experiments), it is natural to compare greedy and random basis selection under random data selection, as in Figure 3 (c)–(Figure 3 d). This setup reflects a realistic scenario in which data are generated incrementally until sufficiently informative. In this case, adaptive basis selection reaches a prescribed accuracy threshold with fewer data points than random selection, thereby improving data efficiency.
ii) Representative data selection. When a large dataset is already available, computational constraints may render it impractical to use the entire set for training or basis updates. An adaptive selection procedure instead identifies a representative subset of data points, together with the most informative basis functions. As shown in Figure 3 (a)–(Figure 3 b), adaptive data selection alone provides limited improvement, whereas adaptive basis selection has a significantly greater impact on overall performance, highlighting its critical role in the approximation process.
Based on these results, we next activate the early stopping criterion in the adaptive selection procedure, further reducing computational cost while maintaining the desired accuracy. The corresponding results are shown in Figure 4 . With ε b a s i s = 0.05 \varepsilon_{\mathrm{basis}} = 0.05 ε basis = 0.05 and ε d a t a = 0.1 \varepsilon_{\mathrm{data}} = 0.1 ε data = 0.1 , Algorithm 2 stops on average after 19 basis functions and 16 training samples, that is, only a small subset of the candidate dictionary, while attaining a validation error comparable to that obtained with the full candidate set.
Figure 4. Error decay of Algorithm 2 for the 2-dimensional Van der Pol oscillator optimal control problem with early-stop criteria ε b a s i s = 0.05 \varepsilon_{\mathrm{basis}} = 0.05 ε basis = 0.05 and ε d a t a = 0.1 \varepsilon_{\mathrm{data}} = 0.1 ε data = 0.1 . Once the maximum absolute value of indicator/score falls below ε \varepsilon ε , no further basis functions or data points are added. The vertical lines marks the average stopping point, occurring at 19.54 basis functions and 16.23 data points. Basis functions are selected using the supervised-loss basis indicator.
Rigid body model of a satellite
We now study a six-state rigid body model of a satellite [31 , 32 ] . The state of the satellite is written as
y ( t ) = [ y 1 y 2 y 3 y 4 y 5 y 6 ] T , y r : = [ y 1 y 2 y 3 ] T , y ω : = [ y 4 y 5 y 6 ] T , \mathbf{y}(t) = [y_1\ y_2\ y_3\ y_4\ y_5\ y_6]^{\mathsf{T}},\quad\mathbf{y}_{r} := [y_1\ y_2\ y_3]^{\mathsf{T}},\quad\mathbf{y}_{\omega} := [y_4\ y_5\ y_6]^{\mathsf{T}}, y ( t ) = [ y 1 y 2 y 3 y 4 y 5 y 6 ] T , y r := [ y 1 y 2 y 3 ] T , y ω := [ y 4 y 5 y 6 ] T ,
where y r y_r y r denotes attitude (rotation angles) and y ω y_\omega y ω the angular velocity in the body-frame. The control input is a torque u = ( u 1 u 2 u 3 ) T \mathbf{u}=(u_1\ u_2\ u_3)^{\mathsf{T}} u = ( u 1 u 2 u 3 ) T . The optimal control problem is given by
min u ∈ L 2 ( 0 , T ; R 3 ) ∫ 0 T ( α 1 ∥ y r ( t ) ∥ 2 2 + α 2 ∥ y ω ( t ) ∥ 2 2 + β ∥ u ( t ) ∥ 2 2 ) d t + α 3 ∥ y ( T ) ∥ 2 2 (30) \min_{\mathbf{u}\in L^2(0,T;\mathbb{R}^3)}\int_0^T\left(\alpha_1\|\mathbf{y}_r(t)\|_2^2+\alpha_2\|\mathbf{y}_\omega(t)\|_2^2+\beta\|\mathbf{u}(t)\|_2^2\right)\,\mathrm{d}t+\alpha_3\|\mathbf{y}(T)\|_2^2 \tag*{(30)} u ∈ L 2 ( 0 , T ; R 3 ) min ∫ 0 T ( α 1 ∥ y r ( t ) ∥ 2 2 + α 2 ∥ y ω ( t ) ∥ 2 2 + β ∥ u ( t ) ∥ 2 2 ) d t + α 3 ∥ y ( T ) ∥ 2 2 (30)
subject to
{ y ˙ r ( t ) = E ( y r ( t ) ) y ω ( t ) , y ˙ ω ( t ) = W S ( y ω ( t ) ) R ( y r ( t ) ) h + W B u ( t ) , y ( 0 ) = x , (31) \begin{cases}
\dot{\mathbf{y}}_r(t)=\mathbf{E}(\mathbf{y}_r(t))\mathbf{y}_\omega(t),\\
\dot{\mathbf{y}}_\omega(t)=\mathbf{W}\mathbf{S}(\mathbf{y}_\omega(t))\mathbf{R}(\mathbf{y}_r(t))\mathbf{h}+\mathbf{W}\mathbf{B}\mathbf{u}(t),\\
\mathbf{y}(0)=\mathbf{x}, \tag*{(31)}
\end{cases} ⎩ ⎨ ⎧ y ˙ r ( t ) = E ( y r ( t )) y ω ( t ) , y ˙ ω ( t ) = WS ( y ω ( t )) R ( y r ( t )) h + WBu ( t ) , y ( 0 ) = x , (31)
where α 1 , α 2 , α 3 , β > 0 \alpha_1,\alpha_2,\alpha_3,\beta>0 α 1 , α 2 , α 3 , β > 0 and the matrices E ( y r ) \mathbf{E}(\mathbf{y}_r) E ( y r ) , S ( y ω ) \mathbf{S}(\mathbf{y}_\omega) S ( y ω ) , R ( y r ) ∈ R 3 × 3 \mathbf{R}(\mathbf{y}_r)\in\mathbb{R}^{3\times3} R ( y r ) ∈ R 3 × 3 are given by
E ( y r ) : = ( 1 sin y 1 tan y 2 cos y 1 tan y 2 0 cos y 1 − sin y 1 0 sin y 1 / cos y 2 cos y 1 / cos y 2 ) , S ( y ω ) : = ( 0 y 6 − y 5 − y 6 0 y 4 y 5 − y 4 0 ) , \mathbf{E}(\mathbf{y}_r):=
\begin{pmatrix}
1 & \sin y_1\tan y_2 & \cos y_1\tan y_2\\
0 & \cos y_1 & -\sin y_1\\
0 & \sin y_1/\cos y_2 & \cos y_1/\cos y_2
\end{pmatrix},
\qquad
\mathbf{S}(\mathbf{y}_\omega):=
\begin{pmatrix}
0 & y_6 & -y_5\\
-y_6 & 0 & y_4\\
y_5 & -y_4 & 0
\end{pmatrix}, E ( y r ) := 1 0 0 sin y 1 tan y 2 cos y 1 sin y 1 / cos y 2 cos y 1 tan y 2 − sin y 1 cos y 1 / cos y 2 , S ( y ω ) := 0 − y 6 y 5 y 6 0 − y 4 − y 5 y 4 0 ,
and
R ( y r ) : = ( cos y 2 cos y 3 cos y 2 sin y 3 − sin y 2 sin y 1 sin y 2 cos y 3 − cos y 1 sin y 3 sin y 1 sin y 2 sin y 3 + cos y 1 cos y 3 cos y 2 sin y 1 cos y 1 sin y 2 cos y 3 + sin y 1 sin y 3 cos y 1 sin y 2 sin y 3 − sin y 1 cos y 3 cos y 2 cos y 1 ) . \mathbf{R}(\mathbf{y}_r):=
\begin{pmatrix}
\cos y_2\cos y_3 & \cos y_2\sin y_3 & -\sin y_2\\
\sin y_1\sin y_2\cos y_3-\cos y_1\sin y_3 & \sin y_1\sin y_2\sin y_3+\cos y_1\cos y_3 & \cos y_2\sin y_1\\
\cos y_1\sin y_2\cos y_3+\sin y_1\sin y_3 & \cos y_1\sin y_2\sin y_3-\sin y_1\cos y_3 & \cos y_2\cos y_1
\end{pmatrix}. R ( y r ) := cos y 2 cos y 3 sin y 1 sin y 2 cos y 3 − cos y 1 sin y 3 cos y 1 sin y 2 cos y 3 + sin y 1 sin y 3 cos y 2 sin y 3 sin y 1 sin y 2 sin y 3 + cos y 1 cos y 3 cos y 1 sin y 2 sin y 3 − sin y 1 cos y 3 − sin y 2 cos y 2 sin y 1 cos y 2 cos y 1 .
The constant matrices W ∈ R 3 × 3 \mathbf{W}\in\mathbb{R}^{3\times3} W ∈ R 3 × 3 , h ∈ R 3 \mathbf{h}\in\mathbb{R}^3 h ∈ R 3 , and B ∈ R 3 × 3 \mathbf{B}\in\mathbb{R}^{3\times3} B ∈ R 3 × 3 are
W : = ( 1 2 0 0 0 1 3 0 0 0 1 4 ) , h : = ( 1 1 1 ) , B : = ( 1 1 20 1 10 1 15 1 1 10 1 10 1 15 1 ) . \mathbf{W}:=
\begin{pmatrix}
\frac{1}{2} & 0 & 0\\
0 & \frac{1}{3} & 0\\
0 & 0 & \frac{1}{4}
\end{pmatrix},
\qquad
\mathbf{h}:=
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix},
\qquad
\mathbf{B}:=
\begin{pmatrix}
1 & \frac{1}{20} & \frac{1}{10}\\
\frac{1}{15} & 1 & \frac{1}{10}\\
\frac{1}{10} & \frac{1}{15} & 1
\end{pmatrix}. W := 2 1 0 0 0 3 1 0 0 0 4 1 , h := 1 1 1 , B := 1 15 1 10 1 20 1 1 15 1 10 1 10 1 1 .
and x : = ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) T \mathbf{x}:=(x_1,x_2,x_3,x_4,x_5,x_6)^{\mathsf{T}} x := ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) T is the initial condition with domain Ω = [ − π 3 , π 3 ] 3 × [ − π 4 , π 4 ] 3 \Omega=[-\frac{\pi}{3},\frac{\pi}{3}]^3\times[-\frac{\pi}{4},\frac{\pi}{4}]^3 Ω = [ − 3 π , 3 π ] 3 × [ − 4 π , 4 π ] 3 . We set α 1 = 1 2 \alpha_1=\frac{1}{2} α 1 = 2 1 , α 2 = 5 \alpha_2=5 α 2 = 5 , α 3 = 1 2 \alpha_3=\frac{1}{2} α 3 = 2 1 , β = 1 4 \beta=\frac{1}{4} β = 4 1 , and T = 20 T=20 T = 20 . This is an instance of (4) with running cost ℓ ( y ) = α 1 ∥ y r ∥ 2 2 + α 2 ∥ y ω ∥ 2 2 \ell(\mathbf{y})=\alpha_1\|\mathbf{y}_r\|_2^2+\alpha_2\|\mathbf{y}_\omega\|_2^2 ℓ ( y ) = α 1 ∥ y r ∥ 2 2 + α 2 ∥ y ω ∥ 2 2 and terminal penalty ℓ T ( y ) = α 3 ∥ y ∥ 2 2 \ell_T(\mathbf{y})=\alpha_3\|\mathbf{y}\|_2^2 ℓ T ( y ) = α 3 ∥ y ∥ 2 2 .
For this problem, we focus on the supervised learning framework. Note that, in the present setting, the adaptive basis-selection strategies (Figure 5 (a) and (c)) are initialized with a small active set and reach the satisfactory accuracy after roughly 10 2 10^2 1 0 2 iterations, while the non-adaptive basis baselines (Figure 5 (b) and (d)) attain a comparable error level only once a substantial fraction of the P = 537 P=537 P = 537 candidate functions has been included, and are therefore plotted over the correspondingly larger range.
Figure 5. (a) Basis selection + data selection (b) Random basis + data selection (c) Basis selection + random data (d) Random basis + random data. Comparison of adaptive basis and data selection strategies using a hyperbolic cross basis with index J ^ = 4 \widehat{J} = 4 J = 4 (the cardinality of the generated basis is 537), generated by Legendre polynomials. Basis functions are selected using the supervised-loss basis indicator. Coefficients are computed by LASSO regression with λ = 10 − 4 \lambda= 10^{-4} λ = 1 0 − 4 . Results are averaged over 100 independent runs, the validation error is computed over 1000 validation points.
35-dimensional infinite-horizon optimal control problem
To further assess the performance of the proposed adaptive basis and data selection strategy in higher dimensions, we consider an infinite-horizon optimal control problem with a known exact solution.
We consider the infinite-horizon problem (1) with m = d m=d m = d , q ( x ) = I d \mathbf{q}(\mathbf{x})=\mathbf{I}_d q ( x ) = I d , and linear dynamics f ( x ) = ( f 1 ( x ) , … , f d ( x ) ) T \mathbf{f}(\mathbf{x})=(f_1(\mathbf{x}),\ldots,f_d(\mathbf{x}))^{\mathsf{T}} f ( x ) = ( f 1 ( x ) , … , f d ( x ) ) T given by
f i ( x ) = − κ i x i , κ i = 0.3 + 0.5 ( i − 1 ) d − 1 , i = 1 , … , d . f_i(\mathbf{x})=-\kappa_i x_i,\qquad\kappa_i=0.3+\frac{0.5(i-1)}{d-1},\qquad i=1,\ldots,d. f i ( x ) = − κ i x i , κ i = 0.3 + d − 1 0.5 ( i − 1 ) , i = 1 , … , d .
The computational domain is Ω = [ − 1 , 1 ] d \Omega=[-1,1]^d Ω = [ − 1 , 1 ] d , and in this experiment we take d = 35 d=35 d = 35 and β = 1 \beta=1 β = 1 . We prescribe the exact value function
V ( x ) = 1 + ∑ i = 1 6 ρ i x i 2 + ∑ i = 1 6 η i x i 3 + 0.08 ∑ i = 1 5 x i x i + 1 , x ∈ Ω , V(\mathbf{x})=1+\sum_{i=1}^{6}\rho_i x_i^2+\sum_{i=1}^{6}\eta_i x_i^3+0.08\sum_{i=1}^{5}x_i x_{i+1},\qquad\mathbf{x}\in\Omega, V ( x ) = 1 + i = 1 ∑ 6 ρ i x i 2 + i = 1 ∑ 6 η i x i 3 + 0.08 i = 1 ∑ 5 x i x i + 1 , x ∈ Ω ,
where ρ i = 1.2 − 0.13 ( i − 1 ) \rho_i = 1.2 - 0.13(i - 1) ρ i = 1.2 − 0.13 ( i − 1 ) and η i = 0.06 ( 1 − 0.11 ( i − 1 ) ) \eta_i = 0.06(1 - 0.11(i - 1)) η i = 0.06 ( 1 − 0.11 ( i − 1 )) for i = 1 , … , 6 i = 1,\ldots,6 i = 1 , … , 6 , and ℓ ( x ) \ell(x) ℓ ( x ) is chosen accordingly. This test yields a smooth solution and admits a sparse representation in the polynomial basis.
Training and validation datasets are generated by sampling points uniformly from Ω \Omega Ω . We use the hyperbolic cross basis with index J ^ = 3 \widehat{J} = 3 J = 3 , generated by Legendre polynomials. The adaptive method is initialized with 10 randomly selected training samples and the constant basis function, and performs 50 iterations, each adding one training sample and one basis function. After each enrichment step, the coefficients are recomputed on the current active basis and data sets using LASSO regression with regularization parameter λ = 10 − 8 \lambda= 10^{-8} λ = 1 0 − 8 . For basis selection, we compare the supervised-loss indicator (24) , with weights ω 1 = 1 \omega_1 = 1 ω 1 = 1 and ω 2 = 1 / d \omega_2 = 1/d ω 2 = 1/ d , and the empirical residual-decay indicator (26) . Each is combined with either the data score (27) or random sampling for data selection. As a baseline, we also fit the full basis on the same randomly selected training samples.
It can be seen from Figure 6 that, when combined with the data score (27) , both basis indicators achieve an error decay comparable to the full-basis regression, which uses the full candidate dictionary of P = 10396 P = 10396 P = 10396 basis functions. Notably, the adaptive strategy attains similar accuracy with an active subspace of only 51 basis functions, demonstrating its computational efficiency in high-dimensional settings. In contrast, when the training samples are selected at random, the error decays more slowly for both indicators.
Figure 6. Validation error decay for the stationary HJB problem with d = 35 d = 35 d = 35 . In (a)–(d), Algorithm 2 starts from 10 random training samples and the constant basis function, and adds one sample and one basis function per iteration. Basis functions are selected with the supervised-loss indicator (24) in (a)–(b), and with the empirical residual-decay indicator (26) in (c)–(d). Training samples are selected with the data score (27) in (a) and (c), and at random in (b) and (d). Subfigure (e) shows the full-basis baseline, which uses all 10396 basis functions, with training samples selected randomly from the same initial size.
Conclusion
We have introduced two adaptive strategies for approximating PDE solutions in both model-based and data-driven regimes, with a particular emphasis on high-dimensional nonlinear HJB equations. The Galerkin framework utilizes a closed-form residual-decay indicator to greedily enrich the basis. The supervised learning framework combines greedy basis expansion with adaptive selection of gradient-augmented training samples driven by a supervised loss, focusing computational effort on the most informative data points. Across numerical experiments on benchmark and control problems, both frameworks achieve accurate solutions with substantially fewer basis functions and far fewer data points (or without data).
These proposed residual-decay indicators, derived from a dual-weighted residual argument via single-direction orthogonal projection, effectively guide basis and data selection in high-dimensional settings. Unlike classical goal-oriented DWR estimators, which aim to control the error in a user-specified functional of physical interest, our indicators are not designed as rigorous a posteriori error estimators. Instead, they provide simple and computationally efficient criteria for adaptive basis enrichment. As a consequence, the predicted residual decay does not necessarily coincide with the actual reduction in approximation error, even though it proves highly effective in practice.
Several directions remain for future work. These include developing quantitative stopping criteria for adaptive basis and data selection, and extending the current single-direction enrichment strategy to multi-direction updates, in which batches of basis functions are selected at each iteration, potentially improving both numerical performance and overall efficiency.
Acknowledgments
Y.H. is supported by a Research Fellowship from the Royal Commission for the Exhibition of 1851. D.K. is supported by the Air Force Office of Scientific Research under award number FA8655-26-1-B011. Y.Z. is supported by the National Science Foundation under DMS award number 2529107.