Mathematical programs with complementarity constraints and a non-Lipschitz objective: optimality and approximation

We consider a class of mathematical programs with complementarity constraints (MPCC) where the objective function involves a non-Lipschitz sparsity-inducing term. Due to the existence of the non-Lipschitz term, existing constraint qualifications for locally Lipschitz MPCC cannot ensure that necessary optimality conditions hold at a local minimizer. In this paper, we present necessary optimality conditions and MPCC-tailored qualifications for the non-Lipschitz MPCC. The proposed qualifications are related to the constraints and the non-Lipschitz term, which ensure that local minimizers satisfy these necessary optimality conditions. Moreover, we present an approximation method for solving the non-Lipschitz MPCC and establish its convergence. Finally, we use numerical examples of sparse solutions of linear complementarity problems and the second-best road pricing problem in transportation science to illustrate the effectiveness of our approximation method for solving the non-Lipschitz MPCC.

Automated summary

In this paper, we propose necessary optimality conditions and tailored qualifications for a class of mathematical programs with complementarity constraints involving a non-Lipschitz sparsity-inducing term. These qualifications ensure that local minimizers satisfy the necessary optimality conditions, which existing constraint qualifications cannot guarantee due to the presence of the non-Lipschitz term. Additionally, an approximation method for solving the non-Lipschitz MPCC is presented along with its convergence analysis, and numerical examples demonstrate the effectiveness of the proposed method.