Introduction
Optimal control problems governed by partial differential equations (PDEs) are ubiquitous in computational science and engineering, and both a mature theory and a large body of numerical methods are available in the deterministic case [35 , 14 ] . Pointwise control bounds a ≤ u ≤ b a \le u \le b a ≤ u ≤ b change the picture. The first-order conditions are no longer a system of equations but a variational inequality, or equivalently a nonsmooth equation built from the metric projection onto the admissible box [20 , 15 ] . Three consequences follow. First, although the reduced objective is strongly convex, the resulting Karush–Kuhn–Tucker (KKT) system is nondifferentiable, so classical Newton methods do not apply. Second, the set of indices at which the bounds are attained—the active set—is not known in advance and must be discovered as part of the solution process. Third, the standard remedies—penalization, interior-point regularization, smoothing—replace the exact constraint by an approximation governed by an additional parameter, and recover it only in the limit.
In the deterministic problem, the primal–dual active set (PDAS) strategy of Bergounioux, Ito and Kunisch [9 ] treats the bounds exactly by alternating between a prediction of the active set and the solution of an equality-constrained subproblem. Hintermüller, Ito and Kunisch [18 ] subsequently showed that PDAS is precisely a semismooth Newton (SSN) method for the projection-based reformulation, which explains its local superlinear and mesh-independent convergence [11 , 28 , 30 , 36 , 19 ] .
In most applications the PDE coefficients are uncertain and are modelled by random fields and lead to optimal control problems under uncertainty [27 ] . The random variable may be discretized by sampling, by stochastic collocation [10 , 21 , 22 , 34 ] , or by stochastic Galerkin (SG) projection onto a global orthogonal polynomial basis [16 , 39 , 23 , 26 , 4 , 24 , 32 ] . We use SG, which yields a single coupled system: the discrete state operator is a sum of Kronecker products, and state and adjoint interact across all stochastic modes.
Combining pointwise constraints with random coefficients is harder than treating either feature alone. For control constraints, the projection onto the box is available in closed form and need not be regularized, yet stochastic Galerkin discretizations of such problems have been studied mainly from the approximation side: Shen et al. [33 ] derive a priori error estimates for obstacle-type control constraints, and Winkler and Yücel [38 ] combine error estimates for a Dirichlet boundary control problem with a primal–dual active set solver and block-diagonal preconditioning. There, the control is deterministic and acts on ∂ D \partial D ∂ D , so the active set stays decoupled from the stochastic tensor structure. Solvers for stochastic control problems are developed in [8 , 6 , 1 , 25 , 3 , 2 , 7 ] . None of them treats control constraints.
An alternative is the Fenchel duality viewpoint, where the dual absorbs the constraint into the objective. Clason and Kunisch [12 ] found the duals of certain unconstrained elliptic control problems structurally more favourable than the primal problems, and Wang et al. [37 ] derived the Fenchel dual of a linear parabolic problem with box constraints on the control, in which the constraints are embedded in an unconstrained, differentiable dual objective, and solved it by conjugate gradients and by semismooth Newton. They also identified the obstacle that reappears here: semismooth Newton applied to the primal problem treats the box and the PDE constraint simultaneously, so the varying active set changes the structure of the Newton equation and the preconditioner has to be adjusted at every step. In the stochastic setting, this obstacle is sharper: control values are indexed by pairs of a spatial node and a quadrature point, so the active-set term of the Jacobian matrix has no Kronecker structure. A preconditioner containing it exactly must be rebuilt at every step, whereas a mean-based Kronecker preconditioner is cheap but blind to the location of the free set.
In this paper, we develop a dual-based SSN framework for optimal control problems governed by elliptic PDEs with random coefficients and pointwise box constraints on the control. We derive the Fenchel dual in Bochner spaces over the parameter domain, which absorbs the control constraints into an unconstrained dual objective in the adjoint variable, and establish the corresponding optimality system and primal–dual recovery relations. After stochastic Galerkin–finite element discretization, we derive the exact finite-dimensional dual and solve the resulting reduced equation directly by a matrix-free semismooth Newton–PCG method, in which the box projection is retained exactly, and no outer iteration, penalty, or smoothing parameter is required. To handle the active set, which changes at every Newton step, we analyze a current-set preconditioner P W P_W P W that places the current active-set correction beside a mean-based reference operator and applies its inverse exactly through the Sherman–Morrison–Woodbury (SMW) identity [17 ] . For numerical implementation, we use a cheap approximation P k P_k P k of the preconditioner P W P_W P W , which keeps only the fraction of free control values, and its application needs one sparse Cholesky factor of a spatial matrix, which is reused across Newton steps.
The remainder of the paper is organized as follows. Section 2-3 presents the problem and derives the Fenchel dual and the optimality system. Section 4 gives the SG-FE discretization and its exact dual. Section 5 develops the direct SSN–PCG method and the spectral analysis of the current-set preconditioner P W P_W P W . Section 6 specifies the practical preconditioner P k P_k P k and reports the numerical experiments. Section 7 draws conclusions and discusses future work.
Problem formulation and well-posedness
The optimal control problem
Let D ⊂ R d D \subset\mathbb{R}^{d} D ⊂ R d , d ∈ { 1 , 2 , 3 } d \in\{1,2,3\} d ∈ { 1 , 2 , 3 } , be a bounded Lipschitz domain with Poincaré constant C P C_{P} C P , that is, ∥ v ∥ L 2 ( D ) ≤ C P ∥ ∇ v ∥ L 2 ( D ) d \lVert v\rVert_{L^{2}(D)} \le C_{P}\lVert\nabla v\rVert_{L^{2}(D)^{d}} ∥ v ∥ L 2 ( D ) ≤ C P ∥ ∇ v ∥ L 2 ( D ) d for all v ∈ H 0 1 ( D ) v \in H_{0}^{1}(D) v ∈ H 0 1 ( D ) , let ξ = ( ξ 1 , … , ξ K ) : ( Ω , F , P ) → R K \xi= (\xi_{1},\ldots,\xi_{K}):(\Omega,\mathcal{F},\mathbb{P}) \to\mathbb{R}^{K} ξ = ( ξ 1 , … , ξ K ) : ( Ω , F , P ) → R K , K < ∞ K < \infty K < ∞ , be a random vector with image Γ ξ : = ξ ( Ω ) \Gamma_{\xi} := \xi(\Omega) Γ ξ := ξ ( Ω ) , and let ( Γ ξ , B , ρ ) (\Gamma_{\xi},\mathcal{B},\rho) ( Γ ξ , B , ρ ) be the induced parameter probability space, where B \mathcal{B} B is the Borel σ \sigma σ -algebra on Γ ξ \Gamma_{\xi} Γ ξ and ρ : = P ∘ ξ − 1 \rho:= \mathbb{P} \circ\xi^{-1} ρ := P ∘ ξ − 1 is the law of ξ \xi ξ . Let y y y denote the state and u u u the control, and set
V = H 0 1 ( D ) , H = L 2 ( D ) , V = L ρ 2 ( Γ ξ ; V ) , H = L ρ 2 ( Γ ξ ; H ) , V = H_{0}^{1}(D), \qquad H = L^{2}(D), \qquad\mathbb{V} = L_{\rho}^{2}(\Gamma_{\xi};V), \qquad\mathbb{H} = L_{\rho}^{2}(\Gamma_{\xi};H), V = H 0 1 ( D ) , H = L 2 ( D ) , V = L ρ 2 ( Γ ξ ; V ) , H = L ρ 2 ( Γ ξ ; H ) ,
where the norms and inner products on V \mathbb{V} V and H \mathbb{H} H include the expectation with respect to ρ \rho ρ . We equip V \mathbb{V} V with the norm ∥ v ∥ V : = ∥ ∇ v ∥ L 2 ( D ) d \lVert v\rVert_{\mathbb{V}} := \lVert\nabla v\rVert_{L^{2}(D)^{d}} ∥ v ∥ V := ∥ ∇ v ∥ L 2 ( D ) d , so that ∥ v ∥ V 2 = ∫ Γ ξ ∥ ∇ v ( ξ ) ∥ L 2 ( D ) d 2 d ρ ( ξ ) \lVert v\rVert_{\mathbb{V}}^{2} = \int_{\Gamma_{\xi}}\lVert\nabla v(\xi)\rVert_{L^{2}(D)^{d}}^{2}\,d\rho(\xi) ∥ v ∥ V 2 = ∫ Γ ξ ∥ ∇ v ( ξ ) ∥ L 2 ( D ) d 2 d ρ ( ξ ) and ∥ v ∥ H ≤ C P ∥ v ∥ V \lVert v\rVert_{\mathbb{H}} \le C_{P}\lVert v\rVert_{\mathbb{V}} ∥ v ∥ H ≤ C P ∥ v ∥ V for v ∈ V v \in\mathbb{V} v ∈ V . Given a desired state y d ∈ H y_{d} \in\mathbb{H} y d ∈ H , a regularization parameter γ > 0 \gamma> 0 γ > 0 , finite bounds a < b a < b a < b , and a random diffusion coefficient κ \kappa κ , the problem studied in this paper is
min y , u 1 2 ∫ Γ ξ ∫ D ∣ y ( x , ξ ) − y d ( x , ξ ) ∣ 2 d x d ρ ( ξ ) + γ 2 ∫ Γ ξ ∫ D ∣ u ( x , ξ ) ∣ 2 d x d ρ ( ξ ) subject to − ∇ ⋅ ( κ ( x , ξ ) ∇ y ( x , ξ ) ) = u ( x , ξ ) in D × Γ ξ , y ( x , ξ ) = 0 on ∂ D × Γ ξ , a ≤ u ( x , ξ ) ≤ b ( d x ⊗ d ρ ) -a.e. (1) \begin{aligned}
\min_{y,u}\quad&\frac{1}{2}\int_{\Gamma_{\xi}}\int_{D}\lvert y(x,\xi)-y_{d}(x,\xi)\rvert^{2}\,dx\,d\rho(\xi)
+\frac{\gamma}{2}\int_{\Gamma_{\xi}}\int_{D}\lvert u(x,\xi)\rvert^{2}\,dx\,d\rho(\xi)\\
\text{subject to}\quad&-\nabla\cdot\bigl(\kappa(x,\xi)\nabla y(x,\xi)\bigr)=u(x,\xi) \quad\text{in }D\times\Gamma_{\xi},\\
&y(x,\xi)=0 \quad\text{on }\partial D\times\Gamma_{\xi},\\
&a\le u(x,\xi)\le b \quad(dx\otimes d\rho)\text{-a.e.} \tag*{(1)}
\end{aligned} y , u min subject to 2 1 ∫ Γ ξ ∫ D ∣ y ( x , ξ ) − y d ( x , ξ ) ∣ 2 d x d ρ ( ξ ) + 2 γ ∫ Γ ξ ∫ D ∣ u ( x , ξ ) ∣ 2 d x d ρ ( ξ ) − ∇ ⋅ ( κ ( x , ξ ) ∇ y ( x , ξ ) ) = u ( x , ξ ) in D × Γ ξ , y ( x , ξ ) = 0 on ∂ D × Γ ξ , a ≤ u ( x , ξ ) ≤ b ( d x ⊗ d ρ ) -a.e. (1)
Both integrals are taken with respect to the product of the Lebesgue measure on D D D and the probability measure ρ \rho ρ ; so, the objective in (1) is exactly
1 2 ∥ y − y d ∥ H 2 + γ 2 ∥ u ∥ H 2 , \frac{1}{2}\lVert y-y_{d}\rVert_{\mathbb{H}}^{2}+\frac{\gamma}{2}\lVert u\rVert_{\mathbb{H}}^{2}, 2 1 ∥ y − y d ∥ H 2 + 2 γ ∥ u ∥ H 2 ,
and we use this compact form from Section 3 3 3 onwards.
We note here that the bounds are imposed pointwise in the spatial and the parameter variables, so the admissible set
C = { u ∈ H : a ≤ u ( x , ξ ) ≤ b for ( d x ⊗ d ρ ) -a.e. ( x , ξ ) } (2) \mathcal{C}=\{u\in\mathbb{H}:a\le u(x,\xi)\le b\text{ for }(dx\otimes d\rho)\text{-a.e. }(x,\xi)\} \tag*{(2)} C = { u ∈ H : a ≤ u ( x , ξ ) ≤ b for ( d x ⊗ d ρ ) -a.e. ( x , ξ )} (2)
is a subset of the full Bochner space rather than of a deterministic space of controls. Since D D D and the parameter space carry finite measure, C \mathcal{C} C is nonempty, bounded, closed, and convex in H \mathbb{H} H .
The state operator and the reduced problem
Assume that κ \kappa κ is jointly measurable, symmetric, and uniformly elliptic:
0 < κ − ≤ κ ( x , ξ ) ≤ κ + < ∞ , (3) 0<\kappa_{-}\le\kappa(x,\xi)\le\kappa_{+}<\infty, \tag*{(3)} 0 < κ − ≤ κ ( x , ξ ) ≤ κ + < ∞ , (3)
for all η ∈ R d \eta\in\mathbb{R}^{d} η ∈ R d and almost every ( x , ξ ) (x,\xi) ( x , ξ ) , with deterministic constants κ − \kappa_{-} κ − and κ + \kappa_{+} κ + . The weak form of the state equation in (1) is governed by the bilinear form
a ( y , v ) = ∫ Γ ξ ∫ D κ ( x , ξ ) ∇ y ( x , ξ ) ⋅ ∇ v ( x , ξ ) d x d ρ ( ξ ) . a(y,v)=\int_{\Gamma_{\xi}}\int_{D}\kappa(x,\xi)\nabla y(x,\xi)\cdot\nabla v(x,\xi)\,dx\,d\rho(\xi). a ( y , v ) = ∫ Γ ξ ∫ D κ ( x , ξ ) ∇ y ( x , ξ ) ⋅ ∇ v ( x , ξ ) d x d ρ ( ξ ) .
Theorem 2.1 (Lax–Milgram [35 ] ). Let W W W be a real Hilbert space and let t : W × W → R t:W\times W\to\mathbb{R} t : W × W → R be a bilinear form for which there are constants M ≥ α > 0 M\ge\alpha>0 M ≥ α > 0 such that
∣ t ( w , z ) ∣ ≤ M ∥ w ∥ W ∥ z ∥ W and t ( w , w ) ≥ α ∥ w ∥ W 2 ( w , z ∈ W ) . \lvert t(w,z)\rvert\le M\lVert w\rVert_{W}\lVert z\rVert_{W}
\quad\text{and}\quad
t(w,w)\ge\alpha\lVert w\rVert_{W}^{2}
\qquad(w,z\in W). ∣ t ( w , z )∣ ≤ M ∥ w ∥ W ∥ z ∥ W and t ( w , w ) ≥ α ∥ w ∥ W 2 ( w , z ∈ W ) .
Then, for every ℓ ∈ W ′ \ell\in W' ℓ ∈ W ′ , there is a unique z ∈ W z \in W z ∈ W such that
t ( z , w ) = ℓ ( w ) ( w ∈ W ) , t(z,w)=\ell(w) \qquad(w\in W), t ( z , w ) = ℓ ( w ) ( w ∈ W ) ,
and ∥ z ∥ W ≤ α − 1 ∥ ℓ ∥ W ′ \lVert z\rVert_W \le\alpha^{-1}\lVert\ell\rVert_{W'} ∥ z ∥ W ≤ α − 1 ∥ ℓ ∥ W ′ .
Proposition 2.2. Under (3) , for every u ∈ H u \in\mathbb{H} u ∈ H there is a unique y = S u ∈ V y=Su \in V y = S u ∈ V such that
a ( y , v ) = ( u , v ) H ( v ∈ V ) . (4) a(y,v)=(u,v)_{\mathbb{H}} \qquad(v\in V). \tag*{(4)} a ( y , v ) = ( u , v ) H ( v ∈ V ) . (4) The solution map
S : H ⟶ V ↪ H S:\mathbb{H}\longrightarrow V\hookrightarrow\mathbb{H} S : H ⟶ V ↪ H is bounded, linear, positive, injective, and self-adjoint as an operator on H \mathbb{H} H .
Proof. Boundedness and coercivity of a a a on V V V follow from (3) . Moreover,
∣ ( u , v ) H ∣ ≤ ∥ u ∥ H ∥ v ∥ H ≤ C P ∥ u ∥ H ∥ v ∥ V . \lvert(u,v)_{\mathbb{H}}\rvert\le\lVert u\rVert_{\mathbb{H}}\lVert v\rVert_{\mathbb{H}}\le C_P\lVert u\rVert_{\mathbb{H}}\lVert v\rVert_V. ∣( u , v ) H ∣ ≤ ∥ u ∥ H ∥ v ∥ H ≤ C P ∥ u ∥ H ∥ v ∥ V .
Theorem 2.1 therefore gives a unique solution and
∥ S u ∥ V ≤ C P κ − ∥ u ∥ H , ∥ S u ∥ H ≤ C P 2 κ − ∥ u ∥ H . \lVert Su\rVert_V\le\frac{C_P}{\kappa_-}\lVert u\rVert_{\mathbb{H}},\qquad
\lVert Su\rVert_{\mathbb{H}}\le\frac{C_P^2}{\kappa_-}\lVert u\rVert_{\mathbb{H}}. ∥ S u ∥ V ≤ κ − C P ∥ u ∥ H , ∥ S u ∥ H ≤ κ − C P 2 ∥ u ∥ H .
Linearity of S S S follows from uniqueness. For u 1 , u 2 ∈ H u_1,u_2\in\mathbb{H} u 1 , u 2 ∈ H and c 1 , c 2 ∈ R c_1,c_2\in\mathbb{R} c 1 , c 2 ∈ R , the bilinearity of a a a and of ( ⋅ , ⋅ ) H (\cdot,\cdot)_{\mathbb{H}} ( ⋅ , ⋅ ) H shows that c 1 S u 1 + c 2 S u 2 c_1Su_1+c_2Su_2 c 1 S u 1 + c 2 S u 2 solves (4) with right-hand side c 1 u 1 + c 2 u 2 c_1u_1+c_2u_2 c 1 u 1 + c 2 u 2 . By uniqueness, S ( c 1 u 1 + c 2 u 2 ) = c 1 S u 1 + c 2 S u 2 S(c_1u_1+c_2u_2)=c_1Su_1+c_2Su_2 S ( c 1 u 1 + c 2 u 2 ) = c 1 S u 1 + c 2 S u 2 , that is, S S S is linear. For f , g ∈ H f,g\in\mathbb{H} f , g ∈ H , utilizing the symmetry of this form, we obtain from the equation corresponding to S g Sg S g (with S f Sf S f ) and the equation corresponding to S f Sf S f (with S g Sg S g ) that
( S f , g ) H = ( g , S f ) H = a ( S g , S f ) = a ( S f , S g ) = ( f , S g ) H . (Sf,g)_{\mathbb{H}}=(g,Sf)_{\mathbb{H}}=a(Sg,Sf)=a(Sf,Sg)=(f,Sg)_{\mathbb{H}}. ( S f , g ) H = ( g , S f ) H = a ( S g , S f ) = a ( S f , S g ) = ( f , S g ) H .
Hence S ∗ = S S^*=S S ∗ = S . Moreover, ( S f , f ) H = a ( S f , S f ) ≥ 0 (Sf,f)_{\mathbb{H}}=a(Sf,Sf)\ge0 ( S f , f ) H = a ( S f , S f ) ≥ 0 , so S S S is positive. Finally, if S f = 0 Sf=0 S f = 0 , then (4) gives ( f , v ) H = 0 (f,v)_{\mathbb{H}}=0 ( f , v ) H = 0 for all v ∈ V v\in V v ∈ V . Since C ∞ ( D ) C^\infty(D) C ∞ ( D ) is dense in L 2 ( D ) L^2(D) L 2 ( D ) and H \mathbb{H} H -valued simple functions are dense in H \mathbb{H} H , the space V V V is dense in H \mathbb{H} H . Then f = 0 f=0 f = 0 , and S S S is injective.
Substituting y = S u y=Su y = S u eliminates the state from (1) and leaves the reduced primal problem
min u ∈ C J ( u ) = 1 2 ∥ S u − y d ∥ H 2 + γ 2 ∥ u ∥ H 2 , (5) \min_{u\in C}J(u)=\frac{1}{2}\lVert Su-y_d\rVert_{\mathbb{H}}^2+\frac{\gamma}{2}\lVert u\rVert_{\mathbb{H}}^2, \tag*{(5)} u ∈ C min J ( u ) = 2 1 ∥ S u − y d ∥ H 2 + 2 γ ∥ u ∥ H 2 , (5)
which is the form used throughout the paper.
Proposition 2.3 (Existence and uniqueness). Problem (5) has a unique minimizer u ∗ ∈ C u^*\in C u ∗ ∈ C . Consequently, with the state equation in (1) and the weak form (4) , ( S u ∗ , u ∗ ) ∈ V × C (Su^*,u^*)\in V\times C ( S u ∗ , u ∗ ) ∈ V × C is the unique solution of (1) .
Proof. The extended functional
j ( u ) = 1 2 ∥ S u − y d ∥ H 2 + γ 2 ∥ u ∥ H 2 + I C ( u ) , j(u)=\frac{1}{2}\lVert Su-y_d\rVert_{\mathbb{H}}^2+\frac{\gamma}{2}\lVert u\rVert_{\mathbb{H}}^2+I_C(u), j ( u ) = 2 1 ∥ S u − y d ∥ H 2 + 2 γ ∥ u ∥ H 2 + I C ( u ) ,
where I C I_C I C is the indicator function of C C C (0 on C C C and + ∞ +\infty + ∞ elsewhere), and it is proper, coercive, convex, and weakly lower semicontinuous. The direct method gives a minimizer. The term γ ∥ u ∥ H 2 / 2 \gamma\lVert u\rVert_{\mathbb{H}}^2/2 γ ∥ u ∥ H 2 /2 is strictly convex, so the minimizer is unique. By Proposition 2.2, the feasible pairs of (1) are exactly ( S u , u ) (Su,u) ( S u , u ) with u ∈ C u\in C u ∈ C , and the objective of (1) at such a pair equals J ( u ) J(u) J ( u ) ; this gives the second assertion.
Fenchel dual and the optimality system
The reduced problem (5) is a constrained minimization over C \mathcal{C} C . This section removes the constraint by dualization. We first compute the two convex conjugates, then invoke Fenchel–Rockafellar duality to obtain a dual problem in a residual variable, and finally change variables to the elliptic adjoint. The last form is the one the algorithm of Section 5 actually solves, and the recovery relations obtained at the end of the section are what return the state and the control once the adjoint is known.
The dual problem
To apply Fenchel–Rockafellar duality, we define F : H → ( − ∞ , ∞ ] F : \mathbb{H} \to(-\infty,\infty] F : H → ( − ∞ , ∞ ] and G : H → R G : \mathbb{H} \to\mathbb{R} G : H → R by
F ( u ) = γ 2 ∥ u ∥ H 2 + I C ( u ) , G ( z ) = 1 2 ∥ z − y d ∥ H 2 . F(u) = \frac{\gamma}{2}\lVert u\rVert_{\mathbb{H}}^2 + \mathcal{I}_{\mathcal{C}}(u), \qquad G(z) = \frac{1}{2}\lVert z-y_d\rVert_{\mathbb{H}}^2. F ( u ) = 2 γ ∥ u ∥ H 2 + I C ( u ) , G ( z ) = 2 1 ∥ z − y d ∥ H 2 .
Problem (5) can then be written as the unconstrained problem
inf u ∈ H { F ( u ) + G ( S u ) } . \inf_{u\in\mathbb{H}}\{F(u)+G(Su)\}. u ∈ H inf { F ( u ) + G ( S u )} .
The box constraint has been absorbed into F F F through the indicator I C \mathcal{I}_{\mathcal{C}} I C , so that both terms are now extended-real-valued convex functions on H \mathbb{H} H and no explicit feasible set remains. The next lemma shows that conjugation turns the indicator into a finite, differentiable function: this is the precise sense in which duality trades a constraint for smoothness.
Lemma 3.1 (Conjugates). For q , v ∈ H q,v\in\mathbb{H} q , v ∈ H ,
G ∗ ( q ) = 1 2 ∥ q ∥ H 2 + ( q , y d ) H , F ∗ ( v ) = ∫ Γ ϵ ∫ D ψ γ ( v ( x , ξ ) ) d x d ρ , G^*(q)=\frac{1}{2}\lVert q\rVert_{\mathbb{H}}^2+(q,y_d)_{\mathbb{H}}, \qquad F^*(v)=\int_{\Gamma_\epsilon}\int_D\psi_\gamma(v(x,\xi))\,dx\,d\rho, G ∗ ( q ) = 2 1 ∥ q ∥ H 2 + ( q , y d ) H , F ∗ ( v ) = ∫ Γ ϵ ∫ D ψ γ ( v ( x , ξ )) d x d ρ , where
ψ γ ( s ) = { a s − γ 2 a 2 , s < γ a , s 2 2 γ , γ a ≤ s ≤ γ b , b s − γ 2 b 2 , s > γ b . (6) \psi_\gamma(s)=
\begin{cases}
as-\dfrac{\gamma}{2}a^2, & s<\gamma a,\\
\dfrac{s^2}{2\gamma}, & \gamma a\le s\le\gamma b,\\
bs-\dfrac{\gamma}{2}b^2, & s>\gamma b.
\end{cases} \tag*{(6)} ψ γ ( s ) = ⎩ ⎨ ⎧ a s − 2 γ a 2 , 2 γ s 2 , b s − 2 γ b 2 , s < γ a , γ a ≤ s ≤ γ b , s > γ b . (6) Moreover,
ψ γ ′ ( s ) = Proj [ a , b ] ( s / γ ) . (7) \psi_\gamma'(s)=\operatorname{Proj}_{[a,b]}(s/\gamma). \tag*{(7)} ψ γ ′ ( s ) = Proj [ a , b ] ( s / γ ) . (7)
Proof. For G ∗ G^* G ∗ , the substitution w = z − y d w=z-y_d w = z − y d gives
sup z { ( q , z ) H − 1 2 ∥ z − y d ∥ H 2 } = ( q , y d ) H + sup w { ( q , w ) H − 1 2 ∥ w ∥ H 2 } . \sup_z\{(q,z)_{\mathbb{H}}-\tfrac{1}{2}\lVert z-y_d\rVert_{\mathbb{H}}^2\}=(q,y_d)_{\mathbb{H}}+\sup_w\{(q,w)_{\mathbb{H}}-\tfrac{1}{2}\lVert w\rVert_{\mathbb{H}}^2\}. z sup {( q , z ) H − 2 1 ∥ z − y d ∥ H 2 } = ( q , y d ) H + w sup {( q , w ) H − 2 1 ∥ w ∥ H 2 } .
For F ∗ F^* F ∗ , maximize the scalar function
s r − γ 2 r 2 sr-\frac{\gamma}{2}r^2 sr − 2 γ r 2
over r ∈ [ a , b ] r\in[a,b] r ∈ [ a , b ] . Its maximizer is Proj [ a , b ] ( s / γ ) \operatorname{Proj}_{[a,b]}(s/\gamma) Proj [ a , b ] ( s / γ ) , which gives (6) . Pointwise integration is justified by normal-integrand conjugacy; it also follows directly because the measurable pointwise maximizer belongs to C \mathcal{C} C .
Note that ψ γ \psi_\gamma ψ γ is continuously differentiable with a piecewise linear derivative (7) : the nonsmoothness of the primal constraint has been reduced to a single projection, which is exactly the structure the semismooth Newton method of § 5 exploits.
Strong duality needs a qualification condition. We use the following classical form, in which the qualification is the finiteness and continuity of G G G at a single point of the image of dom F \operatorname{dom} F dom F ; see [13 , 31 , 5 ] for proofs and for more general statements.
Theorem 3.2 (Fenchel–Rockafellar [13 Chap. III] , [5 Chap. 15] ). Let X , Y X,Y X , Y be Banach spaces, let T : X → Y T:X\to Y T : X → Y be bounded and linear, and let F : X → ( − ∞ , ∞ ] F:X\to(-\infty,\infty] F : X → ( − ∞ , ∞ ] , G : Y → ( − ∞ , ∞ ] G:Y\to(-\infty,\infty] G : Y → ( − ∞ , ∞ ] be proper and convex. If there exists x 0 ∈ dom F x_0\in\operatorname{dom} F x 0 ∈ dom F such that G G G is finite and continuous at T x 0 Tx_0 T x 0 , then
inf x ∈ X { F ( x ) + G ( T x ) } = sup q ∈ Y ′ { − F ∗ ( − T ∗ q ) − G ∗ ( q ) } . \inf_{x\in X}\{F(x)+G(Tx)\}=\sup_{q\in Y'}\{-F^*(-T^*q)-G^*(q)\}. x ∈ X inf { F ( x ) + G ( T x )} = q ∈ Y ′ sup { − F ∗ ( − T ∗ q ) − G ∗ ( q )} . When the primal value is finite, the supremum is attained.
The tracking term G G G is a finite quadratic, hence continuous on all of H \mathbb{H} H , and dom F = C \operatorname{dom} F=C dom F = C is nonempty because the constant control ( a + b ) / 2 (a+b)/2 ( a + b ) /2 is admissible. No interior-point or Slater-type condition on the box is needed.
Theorem 3.3 (Residual-variable Fenchel dual). Under (3) , the Fenchel dual of (5) is
max q ∈ H { − ∫ Γ ξ × D ψ γ ( − S q ) d ρ d x − 1 2 ∥ q ∥ H 2 − ( q , y d ) H } . (8) \max_{q\in\mathbb{H}}\left\{-\int_{\Gamma_\xi\times D}\psi_\gamma(-Sq)\,\mathrm{d}\rho\,\mathrm{d}x-\frac{1}{2}\lVert q\rVert_{\mathbb{H}}^2-(q,y_d)_{\mathbb{H}}\right\}. \tag*{(8)} q ∈ H max { − ∫ Γ ξ × D ψ γ ( − S q ) d ρ d x − 2 1 ∥ q ∥ H 2 − ( q , y d ) H } . (8) There is no duality gap, and the maximum is attained at a unique q ∗ ∈ H q^*\in\mathbb{H} q ∗ ∈ H .
Proof. Apply Theorem 3.2 with
X = Y = H , T = S , X=Y=\mathbb{H},\qquad T=S, X = Y = H , T = S ,
identifying H ′ \mathbb{H}' H ′ with H \mathbb{H} H through the Riesz map, so that T ∗ = S ∗ T^*=S^* T ∗ = S ∗ is the Hilbert-space adjoint. The quadratic G G G is finite and continuous everywhere, and the constant midpoint control ( a + b ) / 2 (a+b)/2 ( a + b ) /2 belongs to dom F = C \operatorname{dom} F=C dom F = C . Thus the qualification holds. Since S ∗ = S S^*=S S ∗ = S , Lemma 3.1 gives (8) . The map q ↦ F ∗ ( − S q ) q\mapsto F^*(-Sq) q ↦ F ∗ ( − S q ) is finite and convex, and − 1 2 ∥ q ∥ H 2 − ( q , y d ) H -\frac{1}{2}\lVert q\rVert_{\mathbb{H}}^2-(q,y_d)_{\mathbb{H}} − 2 1 ∥ q ∥ H 2 − ( q , y d ) H is 1-strongly concave. Hence the dual objective is 1-strongly concave and its maximizer is unique.
The elliptic adjoint form and primal–dual recovery
Problem (8) is already unconstrained, but it is not yet a convenient computational form: the solution operator S S S sits inside the nonlinearity ψ γ ( − S q ) \psi_\gamma(-Sq) ψ γ ( − S q ) , so every evaluation of the objective requires an elliptic solve. Substituting p = − S q p=-Sq p = − S q moves S S S out of the nonlinear term and replaces it by the differential operator A A A in the quadratic term, which is what makes the discretized problem sparse and the Jacobian applications of § 5 matrix-free. For this substitution to be a genuine reparametrization—creating no spurious maximizers, losing none of the existing ones, and not tacitly shrinking the feasible set—we must know that p ↦ − A p p\mapsto-Ap p ↦ − A p maps D ( A ) D(A) D ( A ) bijectively onto H \mathbb{H} H . Establishing that is the sole purpose of the next lemma, and it is the only place where the graph domain (9) is needed.
Let A A A denote the elliptic operator associated with a a a . As an unbounded operator on H \mathbb{H} H , its natural graph domain is
D ( A ) = { p ∈ V : A p ∈ H } (9) D(A)=\{p\in\mathbb{V}:Ap\in\mathbb{H}\} \tag*{(9)} D ( A ) = { p ∈ V : A p ∈ H } (9)
where A p ∈ H Ap \in\mathbb{H} A p ∈ H means that there is an element of H \mathbb{H} H , denoted A p Ap A p , with
a ( p , v ) = ( A p , v ) H ( v ∈ V ) . a(p,v)=(Ap,v)_{\mathbb{H}} \qquad(v\in\mathbb{V}). a ( p , v ) = ( A p , v ) H ( v ∈ V ) .
This element is unique since V \mathbb{V} V is dense in H \mathbb{H} H (see the proof of Proposition 2.2 ).
Lemma 3.4. The map A : D ( A ) → H A:D(A)\to\mathbb{H} A : D ( A ) → H is a bijection with inverse S S S . Consequently p ↦ q = − A p p\mapsto q=-Ap p ↦ q = − A p is a bijection from D ( A ) D(A) D ( A ) onto H \mathbb{H} H .
Proof. For every f ∈ H f\in\mathbb{H} f ∈ H , Proposition 2.2 gives a unique p = S f ∈ V p=Sf\in\mathbb{V} p = S f ∈ V satisfying A p = f Ap=f A p = f . Hence p ∈ D ( A ) p\in D(A) p ∈ D ( A ) , so A A A is surjective and S S S is its right inverse. If A p = 0 Ap=0 A p = 0 , coercivity of a a a gives p = 0 p=0 p = 0 , so A A A is injective. No H 2 ( D ) H^2(D) H 2 ( D ) regularity is used or asserted.
Theorem 3.5 (Elliptic-adjoint PDE dual). The residual dual (8) is equivalent, up to the constant − ∥ y d ∥ H 2 / 2 -\lVert y_d\rVert_{\mathbb{H}}^2/2 − ∥ y d ∥ H 2 /2 , to
min p ∈ D ( A ) { 1 2 ∥ A p − y d ∥ H 2 + ∫ Γ ξ × D ψ γ ( p ) d ρ d x } . (10) \min_{p\in D(A)}\left\{\frac{1}{2}\lVert Ap-y_d\rVert_{\mathbb{H}}^2+\int_{\Gamma_\xi\times D}\psi_\gamma(p)\,d\rho\,dx\right\}. \tag*{(10)} p ∈ D ( A ) min { 2 1 ∥ A p − y d ∥ H 2 + ∫ Γ ξ × D ψ γ ( p ) d ρ d x } . (10)
Proof. Let
Lemma 3.4 gives q = − A p q=-Ap q = − A p , while − S q = p -Sq=p − S q = p . Substitution into (8) gives
max p ∈ D ( A ) { − ∫ ψ γ ( p ) − 1 2 ∥ A p ∥ H 2 + ( A p , y d ) H } . \max_{p\in D(A)}\left\{-\int\psi_\gamma(p)-\frac{1}{2}\lVert Ap\rVert_{\mathbb{H}}^2+(Ap,y_d)_{\mathbb{H}}\right\}. p ∈ D ( A ) max { − ∫ ψ γ ( p ) − 2 1 ∥ A p ∥ H 2 + ( A p , y d ) H } .
Changing the sign of the objective and completing the square yields (10) .
Both duals determine the adjoint, but the quantities of interest—and the residuals used to monitor convergence—are the primal pair ( y , u ) (y,u) ( y , u ) . The final result of this section therefore records how the primal variables are recovered from a dual solution and verifies that the recovered triple solves the classical optimality system, so that nothing is lost in passing to the dual. The projection formula it produces is not merely a postprocessing step: it is the term that reappears in the discrete equation of § 5 and that the semismooth Newton method differentiates.
Theorem 3.6 (Optimality system). Let u ∗ , y ∗ , q ∗ , p ∗ u^*,y^*,q^*,p^* u ∗ , y ∗ , q ∗ , p ∗ be primal and dual optimizers, with y ∗ = S u ∗ y^*=Su^* y ∗ = S u ∗ and p ∗ = − S q ∗ p^*=-Sq^* p ∗ = − S q ∗ . Then
q ∗ = y ∗ − y d , u ∗ = Proj [ a , b ] ( p ∗ / γ ) , q^*=y^*-y_d,\qquad u^*=\operatorname{Proj}_{[a,b]}(p^*/\gamma), q ∗ = y ∗ − y d , u ∗ = Proj [ a , b ] ( p ∗ / γ ) , and the primal and dual problems are equivalent to
{ − ∇ ⋅ ( κ ∇ y ) = u , y ∣ ∂ D = 0 , − ∇ ⋅ ( κ ∇ p ) = y d − y , p ∣ ∂ D = 0 , u = Proj [ a , b ] ( p / γ ) . (11) \left\{
\begin{aligned}
-\nabla\cdot(\kappa\nabla y)&=u, & y|_{\partial D}&=0,\\
-\nabla\cdot(\kappa\nabla p)&=y_d-y, & p|_{\partial D}&=0,\\
u&=\operatorname{Proj}_{[a,b]}(p/\gamma).
\end{aligned}
\right. \tag*{(11)} ⎩ ⎨ ⎧ − ∇ ⋅ ( κ ∇ y ) − ∇ ⋅ ( κ ∇ p ) u = u , = y d − y , = Proj [ a , b ] ( p / γ ) . y ∣ ∂ D p ∣ ∂ D = 0 , = 0 , (11) Here p p p is the negative of the adjoint state in the usual Lagrangian convention and the recovery formula followed as u = Proj [ a , b ] ( p / γ ) u=\operatorname{Proj}_{[a,b]}(p/\gamma) u = Proj [ a , b ] ( p / γ ) .
Proof. Fenchel equality is equivalent to
q ∗ ∈ ∂ G ( S u ∗ ) , − S ∗ q ∗ ∈ ∂ F ( u ∗ ) . q^*\in\partial G(Su^*),\qquad-S^*q^*\in\partial F(u^*). q ∗ ∈ ∂ G ( S u ∗ ) , − S ∗ q ∗ ∈ ∂ F ( u ∗ ) .
The first inclusion gives
q ∗ = S u ∗ − y d = y ∗ − y d . q^*=Su^*-y_d=y^*-y_d. q ∗ = S u ∗ − y d = y ∗ − y d .
Since S ∗ = S S^*=S S ∗ = S and p ∗ = − S q ∗ p^*=-Sq^* p ∗ = − S q ∗ , the second inclusion is
p ∗ ∈ γ u ∗ + N C ( u ∗ ) , p^* \in\gamma u^* + N_{\mathcal{C}}(u^*), p ∗ ∈ γ u ∗ + N C ( u ∗ ) ,
here N C ( u ) = { v ∈ H : ( v , w − u ) H ≤ 0 for all w ∈ C } N_{\mathcal{C}}(u)=\{v\in\mathbb{H}:(v,w-u)_{\mathbb{H}}\leq0\text{ for all }w\in\mathcal{C}\} N C ( u ) = { v ∈ H : ( v , w − u ) H ≤ 0 for all w ∈ C } is the normal cone of C \mathcal{C} C at u ∈ C u\in\mathcal{C} u ∈ C , which is equivalent to
u ∗ = Proj C ( p ∗ / γ ) = Proj [ a , b ] ( p ∗ / γ ) a.e. u^*=\operatorname{Proj}_{\mathcal{C}}(p^*/\gamma)=\operatorname{Proj}_{[a,b]}(p^*/\gamma)\quad\text{a.e.} u ∗ = Proj C ( p ∗ / γ ) = Proj [ a , b ] ( p ∗ / γ ) a.e.
Finally,
A p ∗ = − q ∗ = y d − y ∗ . Ap^*=-q^*=y_d-y^*. A p ∗ = − q ∗ = y d − y ∗ .
Together with primal feasibility, these identities give (11) .
Stochastic Galerkin discretization and its dual
SG–FE state and mass matrices
Let P P ⊂ L ρ 2 ( Γ ξ ) \mathcal{P}_P\subset L^2_\rho(\Gamma_\xi) P P ⊂ L ρ 2 ( Γ ξ ) be the space of polynomials in ξ \xi ξ of total degree at most P P P , and let { ψ i } i = 1 n P \{\psi_i\}_{i=1}^{n_P} { ψ i } i = 1 n P , n P = ( K + P P ) n_P=\binom{K+P}{P} n P = ( P K + P ) , be a basis of P P \mathcal{P}_P P P that is orthonormal in L ρ 2 ( Γ ξ ) L^2_\rho(\Gamma_\xi) L ρ 2 ( Γ ξ ) , i.e., E [ ψ i ψ j ] = δ i j \mathbb{E}[\psi_i\psi_j]=\delta_{ij} E [ ψ i ψ j ] = δ ij , which is the generalized polynomial chaos (gPC) basis [40 ] . Let { ϕ r } r = 1 n h \{\phi_r\}_{r=1}^{n_h} { ϕ r } r = 1 n h be the nodal basis of a conforming finite-element space V h ⊂ H 0 1 ( D ) V_h\subset H_0^1(D) V h ⊂ H 0 1 ( D ) . The SG method approximates the state in the tensor-product space P P ⊗ V h \mathcal{P}_P\otimes V_h P P ⊗ V h ,
y h P ( x , ξ ) = ∑ i = 1 n P ∑ r = 1 n h y ( i , r ) ψ i ( ξ ) ϕ r ( x ) , y_{hP}(x,\xi)=\sum_{i=1}^{n_P}\sum_{r=1}^{n_h}y_{(i,r)}\psi_i(\xi)\phi_r(x), y h P ( x , ξ ) = i = 1 ∑ n P r = 1 ∑ n h y ( i , r ) ψ i ( ξ ) ϕ r ( x ) ,
and requires the weak state equation (4) to hold for all test functions v = ψ j ϕ s v=\psi_j\phi_s v = ψ j ϕ s , j = 1 , … , n P j=1,\ldots,n_P j = 1 , … , n P , s = 1 , … , n h s=1,\ldots,n_h s = 1 , … , n h . The coefficient vector y = ( y ( i , r ) ) ∈ R N y=(y_{(i,r)})\in\mathbb{R}^N y = ( y ( i , r ) ) ∈ R N , N : = n P n h N:=n_Pn_h N := n P n h , is ordered stochastic-major, i.e., the index ( i , r ) (i,r) ( i , r ) is stored at position ( i − 1 ) n h + r (i-1)n_h+r ( i − 1 ) n h + r . The adjoint p p p is expanded in the same basis.
Unlike the state, the control is not expanded in the gPC basis but represented by its values u = ( u ( k , r ) ) ∈ R m u=(u_{(k,r)})\in\mathbb{R}^m u = ( u ( k , r ) ) ∈ R m , m : = n q n h m:=n_qn_h m := n q n h , at the points ( x r , ξ k ) (x_r,\xi_k) ( x r , ξ k ) . This keeps the box constraint a ≤ u ≤ b a\leq u\leq b a ≤ u ≤ b pointwise and componentwise. The SG load E [ ∫ D u ψ j ϕ s d x ] \mathbb{E}[\int_Du\psi_j\phi_s\,dx] E [ ∫ D u ψ j ϕ s d x ] is approximated by the quadrature rule in ξ \xi ξ and the lumped mass in x x x , which gives
( E ⊤ W u ) ( j , s ) = ∑ k w k ψ j ( ξ k ) ( M L ) s s u ( k , s ) . (E^{\top}Wu)_{(j,s)}=\sum_k w_k\psi_j(\xi_k)(M_L)_{ss}u_{(k,s)}. ( E ⊤ W u ) ( j , s ) = k ∑ w k ψ j ( ξ k ) ( M L ) ss u ( k , s ) .
Suppose that the diffusion coefficient κ \kappa κ used in the SG form admits the separable representation
κ ( x , ξ ) = ∑ ℓ = 0 N K − 1 κ ℓ ( x ) ζ ℓ ( ξ ) , ζ 0 ≡ 1 , \kappa(x,\xi)=\sum_{\ell=0}^{N_K-1}\kappa_\ell(x)\zeta_\ell(\xi),\qquad\zeta_0\equiv1, κ ( x , ξ ) = ℓ = 0 ∑ N K − 1 κ ℓ ( x ) ζ ℓ ( ξ ) , ζ 0 ≡ 1 ,
where κ ℓ ∈ L ∞ ( D ) \kappa_\ell\in L^\infty(D) κ ℓ ∈ L ∞ ( D ) are deterministic spatial functions, ζ ℓ : Γ ξ → R \zeta_\ell:\Gamma_\xi\to\mathbb{R} ζ ℓ : Γ ξ → R are given scalar functions of the parameter, and N K N_K N K is the number of terms. For the affine coefficients used in § 6 , N K = K + 1 N_K=K+1 N K = K + 1 and ζ ℓ ( ξ ) = ξ ℓ \zeta_\ell(\xi)=\xi_\ell ζ ℓ ( ξ ) = ξ ℓ for ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 . Followed by [8 ] , with the definition of
( G ℓ ) i j = E [ ζ ℓ ψ i ψ j ] , ( M D ) i j = ∫ D ϕ i ϕ j d x , ( K ℓ ) i j = ∫ D κ ℓ ( x ) ∇ ϕ i ⋅ ∇ ϕ j d x , \begin{aligned}
(G_\ell)_{ij}&=\mathbb{E}[\zeta_\ell\psi_i\psi_j],\\
(M_D)_{ij}&=\int_D\phi_i\phi_j\,dx,\\
(K_\ell)_{ij}&=\int_D\kappa_\ell(x)\nabla\phi_i\cdot\nabla\phi_j\,dx,
\end{aligned} ( G ℓ ) ij ( M D ) ij ( K ℓ ) ij = E [ ζ ℓ ψ i ψ j ] , = ∫ D ϕ i ϕ j d x , = ∫ D κ ℓ ( x ) ∇ ϕ i ⋅ ∇ ϕ j d x ,
the SG mass matrix and stiffness matrix are
M = G 0 ⊗ M D , K = ∑ ℓ = 0 N K − 1 G ℓ ⊗ K ℓ . (12) \mathcal{M}=G_0\otimes M_D,\qquad\mathcal{K}=\sum_{\ell=0}^{N_K-1}G_\ell\otimes K_\ell. \tag*{(12)} M = G 0 ⊗ M D , K = ℓ = 0 ∑ N K − 1 G ℓ ⊗ K ℓ . (12)
For an exactly integrated orthonormal basis, G 0 = I G_0=I G 0 = I . The control is represented by its values at the points ( x r , ξ k ) (x_r,\xi_k) ( x r , ξ k ) , where x 1 , … , x n h x_1,\ldots,x_{n_h} x 1 , … , x n h are the interior nodes of V h V_h V h and { ξ k , w k } k = 1 n q \{\xi_k,w_k\}_{k=1}^{n_q} { ξ k , w k } k = 1 n q is a positive quadrature rule on Γ ξ \Gamma_\xi Γ ξ . Let V ξ ∈ R n q × n P V_\xi\in\mathbb{R}^{n_q\times n_P} V ξ ∈ R n q × n P with ( V ξ ) k j = ψ j ( ξ k ) (V_\xi)_{kj}=\psi_j(\xi_k) ( V ξ ) k j = ψ j ( ξ k ) , W ξ = diag ( w 1 , … , w n q ) W_\xi=\operatorname{diag}(w_1,\ldots,w_{n_q}) W ξ = diag ( w 1 , … , w n q ) , and M L = diag ( M D 1 ) M_L=\operatorname{diag}(M_D\mathbf{1}) M L = diag ( M D 1 ) , the row-sum lumped spatial mass. Define
E = V ξ ⊗ I n h ∈ R n q n h × n P n h , W = W ξ ⊗ M L ∈ R n q n h × n q n h . E=V_\xi\otimes I_{n_h}\in\mathbb{R}^{n_qn_h\times n_Pn_h},\qquad W=W_\xi\otimes M_L\in\mathbb{R}^{n_qn_h\times n_qn_h}. E = V ξ ⊗ I n h ∈ R n q n h × n P n h , W = W ξ ⊗ M L ∈ R n q n h × n q n h .
For a coefficient vector p \mathbf{p} p , ( E p ) ( k , r ) = ∑ j ψ j ( ξ k ) p ( j , r ) (E\mathbf{p})_{(k,r)}=\sum_j\psi_j(\xi_k)p_{(j,r)} ( E p ) ( k , r ) = ∑ j ψ j ( ξ k ) p ( j , r ) is the value at ( x r , ξ k ) (x_r,\xi_k) ( x r , ξ k ) of the SG function ∑ j , r p ( j , r ) ψ j ( ξ ) ϕ r ( x ) \sum_{j,r}p_{(j,r)}\psi_j(\xi)\phi_r(x) ∑ j , r p ( j , r ) ψ j ( ξ ) ϕ r ( x ) , because the nodal basis satisfies ϕ s ( x r ) = δ r s \phi_s(x_r)=\delta_{rs} ϕ s ( x r ) = δ r s . The entries of W W W are positive, so W W W is positive definite and diagonal. Boundary nodes carry no control values, since the Dirichlet degrees of freedom are eliminated. Thus E E E and W W W belong to the control discretization, whereas M D M_D M D , K ℓ K_\ell K ℓ , M \mathcal{M} M , and K \mathcal{K} K belong to the state discretization.
We assume that M \mathcal{M} M and K \mathcal{K} K are symmetric positive definite; this holds, for instance, when the matrices G ℓ G_\ell G ℓ are computed exactly and κ \kappa κ satisfies (3) .
Lagrange dual and KKT system
Let u ∈ R m \mathbf{u}\in\mathbb{R}^m u ∈ R m be independent control values at the positive quadrature points. Observe that the discrete state y ∈ R N \mathbf{y}\in\mathbb{R}^N y ∈ R N satisfies the SG weak equation
K y = E T W u . \mathcal{K}\mathbf{y}=E^\mathsf{T}W\mathbf{u}. K y = E T W u .
The exact finite-dimensional constrained primal is
min y ∈ R N , u ∈ R m 1 2 ( y − y d ) T M ( y − y d ) + γ 2 u T W u , subject to K y − E T W u = 0 , a ≤ u ≤ b . (13) \begin{aligned}
\min_{\mathbf{y}\in\mathbb{R}^N,\ \mathbf{u}\in\mathbb{R}^m}\quad&
\frac{1}{2}(\mathbf{y}-\mathbf{y}_d)^\mathsf{T}\mathcal{M}(\mathbf{y}-\mathbf{y}_d)+\frac{\gamma}{2}\mathbf{u}^\mathsf{T}W\mathbf{u},\\
\text{subject to}\quad&\mathcal{K}\mathbf{y}-E^\mathsf{T}W\mathbf{u}=0,\\
&a\leq\mathbf{u}\leq b. \tag*{(13)}
\end{aligned} y ∈ R N , u ∈ R m min subject to 2 1 ( y − y d ) T M ( y − y d ) + 2 γ u T W u , K y − E T W u = 0 , a ≤ u ≤ b . (13)
Theorem 4.1. Problem (13) has the concave dual
max p ∈ R N { − 1 2 p T K M − 1 K T p + p T K y d − ∑ ℓ = 1 m w ℓ ψ γ ( ( E p ) ℓ ) } . (14) \max_{\mathbf{p}\in\mathbb{R}^N}\left\{-\frac{1}{2}\mathbf{p}^\mathsf{T}\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^\mathsf{T}\mathbf{p}+\mathbf{p}^\mathsf{T}\mathcal{K}\mathbf{y}_d-\sum_{\ell=1}^{m}w_\ell\psi_\gamma((E\mathbf{p})_\ell)\right\}. \tag*{(14)} p ∈ R N max { − 2 1 p T K M − 1 K T p + p T K y d − ℓ = 1 ∑ m w ℓ ψ γ (( E p ) ℓ ) } . (14)
There is no duality gap. Moreover, the primal and dual optimizers are unique.
Proof. Let
u ‾ = a + b 2 1 , y ‾ = K − 1 E T W u ‾ . \overline{\mathbf{u}}=\frac{a+b}{2}\mathbf{1},\qquad\overline{\mathbf{y}}=\mathcal{K}^{-1}E^\mathsf{T}W\overline{\mathbf{u}}. u = 2 a + b 1 , y = K − 1 E T W u .
This is an affine-feasible point in the relative interior of the box, so the finite-dimensional relative-interior qualification holds. Now, consider the Lagrangian
L h ( y , u , p ) = 1 2 ( y − y d ) T M ( y − y d ) + γ 2 u T W u + p T ( K y − E T W u ) + I [ a , b ] m ( u ) . (15) \mathcal{L}_h(\mathbf{y},\mathbf{u},\mathbf{p})=\frac{1}{2}(\mathbf{y}-\mathbf{y}_d)^\mathsf{T}\mathcal{M}(\mathbf{y}-\mathbf{y}_d)+\frac{\gamma}{2}\mathbf{u}^\mathsf{T}W\mathbf{u}+\mathbf{p}^\mathsf{T}(\mathcal{K}\mathbf{y}-E^\mathsf{T}W\mathbf{u})+I_{[a,b]^m}(\mathbf{u}). \tag*{(15)} L h ( y , u , p ) = 2 1 ( y − y d ) T M ( y − y d ) + 2 γ u T W u + p T ( K y − E T W u ) + I [ a , b ] m ( u ) . (15)
Minimization in y \mathbf{y} y of (15) gives
y = y d − M − 1 K T p \mathbf{y}=\mathbf{y}_d-\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\mathbf{p} y = y d − M − 1 K T p
and the minimum objective
− 1 2 p T K M − 1 K T p + p T K y d . -\frac{1}{2}\mathbf{p}^{\mathsf{T}}\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\mathbf{p}+\mathbf{p}^{\mathsf{T}}\mathcal{K}\mathbf{y}_d. − 2 1 p T K M − 1 K T p + p T K y d .
For s ℓ = ( E p ) ℓ s_\ell=(E\mathbf{p})_\ell s ℓ = ( E p ) ℓ ,
inf r ∈ [ a , b ] w ℓ ( γ 2 r 2 − s ℓ r ) = − w ℓ ψ γ ( s ℓ ) . \inf_{r\in[a,b]}w_\ell\left(\frac{\gamma}{2}r^2-s_\ell r\right)=-w_\ell\psi_\gamma(s_\ell). r ∈ [ a , b ] inf w ℓ ( 2 γ r 2 − s ℓ r ) = − w ℓ ψ γ ( s ℓ ) .
Since W = diag ( w 1 , … , w m ) W=\operatorname{diag}(w_1,\ldots,w_m) W = diag ( w 1 , … , w m ) is diagonal and the box is a product of intervals, the u \mathbf{u} u -part of L h \mathcal{L}_h L h separates into the m m m scalar problems above. Summing them over ℓ = 1 , … , m \ell=1,\ldots,m ℓ = 1 , … , m and adding the minimum in y \mathbf{y} y gives (14) . Since K \mathcal{K} K is invertible, K M − 1 K T ≻ 0 \mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\succ0 K M − 1 K T ≻ 0 , so the dual objective is strongly concave and tends to − ∞ -\infty − ∞ as ∥ p ∥ → ∞ \lVert\mathbf{p}\rVert\to\infty ∥ p ∥ → ∞ . Hence it has a unique maximizer. The primal objective is strictly convex on the affine feasible set, giving primal uniqueness.
Corollary 4.2. After eliminating u \mathbf{u} u , the KKT conditions are
M y + K T p = M y d , (16) \mathcal{M}\mathbf{y}+\mathcal{K}^{\mathsf{T}}\mathbf{p}=\mathcal{M}\mathbf{y}_d, \tag*{(16)} M y + K T p = M y d , (16) K y = R ( p ) , (17) \mathcal{K}\mathbf{y}=R(\mathbf{p}), \tag*{(17)} K y = R ( p ) , (17) where R ( p ) = E T W Proj [ a , b ] ( E p / γ ) R(\mathbf{p})=E^{\mathsf{T}}W\operatorname{Proj}_{[a,b]}(E\mathbf{p}/\gamma) R ( p ) = E T W Proj [ a , b ] ( E p / γ ) .
Proof. Stationarity in y \mathbf{y} y , ∇ y L h = M ( y − y d ) + K T p = 0 \nabla_{\mathbf{y}}\mathcal{L}_h=\mathcal{M}(\mathbf{y}-\mathbf{y}_d)+\mathcal{K}^{\mathsf{T}}\mathbf{p}=0 ∇ y L h = M ( y − y d ) + K T p = 0 , gives (16) . Stationarity in each control value is
0 ∈ γ u − E p + N [ a , b ] m ( u ) , 0\in\gamma\mathbf{u}-E\mathbf{p}+N_{[a,b]^m}(\mathbf{u}), 0 ∈ γ u − E p + N [ a , b ] m ( u ) ,
where N [ a , b ] m N_{[a,b]^m} N [ a , b ] m is the normal cone of the box [ a , b ] m ⊂ R m [a,b]^m\subset\mathbb{R}^m [ a , b ] m ⊂ R m , because positive diagonal rescaling leaves the componentwise box normal cone unchanged. Therefore
u = Proj [ a , b ] ( E p / γ ) . \mathbf{u}=\operatorname{Proj}_{[a,b]}(E\mathbf{p}/\gamma). u = Proj [ a , b ] ( E p / γ ) .
Substitution into the primal feasibility condition K y − E T W u = 0 \mathcal{K}\mathbf{y}-E^{\mathsf{T}}W\mathbf{u}=0 K y − E T W u = 0 gives (17) . Equivalently, differentiating (14) and using (7) gives
− K M − 1 K T p + K y d − R ( p ) = 0 , -\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\mathbf{p}+\mathcal{K}\mathbf{y}_d-R(\mathbf{p})=0, − K M − 1 K T p + K y d − R ( p ) = 0 ,
which is the same equation after substituting y = y d − M − 1 K T p \mathbf{y}=\mathbf{y}_d-\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\mathbf{p} y = y d − M − 1 K T p .
Lemma 4.3. If W ≻ 0 W\succ0 W ≻ 0 , then R : R N → R N R:\mathbb{R}^{N}\to\mathbb{R}^{N} R : R N → R N in (4.5) is monotone and Lipschitz continuous.
Proof. For any v , z ∈ R N \mathbf{v},\mathbf{z}\in\mathbb{R}^{N} v , z ∈ R N ,
( v − z ) T ( R ( v ) − R ( z ) ) = ( E v − E z ) T W [ Proj [ a , b ] ( E v / γ ) − Proj [ a , b ] ( E z / γ ) ] ≥ 0. (\mathbf{v}-\mathbf{z})^{\mathsf{T}}(R(\mathbf{v})-R(\mathbf{z}))=(E\mathbf{v}-E\mathbf{z})^{\mathsf{T}}W\left[\operatorname{Proj}_{[a,b]}(E\mathbf{v}/\gamma)-\operatorname{Proj}_{[a,b]}(E\mathbf{z}/\gamma)\right]\geq0. ( v − z ) T ( R ( v ) − R ( z )) = ( E v − E z ) T W [ Proj [ a , b ] ( E v / γ ) − Proj [ a , b ] ( E z / γ ) ] ≥ 0.
Each summand is nonnegative because the scalar projection is monotone and each quadrature weight is positive. The scalar projection is 1-Lipschitz, so R R R is Lipschitz.
A semismooth Newton–PCG method
Eliminating y y y in (4.5) gives
F ( p ) = K M − 1 K T p − K y d + E T W Proj [ a , b ] ( E p / γ ) = 0. (18) F(\mathbf{p})=\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}\mathbf{p}-\mathcal{K}\mathbf{y}_{d}+E^{\mathsf{T}}W\operatorname{Proj}_{[a,b]}(E\mathbf{p}/\gamma)=0. \tag*{(18)} F ( p ) = K M − 1 K T p − K y d + E T W Proj [ a , b ] ( E p / γ ) = 0. (18)
For the diagonal free-set mask D ( p ) = diag ( d q ( p ) ) ∈ R m × m D(\mathbf{p})=\operatorname{diag}(d_q(\mathbf{p}))\in\mathbb{R}^{m\times m} D ( p ) = diag ( d q ( p )) ∈ R m × m , where d q ( p ) = 1 d_q(\mathbf{p})=1 d q ( p ) = 1 on a free component and d q ( p ) = 0 d_q(\mathbf{p})=0 d q ( p ) = 0 on a saturated component (and zero is selected at a breakpoint), the Newton derivative of F F F in the sense of [18 , 36 ] is
J D = K M − 1 K T + γ − 1 E T W D ( p ) E . (19) J_D=\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}}+\gamma^{-1}E^{\mathsf{T}}WD(\mathbf{p})E. \tag*{(19)} J D = K M − 1 K T + γ − 1 E T W D ( p ) E . (19)
For a vector v \mathbf{v} v , J D v J_D\mathbf{v} J D v is evaluated matrix-free using one application each of K \mathcal{K} K , K T \mathcal{K}^{\mathsf{T}} K T , M − 1 \mathcal{M}^{-1} M − 1 , E E E , and E T E^{\mathsf{T}} E T . Each Newton system is solved by PCG to the forcing tolerance
η k = min { η max , max ( 10 − 12 , 0.1 r k ) } , r k = ∥ F ( p k ) ∥ max { 1 , ∥ K y d ∥ } , (20) \eta_k=\min\{\eta_{\max},\max(10^{-12},0.1\sqrt{r_k})\},\qquad r_k=\frac{\lVert F(\mathbf{p}_k)\rVert}{\max\{1,\lVert\mathcal{K}\mathbf{y}_d\rVert\}}, \tag*{(20)} η k = min { η m a x , max ( 1 0 − 12 , 0.1 r k )} , r k = max { 1 , ∥ K y d ∥} ∥ F ( p k )∥ , (20)
and the step is globalized by Armijo backtracking with parameters 10 − 4 10^{-4} 1 0 − 4 and 1 / 2 1/2 1/2 , which preserves descent of the convex dual merit function. The iteration stops when the normalized KKT residual is at most 10 − 6 10^{-6} 1 0 − 6 or after k max k_{\max} k m a x Newton steps, and the values of η max \eta_{\max} η m a x and k max k_{\max} k m a x are given in § 6 . The complete procedure is specified by Algorithm 6.1 in § 6 , after the preconditioner has been specified.
Current-set preconditioner and spectral bounds
Here M D M_D M D , K 0 K_0 K 0 , and K ℓ K_\ell K ℓ retain the spatial finite-element meanings defined in § 4 . The calligraphic symbols M \mathcal{M} M , K \mathcal{K} K , and K ‾ \overline{\mathcal{K}} K denote the full stochastic–Galerkin matrices. We use stochastic-major ordering first and apply an orthogonal permutation to node-major ordering for the local assembly estimates. In stochastic-major ordering, since G 0 = I G_0=I G 0 = I for the exactly integrated orthonormal basis of § 4 , the matrices in (12) , with the mean term ℓ = 0 \ell=0 ℓ = 0 written separately, become
M = I n P ⊗ M D , K = I n P ⊗ K 0 + ∑ ℓ = 1 N K − 1 G ℓ ⊗ K ℓ , K ‾ = I n P ⊗ K 0 . (21) \mathcal{M}=I_{n_P}\otimes M_D,\qquad\mathcal{K}=I_{n_P}\otimes K_0+\sum_{\ell=1}^{N_K-1}G_\ell\otimes K_\ell,\qquad\overline{\mathcal{K}}=I_{n_P}\otimes K_0. \tag*{(21)} M = I n P ⊗ M D , K = I n P ⊗ K 0 + ℓ = 1 ∑ N K − 1 G ℓ ⊗ K ℓ , K = I n P ⊗ K 0 . (21)
Here K ‾ \overline{\mathcal{K}} K is the part of K \mathcal{K} K generated by the mean coefficient κ 0 \kappa_0 κ 0 , N K − 1 N_K-1 N K − 1 is the number of non-mean terms of κ \kappa κ , and M D M_D M D , K 0 K_0 K 0 are symmetric positive definite, G ℓ G_\ell G ℓ , K ℓ K_\ell K ℓ are symmetric, and K \mathcal{K} K is positive definite. The stochastic basis is orthonormal for the mass inner product represented in M \mathcal{M} M . All coefficient amplitudes and normalization factors are already included in G ℓ G_\ell G ℓ or K ℓ K_\ell K ℓ .
The control weights W W W are positive and diagonal, as above. Written in terms of the reduced equation (18) , the Jacobian matrix (19) associated with a selected projection derivative D D D has the form
H = K M − 1 K T , H 0 = K ‾ M − 1 K ‾ T , J = H + γ − 1 C D , P W = H 0 + γ − 1 C D , (22) H=\mathcal{K}\mathcal{M}^{-1}\mathcal{K}^{\mathsf{T}},\qquad H_0=\overline{\mathcal{K}}\mathcal{M}^{-1}\overline{\mathcal{K}}^{\mathsf{T}},\qquad J=H+\gamma^{-1}C_D,\qquad P_W=H_0+\gamma^{-1}C_D, \tag*{(22)} H = K M − 1 K T , H 0 = K M − 1 K T , J = H + γ − 1 C D , P W = H 0 + γ − 1 C D , (22)
where γ > 0 \gamma>0 γ > 0 and C D = E T W D E ⪰ 0 C_D=E^{\mathsf{T}}WDE\succeq0 C D = E T W D E ⪰ 0 . The algorithm uses the binary mask D = D ( p ) D=D(\mathbf{p}) D = D ( p ) of (19) and the spectral results below hold for any positive semidefinite C D C_D C D shared by J J J and P W P_W P W .
Let ∥ v ∥ Q = ( v T Q v ) 1 / 2 \lVert\mathbf{v}\rVert_Q=(\mathbf{v}^{\mathsf{T}}Q\mathbf{v})^{1/2} ∥ v ∥ Q = ( v T Q v ) 1/2 for an SPD matrix Q Q Q . All unweighted matrix norms below are Euclidean operator norms. The notation cond s p ( P W − 1 J ) \operatorname{cond}_{\mathrm{sp}}(P_W^{-1}J) cond sp ( P W − 1 J ) means the ratio of extreme eigenvalues, equivalently the condition number of the SPD matrix P W − 1 / 2 J P W − 1 / 2 P_W^{-1/2}JP_W^{-1/2} P W − 1/2 J P W − 1/2 .
Lemma 5.1. Let
T = M − 1 / 2 K K ‾ − 1 M 1 / 2 , σ − = σ min ( T ) > 0 , σ + = σ max ( T ) , \mathcal{T}=\mathcal{M}^{-1/2}\mathcal{K}\overline{\mathcal{K}}^{-1}\mathcal{M}^{1/2},\qquad\sigma_-=\sigma_{\min}(\mathcal{T})>0,\qquad\sigma_+=\sigma_{\max}(\mathcal{T}), T = M − 1/2 K K − 1 M 1/2 , σ − = σ m i n ( T ) > 0 , σ + = σ m a x ( T ) ,
where σ min ( T ) \sigma_{\min}(\mathcal{T}) σ m i n ( T ) and σ max ( T ) \sigma_{\max}(\mathcal{T}) σ m a x ( T ) denote the smallest and largest singular values of T \mathcal{T} T , and the extreme generalized eigenvalues of ( H , H 0 ) (H,H_0) ( H , H 0 ) are exactly σ − 2 , σ + 2 \sigma_{-}^{2},\sigma_{+}^{2} σ − 2 , σ + 2 . In particular,
σ − 2 H 0 ⪯ H ⪯ σ + 2 H 0 . (23) \sigma_{-}^{2}H_0 \preceq H \preceq\sigma_{+}^{2}H_0. \tag*{(23)} σ − 2 H 0 ⪯ H ⪯ σ + 2 H 0 . (23)
Proof. Let L 0 = M − 1 / 2 K ‾ L_0=\mathcal{M}^{-1/2}\overline{K} L 0 = M − 1/2 K , an invertible matrix, since M ≻ 0 \mathcal{M}\succ0 M ≻ 0 and K ‾ = I n P ⊗ K 0 \overline{K}=I_{n_P}\otimes K_0 K = I n P ⊗ K 0 is invertible. With the fact that K = K ⊤ K=K^{\top} K = K ⊤ and K ‾ = K ‾ ⊤ \overline{K}=\overline{K}^{\top} K = K ⊤ from (21) , direct multiplication gives H 0 = L 0 ⊤ L 0 H_0=L_0^{\top}L_0 H 0 = L 0 ⊤ L 0 and H = L 0 ⊤ T ⊤ T L 0 H=L_0^{\top}\mathcal{T}^{\top}\mathcal{T}L_0 H = L 0 ⊤ T ⊤ T L 0 , indeed T L 0 = M − 1 / 2 K \mathcal{T}L_0=\mathcal{M}^{-1/2}K T L 0 = M − 1/2 K . Therefore
v ⊤ H v v ⊤ H 0 v = ∥ T z ∥ 2 2 ∥ z ∥ 2 2 , z = L 0 v . \frac{\mathbf{v}^{\top}H\mathbf{v}}{\mathbf{v}^{\top}H_0\mathbf{v}}=\frac{\|\mathcal{T}\mathbf{z}\|_2^2}{\|\mathbf{z}\|_2^2},\qquad\mathbf{z}=L_0\mathbf{v}. v ⊤ H 0 v v ⊤ H v = ∥ z ∥ 2 2 ∥ T z ∥ 2 2 , z = L 0 v .
Since L 0 L_0 L 0 is onto, extrema over v ≠ 0 \mathbf{v}\ne0 v = 0 equal extrema over z ≠ 0 \mathbf{z}\ne0 z = 0 . They are the extreme eigenvalues of T ⊤ T \mathcal{T}^{\top}\mathcal{T} T ⊤ T , namely σ − 2 \sigma_{-}^{2} σ − 2 and σ + 2 \sigma_{+}^{2} σ + 2 . Note that σ − > 0 \sigma_{-}>0 σ − > 0 because T \mathcal{T} T is invertible. □ \square □
Theorem 5.2. If c H 0 ⪯ H ⪯ C H 0 cH_0\preceq H\preceq CH_0 c H 0 ⪯ H ⪯ C H 0 for constants 0 < c ≤ C 0<c\le C 0 < c ≤ C , then for every γ > 0 \gamma>0 γ > 0 and C D ⪰ 0 C_D\succeq0 C D ⪰ 0 ,
spec ( P W − 1 J ) ⊂ [ θ − , θ + ] , θ − = min { c , 1 } , θ + = max { C , 1 } . (24) \operatorname{spec}(P_W^{-1}J)\subset[\theta_{-},\theta_{+}],\qquad\theta_{-}=\min\{c,1\},\qquad\theta_{+}=\max\{C,1\}. \tag*{(24)} spec ( P W − 1 J ) ⊂ [ θ − , θ + ] , θ − = min { c , 1 } , θ + = max { C , 1 } . (24) Consequently cond s p ( P W − 1 J ) ≤ θ + / θ − \operatorname{cond}_{\mathrm{sp}}(P_W^{-1}J)\le\theta_{+}/\theta_{-} cond sp ( P W − 1 J ) ≤ θ + / θ − . In particular, one can always take c = σ − 2 c=\sigma_{-}^{2} c = σ − 2 , C = σ + 2 C=\sigma_{+}^{2} C = σ + 2 at a fixed discretization.
Proof. First, observe that both
J − θ − P W = ( H − θ − H 0 ) + ( 1 − θ − ) γ − 1 C D J-\theta_{-}P_W=(H-\theta_{-}H_0)+(1-\theta_{-})\gamma^{-1}C_D J − θ − P W = ( H − θ − H 0 ) + ( 1 − θ − ) γ − 1 C D and
θ + P W − J = ( θ + H 0 − H ) + ( θ + − 1 ) γ − 1 C D \theta_{+}P_W-J=(\theta_{+}H_0-H)+(\theta_{+}-1)\gamma^{-1}C_D θ + P W − J = ( θ + H 0 − H ) + ( θ + − 1 ) γ − 1 C D are positive semidefinite: in the first terms because θ − ≤ c \theta_{-}\le c θ − ≤ c and θ + ≥ C \theta_{+}\ge C θ + ≥ C , and in the second terms because θ − ≤ 1 ≤ θ + \theta_{-}\le1\le\theta_{+} θ − ≤ 1 ≤ θ + and C D ⪰ 0 C_D\succeq0 C D ⪰ 0 . Since P W ≻ 0 P_W\succ0 P W ≻ 0 , congruence with P W − 1 / 2 P_W^{-1/2} P W − 1/2 preserves semidefiniteness and gives θ − I ⪯ P W − 1 / 2 J P W − 1 / 2 ⪯ θ + I \theta_{-}I\preceq P_W^{-1/2}JP_W^{-1/2}\preceq\theta_{+}I θ − I ⪯ P W − 1/2 J P W − 1/2 ⪯ θ + I . Hence the eigenvalues of the symmetric matrix P W − 1 / 2 J P W − 1 / 2 P_W^{-1/2}JP_W^{-1/2} P W − 1/2 J P W − 1/2 lie in [ θ − , θ + ] [\theta_{-},\theta_{+}] [ θ − , θ + ] , and so do those of P W − 1 J = P W − 1 / 2 ( P W − 1 / 2 J P W − 1 / 2 ) P W 1 / 2 P_W^{-1}J=P_W^{-1/2}(P_W^{-1/2}JP_W^{-1/2})P_W^{1/2} P W − 1 J = P W − 1/2 ( P W − 1/2 J P W − 1/2 ) P W 1/2 . □ \square □
We next provide sufficient local structure that yields a uniform bound. Consider a square of fixed side length L D > 0 L_D>0 L D > 0 with n e ≥ 2 n_e\ge2 n e ≥ 2 equal elements per direction, h = L D / n e h=L_D/n_e h = L D / n e , and conforming bilinear elements. All boundary nodal values are zero and are eliminated. On each element T T T , let q q q index the four tensor Gauss points x T q \mathbf{x}_{Tq} x T q , let w T q > 0 w_{Tq}>0 w T q > 0 include the physical Jacobian, let g T i q ∈ R 2 \mathbf{g}_{Tiq}\in\mathbb{R}^{2} g T i q ∈ R 2 be the gradient of the local nodal basis function i i i at x T q \mathbf{x}_{Tq} x T q , and let a ℓ , T q = κ ℓ ( x T q ) a_{\ell,Tq}=\kappa_{\ell}(\mathbf{x}_{Tq}) a ℓ , T q = κ ℓ ( x T q ) .
Assumption 5.3. Let the scalar reference weights and symmetric coefficient blocks satisfy
0 < ν − ≤ a 0 , T q ≤ ν + , α I n P ⪯ A T q ⪯ β I n P , 0 < α ≤ β . (25) 0<\nu_{-}\le a_{0,Tq}\le\nu_{+},\qquad\alpha I_{n_P}\preceq A_{Tq}\preceq\beta I_{n_P},\qquad0<\alpha\le\beta. \tag*{(25)} 0 < ν − ≤ a 0 , T q ≤ ν + , α I n P ⪯ A T q ⪯ β I n P , 0 < α ≤ β . (25) The reference stiffness has entries
( K 0 ) i j = ∑ T ∋ i , j ∑ q w T q a 0 , T q g T i q ⊤ g T j q . (K_0)_{ij}=\sum_{T\ni i,j}\sum_q w_{Tq}a_{0,Tq}\mathbf{g}_{Tiq}^{\top}\mathbf{g}_{Tjq}. ( K 0 ) ij = T ∋ i , j ∑ q ∑ w T q a 0 , T q g T i q ⊤ g T j q .
After an orthogonal permutation into node-major ordering, the full stiffness has n P × n P n_P \times n_P n P × n P blocks
K i j = ∑ T ∋ i , j ∑ q w T q a 0 , T q ( g T i q T g T j q ) A T q . (26) K_{ij}=\sum_{T\ni i,j}\sum_q w_{Tq}a_{0,Tq}(\mathbf{g}_{Tiq}^{\mathsf{T}}\mathbf{g}_{Tjq})A_{Tq}. \tag*{(26)} K ij = T ∋ i , j ∑ q ∑ w T q a 0 , T q ( g T i q T g T j q ) A T q . (26)
The spatial mass is the consistent bilinear mass, integrated exactly by the same Gauss rule.
Orthogonal reordering does not change any spectral or norm assertion. For a Kronecker assembly with scalar coefficient arrays a ℓ , T q a_{\ell,Tq} a ℓ , T q , (26) is exactly (21) when
A T q = I n P + ∑ ℓ = 1 N K − 1 a ℓ , T q a 0 , T q G ℓ . (27) A_{Tq}=I_{n_P}+\sum_{\ell=1}^{N_K-1}\frac{a_{\ell,Tq}}{a_{0,Tq}}G_\ell. \tag*{(27)} A T q = I n P + ℓ = 1 ∑ N K − 1 a 0 , T q a ℓ , T q G ℓ . (27)
Lemma 5.4. Under Assumption 5.3 5.3 5.3 ,
h 2 9 I ⪯ M D ⪯ h 2 I , ( K 0 ) i i ≤ 8 ν + 3 , K 0 ⪰ λ ∗ M D , λ ∗ : = 8 ν − L D 2 . (28) \frac{h^2}{9}I\preceq M_D\preceq h^2I,\qquad(K_0)_{ii}\leq\frac{8\nu_+}{3},\qquad K_0\succeq\lambda_*M_D,\quad\lambda_*:=\frac{8\nu_-}{L_D^2}. \tag*{(28)} 9 h 2 I ⪯ M D ⪯ h 2 I , ( K 0 ) ii ≤ 3 8 ν + , K 0 ⪰ λ ∗ M D , λ ∗ := L D 2 8 ν − . (28) Moreover α ‾ K ⪯ K ⪯ β ‾ K \overline{\alpha}K\preceq\mathcal{K}\preceq\overline{\beta}K α K ⪯ K ⪯ β K .
Proof. Let one-dimensional interior matrices be
M 1 = h 6 tridiag ( 1 , 4 , 1 ) , S 1 = 1 h tridiag ( − 1 , 2 , − 1 ) . M_1=\frac{h}{6}\operatorname{tridiag}(1,4,1),\qquad S_1=\frac{1}{h}\operatorname{tridiag}(-1,2,-1). M 1 = 6 h tridiag ( 1 , 4 , 1 ) , S 1 = h 1 tridiag ( − 1 , 2 , − 1 ) .
Inserting the vector with entries sin ( i r π / n e ) \sin(ir\pi/n_e) sin ( i r π / n e ) into the three-point stencils shows that the eigenvalues are
m r = h 3 ( 2 + cos θ r ) , s r = 2 h ( 1 − cos θ r ) , θ r = r π n e . m_r=\frac{h}{3}(2+\cos\theta_r),\qquad s_r=\frac{2}{h}(1-\cos\theta_r),\qquad\theta_r=\frac{r\pi}{n_e}. m r = 3 h ( 2 + cos θ r ) , s r = h 2 ( 1 − cos θ r ) , θ r = n e r π .
These orthogonal sine vectors form a basis. Since h / 3 ≤ m r ≤ h h/3\leq m_r\leq h h /3 ≤ m r ≤ h , the tensor identity M D = M 1 ⊗ M 1 M_D=M_1\otimes M_1 M D = M 1 ⊗ M 1 gives the mass bounds. The unit-reference stiffness is K u n i t = M 1 ⊗ S 1 + S 1 ⊗ M 1 K_{\mathrm{unit}}=M_1\otimes S_1+S_1\otimes M_1 K unit = M 1 ⊗ S 1 + S 1 ⊗ M 1 . Its generalized eigenvalues relative to M D M_D M D are s r / m r + s t / m t s_r/m_r+s_t/m_t s r / m r + s t / m t . The ratio is increasing with θ r \theta_r θ r and
s 1 m 1 = 12 sin 2 ( π / ( 2 n e ) ) h 2 ( 2 + cos ( π / n e ) ) ≥ 4 h 2 n e 2 = 4 L D 2 . \frac{s_1}{m_1}=\frac{12\sin^2(\pi/(2n_e))}{h^2(2+\cos(\pi/n_e))}\geq\frac{4}{h^2n_e^2}=\frac{4}{L_D^2}. m 1 s 1 = h 2 ( 2 + cos ( π / n e )) 12 sin 2 ( π / ( 2 n e )) ≥ h 2 n e 2 4 = L D 2 4 .
Here sin x ≥ 2 x / π \sin x\geq2x/\pi sin x ≥ 2 x / π for 0 ≤ x ≤ π / 2 0\leq x\leq\pi/2 0 ≤ x ≤ π /2 follows from concavity of sine. Positive quadrature gives K 0 ⪰ ν − K u n i t K_0\succeq\nu_-K_{\mathrm{unit}} K 0 ⪰ ν − K unit , proving the generalized lower bound.
The diagonal of the unit local 4 × 4 4\times4 4 × 4 bilinear stiffness is 2 / 3 2/3 2/3 . Indeed, for N = ( 1 − r ) ( 1 − s ) / 4 N=(1-r)(1-s)/4 N = ( 1 − r ) ( 1 − s ) /4 on [ − 1 , 1 ] 2 [-1,1]^2 [ − 1 , 1 ] 2 , the physical gradient and Jacobian give the integral
1 16 ∫ − 1 1 ∫ − 1 1 ( ( 1 − s ) 2 + ( 1 − r ) 2 ) d r d s = 2 / 3. \frac{1}{16}\int_{-1}^{1}\int_{-1}^{1}\left((1-s)^2+(1-r)^2\right)\,dr\,ds=2/3. 16 1 ∫ − 1 1 ∫ − 1 1 ( ( 1 − s ) 2 + ( 1 − r ) 2 ) d r d s = 2/3.
Gauss quadrature is exact here. An interior node belongs to four elements, yielding ( K 0 ) i i ≤ 4 ν + ( 2 / 3 ) (K_0)_{ii}\leq4\nu_+(2/3) ( K 0 ) ii ≤ 4 ν + ( 2/3 ) .
Finally let v i ∈ R n P \mathbf{v}_i\in\mathbb{R}^{n_P} v i ∈ R n P be nodal values, extended by zero at boundary nodes, and let
U T q ( v ) = ∑ i ∈ T v i g T i q T ∈ R n P × 2 , U_{Tq}(\mathbf{v})=\sum_{i\in T}\mathbf{v}_i\mathbf{g}_{Tiq}^{\mathsf{T}}\in\mathbb{R}^{n_P\times2}, U T q ( v ) = i ∈ T ∑ v i g T i q T ∈ R n P × 2 ,
then
v T K ‾ v = ∑ T , q w T q a 0 , T q ∥ U T q ( v ) ∥ F 2 . \mathbf{v}^{\mathsf{T}}\overline{K}\mathbf{v}=\sum_{T,q}w_{Tq}a_{0,Tq}\lVert U_{Tq}(\mathbf{v})\rVert_F^2. v T K v = T , q ∑ w T q a 0 , T q ∥ U T q ( v ) ∥ F 2 .
while v T K v \mathbf{v}^{\mathsf{T}}K\mathbf{v} v T K v replaces the squared Frobenius norm by tr ( U T q ( v ) T A T q U T q ( v ) ) \operatorname{tr}(U_{Tq}(\mathbf{v})^{\mathsf{T}}A_{Tq}U_{Tq}(\mathbf{v})) tr ( U T q ( v ) T A T q U T q ( v )) . The eigenvalue bounds on A T q A_{Tq} A T q prove the final assertion. □
For each interior node i i i , let Q i Q_i Q i consist of all incident element–quadrature pairs. We take A i A_i A i to be the arithmetic average
A i = 1 ∣ Q i ∣ ∑ ( T , q ) ∈ Q i A T q , Ω h = max i max ( T , q ) ∈ Q i ∥ A T q − A i ∥ 2 h . (29) A_i = \frac{1}{|Q_i|}\sum_{(T,q)\in Q_i} A_{Tq}, \qquad\Omega_h = \max_i\max_{(T,q)\in Q_i}\frac{\lVert A_{Tq}-A_i\rVert_2}{h}. \tag*{(29)} A i = ∣ Q i ∣ 1 ( T , q ) ∈ Q i ∑ A T q , Ω h = i max ( T , q ) ∈ Q i max h ∥ A T q − A i ∥ 2 . (29)
Each A i A_i A i is a convex combination of the symmetric blocks A T q A_{Tq} A T q , and the set { X = X T : α I ⪯ X ⪯ β I } \{X=X^\mathsf{T}:\alpha I\preceq X\preceq\beta I\} { X = X T : α I ⪯ X ⪯ β I } is convex, then (25) gives α I ⪯ A i ⪯ β I \alpha I\preceq A_i\preceq\beta I α I ⪯ A i ⪯ β I . Consequently the matrix D D D defined next is symmetric positive definite, with ∥ D ∥ 2 ≤ β \lVert D\rVert_2\le\beta ∥ D ∥ 2 ≤ β and ∥ D − 1 ∥ 2 ≤ α − 1 \lVert D^{-1}\rVert_2\le\alpha^{-1} ∥ D − 1 ∥ 2 ≤ α − 1 . Define the nodal block-diagonal multiplication matrix D = diag i ( A i ) D=\operatorname{diag}_i(A_i) D = diag i ( A i ) and set
K = D K ‾ + R . (30) \mathcal{K}=D\overline{\mathcal{K}}+R. \tag*{(30)} K = D K + R . (30)
Lemma 5.5. Under Assumption 5.3, the remainder in (30) satisfies
∥ R v ∥ M − 1 ≤ C R Ω h ∥ v ∥ K ‾ , C R = 96 ν + . (31) \lVert Rv\rVert_{\mathcal{M}^{-1}}\le C_R\Omega_h\lVert v\rVert_{\overline{\mathcal{K}}},\qquad C_R=\sqrt{96\nu_+}. \tag*{(31)} ∥ R v ∥ M − 1 ≤ C R Ω h ∥ v ∥ K , C R = 96 ν + . (31)
Proof. Subtracting the two assembled rows before the boundary values are eliminated, we find that the i i i th block row is exactly
( R v ) i = ∑ ( T , q ) ∈ Q i w T q a 0 , T q ( A T q − A i ) U T q ( v ) g T i q . (Rv)_i=\sum_{(T,q)\in Q_i}w_{Tq}a_{0,Tq}(A_{Tq}-A_i)U_{Tq}(v)g_{Tiq}. ( R v ) i = ( T , q ) ∈ Q i ∑ w T q a 0 , T q ( A T q − A i ) U T q ( v ) g T i q .
Since ∥ U g ∥ 2 ≤ ∥ U ∥ F ∥ g ∥ 2 \lVert Ug\rVert_2\le\lVert U\rVert_F\lVert g\rVert_2 ∥ U g ∥ 2 ≤ ∥ U ∥ F ∥ g ∥ 2 , weighted Cauchy–Schwarz gives
∥ ( R v ) i ∥ 2 2 ≤ h 2 Ω h 2 ( ∑ Q i w T q a 0 , T q ∥ g T i q ∥ 2 2 ) ( ∑ Q i w T q a 0 , T q ∥ U T q ( v ) ∥ F 2 ) . \lVert(Rv)_i\rVert_2^2\le h^2\Omega_h^2\left(\sum_{Q_i}w_{Tq}a_{0,Tq}\lVert g_{Tiq}\rVert_2^2\right)\left(\sum_{Q_i}w_{Tq}a_{0,Tq}\lVert U_{Tq}(v)\rVert_F^2\right). ∥( R v ) i ∥ 2 2 ≤ h 2 Ω h 2 Q i ∑ w T q a 0 , T q ∥ g T i q ∥ 2 2 Q i ∑ w T q a 0 , T q ∥ U T q ( v ) ∥ F 2 .
The first parenthesis equals ( K 0 ) i i ≤ 8 ν + / 3 (K_0)_{ii}\le8\nu_+/3 ( K 0 ) ii ≤ 8 ν + /3 . Upon summing over interior nodes, any element energy is counted at most four times. Thus
∥ R v ∥ 2 2 ≤ 32 ν + 3 h 2 Ω h 2 v T K ‾ v . \lVert Rv\rVert_2^2\le\frac{32\nu_+}{3}h^2\Omega_h^2v^\mathsf{T}\overline{\mathcal{K}}v. ∥ R v ∥ 2 2 ≤ 3 32 ν + h 2 Ω h 2 v T K v .
By (28) , M D − 1 ⪯ 9 h − 2 I M_D^{-1}\preceq9h^{-2}I M D − 1 ⪯ 9 h − 2 I , hence M − 1 = I n P ⊗ M D − 1 ⪯ 9 h − 2 I \mathcal{M}^{-1}=I_{n_P}\otimes M_D^{-1}\preceq9h^{-2}I M − 1 = I n P ⊗ M D − 1 ⪯ 9 h − 2 I and
∥ R v ∥ M − 1 2 = ( R v ) T M − 1 ( R v ) ≤ ( R v ) T ( 9 h − 2 I ) ( R v ) = 9 h − 2 ∥ R v ∥ 2 2 ≤ 96 ν + Ω h 2 ∥ v ∥ K ‾ 2 . \lVert Rv\rVert_{\mathcal{M}^{-1}}^2=(Rv)^\mathsf{T}\mathcal{M}^{-1}(Rv)\le(Rv)^\mathsf{T}(9h^{-2}I)(Rv)=9h^{-2}\lVert Rv\rVert_2^2\le96\nu_+\Omega_h^2\lVert v\rVert_{\overline{\mathcal{K}}}^2. ∥ R v ∥ M − 1 2 = ( R v ) T M − 1 ( R v ) ≤ ( R v ) T ( 9 h − 2 I ) ( R v ) = 9 h − 2 ∥ R v ∥ 2 2 ≤ 96 ν + Ω h 2 ∥ v ∥ K 2 .
Taking square roots gives (31) with C R = 96 ν + C_R=\sqrt{96\nu_+} C R = 96 ν + . All vector bounds use operator norms of the coefficient blocks. The Frobenius norm above sums the physical gradient energies, not the entries of A T q A_{Tq} A T q .
Lemma 5.6 (Multiplication and discrete energy estimates). For all f ∈ R N f\in\mathbb{R}^N f ∈ R N ,
∥ D f ∥ M − 1 ≤ 3 β ∥ f ∥ M − 1 , ∥ D − 1 f ∥ M − 1 ≤ 3 α ∥ f ∥ M − 1 . (32) \lVert Df\rVert_{\mathcal{M}^{-1}}\le3\beta\lVert f\rVert_{\mathcal{M}^{-1}},\qquad\lVert D^{-1}f\rVert_{\mathcal{M}^{-1}}\le\frac{3}{\alpha}\lVert f\rVert_{\mathcal{M}^{-1}}. \tag*{(32)} ∥ D f ∥ M − 1 ≤ 3 β ∥ f ∥ M − 1 , ∥ D − 1 f ∥ M − 1 ≤ α 3 ∥ f ∥ M − 1 . (32) With c ∗ : = λ ∗ − 1 / 2 c_*:=\lambda_*^{-1/2} c ∗ := λ ∗ − 1/2 , one also has
∥ v ∥ K ‾ ≤ c ∗ ∥ K ‾ v ∥ M − 1 , ∥ v ∥ K ≤ c ∗ α ∥ K v ∥ M − 1 . (33) \lVert v\rVert_{\overline{\mathcal{K}}}\le c_*\lVert\overline{\mathcal{K}}v\rVert_{\mathcal{M}^{-1}},\qquad\lVert v\rVert_{\mathcal{K}}\le\frac{c_*}{\alpha}\lVert\mathcal{K}v\rVert_{\mathcal{M}^{-1}}. \tag*{(33)} ∥ v ∥ K ≤ c ∗ ∥ K v ∥ M − 1 , ∥ v ∥ K ≤ α c ∗ ∥ K v ∥ M − 1 . (33)
Proof. Since the spectral condition number cond 2 ( M ) = λ max ( M ) / λ min ( M ) \operatorname{cond}_{2}(\mathcal{M}) = \lambda_{\max}(\mathcal{M})/\lambda_{\min}(\mathcal{M}) cond 2 ( M ) = λ m a x ( M ) / λ m i n ( M ) , the operator norm of the nodal multiplication, which multiplies the gPC coefficients at each node i i i by A i A_i A i , satisfies
∥ M − 1 / 2 D M 1 / 2 ∥ 2 ≤ cond 2 ( M ) ∥ D ∥ 2 ≤ 3 β . \lVert\mathcal{M}^{-1/2}D\mathcal{M}^{1/2}\rVert_{2} \le\sqrt{\operatorname{cond}_{2}(\mathcal{M})}\lVert D\rVert_{2} \le3\beta. ∥ M − 1/2 D M 1/2 ∥ 2 ≤ cond 2 ( M ) ∥ D ∥ 2 ≤ 3 β .
Applying the same argument to D − 1 D^{-1} D − 1 yields 3 / α 3/\alpha 3/ α .
Since K ‾ = I n P ⊗ K 0 ⪰ λ ∗ M \overline{K}=I_{n_P}\otimes K_0 \succeq\lambda_*\mathcal{M} K = I n P ⊗ K 0 ⪰ λ ∗ M by (28) , we have ∥ v ∥ M ≤ c ∗ ∥ v ∥ K ‾ \lVert v\rVert_{\mathcal{M}} \le c_*\lVert v\rVert_{\overline{K}} ∥ v ∥ M ≤ c ∗ ∥ v ∥ K . The weighted Cauchy–Schwarz inequality ∣ a ⊤ b ∣ ≤ ∥ a ∥ M ∥ b ∥ M − 1 \lvert a^\top b\rvert\le\lVert a\rVert_{\mathcal{M}}\lVert b\rVert_{\mathcal{M}^{-1}} ∣ a ⊤ b ∣ ≤ ∥ a ∥ M ∥ b ∥ M − 1 with a = v a=v a = v , b = K ‾ v b=\overline{K}v b = K v then gives
∥ v ∥ K ‾ 2 = v ⊤ K ‾ v ≤ ∥ v ∥ M ∥ K ‾ v ∥ M − 1 ≤ c ∗ ∥ v ∥ K ‾ ∥ K ‾ v ∥ M − 1 , \lVert v\rVert_{\overline{K}}^2 = v^\top\overline{K}v \le\lVert v\rVert_{\mathcal{M}}\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}} \le c_*\lVert v\rVert_{\overline{K}}\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}}, ∥ v ∥ K 2 = v ⊤ K v ≤ ∥ v ∥ M ∥ K v ∥ M − 1 ≤ c ∗ ∥ v ∥ K ∥ K v ∥ M − 1 ,
Similarly,
α ∥ v ∥ K ‾ 2 ≤ v ⊤ K v ≤ ∥ v ∥ M ∥ K v ∥ M − 1 ≤ c ∗ ∥ v ∥ K ‾ ∥ K v ∥ M − 1 . \alpha\lVert v\rVert_{\overline{K}}^2 \le v^\top Kv \le\lVert v\rVert_{\mathcal{M}}\lVert Kv\rVert_{\mathcal{M}^{-1}} \le c_*\lVert v\rVert_{\overline{K}}\lVert Kv\rVert_{\mathcal{M}^{-1}}. α ∥ v ∥ K 2 ≤ v ⊤ K v ≤ ∥ v ∥ M ∥ K v ∥ M − 1 ≤ c ∗ ∥ v ∥ K ∥ K v ∥ M − 1 .
Dividing by ∥ v ∥ K ‾ \lVert v\rVert_{\overline{K}} ∥ v ∥ K (the case v = 0 v=0 v = 0 is trivial) yields (33) .
Theorem 5.7. Under Assumption 5.3 , let
q h = C R c ∗ Ω h , U h = 3 β + q h , V h = 3 α ( 1 + q h α ) . (34) q_h = C_Rc_*\Omega_h,\qquad U_h = 3\beta+ q_h,\qquad V_h = \frac{3}{\alpha}\left(1+\frac{q_h}{\alpha}\right). \tag*{(34)} q h = C R c ∗ Ω h , U h = 3 β + q h , V h = α 3 ( 1 + α q h ) . (34) Then
V h − 1 ∥ K ‾ v ∥ M − 1 ≤ ∥ K v ∥ M − 1 ≤ U h ∥ K ‾ v ∥ M − 1 , V h − 2 H 0 ⪯ H ⪯ U h 2 H 0 . (35) V_h^{-1}\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}} \le\lVert Kv\rVert_{\mathcal{M}^{-1}} \le U_h\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}},\qquad V_h^{-2}H_0 \preceq H \preceq U_h^2H_0. \tag*{(35)} V h − 1 ∥ K v ∥ M − 1 ≤ ∥ K v ∥ M − 1 ≤ U h ∥ K v ∥ M − 1 , V h − 2 H 0 ⪯ H ⪯ U h 2 H 0 . (35) No smallness of q h q_h q h , Ω h \Omega_h Ω h , or K − K ‾ K-\overline{K} K − K is required.
Proof. The upper bound follows from (30) and Lemmas 5.5 and 5.6:
∥ K v ∥ M − 1 ≤ 3 β ∥ K ‾ v ∥ M − 1 + C R Ω h ∥ v ∥ K ‾ ≤ U h ∥ K ‾ v ∥ M − 1 . \lVert Kv\rVert_{\mathcal{M}^{-1}} \le3\beta\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}} + C_R\Omega_h\lVert v\rVert_{\overline{K}} \le U_h\lVert\overline{K}v\rVert_{\mathcal{M}^{-1}}. ∥ K v ∥ M − 1 ≤ 3 β ∥ K v ∥ M − 1 + C R Ω h ∥ v ∥ K ≤ U h ∥ K v ∥ M − 1 .
For the other one, let f = K v f=Kv f = K v , then the decomposition gives K ‾ v = D − 1 ( f − R v ) \overline{K}v=D^{-1}(f-Rv) K v = D − 1 ( f − R v ) , and therefore
∥ K ‾ v ∥ M − 1 ≤ 3 α ( ∥ f ∥ M − 1 + C R Ω h ∥ v ∥ K ‾ ) ≤ 3 α ( 1 + C R c ∗ Ω h α ) ∥ f ∥ M − 1 . \lVert\overline{K}v\rVert_{\mathcal{M}^{-1}} \le\frac{3}{\alpha}\left(\lVert f\rVert_{\mathcal{M}^{-1}}+C_R\Omega_h\lVert v\rVert_{\overline{K}}\right) \le\frac{3}{\alpha}\left(1+\frac{C_Rc_*\Omega_h}{\alpha}\right)\lVert f\rVert_{\mathcal{M}^{-1}}. ∥ K v ∥ M − 1 ≤ α 3 ( ∥ f ∥ M − 1 + C R Ω h ∥ v ∥ K ) ≤ α 3 ( 1 + α C R c ∗ Ω h ) ∥ f ∥ M − 1 .
Here the second inequality uses energy coercivity of K K K . Finally, ∥ K v ∥ M − 1 2 = v ⊤ H v \lVert Kv\rVert_{\mathcal{M}^{-1}}^2=v^\top Hv ∥ K v ∥ M − 1 2 = v ⊤ H v and ∥ K ‾ v ∥ M − 1 2 = v ⊤ H 0 v \lVert\overline{K}v\rVert_{\mathcal{M}^{-1}}^2=v^\top H_0v ∥ K v ∥ M − 1 2 = v ⊤ H 0 v , so squaring gives the matrix inequalities.
Corollary 5.8. Let the side length L D L_D L D be fixed, and suppose the local constants ν − , ν + , α , β \nu_-,\nu_+,\alpha,\beta ν − , ν + , α , β can be chosen uniformly over a family of meshes and stochastic spaces, with ν − , α > 0 \nu_-,\alpha>0 ν − , α > 0 , and suppose Ω h ≤ Ω \Omega_h\le\Omega Ω h ≤ Ω uniformly. Define
q = C R c ∗ Ω , U = 3 β + q , V = 3 α ( 1 + q / α ) . q=C_Rc_*\Omega,\qquad U=3\beta+q,\qquad V=\frac{3}{\alpha}(1+q/\alpha). q = C R c ∗ Ω , U = 3 β + q , V = α 3 ( 1 + q / α ) . Then for every member of the family, every γ > 0 \gamma>0 γ > 0 , and every current mask,
spec ( P W − 1 J ) ⊂ [ min { V − 2 , 1 } , max { U 2 , 1 } ] . (36) \operatorname{spec}(P_W^{-1}J)\subset[\min\{V^{-2},1\},\max\{U^2,1\}]. \tag*{(36)} spec ( P W − 1 J ) ⊂ [ min { V − 2 , 1 } , max { U 2 , 1 }] . (36) The interval is independent of h , n P , N K , γ h,n_P,N_K,\gamma h , n P , N K , γ , and the mask D ( p ) D(\mathbf{p}) D ( p ) .
Proof. The constants in (28) and (31) depend only on d , ν − , ν + d,\nu_-,\nu_+ d , ν − , ν + . Hence Theorem 5.7 gives uniform constants U , V U,V U , V , and Theorem 5.2 applies with c = V − 2 c=V^{-2} c = V − 2 and C = U 2 C=U^2 C = U 2 . ∢
Perturbation bounds and PCG convergence
Back to stochastic-major ordering, multiplication in (21) gives the exact identity
T = I + E , E = ∑ ℓ = 1 N K − 1 G ℓ ⊗ B ℓ , B ℓ = M D − 1 / 2 K ℓ K 0 − 1 M D 1 / 2 . (37) \mathcal{T}=I+\mathcal{E},\qquad\mathcal{E}=\sum_{\ell=1}^{N_K-1}G_\ell\otimes B_\ell,\qquad B_\ell=M_D^{-1/2}K_\ell K_0^{-1}M_D^{1/2}. \tag*{(37)} T = I + E , E = ℓ = 1 ∑ N K − 1 G ℓ ⊗ B ℓ , B ℓ = M D − 1/2 K ℓ K 0 − 1 M D 1/2 . (37)
Proposition 5.9 (Small-perturbation enclosure). If ∥ E ∥ 2 ≤ δ < 1 \|\mathcal{E}\|_2\le\delta<1 ∥ E ∥ 2 ≤ δ < 1 , then
spec ( P W − 1 J ) ⊂ [ ( 1 − δ ) 2 , ( 1 + δ ) 2 ] , cond s p ( P W − 1 J ) ≤ ( 1 + δ 1 − δ ) 2 . (38) \operatorname{spec}(P_W^{-1}J)\subset[(1-\delta)^2,(1+\delta)^2],\qquad\operatorname{cond}_{\mathrm{sp}}(P_W^{-1}J)\le\left(\frac{1+\delta}{1-\delta}\right)^2. \tag*{(38)} spec ( P W − 1 J ) ⊂ [( 1 − δ ) 2 , ( 1 + δ ) 2 ] , cond sp ( P W − 1 J ) ≤ ( 1 − δ 1 + δ ) 2 . (38) Moreover,
∥ E ∥ 2 ≤ ∑ ℓ = 1 N K − 1 ∥ G ℓ ∥ 2 ∥ B ℓ ∥ 2 . (39) \|\mathcal{E}\|_2\le\sum_{\ell=1}^{N_K-1}\|G_\ell\|_2\|B_\ell\|_2. \tag*{(39)} ∥ E ∥ 2 ≤ ℓ = 1 ∑ N K − 1 ∥ G ℓ ∥ 2 ∥ B ℓ ∥ 2 . (39) Proof. The triangle and reverse triangle inequalities give ( 1 − δ ) ∥ z ∥ 2 ≤ ∥ T z ∥ 2 ≤ ( 1 + δ ) ∥ z ∥ 2 (1-\delta)\|z\|_2\le\|\mathcal{T}z\|_2\le(1+\delta)\|z\|_2 ( 1 − δ ) ∥ z ∥ 2 ≤ ∥ T z ∥ 2 ≤ ( 1 + δ ) ∥ z ∥ 2 . Hence σ − ≥ 1 − δ \sigma_-\ge1-\delta σ − ≥ 1 − δ and σ + ≤ 1 + δ \sigma_+\le1+\delta σ + ≤ 1 + δ , so Lemma 5.1 gives ( 1 − δ ) 2 H 0 ⪯ H ⪯ ( 1 + δ ) 2 H 0 (1-\delta)^2H_0\preceq H\preceq(1+\delta)^2H_0 ( 1 − δ ) 2 H 0 ⪯ H ⪯ ( 1 + δ ) 2 H 0 . Theorem 5.2 with c = ( 1 − δ ) 2 ≤ 1 ≤ C = ( 1 + δ ) 2 c=(1-\delta)^2\le1\le C=(1+\delta)^2 c = ( 1 − δ ) 2 ≤ 1 ≤ C = ( 1 + δ ) 2 then yields (38) .
For (39) , the triangle inequality gives ∥ E ∥ 2 ≤ ∑ ℓ ∥ G ℓ ⊗ B ℓ ∥ 2 \|\mathcal{E}\|_2\le\sum_\ell\|G_\ell\otimes B_\ell\|_2 ∥ E ∥ 2 ≤ ∑ ℓ ∥ G ℓ ⊗ B ℓ ∥ 2 , and ∥ G ℓ ⊗ B ℓ ∥ 2 = ∥ G ℓ ∥ 2 ∥ B ℓ ∥ 2 \|G_\ell\otimes B_\ell\|_2=\|G_\ell\|_2\|B_\ell\|_2 ∥ G ℓ ⊗ B ℓ ∥ 2 = ∥ G ℓ ∥ 2 ∥ B ℓ ∥ 2 because the singular values of a Kronecker product are the products of the singular values of its factors (tensor the two singular value decompositions).
The following proposition gives computable bounds on ∥ B ℓ ∥ 2 \|B_\ell\|_2 ∥ B ℓ ∥ 2 and ∥ E ∥ 2 \|\mathcal{E}\|_2 ∥ E ∥ 2 from local coefficient values, rather than assuming the desired graph-matrix bound. Let K ℓ K_\ell K ℓ be assembled with scalar weights a ℓ , T q a_{\ell,Tq} a ℓ , T q , and let μ ℓ , T q = a ℓ , T q / a 0 , T q \mu_{\ell,Tq}=a_{\ell,Tq}/a_{0,Tq} μ ℓ , T q = a ℓ , T q / a 0 , T q . Define
d ℓ i = 1 ∣ Q i ∣ ∑ Q i μ ℓ , T q , b ℓ = max T , q ∣ μ ℓ , T q ∣ , ω ℓ , h = max i , ( T , q ) ∈ Q i ∣ μ ℓ , T q − d ℓ i ∣ h . d_{\ell i}=\frac{1}{|Q_i|}\sum_{Q_i}\mu_{\ell,Tq},\qquad b_\ell=\max_{T,q}|\mu_{\ell,Tq}|,\qquad\omega_{\ell,h}=\max_{i,(T,q)\in Q_i}\frac{|\mu_{\ell,Tq}-d_{\ell i}|}{h}. d ℓ i = ∣ Q i ∣ 1 Q i ∑ μ ℓ , T q , b ℓ = T , q max ∣ μ ℓ , T q ∣ , ω ℓ , h = i , ( T , q ) ∈ Q i max h ∣ μ ℓ , T q − d ℓ i ∣ .
Proposition 5.10. With the matrix assumptions above, signed fluctuation arrays satisfy
∥ B ℓ ∥ 2 ≤ 3 b ℓ + C R c ∗ ω ℓ , h . (40) \|B_\ell\|_2\le3b_\ell+C_{R}c_*\omega_{\ell,h}. \tag*{(40)} ∥ B ℓ ∥ 2 ≤ 3 b ℓ + C R c ∗ ω ℓ , h . (40) Alternatively, for the jointly assembled blocks, let τ h = max i ∥ A i − I ∥ 2 \tau_h=\max_i\|A_i-I\|_2 τ h = max i ∥ A i − I ∥ 2 . Then
∥ E ∥ 2 ≤ 3 τ h + C R c ∗ Ω h . (41) \|\mathcal{E}\|_2\le3\tau_h+C_{R}c_*\Omega_h. \tag*{(41)} ∥ E ∥ 2 ≤ 3 τ h + C R c ∗ Ω h . (41) Proof. Let D ℓ = diag ( d ℓ i ) D_\ell=\operatorname{diag}(d_{\ell i}) D ℓ = diag ( d ℓ i ) and R ℓ = K ℓ − D ℓ K 0 R_\ell=K_\ell-D_\ell K_0 R ℓ = K ℓ − D ℓ K 0 . The proof of Lemma 5.5 carries over to the scalar case n P = 1 n_P=1 n P = 1 , with A T q A_{Tq} A T q and A i A_i A i replaced by μ ℓ , T q \mu_{\ell,Tq} μ ℓ , T q and d ℓ i d_{\ell i} d ℓ i . Positivity is needed only for a 0 , T q a_{0,Tq} a 0 , T q , not for μ ℓ , T q \mu_{\ell,Tq} μ ℓ , T q . Since ∣ d ℓ i ∣ ≤ b ℓ |d_{\ell i}|\le b_\ell ∣ d ℓ i ∣ ≤ b ℓ , the argument for (32) also applies to D ℓ D_\ell D ℓ . Hence
∥ R ℓ v ∥ M D − 1 ≤ C R ω ℓ , h ∥ v ∥ K 0 , ∥ D ℓ f ∥ M D − 1 ≤ 3 b ℓ ∥ f ∥ M D − 1 . \|R_\ell v\|_{M_D^{-1}}\le C_R\omega_{\ell,h}\|v\|_{K_0},\qquad\|D_\ell f\|_{M_D^{-1}}\le3b_\ell\|f\|_{M_D^{-1}}. ∥ R ℓ v ∥ M D − 1 ≤ C R ω ℓ , h ∥ v ∥ K 0 , ∥ D ℓ f ∥ M D − 1 ≤ 3 b ℓ ∥ f ∥ M D − 1 . Substituting v = K 0 − 1 M D 1 / 2 z v=K_0^{-1}M_D^{1/2}z v = K 0 − 1 M D 1/2 z in the definition of B ℓ B_\ell B ℓ gives
∥ B ℓ ∥ 2 = sup z ≠ 0 ∥ M D − 1 / 2 K ℓ K 0 − 1 M D 1 / 2 z ∥ 2 ∥ z ∥ 2 = sup v ≠ 0 ∥ K ℓ v ∥ M D − 1 ∥ K 0 v ∥ M D − 1 . \|B_\ell\|_2=\sup_{z\ne0}\frac{\|M_D^{-1/2}K_\ell K_0^{-1}M_D^{1/2}z\|_2}{\|z\|_2}=\sup_{v\ne0}\frac{\|K_\ell v\|_{M_D^{-1}}}{\|K_0v\|_{M_D^{-1}}}. ∥ B ℓ ∥ 2 = z = 0 sup ∥ z ∥ 2 ∥ M D − 1/2 K ℓ K 0 − 1 M D 1/2 z ∥ 2 = v = 0 sup ∥ K 0 v ∥ M D − 1 ∥ K ℓ v ∥ M D − 1 .
Since K ℓ = D ℓ K 0 + R ℓ K_{\ell}=D_{\ell}K_{0}+R_{\ell} K ℓ = D ℓ K 0 + R ℓ , the two estimates above with f = K 0 v f=K_{0}v f = K 0 v , together with the first inequality in (33) for n P = 1 n_{P}=1 n P = 1 , i.e., ∥ v ∥ K 0 ≤ c ∗ ∥ K 0 v ∥ M D − 1 \lVert v\rVert_{K_{0}}\le c_{*}\lVert K_{0}v\rVert_{M_{D}^{-1}} ∥ v ∥ K 0 ≤ c ∗ ∥ K 0 v ∥ M D − 1 , give
∥ K ℓ v ∥ M D − 1 ≤ 3 b ℓ ∥ K 0 v ∥ M D − 1 + C R ω ℓ , h ∥ v ∥ K 0 ≤ ( 3 b ℓ + C R c ∗ ω ℓ , h ) ∥ K 0 v ∥ M D − 1 . \lVert K_{\ell}v\rVert_{M_{D}^{-1}}\le3b_{\ell}\lVert K_{0}v\rVert_{M_{D}^{-1}}+C_{R}\omega_{\ell,h}\lVert v\rVert_{K_{0}}\le\left(3b_{\ell}+C_{R}c_{*}\omega_{\ell,h}\right)\lVert K_{0}v\rVert_{M_{D}^{-1}}. ∥ K ℓ v ∥ M D − 1 ≤ 3 b ℓ ∥ K 0 v ∥ M D − 1 + C R ω ℓ , h ∥ v ∥ K 0 ≤ ( 3 b ℓ + C R c ∗ ω ℓ , h ) ∥ K 0 v ∥ M D − 1 .
Taking the supremum over v ≠ 0 v\ne0 v = 0 proves (40) . For (41) , we find K − K ‾ = ( D − I ) K ‾ + R \mathcal{K}-\overline{\mathcal{K}}=(D-I)\overline{\mathcal{K}}+R K − K = ( D − I ) K + R and apply the same estimates with the joint block norm τ h \tau_h τ h . Then, taking the supremum over v v v gives the claim.
Corollary 5.11. Suppose, uniformly over the considered meshes and stochastic spaces,
∑ ℓ = 1 N K − 1 ∥ G ℓ ∥ 2 b ℓ ≤ η < 1 , ∑ ℓ = 1 N K − 1 ∥ G ℓ ∥ 2 ω ℓ , h ≤ Ω 0 < ∞ . \sum_{\ell=1}^{N_{\mathcal{K}}-1}\lVert G_{\ell}\rVert_{2}b_{\ell}\le\eta<1,\qquad
\sum_{\ell=1}^{N_{\mathcal{K}}-1}\lVert G_{\ell}\rVert_{2}\omega_{\ell,h}\le\Omega_{0}<\infty. ℓ = 1 ∑ N K − 1 ∥ G ℓ ∥ 2 b ℓ ≤ η < 1 , ℓ = 1 ∑ N K − 1 ∥ G ℓ ∥ 2 ω ℓ , h ≤ Ω 0 < ∞. Then (27) satisfies the uniform local hypotheses with α = 1 − η \alpha=1-\eta α = 1 − η , β = 1 + η \beta=1+\eta β = 1 + η , and Ω = Ω 0 \Omega=\Omega_{0} Ω = Ω 0 . Consequently Corollary 5.8 applies, whether or not 3 η + C R c ∗ Ω 0 < 1 3\eta+C_{R}c_{*}\Omega_{0}<1 3 η + C R c ∗ Ω 0 < 1 .
Proof. By (27) and the triangle inequality, ∥ A T q − I ∥ 2 ≤ ∑ ℓ ∣ μ ℓ , T q ∣ ∥ G ℓ ∥ 2 ≤ ∑ ℓ b ℓ ∥ G ℓ ∥ 2 ≤ η \lVert A_{Tq}-I\rVert_{2}\le\sum_{\ell}|\mu_{\ell,Tq}|\lVert G_{\ell}\rVert_{2}\le\sum_{\ell}b_{\ell}\lVert G_{\ell}\rVert_{2}\le\eta ∥ A T q − I ∥ 2 ≤ ∑ ℓ ∣ μ ℓ , T q ∣ ∥ G ℓ ∥ 2 ≤ ∑ ℓ b ℓ ∥ G ℓ ∥ 2 ≤ η . Since every G ℓ G_{\ell} G ℓ is symmetric, so is A T q − I A_{Tq}-I A T q − I . Hence its eigenvalues lie in [ − η , η ] [-\eta,\eta] [ − η , η ] , i.e., ( 1 − η ) I ⪯ A T q ⪯ ( 1 + η ) I (1-\eta)I\preceq A_{Tq}\preceq(1+\eta)I ( 1 − η ) I ⪯ A T q ⪯ ( 1 + η ) I . Linearity of the same nodal averaging gives A i = I + ∑ ℓ d ℓ i G ℓ A_i=I+\sum_{\ell}d_{\ell i}G_{\ell} A i = I + ∑ ℓ d ℓ i G ℓ and
∥ A T q − A i ∥ 2 ≤ ∑ ℓ ∥ G ℓ ∥ 2 ∣ μ ℓ , T q − d ℓ i ∣ ≤ h Ω 0 . \lVert A_{Tq}-A_i\rVert_{2}\le\sum_{\ell}\lVert G_{\ell}\rVert_{2}|\mu_{\ell,Tq}-d_{\ell i}|\le h\Omega_{0}. ∥ A T q − A i ∥ 2 ≤ ℓ ∑ ∥ G ℓ ∥ 2 ∣ μ ℓ , T q − d ℓ i ∣ ≤ h Ω 0 .
It remains to show how the preconditioner is applied.
Proposition 5.12 (Exact current-set inverse). Let C D = B B T C_D=BB^{\mathsf{T}} C D = B B T with B ∈ R N × r B\in\mathbb{R}^{N\times r} B ∈ R N × r ; the columns need not be independent. From the SMW identity
( A + U C V ) − 1 = A − 1 − A − 1 U ( C − 1 + V A − 1 U ) − 1 V A − 1 . (A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. ( A + U C V ) − 1 = A − 1 − A − 1 U ( C − 1 + V A − 1 U ) − 1 V A − 1 . Here we use A = H 0 A=H_{0} A = H 0 , U = B U=B U = B , V = B T V=B^{\mathsf{T}} V = B T , C = γ − 1 I r C=\gamma^{-1}I_{r} C = γ − 1 I r , gives
P W − 1 = ( H 0 + B ( γ − 1 I r ) B T ) − 1 = H 0 − 1 − H 0 − 1 B ( γ I r + B T H 0 − 1 B ) − 1 B T H 0 − 1 . (42) P_{W}^{-1}=(H_{0}+B(\gamma^{-1}I_{r})B^{\mathsf{T}})^{-1}=H_{0}^{-1}-H_{0}^{-1}B(\gamma I_{r}+B^{\mathsf{T}}H_{0}^{-1}B)^{-1}B^{\mathsf{T}}H_{0}^{-1}. \tag*{(42)} P W − 1 = ( H 0 + B ( γ − 1 I r ) B T ) − 1 = H 0 − 1 − H 0 − 1 B ( γ I r + B T H 0 − 1 B ) − 1 B T H 0 − 1 . (42) For a binary mask, one may take the columns of E T W 1 / 2 E^{\mathsf{T}}W^{1/2} E T W 1/2 selected by D D D . Reusing unchanged columns of B B B , H 0 − 1 B H_{0}^{-1}B H 0 − 1 B , computing added columns, and discarding removed columns preserves this inverse if the correction matrix is formed and solved for the current columns.
Proof. The matrix Z γ = γ I r + B T H 0 − 1 B Z_{\gamma}=\gamma I_{r}+B^{\mathsf{T}}H_{0}^{-1}B Z γ = γ I r + B T H 0 − 1 B is SPD since q T Z γ q ≥ γ ∥ q ∥ 2 2 \mathbf{q}^{\mathsf{T}}Z_{\gamma}\mathbf{q}\ge\gamma\lVert\mathbf{q}\rVert_{2}^{2} q T Z γ q ≥ γ ∥ q ∥ 2 2 for all q ∈ R r \mathbf{q}\in\mathbb{R}^{r} q ∈ R r . Multiplying the right-hand side of (42) by P W P_{W} P W on the left gives
I + B [ γ − 1 I r − Z γ − 1 − γ − 1 B T H 0 − 1 B Z γ − 1 ] ( H 0 − 1 B ) T = I . I+B\left[\gamma^{-1}I_{r}-Z_{\gamma}^{-1}-\gamma^{-1}B^{\mathsf{T}}H_{0}^{-1}BZ_{\gamma}^{-1}\right](H_{0}^{-1}B)^{\mathsf{T}}=I. I + B [ γ − 1 I r − Z γ − 1 − γ − 1 B T H 0 − 1 B Z γ − 1 ] ( H 0 − 1 B ) T = I . For r = 0 r=0 r = 0 , the correction is absent. Because H 0 H_{0} H 0 is fixed, an unchanged column has the same inverse image. Reordering the columns simply permutes Z γ Z_{\gamma} Z γ . Finally, we have
H 0 − 1 = I n P ⊗ ( K 0 − 1 M D K 0 − 1 ) , H_{0}^{-1}=I_{n_{P}}\otimes(K_{0}^{-1}M_{D}K_{0}^{-1}), H 0 − 1 = I n P ⊗ ( K 0 − 1 M D K 0 − 1 ) , so its action uses reference stiffness solves and a mass multiplication, without assembling the double-stiffness matrix.
Corollary 5.13 (PCG consequence). Consider one Newton system J x = b \mathbf{J}x=\mathbf{b} J x = b with current-set preconditioner P W P_W P W . If (24) holds, let χ = θ + / θ − \chi=\theta_+/\theta_- χ = θ + / θ − . With exact arithmetic and exact preconditioner applications, PCG satisfies
∥ x k − x ∗ ∥ J ≤ 2 ( χ − 1 χ + 1 ) k ∥ x 0 − x ∗ ∥ J . (43) \lVert x_k-x_\ast\rVert_J \le2\left(\frac{\sqrt{\chi}-1}{\sqrt{\chi}+1}\right)^k\lVert x_0-x_\ast\rVert_J. \tag*{(43)} ∥ x k − x ∗ ∥ J ≤ 2 ( χ + 1 χ − 1 ) k ∥ x 0 − x ∗ ∥ J . (43) Under Proposition 5.9, the right-hand side is bounded by 2 δ k ∥ x 0 − x ∗ ∥ J 2\delta^k\lVert x_0-x_\ast\rVert_J 2 δ k ∥ x 0 − x ∗ ∥ J .
Proof. PCG is CG for P W − 1 / 2 J P W − 1 / 2 P_W^{-1/2}JP_W^{-1/2} P W − 1/2 J P W − 1/2 after the substitution x ^ = P W 1 / 2 x \widehat{x}=P_W^{1/2}x x = P W 1/2 x . Its energy-error norm equals ∥ x − x ∗ ∥ J \lVert x-x_\ast\rVert_J ∥ x − x ∗ ∥ J . CG minimizes the SPD quadratic over its affine Krylov space. The Galerkin orthogonality of that minimizer bounds its relative energy error by the maximum modulus of any degree-k k k error polynomial with value one at zero on the spectral interval. The normalized Chebyshev polynomial gives the factor in (43) ; see, e.g., [14 ] . In the perturbation case, χ ≤ ( 1 + δ ) / ( 1 − δ ) \sqrt{\chi}\le(1+\delta)/(1-\delta) χ ≤ ( 1 + δ ) / ( 1 − δ ) , and substitution gives the factor δ \delta δ .
Numerical Experiments
This section reports two examples. Example 1 has a manufactured solution and measures the discretization error together with the solver cost. Example 2 has no known solution and measures how the solver cost depends on the noise amplitude, the stochastic space, the mesh and γ \gamma γ . The stochastic approximation uses total-degree Legendre polynomials in random variables. We use continuous bilinear finite elements on uniform Cartesian meshes with 2 n c 2^{n_c} 2 n c elements in each coordinate direction, that is, n e = 2 n c n_e=2^{n_c} n e = 2 n c and h = 2 1 − n c h=2^{1-n_c} h = 2 1 − n c in the notation of Assumption 5.3, where n c = 4 , … , 8 n_c=4,\ldots,8 n c = 4 , … , 8 . All runs start from the zero dual variable and use a normalized KKT stopping tolerance of 10 − 6 10^{-6} 1 0 − 6 . The inexact Newton forcing tolerance is bounded below by 10 − 12 10^{-12} 1 0 − 12 and above by η max = 10 − 2 \eta_{\max}=10^{-2} η m a x = 1 0 − 2 , and at most k max = 100 k_{\max}=100 k m a x = 100 Newton steps are allowed in both examples. Successful runs additionally satisfy a box-constraint violation not exceeding 10 − 12 10^{-12} 1 0 − 12 . In Example 1, they also satisfy a normalized primal–dual gap not exceeding 10 − 9 10^{-9} 1 0 − 9 . The computations use MATLAB R2023b on the 26-core Intel Xeon Gold 6230R machine.
We use the notation of (21) : M = I n P ⊗ M D \mathcal{M}=I_{n_P}\otimes M_D M = I n P ⊗ M D , K = I n P ⊗ K 0 \mathcal{K}=I_{n_P}\otimes K_0 K = I n P ⊗ K 0 and H 0 = K M − 1 K H_0=\mathcal{K}\mathcal{M}^{-1}\mathcal{K} H 0 = K M − 1 K . The stochastic quadrature integrates ψ i ψ j \psi_i\psi_j ψ i ψ j exactly, so V ξ T W ξ V ξ = I n P V_\xi^{\mathsf{T}}W_\xi V_\xi=I_{n_P} V ξ T W ξ V ξ = I n P and E T W E = I n P ⊗ M L ≈ M E^{\mathsf{T}}WE=I_{n_P}\otimes M_L\approx\mathcal{M} E T W E = I n P ⊗ M L ≈ M .
If every control value is free (D = I m D=I_m D = I m ) and K \mathcal{K} K is replaced by K ‾ \overline{\mathcal{K}} K , the Jacobian matrix (19) becomes approximately H 0 + γ − 1 M H_0+\gamma^{-1}\mathcal{M} H 0 + γ − 1 M . This sum is not factorized directly. Following the matching strategy of [29 ] , we use
P m e a n = ( K ‾ + γ − 1 / 2 M ) M − 1 ( K ‾ + γ − 1 / 2 M ) = I n P ⊗ [ ( K 0 + γ − 1 / 2 M D ) M D − 1 ( K 0 + γ − 1 / 2 M D ) ] . (44) P_{\mathrm{mean}}=(\overline{\mathcal{K}}+\gamma^{-1/2}\mathcal{M})\mathcal{M}^{-1}(\overline{\mathcal{K}}+\gamma^{-1/2}\mathcal{M})
=I_{n_P}\otimes\left[(K_0+\gamma^{-1/2}M_D)M_D^{-1}(K_0+\gamma^{-1/2}M_D)\right]. \tag*{(44)} P mean = ( K + γ − 1/2 M ) M − 1 ( K + γ − 1/2 M ) = I n P ⊗ [ ( K 0 + γ − 1/2 M D ) M D − 1 ( K 0 + γ − 1/2 M D ) ] . (44)
Expanding (44) gives
P m e a n = H 0 + 2 γ − 1 / 2 K ‾ + γ − 1 M = I n P ⊗ [ K 0 M D − 1 K 0 + 2 γ − 1 / 2 K 0 + γ − 1 M D ] . P_{\mathrm{mean}}=H_0+2\gamma^{-1/2}\overline{\mathcal{K}}+\gamma^{-1}\mathcal{M}
=I_{n_P}\otimes\left[K_0M_D^{-1}K_0+2\gamma^{-1/2}K_0+\gamma^{-1}M_D\right]. P mean = H 0 + 2 γ − 1/2 K + γ − 1 M = I n P ⊗ [ K 0 M D − 1 K 0 + 2 γ − 1/2 K 0 + γ − 1 M D ] .
The two outer terms reproduce H 0 + γ − 1 M H_0+\gamma^{-1}\mathcal{M} H 0 + γ − 1 M exactly. The cross term is controlled by ( K ‾ − γ − 1 / 2 M ) M − 1 ( K ‾ − γ − 1 / 2 M ) ⪰ 0 (\overline{\mathcal{K}}-\gamma^{-1/2}\mathcal{M})\mathcal{M}^{-1}(\overline{\mathcal{K}}-\gamma^{-1/2}\mathcal{M})\succeq0 ( K − γ − 1/2 M ) M − 1 ( K − γ − 1/2 M ) ⪰ 0 , which gives
H 0 + γ − 1 M ⪯ P m e a n ⪯ 2 ( H 0 + γ − 1 M ) . H_0+\gamma^{-1}\mathcal{M}\preceq P_{\mathrm{mean}}\preceq2(H_0+\gamma^{-1}\mathcal{M}). H 0 + γ − 1 M ⪯ P mean ⪯ 2 ( H 0 + γ − 1 M ) .
Only the sparse spatial matrix K ^ γ = K 0 + γ − 1 / 2 M D ∈ R n h × n h \widehat{K}_\gamma=K_0+\gamma^{-1/2}M_D\in\mathbb{R}^{n_h\times n_h} K γ = K 0 + γ − 1/2 M D ∈ R n h × n h is factorized by Cholesky decomposition. Using the identity ( B T ⊗ A ) vec ( X ) = vec ( A X B ) (B^{\mathsf{T}}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(AXB) ( B T ⊗ A ) vec ( X ) = vec ( A X B ) , we observe from (44) that
P m e a n − 1 r = vec ( K ^ γ − 1 M D K ^ γ − 1 R ) , P_{\mathrm{mean}}^{-1}r=\operatorname{vec}(\widehat{K}_\gamma^{-1}M_D\widehat{K}_\gamma^{-1}R), P mean − 1 r = vec ( K γ − 1 M D K γ − 1 R ) ,
where r = vec ( R ) \mathbf{r} = \operatorname{vec}(R) r = vec ( R ) with R ∈ R n h × n P R \in\mathbb{R}^{n_h \times n_P} R ∈ R n h × n P .
In practice, part of the control is saturated, and the term γ − 1 M \gamma^{-1}\mathcal{M} γ − 1 M overestimates γ − 1 E ⊤ W D ( p k ) E \gamma^{-1}E^{\top}W D(\mathbf{p}_k)E γ − 1 E ⊤ W D ( p k ) E . At Newton step k k k , we therefore replace γ − 1 \gamma^{-1} γ − 1 by ϑ ^ k / γ \widehat{\vartheta}_k/\gamma ϑ k / γ , where
ϑ k = 1 m Tr D ( p k ) ∈ [ 0 , 1 ] , \vartheta_k = \frac{1}{m}\operatorname{Tr}D(\mathbf{p}_k) \in[0,1], ϑ k = m 1 Tr D ( p k ) ∈ [ 0 , 1 ] ,
and Tr \operatorname{Tr} Tr stands for the trace operator. Next, let c k = ϑ ^ k / γ c_k = \sqrt{\widehat{\vartheta}_k}/\gamma c k = ϑ k / γ and K ^ k = K 0 + c k M D \widehat{K}_k = K_0 + c_kM_D K k = K 0 + c k M D . We then define an approximation P k P_k P k of P m e a n P_{\mathrm{mean}} P mean as follows:
P k = ( K ^ + c k M ) M − 1 ( K ^ + c k M ) , P k − 1 r = vec ( K ^ k − 1 M D K ^ k − 1 R ) . P_k = (\widehat{K}+c_k\mathcal{M})\mathcal{M}^{-1}(\widehat{K}+c_k\mathcal{M}), \qquad P_k^{-1}\mathbf{r} = \operatorname{vec}(\widehat{K}_k^{-1}M_D\widehat{K}_k^{-1}R). P k = ( K + c k M ) M − 1 ( K + c k M ) , P k − 1 r = vec ( K k − 1 M D K k − 1 R ) .
Observe then that P k = P m e a n P_k = P_{\mathrm{mean}} P k = P mean when ϑ ^ k = 1 \widehat{\vartheta}_k=1 ϑ k = 1 and P k = H 0 P_k = H_0 P k = H 0 when ϑ ^ k = 0 \widehat{\vartheta}_k=0 ϑ k = 0 . Note that K ^ k \widehat{K}_k K k is not recomputed at every Newton step. Let t k = ϑ k / γ t_k = \vartheta_k/\gamma t k = ϑ k / γ , and let t l a s t t_{\mathrm{last}} t last be its value at the last refactorization. We refactorize only at the first Newton step or when
∣ t k − t l a s t ∣ > 0.15 max { ∣ t k ∣ , ∣ t l a s t ∣ , ε m a c h } . \lvert t_k-t_{\mathrm{last}}\rvert> 0.15\max\{\lvert t_k\rvert,\lvert t_{\mathrm{last}}\rvert,\sqrt{\varepsilon_{\mathrm{mach}}}\}. ∣ t k − t last ∣ > 0.15 max {∣ t k ∣ , ∣ t last ∣ , ε mach } .
In that case ϑ ^ k = ϑ k \widehat{\vartheta}_k=\vartheta_k ϑ k = ϑ k ; otherwise ϑ ^ k \widehat{\vartheta}_k ϑ k is the fraction stored at the last refactorization and the old factor is reused. The free set enters only through the scalar ϑ k \vartheta_k ϑ k , so no information on the location of the free set is needed.
Algorithm 6.1 Direct semismooth Newton–PCG for the reduced dual equation (18) .
Set p 0 = 0 \mathbf{p}_0=0 p 0 = 0 and evaluate F ( p 0 ) F(\mathbf{p}_0) F ( p 0 ) and D ( p 0 ) D(\mathbf{p}_0) D ( p 0 ) .
for k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … do
Compute the free fraction ϑ k \vartheta_k ϑ k . Refactorize K ^ k \widehat{K}_k K k if the test above is met, otherwise reuse the stored factor. This defines P k P_k P k .
Solve J D δ p k = − F ( p k ) J_D\delta\mathbf{p}_k=-F(\mathbf{p}_k) J D δ p k = − F ( p k ) by PCG with preconditioner P k P_k P k to the tolerance η k \eta_k η k of (20) .
Choose α k \alpha_k α k by Armijo backtracking and set p k + 1 = p k + α k δ p k \mathbf{p}_{k+1}=\mathbf{p}_k+\alpha_k\delta\mathbf{p}_k p k + 1 = p k + α k δ p k .
Recompute the projection, the active set, the residual r k + 1 r_{k+1} r k + 1 and the stopping indicators.
if r k + 1 r_{k+1} r k + 1 meets the stopping tolerance or k + 1 = k max k+1=k_{\max} k + 1 = k m a x then
break
end if
end for
return y = y d − M − 1 K ⊤ p \mathbf{y}=\mathbf{y}_d-\mathcal{M}^{-1}K^{\top}\mathbf{p} y = y d − M − 1 K ⊤ p and u = Proj [ a , b ] ( E p / γ ) \mathbf{u}=\operatorname{Proj}_{[a,b]}(E\mathbf{p}/\gamma) u = Proj [ a , b ] ( E p / γ )
Example 1 We consider a control box-constrained stochastic elliptic optimal control problem on D = ( − 1 , 1 ) 2 D=(-1,1)^2 D = ( − 1 , 1 ) 2 . Let ξ 1 , ξ 2 , ξ 3 \xi_1,\xi_2,\xi_3 ξ 1 , ξ 2 , ξ 3 be independent random variables uniformly distributed on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , and set
Γ = [ − 1 , 1 ] 3 , ρ ( ξ ) = 1 8 , κ ( ξ ) = 10 + ∑ ℓ = 1 3 ξ ℓ . \Gamma=[-1,1]^3,\qquad\rho(\xi)=\frac{1}{8},\qquad\kappa(\xi)=10+\sum_{\ell=1}^{3}\xi_\ell. Γ = [ − 1 , 1 ] 3 , ρ ( ξ ) = 8 1 , κ ( ξ ) = 10 + ℓ = 1 ∑ 3 ξ ℓ .
Thus 7 ≤ κ ( ξ ) ≤ 13 7\le\kappa(\xi)\le13 7 ≤ κ ( ξ ) ≤ 13 throughout the parameter domain. The optimization problem is
min y , u 1 2 E [ ∥ y − y d ∥ L 2 ( D ) 2 ] + γ 2 E [ ∥ u ∥ L 2 ( D ) 2 ] , \min_{y,u}\ \frac{1}{2}\mathbb{E}\left[\lVert y-y_d\rVert_{L^2(D)}^2\right]+\frac{\gamma}{2}\mathbb{E}\left[\lVert u\rVert_{L^2(D)}^2\right], y , u min 2 1 E [ ∥ y − y d ∥ L 2 ( D ) 2 ] + 2 γ E [ ∥ u ∥ L 2 ( D ) 2 ] ,
subject to − ∇ ⋅ ( κ ( ξ ) ∇ y ( x , ξ ) ) = f ( x , ξ ) + u ( x , ξ ) , \text{subject to}\quad-\nabla\cdot\left(\kappa(\xi)\nabla y(x,\xi)\right)=f(x,\xi)+u(x,\xi), subject to − ∇ ⋅ ( κ ( ξ ) ∇ y ( x , ξ ) ) = f ( x , ξ ) + u ( x , ξ ) ,
y ( x , ξ ) = 0 on ∂ D , y(x,\xi)=0\quad\text{on }\partial D, y ( x , ξ ) = 0 on ∂ D ,
− 1 ≤ u ( x , ξ ) ≤ 1 a.e. in D × Γ , (45) -1\le u(x,\xi)\le1\quad\text{a.e. in }D\times\Gamma, \tag*{(45)} − 1 ≤ u ( x , ξ ) ≤ 1 a.e. in D × Γ , (45)
where γ = 10 − 3 \gamma= 10^{-3} γ = 1 0 − 3 .
To obtain a known optimal solution, define
y ∗ ( x , ξ ) = sin ( π x 1 ) sin ( π x 2 ) , p ∗ ( x , ξ ) = β κ ( ξ ) s ( x ) , u ∗ ( x , ξ ) = Proj [ − 1 , 1 ] ( p ∗ ( x , ξ ) γ ) . (46) y^{\ast}(x,\xi) = \sin(\pi x_1)\sin(\pi x_2),\quad p^{\ast}(x,\xi) = \frac{\beta}{\kappa(\xi)}s(x),\quad u^{\ast}(x,\xi) = \operatorname{Proj}_{[-1,1]}\left(\frac{p^{\ast}(x,\xi)}{\gamma}\right). \tag*{(46)} y ∗ ( x , ξ ) = sin ( π x 1 ) sin ( π x 2 ) , p ∗ ( x , ξ ) = κ ( ξ ) β s ( x ) , u ∗ ( x , ξ ) = Proj [ − 1 , 1 ] ( γ p ∗ ( x , ξ ) ) . (46)
Here s ( x ) = sin ( π x 1 ) sin ( π x 2 ) s(x)=\sin(\pi x_1)\sin(\pi x_2) s ( x ) = sin ( π x 1 ) sin ( π x 2 ) , so that y ∗ = s y^{\ast}=s y ∗ = s , and β = 0.02 \beta=0.02 β = 0.02 . The corresponding target and source are
y d ( x ) = ( 1 + 2 π 2 β ) s ( x ) , f ( x , ξ ) = 2 π 2 κ ( ξ ) s ( x ) − u ∗ ( x , ξ ) . (47) y_d(x) = (1+2\pi^2\beta)s(x),\quad f(x,\xi) = 2\pi^2\kappa(\xi)s(x)-u^{\ast}(x,\xi). \tag*{(47)} y d ( x ) = ( 1 + 2 π 2 β ) s ( x ) , f ( x , ξ ) = 2 π 2 κ ( ξ ) s ( x ) − u ∗ ( x , ξ ) . (47)
These choices satisfy the state equation and the adjoint relation
− ∇ ⋅ ( κ ( ξ ) ∇ p ∗ ( x , ξ ) ) = y d ( x ) − y ∗ ( x , ξ ) , -\nabla\cdot\left(\kappa(\xi)\nabla p^{\ast}(x,\xi)\right)=y_d(x)-y^{\ast}(x,\xi), − ∇ ⋅ ( κ ( ξ ) ∇ p ∗ ( x , ξ ) ) = y d ( x ) − y ∗ ( x , ξ ) ,
together with the box-projection optimality condition. The sign convention is therefore consistent with u ∗ = Proj [ − 1 , 1 ] ( p ∗ / γ ) u^{\ast}=\operatorname{Proj}_{[-1,1]}(p^{\ast}/\gamma) u ∗ = Proj [ − 1 , 1 ] ( p ∗ / γ ) .
For the accuracy assessment, define
∥ v ∥ 0 , ρ 2 = ∫ Γ ∫ D ∣ v ( x , ξ ) ∣ 2 d x ρ ( ξ ) d ξ , \lVert v\rVert_{0,\rho}^{2}=\int_{\Gamma}\int_D \lvert v(x,\xi)\rvert^2\,dx\,\rho(\xi)\,d\xi, ∥ v ∥ 0 , ρ 2 = ∫ Γ ∫ D ∣ v ( x , ξ ) ∣ 2 d x ρ ( ξ ) d ξ ,
and report the absolute errors
e y = ∥ y h − y ∗ ∥ 0 , ρ , e p = ∥ p h − p ∗ ∥ 0 , ρ , e u = ∥ u h − u ∗ ∥ 0 , ρ . e_y=\lVert y_h-y^{\ast}\rVert_{0,\rho},\qquad e_p=\lVert p_h-p^{\ast}\rVert_{0,\rho},\qquad e_u=\lVert u_h-u^{\ast}\rVert_{0,\rho}. e y = ∥ y h − y ∗ ∥ 0 , ρ , e p = ∥ p h − p ∗ ∥ 0 , ρ , e u = ∥ u h − u ∗ ∥ 0 , ρ .
At independent evaluation points, the control is reconstructed as
u h ( x , ξ ) = Proj [ − 1 , 1 ] ( p h ( x , ξ ) γ ) , u_h(x,\xi)=\operatorname{Proj}_{[-1,1]}\left(\frac{p_h(x,\xi)}{\gamma}\right), u h ( x , ξ ) = Proj [ − 1 , 1 ] ( γ p h ( x , ξ ) ) ,
The empirical state convergence rate is defined by
EOC y ( n c ) = log 2 ( e y ( n c − 1 ) e y ( n c ) ) , \operatorname{EOC}_y(n_c)=\log_2\left(\frac{e_y(n_c-1)}{e_y(n_c)}\right), EOC y ( n c ) = log 2 ( e y ( n c ) e y ( n c − 1 ) ) ,
where e y ( n c ) e_y(n_c) e y ( n c ) is the error on the mesh with 2 n c 2^{n_c} 2 n c elements per direction.
Observe from Table 1 that the value of EOC y \operatorname{EOC}_y EOC y for all the mesh sizes is roughly 2, which suggests that the method achieves approximately second-order convergence in the state. Moreover, we notice small errors corresponding to the state, the adjoint, and the control on fine meshes. On every mesh the solver takes three Newton steps and 16 PCG iterations in total, at most seven per step, while N N N grows by a factor of 289 from 4,500 to 1,300,500.
Table 1. Table 1. SSN–PCG performance and absolute L ρ 2 ( Γ ; L 2 ( D ) ) L^2_\rho(\Gamma;L^2(D)) L ρ 2 ( Γ ; L 2 ( D )) errors for the manufactured problem. The stochastic degree is fixed at P = 3 P=3 P = 3 with β = 0.02 \beta=0.02 β = 0.02 . PCG mean/max refers to the iterations per Newton step. Here γ = 10 − 3 \gamma=10^{-3} γ = 1 0 − 3 , and PCG uses the preconditioner P k P_k P k of § 6 .
Example 2 is designed for stress test for parameters to verify the preconditioner robustness.
Example 2 The optimization problem is
min y , u 1 2 E [ ∥ y − y d ∥ L 2 ( D ) 2 ] + γ 2 E [ ∥ u ∥ L 2 ( D ) 2 ] , subject to − ∇ ⋅ ( κ ( x , ξ ) ∇ y ( x , ξ ) ) = u ( x , ξ ) , y ( x , ξ ) = 0 on ∂ D , 0.3 ≤ u ( x , ξ ) ≤ 1 a.e. in D × Γ , (48) \begin{aligned}
\min_{y,u}\quad& \frac{1}{2}\mathbb{E}\left[\lVert y-y_d\rVert_{L^2(D)}^2\right]+\frac{\gamma}{2}\mathbb{E}\left[\lVert u\rVert_{L^2(D)}^2\right],\\
\text{subject to}\quad&-\nabla\cdot\left(\kappa(x,\xi)\nabla y(x,\xi)\right)=u(x,\xi),\\
&y(x,\xi)=0\quad\text{on }\partial D,\\
&0.3\le u(x,\xi)\le1\quad\text{a.e. in }D\times\Gamma, \tag*{(48)}
\end{aligned} y , u min subject to 2 1 E [ ∥ y − y d ∥ L 2 ( D ) 2 ] + 2 γ E [ ∥ u ∥ L 2 ( D ) 2 ] , − ∇ ⋅ ( κ ( x , ξ ) ∇ y ( x , ξ ) ) = u ( x , ξ ) , y ( x , ξ ) = 0 on ∂ D , 0.3 ≤ u ( x , ξ ) ≤ 1 a.e. in D × Γ , (48)
and the random coefficient κ ( x , ξ ) \kappa(x,\xi) κ ( x , ξ ) is the truncated Karhunen–Loève (KL) expansion κ ( x , ξ ) = 1 + 3 σ ∑ j = 1 K λ j g j ( x ) ξ j \kappa(x,\xi)=1+\sqrt{3}\sigma\sum_{j=1}^{K}\sqrt{\lambda_j}g_j(x)\xi_j κ ( x , ξ ) = 1 + 3 σ ∑ j = 1 K λ j g j ( x ) ξ j with ξ j ∼ U [ − 1 , 1 ] \xi_j\sim U[-1,1] ξ j ∼ U [ − 1 , 1 ] , where ( λ j , g j ) (\lambda_j,g_j) ( λ j , g j ) are the eigenpairs of the covariance function
C g ( x , y ) = σ 2 exp ( − ∣ x 1 − y 1 ∣ ℓ 1 − ∣ x 2 − y 2 ∣ ℓ 2 ) ∀ ( x , y ) ∈ [ − 1 , 1 ] 2 , C_g(x,y)=\sigma^2\exp\left(-\frac{\lvert x_1-y_1\rvert}{\ell_1}-\frac{\lvert x_2-y_2\rvert}{\ell_2}\right)\quad\forall(x,y)\in[-1,1]^2, C g ( x , y ) = σ 2 exp ( − ℓ 1 ∣ x 1 − y 1 ∣ − ℓ 2 ∣ x 2 − y 2 ∣ ) ∀ ( x , y ) ∈ [ − 1 , 1 ] 2 ,
where σ \sigma σ denotes the standard deviation and ℓ 1 = ℓ 2 = 1 \ell_1=\ell_2=1 ℓ 1 = ℓ 2 = 1 are correlation lengths. The discontinuous target is defined on D = ( − 1 , 1 ) 2 D=(-1,1)^2 D = ( − 1 , 1 ) 2 as
y d ( x , ξ ) = { 1 , x 1 ≤ 0 , x 2 ≤ 0 , 0 , otherwise . y_d(x,\xi)=
\begin{cases}
1, & x_1\le0,\quad x_2\le0,\\
0, & \text{otherwise}.
\end{cases} y d ( x , ξ ) = { 1 , 0 , x 1 ≤ 0 , x 2 ≤ 0 , otherwise .
We fix γ = 10 − 3 \gamma=10^{-3} γ = 1 0 − 3 and vary the amplitude σ ∈ { 0.01 , 0.02 , 0.05 , 0.1 , 0.2 } \sigma\in\{0.01,0.02,0.05,0.1,0.2\} σ ∈ { 0.01 , 0.02 , 0.05 , 0.1 , 0.2 } , the pair ( K , P ) ∈ { ( 3 , 3 ) , ( 4 , 4 ) , ( 6 , 3 ) } (K,P)\in\{(3,3),(4,4),(6,3)\} ( K , P ) ∈ {( 3 , 3 ) , ( 4 , 4 ) , ( 6 , 3 )} of the number of retained expansion terms and the total polynomial degree, and the mesh level n c = 4 , … , 8 n_c=4,\ldots,8 n c = 4 , … , 8 . The total-degree Legendre space has n P = ( K + P P ) ∈ { 20 , 70 , 84 } n_P=\binom{K+P}{P}\in\{20,70,84\} n P = ( P K + P ) ∈ { 20 , 70 , 84 } modes, and with n h = ( 2 n c − 1 ) 2 n_h=(2^{n_c}-1)^2 n h = ( 2 n c − 1 ) 2 interior nodes the SG–FE system has N = n h n P N=n_hn_P N = n h n P unknowns, from 4,500 for ( K , P , n c ) = ( 3 , 3 , 4 ) (K,P,n_c)=(3,3,4) ( K , P , n c ) = ( 3 , 3 , 4 ) to 5,462,100 for ( K , P , n c ) = ( 6 , 3 , 8 ) (K,P,n_c)=(6,3,8) ( K , P , n c ) = ( 6 , 3 , 8 ) . Example 2 tests the solver on a problem without a known solution. Since u ≥ 0.3 u\ge0.3 u ≥ 0.3 while y d = 0 y_d=0 y d = 0 on three quarters of D D D , the lower bound is expected to be active on a large part of the domain, and the active set changes during the iteration.
Table 2 shows three trends. First, the Newton count is insensitive to the discretization. Over all 75 runs it lies between 6 and 9, and it does not grow under refinement: it decreases from 7–9 at n c = 4 nc = 4 n c = 4 to exactly 6 at n c = 8 nc = 8 n c = 8 for every σ \sigma σ and every ( K , P ) (K, P) ( K , P ) . This is in line with the mesh-independent behaviour of semismooth Newton methods [19 ] .
Table 2. Each entry is Newton / mean PCG (maximum PCG) / solve time in seconds with γ = 10 − 3 \gamma=10^{-3} γ = 1 0 − 3 . Example 2 with the preconditioner P k P_k P k . Here σ \sigma σ is the amplitude, K K K is the number of random variables, and P P P is the degree of the polynomials.
Second, the number of PCG iterations per Newton step is essentially independent of the mesh and of the stochastic discretization. For fixed σ \sigma σ and ( K , P ) (K, P) ( K , P ) , the mean count rises by at most about two iterations from n c = 4 nc = 4 n c = 4 to n c = 6 nc = 6 n c = 6 and then stays nearly constant. For fixed σ \sigma σ and n c nc n c , the three choices of ( K , P ) (K, P) ( K , P ) differ by about one iteration or less, although n P n_P n P grows from 20 to 84.
Third, the amplitude σ \sigma σ is the only parameter with an effect on PCG. At n c = 8 nc = 8 n c = 8 , as σ \sigma σ grows from 0.01 to 0.2, the mean count rises from 6.33 to 10.5–11.0 and the maximum from 10 to 14. This is consistent with the theory: the reference H 0 H_0 H 0 uses only the mean coefficient, and the constants U U U and V V V of Corollary 5.8 grow with the deviation of the coefficient from its mean through α \alpha α , β \beta β and Ω \Omega Ω . Even for σ = 0.2 \sigma= 0.2 σ = 0.2 the growth is moderate, and the Newton count is unaffected. The solution time grows reasonably with the scale of the problem, yet it remains within an acceptable range, even the most difficult one can still be solved in 212 seconds.
Table 3 separates the two levels of the method. Its row γ = 10 − 3 \gamma= 10^{-3} γ = 1 0 − 3 is the entry σ = 0.1 \sigma= 0.1 σ = 0.1 , ( K , P ) = ( 3 , 3 ) (K, P) = (3, 3) ( K , P ) = ( 3 , 3 ) , n c = 4 nc = 4 n c = 4 of Table 2 . For γ ≥ 10 − 3 \gamma\ge10^{-3} γ ≥ 1 0 − 3 , the Newton count lies between 4 and 7, and the mean PCG count per Newton step lies between 5.00 and 6.29. Below γ = 10 − 3 \gamma= 10^{-3} γ = 1 0 − 3 both counts grow. At γ = 10 − 6 \gamma= 10^{-6} γ = 1 0 − 6 the solver takes 47 Newton steps with 44.81 PCG iterations per step on average and 127 at most, that is, 2,106 PCG iterations in total against 44 at γ = 10 − 3 \gamma= 10^{-3} γ = 1 0 − 3 . This is the regime in which P k P_k P k stops being robust. The growth of the Newton count is a property of the nonlinear iteration: the projection term in (18) has slope γ − 1 \gamma^{-1} γ − 1 , so for small γ \gamma γ the reduced equation approaches a bang-bang system, and more steps are needed before the fast local convergence of the semismooth Newton method sets in. While, the solve time is acceptable and it grows from 0.074 s at γ = 10 − 1 \gamma= 10^{-1} γ = 1 0 − 1 to 2.980 s at γ = 10 − 6 \gamma= 10^{-6} γ = 1 0 − 6 .
Table 3. Dependence on γ \gamma γ of Direct SSN–PCG with the preconditioner P k P_k P k at ( K , P , n c , σ ) = ( 3 , 3 , 4 , 0.1 ) (K, P, nc, \sigma) = (3, 3, 4, 0.1) ( K , P , n c , σ ) = ( 3 , 3 , 4 , 0.1 ) . Entries report Newton steps, total PCG, mean/max PCG, and solve time in seconds.
Conclusions
We have studied the optimal control problem of elliptic PDEs with random coefficients subject to a box-constrained control variable via Fenchel duality. In both the function space and the discrete setting via stochastic Galerkin–finite element methods, the dual formulation yields an unconstrained problem in the adjoint variable and reduces to a single semismooth equation without a duality gap. Our matrix-free semismooth Newton–PCG algorithm solves this equation directly without requiring outer iterations, penalties, or smoothing parameters. The current-set preconditioner P W P_W P W adds the active-set correction to a mean-based reference operator and is inverted exactly by the Sherman–Morrison–Woodbury identity. For P W P_W P W we prove that the preconditioned spectrum is bounded uniformly in the mesh size, the stochastic dimension, γ \gamma γ and the active set. In the numerical experiments, the solver uses the cheap approximation P k P_k P k of the preconditioner P W P_W P W . The state solution converges at second order, and the Newton and PCG counts stay bounded under mesh refinement and enlargement of the stochastic space.
Future work includes developing continuation strategies for small regularization parameters, extending the duality framework to lognormal diffusion coefficients using weighted spaces, and exploring risk-averse objectives alongside alternative stochastic discretizations.