Lifting mathematical programs with complementarity constraints (Q662308)

A problem of minimization of a criterion \(f(x)\) subject to a constraint \[ x\in M = \left\{ x\in{\mathbb{R}}^n\;| \, (F_j^1(x),F_j^2(x))\in L, j=1,2,\ldots,k \right\} \] where \[ L=\left\{(a,b)\in\mathbb{R}^2\;| a\geq0,\,b\geq0,\, ab=0\right\} \] is called a problem of mathematical programming with complementary constraints (MPCC). The set \(L\) is not smooth. Instead of approximating \(L\) with a smooth set in \(\mathbb{R}^2\), the authors propose to interpret the set \(L\) as the orthogonal projection of a \textit{smooth} set in \(\mathbb{R}^3\). The proposed lifting construction transforms an MPCC into a smooth problem with additional \(k\) parameters. The extended problem inherits some properties of the original MPCC. For example, it is obtained that the modified problem inherits the the linear independence constraint qualification from the original MPCC. The criticality in the modified problem is equivalent to the weak stationarity in the original MPCC. A modified problem is perturbed by adding to the target criterion a linear functional, which is the dot product of a vector \(t\) and a vector whose components are the additional variables. Such a perturbation is called tilting. For a weakly stationary point \(\bar{x}\) in the original MPCC, \textit{tilting stability} means that there exists a family of critical points for the respective tilted problems, which is continuous in \(t\) and which yields \(\bar{x}\) for \(t=0\). It is obtained that if \(\bar{x}\) is a nondegenerate {C}-stationary point for the original {MPCC}, then it is tilting stable and the respective critical points in tilted problems are unique and, in a certain sense, regular. The authors present results of computations for a number of examples. A comparison between the lifting method and direct smoothing of the original MPCC suggests that both methods produce accurate results. However, the direct smoothing approach performs faster, which is attributed to the multi-step nature of the lifting approach.