  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.
