  We aim to compute lifted stationary points of a sparse optimization problem
(P0) with complementarity constraints. We define a continuous relaxation
problem (Rv) that has the same global minimizers and optimal value with problem
(P0). Problem (Rv) is a mathematical program with complementarity constraints
(MPCC) and a difference-of-convex (DC) objective function. We define MPCC
lifted-stationarity of (Rv) and show that it is weaker than directional
stationarity, but stronger than Clarke stationarity for local optimality.
Moreover, we propose an approximation method to solve (Rv) and an augmented
Lagrangian method to solve its subproblem, which relaxes the equality
constraint in (Rv) with a tolerance. We prove the convergence of our algorithm
to an MPCC lifted-stationary point of problem (Rv) and use a sparse
optimization problem with vertical linear complementarity constraints to
demonstrate the efficiency of our algorithm on finding sparse solutions in
practice.

Optimization and Control