Finite-budget finite-element PDE Tikhonov inversion

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