Bilevel Imaging Learning Problems as Mathematical Programs with Complementarity Constraints: Reformulation and Theory
This work provides a theoretical foundation for solving bilevel optimization problems in imaging, which is incremental as it builds on existing variational models but offers new reformulation and analysis tools.
The authors tackled bilevel imaging learning problems by reformulating them as Mathematical Programs with Complementarity Constraints (MPCC), proving tight constraint qualifications and deriving stationarity and second-order optimality conditions. This reformulation enables the use of large-scale nonlinear programming solvers for efficient application in imaging tasks.
We investigate a family of bilevel imaging learning problems where the lower-level instance corresponds to a convex variational model involving first- and second-order nonsmooth sparsity-based regularizers. By using geometric properties of the primal-dual reformulation of the lower-level problem and introducing suitable auxiliar variables, we are able to reformulate the original bilevel problems as Mathematical Programs with Complementarity Constraints (MPCC). For the latter, we prove tight constraint qualification conditions (MPCC-RCPLD and partial MPCC-LICQ) and derive Mordukhovich (M-) and Strong (S-) stationarity conditions. The stationarity systems for the MPCC turn also into stationarity conditions for the original formulation. Second-order sufficient optimality conditions are derived as well, together with a local uniqueness result for stationary points. The proposed reformulation may be extended to problems in function spaces, leading to MPCC's with constraints on the gradient of the state. The MPCC reformulation also leads to the efficient use of available large-scale nonlinear programming solvers, as shown in a companion paper, where different imaging applications are studied.