Source-linked AI summary
A fully globalized solver for discretized inverse elliptic coefficient problems with exact data
Bastian Harrach
TL;DR
Finite-dimensional nonlinear inverse coefficient problems are difficult because of nonlinearity, ill-posedness, and dependence on good initial values. The paper develops an SDP-based locally convergent solver with a residual criterion and a globalized variant that uses global search before switching to the local method.
Problem
Finite-dimensional discretizations of elliptic inverse coefficient problems are nonlinear and ill-posed, while numerical solvers can depend strongly on good initial values.
Method
The paper develops an SDP-based iterative solver with a residual-based local convergence test and a global search strategy for avoiding non-solution stationary points.
Results
The globalized method is guaranteed to yield linear convergence from every initial value in the admissible set and to switch to the locally convergent regime after global search succeeds.
Takeaways & Limitations
The method provides a globally initialized route to the inverse-problem solution while retaining the faster locally convergent SDP iteration.
Takeaways & Limitations
The analysis assumes unique solvability and Lipschitz stability, although the Lipschitz constant need not be known.
Abstract
from arXiv · showhide
We consider finite-dimensional nonlinear inverse problems arising from finite element discretizations of elliptic inverse coefficient problems such as the Calderón problem with finitely many measurements and unknowns. Such inverse coefficient problems are notorious for their nonlinearity and ill-posedness, and numerical solvers tend to depend strongly on good initial values. In this work, we develop a new locally convergent algorithm with an explicit residual criterion that ensures convergence to the inverse problem solution, and a globalized variant that is guaranteed to automatically switch to the faster locally convergent algorithm after finitely many global search steps.
1 Disclaimer
The paper is identified as a preliminary draft and explicitly lacks references, an introduction, and a numerical-results section.
- The document is a preliminary draft version.
- References are not included in this draft.
- The draft lacks an introduction and a numerical-results section.
2 Setting and first results
The paper formulates finite-dimensional nonlinear inverse problems with assumptions supporting well-defined, uniquely solvable, and Lipschitz-stable recovery. It connects the inverse problem to semidefinite programming and derives an SDP-based iterative solver.
- 2 Setting and first results: The setting assumes a known box margin, positive-definite coefficient matrices, full row rank of B, unique solvability, and Lipschitz stability.The Lipschitz constant L itself need not be known.
- 2 Setting and first results: Discretized Calderón problems with finitely many measurements and unknowns fit the finite-dimensional formulation.Here, m counts unknowns, the measurements form a symmetric l × l matrix, and n is the FEM degrees of freedom.
- 2 Setting and first results: The Schur-complement formulation gives F(y) ≺ Y iff M_y ≻ 0 iff A_y ≻ C, with the determinant identity det M_y = det A_y det(Y − F(y)) = det Y det(A_y − C).The same construction also characterizes equality through dim N(A_y − C) = l iff F(y) = Y.
- 2 Setting and first results: The forward operator is infinitely differentiable, monotonically non-increasing, convex in the Loewner order, and positively homogeneous of degree −1.Its first and second derivatives are given explicitly, and it satisfies F′(y)y = −F(y) and F(ty) = t−1F(y).
- 2.2 Semidefinite programming: The associated primal and dual SDPs have strong duality with attained equal optimal values.Strictly feasible primal and dual points are constructed from feasible y and convex combinations with a strictly dual-feasible point.
- 2.2 Semidefinite programming: For b = ∇tr F(ŷ), the inverse-problem solution ŷ is the unique dual SDP solution, motivating an SDP-based iterative solver.Given y_k, the method sets b := ∇tr F(y_k) and obtains y_{k+1} by solving the dual SDP.
3 Globalized Frank-Wolfe trace minimization
The method minimizes a trace residual through SDP-based Frank–Wolfe steps, using explicit duality-gap and residual criteria to exclude spurious stationary points. A globalized variant combines these steps with global search and eventually achieves linear convergence while requiring only finitely many global searches.
- 3 Globalized Frank-Wolfe trace minimization: The solver minimizes the trace residual over an LMI-represented admissible set using iterative Frank–Wolfe updates whose SDP subproblem controls dual objective improvement.The nonlinear semidefinite constraint is rewritten as an LMI, and each iteration uses b := ∇tr F(yk) to obtain the next iterate.
- 3.1 Avoiding Frank-Wolfe stationary points: A duality-gap criterion rejects SDP steps that could approach Frank–Wolfe stationary points other than the inverse-problem solution.The solver treats an iterate as failed when its duality gap falls below a prescribed fraction γ of the residual.
- 3.1 Avoiding Frank-Wolfe stationary points: Near the true solution, a neighborhood can be characterized in which the solution is the only Frank–Wolfe stationary point.The argument bounds the positive semidefinite first-order Taylor remainder and uses Lipschitz stability to exclude other stationary points.
- 3.2 Local and global convergence against the true solution: Each accepted inexact Frank–Wolfe step contracts the residual as r(yk+1) ≤ (1 − θγ)r(yk), yielding local linear convergence under the stated criterion.The contraction follows from the prescribed fraction θ of maximal dual improvement and the γ residual test.
- 3.2 Local and global convergence against the true solution: The globalized algorithm uses global search whenever the candidate or γ-criterion fails, and for every feasible initial value it converges linearly with only finitely many global searches.Once iterates enter the local neighborhood, every sufficiently late SDP candidate passes the acceptance test.
- 3.3 The SDP solver: The SDP solver terminates finitely for each outer iteration, and its inner iteration count is asymptotically uniformly bounded near the solution.The global search also terminates finitely by its box-splitting rule, while the dual-scaling solver supplies feasible candidates or reports failure.
4 Application to the discretized Calder´on problem
The section formulates the finitely measured Calderón problem after FEM discretization as a finite-dimensional matrix inverse problem and discusses implementation and dimension reduction.
- Discretized inverse problem: The conductivity equation imposes ∇·(σ∇u) = 0 in Ω with boundary flux σ∂νu = g, while EIT measurements approximate boundary potentials for selected currents.The finite measurements use linearly independent boundary currents and corresponding projected solutions.
- FEM formulation: Evaluating the forward map requires solving the underlying PDE, whereas FEM restricts the variational formulation to a finite-dimensional space with basis functions.The resulting coefficient vectors and stiffness and boundary matrices provide the algebraic representation used by the solver.
- Discretized inverse problem: FEM discretization converts the Calderón problem with finitely many currents and measurements into a matrix-valued mapping from pixel conductivities to approximated measurements.The measurements are obtained through a finite-dimensional Galerkin projection of the Neumann-to-Dirichlet operator.
- FEM formulation: Coercivity gives A1 ≻ 0, and a sufficiently fine FEM mesh makes the boundary matrix B surjective.These properties support the matrix formulation's stated assumptions.
- Efficient implementation: Static condensation and skeleton decomposition eliminate pixel-interior degrees of freedom, reducing the system dimension using only the structure of the matrices Ai and B.The implementation also uses caching, sparsity, and half-vectorization of symmetric matrices.
- Efficient implementation: The implementation selects α = 0.4 to guarantee strict feasibility and a decrease of the Tanabe–Todd–Ye potential, while larger feasible steps may also preserve the convergence bounds.The maximal feasible step is estimated through a generalized eigenvalue computation and then reduced geometrically from 0.95 of that value.
Appendix A Efficient numerical implementation
The appendix proves structural properties of the skeleton decomposition and gives algebraic identities supporting dimension reduction and efficient potential-function evaluation.
- Skeleton decomposition: The sets Jskel, J1, . . . , Jm form a pairwise disjoint partition of all degrees of freedom, and each restricted matrix (Ai)(Ji,Ji) is invertible.These properties follow from A1 ≻ 0 and the defining sparsity structure of the index sets.
- Reduced system properties: The appendix establishes that the reduced skeleton matrices preserve the required positive-semidefinite and full-row-rank assumptions.In particular, Bskel has full row rank after the reduction.
- Skeleton decomposition: For vectors u, each product Aiu splits into a skeleton contribution and a pixel-interior contribution indexed by Jskel and Ji.This decomposition isolates the local degrees of freedom associated with pixel i.
- Reduced system properties: The structural identities imply that vectors of the form A−1_yBTg can be represented through the reduced decomposition.The stated conclusion is used to prove the remaining structural property of the reduction.
P T AyPu(Jskel) = P T BT g
This appendix develops identities for dual-scaling updates and determinants that enable efficient evaluation of the Tanabe–Todd–Ye potential function.
- Potential-function evaluation: Lemma 19 gives an identity for the change in the Tanabe–Todd–Ye potential when the primal variable remains fixed and the dual variable is updated.The identity relates the new and previous potential values for strictly feasible iterates.
- Determinant identity: For strictly dual-feasible y, the determinant of the dual slack matrix decomposes into determinants involving Ay, ˆY − F(y), and ˆY.This follows from the block structure of the dual slack matrix.
- Proof basis: The proof of the determinant relation uses the block structure of the slack matrix, while the potential identity follows directly from the potential definition.Together, these formulas provide efficient quantities for implementation.