Bound Constrained Partial DifferentialEquation Inverse Problem Solution by theSemi-Smooth Newton Method

Tucker Hartland, Cosmin G. Petra, Noémi Petra, Jingyi Wang2021 · DOI

TL;DR

This paper introduces a semi-smooth Newton (ssN) method for solving inverse problems governed by partial differential equations (PDEs) with bound constraints. The method is demonstrated to be mesh-independent and efficient, offering a robust approach for problems with similarities to topology optimization.

What Problem Does This Paper Address?

Inverse problems in science and engineering often involve determining unknown parameters within a system based on observed data. A common challenge is when these unknown parameters are subject to physical constraints, such as being within a specific range (e.g., material properties cannot be negative or exceed a certain value). This paper tackles inverse problems where these parameter constraints are "bound constraints," meaning the parameters must lie between a lower and upper bound. The authors specifically focus on problems governed by partial differential equations (PDEs), which are prevalent in many scientific domains. A key difficulty in solving these problems is the combination of the PDE's complexity, the inverse nature of the problem (inferring parameters from outputs), and the presence of these bound constraints, which can lead to non-smoothness in the optimization problem.

Methods

The core of this paper is the application and development of a semi-smooth Newton (ssN) method. This is an iterative optimization technique that extends the standard Newton's method to handle problems that are not everywhere differentiable. The authors achieve this by reformulating the complementarity conditions (which arise from the bound constraints) using a complementarity function. This function allows the non-smooth complementarity conditions to be treated as a system of non-smooth equations, which the ssN method can then tackle.

Key methodological aspects include:

  • Optimize-then-discretize approach: This principle is used to derive mesh-independent ssN schemes.
  • Semi-smooth Newton (ssN) method: This iterative algorithm is employed to solve the optimization problem. It's particularly suited for problems with non-smoothness arising from complementarity conditions.
  • Complementarity function: A specific function is used to reformulate the bound constraints into a system of non-smooth equations, making them amenable to ssN.
  • MFEM library: The authors leverage the modular finite element method (FEM) package MFEM for software implementation.
  • Matrix-free Operator: A matrix-free operator is constructed to enable the use of efficient Krylov subspace iterative solvers within MFEM. This is crucial for handling large-scale problems.
  • Active Set Strategy: The ssN method is shown to behave like an active set method, where at each iteration, the algorithm identifies which constraints are "active" (i.e., binding) and adjusts the solution accordingly.

Datasets

Not discussed in the paper. The paper focuses on synthetic problems designed to test the methodology.

Key Insights and Ideas

  • Mesh Independence: A significant insight is that the ssN method, when properly formulated, can achieve mesh independence. This means the number of iterations required to converge to a solution is largely unaffected by the fineness of the mesh used for discretization, which is a highly desirable property for computational efficiency and robustness.
  • Bridging Optimization and PDE Solvers: The work demonstrates a powerful synergy between advanced optimization techniques (ssN) and robust PDE solvers (MFEM). This integration is key to tackling complex inverse problems.
  • ssN as an Active Set Method: The paper reveals that the ssN method naturally behaves like an active set strategy for these bound-constrained problems. This provides a deeper understanding of its behavior and allows for efficient handling of the constraints.
  • Computational Efficiency: By using matrix-free operators and efficient Krylov subspace solvers, the method is designed for computational efficiency, which is critical for large-scale inverse problems.

Key Results

The paper presents numerical results for two example problems:

  • Example 1: Source term in Poisson's equation: The ssN method successfully determined a source term in a Poisson equation with bound constraints. The results showed that the number of ssN iterations was largely independent of mesh refinement, confirming mesh independence. The relative size of the active set at the KKT point was also analyzed.
  • Example 2: Diffusion coefficient in Poisson's equation: This problem was more challenging due to nonconvexity and the forward state equation not being well-posed for all parameter values. While the ssN method showed superlinear convergence, globalizing the method for this nonconvex problem proved difficult, and the authors noted that the ssN direction was not always a descent direction for the merit functional.

Quantitative results include:

  • Table 1: Shows that for Example 1, the number of ssN iterations remained low (3-4) across different mesh refinements, while the relative size of the active set increased with mesh refinement.
  • Table 2: Demonstrates superlinear convergence for Example 1, with the error decreasing rapidly with each iteration.

Limitations and Future Work

  • Globalization for Nonconvex Problems: A significant limitation identified is the difficulty in globalizing the ssN method for nonconvex problems (as seen in Example 2). The authors were unable to find a merit function that consistently provided a descent direction for the ssN update, hindering robust convergence for such cases.
  • Approximation of P₁MPA: The framework relies on the approximation $P_1MP_A = 0$, which introduces an error that increases with the order of finite element discretization and the number of nonzeros in the mass matrix $M$.
  • MFEM API for Active/Inactive Sets: The authors note that MFEM currently lacks direct API support for computing boundaries between active and inactive sets that conform to finite element discretizations, which could be a useful extension.
  • Preconditioner Development: While conjugate gradient was used, the paper suggests that incorporating advanced preconditioners (like multigrid) could further enhance efficiency.

Future work could focus on developing more robust globalization strategies for nonconvex problems, exploring alternative approximations for $P_1MP_A$, and investigating MFEM's capabilities for more advanced active set computations.

Summary updated

Abstract

We present the mathematical derivation, software implementation details, and computational results for a semi-smooth Newton method applied to two inverse problems governed by partial differential equations with bound constraints. The two problems share mathematical structural similarities to density-based topology optimization problems. The semi-smooth Newton method provides a mesh independent solution computation for the two test problems. A key step is that the complementarity part of the necessary optimality conditions are reformulated with the use of a complementarity functionφsuch that the complementarity conditions are satisfied if and only if a zero of a nonsmooth function has been obtained. The modular finite element package MFEM is utilized for the software implementation. In addition we constructed a matrix-free Operator to enable the use of efficient Krylov subspace IterativeSolver of MFEM for the solution of our two target problems.
BibTeX
@misc{hartland2021bound,
  author = {Tucker Hartland and Cosmin G. Petra and Noémi Petra and Jingyi Wang},
  title = {{Bound Constrained Partial DifferentialEquation Inverse Problem Solution by theSemi-Smooth Newton Method}},
  year = {2021},
  doi = {10.2172/1765792},
}
Figure