PDE-constrained inversion and adjoint error control

Fix an integer $d\ge 2$, a bounded polyhedral open set $\mathrm{\Omega }\subset {\mathbb{R}}^d$, a finite matching affine simplicial mesh ${\mathcal{T}}_h$ of $\mathrm{\Omega }$, and unisolvent reference finite elements assembled on that mesh. Thus the mesh is a finite face-to-face cover by nondegenerate affine simplices with disjoint interiors, and each local finite-element degree-of-freedom map is bijective on its finite-dimensional shape-function space. Fix coefficient spaces ${\mathrm{\Theta }}_h={\mathbb{R}}^m$, $V_h={\mathbb{R}}^n$, and $Y_h={\mathbb{R}}^s$ with their standard Euclidean inner products, where $m,n,s\ge 1$. Let $Q_h\subseteq {\mathrm{\Theta }}_h$ be nonempty, closed, and convex, and let $O_h\subseteq {\mathrm{\Theta }}_h$ be open with $Q_h\subseteq O_h$.

A finite-element PDE model in this contract consists of a continuously differentiable residual map $R_h:O_h\times V_h\to V_h$ and a continuously differentiable observation map $G_h:O_h\times V_h\to Y_h$. It must supply a continuously differentiable state branch $S_h:O_h\to V_h$ satisfying $R_h(q,S_h(q))=0$ for every $q\in O_h$. For every $q\in Q_h$, this branch must be the specified unique admissible state and the matrix $D_u{R}_h(q,S_h(q))$ must be invertible. The discrete forward map is $F_h(q):=G_h(q,S_h(q))$. The unisolvent finite-element degrees of freedom identify $V_h$ with its coefficient space; all matrix transposes below are in the fixed Euclidean coefficient inner products.

For data $y^{\delta }\in Y_h$, reference parameter $q_0\in {\mathrm{\Theta }}_h$, and $\alpha >0$, the discrete nonlinear Tikhonov objective is

Define the finite-dimensional objective before eliminating the state by

The symbols ${\mathrm{\nabla }}_u{J}_h$ and ${\mathrm{\nabla }}_q{J}_h$ denote the Euclidean gradient vectors representing the two partial derivative functionals. At an admissible $q$, the exact discrete adjoint $p_h(q)\in V_h$ is the unique solution of

The associated discrete-adjoint gradient vector is

The next lemma proves that this vector is the gradient of ${\mathrm{\Phi }}_h$; the definition itself asserts no minimizer exists and no gradient iteration converges.

An admissibility predicate is a specified finite-time test ${\mathrm{adm}}_h(q)$ that decides whether $q\in Q_h$ and checks the model's stated coefficient, boundary, mesh, and time-step hypotheses before a PDE solve. For an explicit time discretization, a Courant–Friedrichs–Lewy condition (CFL condition) is a method-specific bound relating the time step to the mesh and the discrete evolution operator; no universal CFL threshold is part of this definition. A true predicate result certifies that the declared model hypotheses hold for that input, not merely that a heuristic check passed.

The model must also supply an exact finite-dimensional projection routine which returns $P_{Q_h}(z)$ for a queried $z\in {\mathrm{\Theta }}_h$ in finite time or reports failure only when its declared finite call budget is exhausted. The unique nearest point exists because $Q_h$ is nonempty, closed, and convex, but an operational routine for computing it is an additional part of this contract.

A solver routine with declared nonnegative state and adjoint tolerances ${\tau }_u,{\tau }_p$ and a finite solve budget must return either failure or approximate state and adjoint vectors $\tilde{u},\tilde{p}$ together with certified finite bounds ${\rho }_u,{\rho }_p,{\eta }_u,{\eta }_p,P,L_{J,u},L_{R,u},M_q,L_{G,u}$. The residual bounds have the exact-system meaning $\mathrm{\parallel }{R}_h(q,\tilde{u}){\mathrm{\parallel }}_{V_h}\le {\rho }_u$ and $\mathrm{\parallel }(D_u{R}_h(q,u){)}^T\tilde{p}-{\mathrm{\nabla }}_u{J}_h(q,u){\mathrm{\parallel }}_{V_h}\le {\rho }_p$, where $u=S_h(q)$; both must satisfy ${\rho }_u\le {\tau }_u$ and ${\rho }_p\le {\tau }_p$. In particular, an adjoint residual evaluated at $\tilde{u}$ alone does not certify ${\rho }_p$ unless the model also bounds the resulting state and derivative-data defects. With $u=S_h(q)$ and $p=p_h(q)$, the model must certify

and $\mathrm{\parallel }{G}_h(q,u)-G_h(q,\tilde{u}){\mathrm{\parallel }}_{Y_h}\le L_{G,u}{\eta }_u$. It then returns

All constants and state/adjoint error bounds must be justified for the chosen model with every derivative-data, geometry, quadrature, and algebraic-solve defect retained. Certified residual bounds ${\rho }_u,{\rho }_p$ do not by themselves imply ${\eta }_u,{\eta }_p$; a separate model-valid stability estimate is required. The proposition below derives the resulting ${\epsilon }_g$ and ${\epsilon }_F$ bounds. An objective-evaluation routine must return in its finite budget either failure or an interval $[{\mathrm{\ell }}_h(q),u_h(q)]$ containing the exact value ${\mathrm{\Phi }}_h(q)$; failure is permitted only when a required state/adjoint solve fails its contract or the evaluation-call budget is exhausted. Exact evaluation is the degenerate-interval case. Projection and objective-evaluation calls consume the algorithm's finite evaluation budget. Each routine must return within its declared budget or report failure.

If a continuous model $F$ is also supplied, an optional mesh certificate ${\epsilon }_{\mathrm{m}\mathrm{e}\mathrm{s}\mathrm{h}}$ must separately bound the claimed continuous-to-discrete error, such as $\mathrm{\parallel }{F}_h(q)-F(q)\mathrm{\parallel }$ or $\mathrm{\parallel }\mathrm{\nabla }{\mathrm{\Phi }}_h(q)-\mathrm{\nabla }\mathrm{\Phi }(q)\mathrm{\parallel }$. The state and adjoint algebraic residual certificates do not imply this mesh certificate.

Nonlinear forward maps on an open real Hilbert-space domain

Nonlinear Tikhonov functional and its domain

Matching affine simplicial meshes and shape regularity

Reference finite elements and unisolvent degrees of freedom

Standard Euclidean inner product and coefficient norm

Existence and uniqueness of Euclidean nearest-point projections

Finite-dimensional Riesz representation

Linear finite-element residual-to-state and adjoint error estimate

Exact discrete adjoint on a finite state-step graph

Continuous elliptic PDE adjoint gradient

Finite-element state and adjoint error bounds for a linear elliptic control model

Hannes Meinlschmidt, Optimization with Partial Differential Equations, complete lecture notes

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case

Fernando Gaspoz, Christian Kreuzer, Andreas Veeser, and Winnifried Wollner, A Posteriori Error Analysis for Optimization with PDE Constraints

The algorithmic wrapper below is finite-dimensional and uses only supplied finite returns. No axiom of choice is used by its projection or finite-dimensional Riesz steps. A model-specific elliptic state/adjoint theorem may require Countable Choice, and that branch must retain its own hypotheses. The nonlinear tangential-cone and Tikhonov existence/stability results are not convergence theorems for this finite-budget procedure.

Let $O\subseteq {\mathbb{R}}^m$ be open and $V={\mathbb{R}}^n$ have its standard Euclidean inner product. Let $R:O\times V\to V$ and $G:O\times V\to Y$ be continuously differentiable, where $Y$ is a finite-dimensional real Euclidean space. Suppose $S:O\to V$ is continuously differentiable, $R(q,S(q))=0$ for every $q\in O$, and the matrix $D_{u}R(q,S(q))$ is invertible at a fixed $q\in O$. Let $y\in Y$, $q_0\in {\mathbb{R}}^m$, and $\alpha >0$. Define

Let $p\in V$ be the unique solution of

where ${\mathrm{\nabla }}_{q}J$ and ${\mathrm{\nabla }}_{u}J$ are the Euclidean representatives of the two partial derivative functionals. Then for every $h\in {\mathbb{R}}^m$,

Consequently $\mathrm{\nabla }\mathrm{\Phi }(q)={\mathrm{\nabla }}_{q}J(q,S(q))-(D_{q}R(q,S(q)){)}^{T}p$. This is the exact derivative of the specified finite-dimensional model; it asserts no convergence of an iteration that changes $q$.

Finite-element state, residual, and discrete-adjoint contract

Euclidean inner products, norms, and matrix transposes

Finite-dimensional Riesz representation

Chain rule for total derivatives in Euclidean spaces

Hannes Meinlschmidt, Optimization with Partial Differential Equations, §3.2

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case, §§1–3

The transpose convention is the Euclidean coefficient-space convention fixed in the definition. A continuous PDE adjoint or an adjoint for another coefficient inner product must be derived using that model's own operator pairing.

Let $A\in {\mathbb{R}}^{n\times n}$ and $B\in {\mathbb{R}}^{r\times r}$ be invertible finite-element state and adjoint system matrices. Let $u=A^{-1}b$ and $p=B^{-1}c$ be the exact solutions, and let $\tilde{u},\tilde{p}$ be computed vectors. Suppose certified residual upper bounds ${\rho }_u,{\rho }_p\ge 0$ and certified operator bounds $K_u,K_p\ge 0$ satisfy

Then the exact state and adjoint errors satisfy

The inverse-norm bounds are separate inputs; a residual bound alone gives no state or adjoint error estimate.

Certified state and adjoint residual interface

Induced operator norm and its least-bound property

Euclidean coefficient norms

Fernando Gaspoz, Christian Kreuzer, Andreas Veeser, and Winnifried Wollner, A Posteriori Error Analysis for Optimization with PDE Constraints, §3.1

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case, §§2–3

This finite-dimensional estimate is choice-free. It does not provide $K_u$ or $K_p$; the model must certify them separately. For a nonlinear state equation or a continuous-to-discrete comparison, another stability argument is required.

Let $Q_h\subseteq {\mathbb{R}}^m$ be a nonempty closed convex set and let $q\in Q_h$. Write $u=S_h(q)$, $p=p_h(q)$, and $g_h(q)=\mathrm{\nabla }{\mathrm{\Phi }}_h(q)$ for the exact finite-element state, exact discrete adjoint, and exact discrete-objective gradient. Suppose a solver supplies $\tilde{u},\tilde{p}$, a forward output ${\tilde{F}}_h=G_h(q,\tilde{u})$, and a computed gradient ${\tilde{g}}_h={\mathrm{\nabla }}_q{J}_h(q,\tilde{u})-(D_q{R}_h(q,\tilde{u}){)}^T\tilde{p}$. It also supplies finite nonnegative bounds ${\eta }_u,{\eta }_p,P,L_{J,u},L_{R,u},M_q,L_{G,u}$ satisfying

and $\mathrm{\parallel }{G}_h(q,u)-G_h(q,\tilde{u}){\mathrm{\parallel }}_{Y_h}\le L_{G,u}{\eta }_u$. Define

Then $\mathrm{\parallel }{\tilde{g}}_h-g_h(q)\mathrm{\parallel }\le {\epsilon }_g$ and $\mathrm{\parallel }{\tilde{F}}_h-F_h(q){\mathrm{\parallel }}_{Y_h}\le {\epsilon }_F$. For $L>0$, define

Then $\mathrm{\parallel }{G}_L(q){\mathrm{\parallel }}_2\le \mathrm{\parallel }{\tilde{G}}_L(q){\mathrm{\parallel }}_2+{\epsilon }_g,\mathrm{\parallel }{F}_h(q)-y^{\delta }{\mathrm{\parallel }}_{Y_h}\le \mathrm{\parallel }{\tilde{F}}_h-y^{\delta }{\mathrm{\parallel }}_{Y_h}+{\epsilon }_F\mathrm{.}$ Thus the finite-element algorithm may certify discrete projected stationarity and discrete discrepancy from these bounds. The state and adjoint residuals must first be converted to valid ${\eta }_u,{\eta }_p$ bounds under the chosen model's hypotheses; raw residuals alone do not imply the asserted gradient or mesh error.

Finite-element state, adjoint, and error-bound contract

Exact reduced gradient from the finite-element discrete adjoint

Linear finite-element residual-to-error certificate

Existence and uniqueness of Euclidean nearest-point projection

Nonexpansiveness of Euclidean projection

Induced operator norm bound

Euclidean norm and triangle inequality

Hannes Meinlschmidt, Optimization with Partial Differential Equations, complete lecture notes

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case

Fernando Gaspoz, Christian Kreuzer, Andreas Veeser, and Winnifried Wollner, A Posteriori Error Analysis for Optimization with PDE Constraints

The certificates ${\eta }_u,{\eta }_p$ are model-specific consequences of residuals and stability constants; they must be justified before this proposition is applied. The published linear elliptic finite-element residual result has its own continuous-objective and full Strang hypotheses; it is not substituted for the discrete target error bounds above.

Assume a finite-element PDE model satisfying the admissibility and certificate contract, with nonempty closed convex coefficient set $Q_h$, discrete Tikhonov objective ${\mathrm{\Phi }}_h$ using reference coefficient $q_0$, a state/adjoint solve routine, an exact projection routine, an objective interval routine, and finite solve and evaluation budgets. Let the input be an initial coefficient $q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\in Q_h$, data $y^{\delta }\in Y_h$, noise bound $\delta \ge 0$, penalty $\alpha >0$, state and adjoint residual tolerances ${\tau }_u,{\tau }_p\ge 0$, discrepancy factor $\kappa \ge 1$, stationarity tolerance ${\tau }_g\ge 0$, scaling parameter $L>0$, and positive integer budgets $N_{\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}}$, $N_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}}$, $N_{\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}}$, and $N_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{k}}$. The global budget $N_{\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{v}\mathrm{e}}$ counts state and adjoint solves; $N_{\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}}$ counts exact projections and objective-interval evaluations. The scaling parameter $L$ is only a positive step-size scale; it is not assumed to be a Lipschitz constant. The algorithm returns a coefficient, one status from converged, discrepancy-stopped, linear-solve-failed, inadmissible, or budget-exhausted, and any diagnostics certified at that coefficient.

1. If $q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\mathrm{\notin }{Q}_h$ or the model's exact admissibility predicate is false at $q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$, return status inadmissible without solving a PDE. Otherwise set $q:=q_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$.

2. For $k=0,\dots ,N_{\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}}$, first check the finite-time admissibility predicate, which includes membership in $Q_h$. If it is false, return inadmissible. If no global solve or evaluation budget remains, return budget-exhausted.

3. Call the state/adjoint solver at $q$ with tolerances ${\tau }_u,{\tau }_p$ and the remaining solve budget. If it returns failure, if either certified residual bound exceeds its declared tolerance, or if any required state/adjoint error estimate or derivative bound is missing or invalid, return linear-solve-failed. Otherwise receive ${\tilde{g}}_h$, ${\tilde{F}}_h$, ${\eta }_u,{\eta }_p,P,L_{J,u},L_{R,u},M_q,L_{G,u}$ and set ${\epsilon }_g=(L_{J,u}+L_{R,u}P){\eta }_u+M_q{\eta }_p$ and ${\epsilon }_F=L_{G,u}{\eta }_u$.

4. Use the exact projection routine to compute $P_{Q_h}(q-{\tilde{g}}_h\mathrm{/}L)$. If the routine fails or the evaluation budget is exhausted, return budget-exhausted. Set $\tilde{\rho }:=L\mathrm{\parallel }q-P_{Q_h}(q-{\tilde{g}}_h\mathrm{/}L){\mathrm{\parallel }}_2$. If $\tilde{\rho }+{\epsilon }_g\le {\tau }_g$, return converged with stationarity upper bound $\tilde{\rho }+{\epsilon }_g$. This status means only that the exact projected-gradient residual of the discrete objective is within tolerance; it is not a claim that an iterate sequence converges or that $q$ is a global minimizer.

5. Compute $d^{+}:=\mathrm{\parallel }{\tilde{F}}_h-y^{\delta }{\mathrm{\parallel }}_{Y_h}+{\epsilon }_F$. If $d^{+}\le \kappa \delta$, return discrepancy-stopped with data-residual upper bound $d^{+}$. This status certifies only the discrete model's data discrepancy.

6. If $k=N_{\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}}$, return budget-exhausted at the current coefficient with its current diagnostics. Otherwise, evaluate the current objective using its certified interval $[{\mathrm{\ell }}_h(q),u_h(q)]$. If the evaluation fails because a required state or adjoint solve fails its contract, return linear-solve-failed; if the global solve or evaluation budget is exhausted, return budget-exhausted.

7. For $j=0,\dots ,N_{\mathrm{b}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{k}}-1$, set $t_j=2^{-j}\mathrm{/}L$ and use the exact projection routine to compute $q_j=P_{Q_h}(q-t_j{\tilde{g}}_h)$. If projection fails or the evaluation budget is exhausted, return budget-exhausted. Reject this trial and continue to the next $j$ if $q_j=q$ or its admissibility predicate is false. Otherwise evaluate a certified interval $[{\mathrm{\ell }}_h(q_j),u_h(q_j)]$. If evaluation fails because a required state or adjoint solve fails its contract, return linear-solve-failed; if the global solve or evaluation budget is exhausted, return budget-exhausted. Accept the first trial with $u_h(q_j)\le {\mathrm{\ell }}_h(q)$, set $q:=q_j$, and continue to the next outer iteration.

8. If no trial is accepted within the backtracking budget, return budget-exhausted at the current coefficient.

The global solve budget counts all primal and adjoint solves used both at iterates and in objective trials. The evaluation budget counts every projection and objective-interval call. Any continuous-to-discrete mesh bound is reported separately by the model contract and is never inferred from the algebraic state or adjoint residuals.

Finite-element PDE model, adjoint, and error-certificate contract

Exact finite-element reduced gradient

Nonlinear Tikhonov objective

Sound finite statuses from certified discrete gradients and data residuals

Exact discrete gradient for finite state-step models

Model-specific finite-element state and adjoint error certificate

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case

Fernando Gaspoz, Christian Kreuzer, Andreas Veeser, and Winnifried Wollner, A Posteriori Error Analysis for Optimization with PDE Constraints

Hannes Meinlschmidt, Optimization with Partial Differential Equations, complete lecture notes

For any finite-element PDE model satisfying its solver and admissibility contract, the finite-budget Tikhonov algorithm returns after finitely many operations one of converged, discrepancy-stopped, linear-solve-failed, inadmissible, or budget-exhausted. A converged return satisfies the exact discrete projected-gradient bound $\mathrm{\parallel }{G}_L(q){\mathrm{\parallel }}_2\le {\tau }_g$; a discrepancy-stopped return satisfies $\mathrm{\parallel }{F}_h(q)-y^{\delta }{\mathrm{\parallel }}_{Y_h}\le \kappa \delta$. Every accepted safeguarded step has nonincreasing exact discrete objective ${\mathrm{\Phi }}_h$. inadmissible and linear-solve-failed are returned only on the corresponding failed predicate or solver-certificate checks. budget-exhausted asserts no optimizer or continuous-model accuracy.

Finite-budget finite-element PDE Tikhonov inversion

Gradient and discrepancy certificate inequalities

Finite solver and objective-interval return contract

Michael Hinze, A Variational Discretization Concept in Control Constrained Optimization: The Linear-Quadratic Case

Fernando Gaspoz, Christian Kreuzer, Andreas Veeser, and Winnifried Wollner, A Posteriori Error Analysis for Optimization with PDE Constraints