###### Acknowledgements.

The author would like to thank Gerd Wachsmuth for making the author aware of
the conjecture in the Diploma thesis [12]. This work is supported by the DFG
Grant _Bilevel Optimal Control: Theory, Algorithms, and Applications_ (Grant
No. WA 3636/4-2) within the Priority Program SPP 1962 (Non-smooth and
Complementarity-based Distributed Parameter Systems: Simulation and
Hierarchical Optimization). 2020-11-13 2021-10-20 2 6903 2021
10.46298/jnsao-2021-6903 CC-BY-SA 4.0

# A new elementary proof for M-stationarity under MPCC-GCQ for mathematical
programs with complementarity constraints

Felix Harder  Institute of Mathematics, Chair of Optimal Control.
Brandenburgische Technische Universität Cottbus–Senftenberg, Germany. .
<EMAIL_ADDRESS>
(2021-10-14)

###### Abstract

It is known in the literature that local minimizers of mathematical programs
with complementarity constraints (MPCCs) are so-called M-stationary points, if
a weak MPCC-tailored Guignard constraint qualification (called MPCC-GCQ)
holds. In this paper we present a new elementary proof for this result. Our
proof is significantly simpler than existing proofs and does not rely on
deeper technical theory such as calculus rules for limiting normal cones. A
crucial ingredient is a proof of a (to the best of our knowledge previously
open) conjecture, which was formulated in a Diploma thesis by Schinabeck.

###### keywords:

Mathematical program with complementarity constraints, Necessary optimality
conditions, M-stationarity, Guignard constraint qualification

> MSC (2020): 90C33, 90C30
>
> ##  1 Introduction
>
> We consider mathematical programs with complementarity constraints, or MPCCs
> for short, which are nonlinear optimization problems of the form
>
> (MPCC) $\displaystyle\min_{x\in\mathbb{R}^{n}}$ $\displaystyle f(x)$ s.t.
> $\displaystyle\begin{aligned} g(x)&\leq 0,&h(x)&=0,\\\ G(x)&\geq
> 0,&H(x)&\geq 0,&G(x)^{\top}H(x)&=0.\end{aligned}$
>
> Here, $f:\mathbb{R}^{n}\to\mathbb{R}$, $g:\mathbb{R}^{n}\to\mathbb{R}^{l}$,
> $h:\mathbb{R}^{n}\to\mathbb{R}^{m}$, $G,H:\mathbb{R}^{n}\to\mathbb{R}^{p}$
> are differentiable functions.
>
> MPCCs have been studied extensively in the literature, both from a numerical
> and a theoretical perspective. Various problem-tailored stationarity
> conditions and constraint qualifications have been developed. One
> (necessary, first-order) stationarity condition for MPCCs is the so-called
> strong stationarity (which is equivalent to the KKT conditions). However,
> the strong stationarity condition is often too strong, as there are examples
> of MPCCs where the data is linear, but the unique minimizer is not strongly
> stationary, see [11, Example 3].
>
> In this article we will focus on M-stationarity (see Definition 2.1), which
> is another prominent stationarity condition for MPCCs in the literature. We
> mention that there are other stationarity conditions between M- and strong
> stationarity, such as extended M-stationarity, strong M-stationarity,
> $\mathcal{Q}_{M}$-stationarity, and linearized M-stationarity, see [6, 2,
> 7]. However, these conditions are used less frequently than M-stationarity
> and are more complicated to formulate.
>
> As shown in [5], M-stationarity holds for local minimizers of (MPCC) under
> MPCC-GCQ, see also [4]. MPCC-GCQ, defined in Definition 2.3, is a relatively
> weak constraint qualification. These proofs for M-stationarity under MPCC-
> GCQ rely on advanced techniques from variational analysis such as the
> concept of the so-called limiting normal cone. In particular, calculus rules
> for limiting normal cones are used, which are based on deeper technical
> theory and require to verify the calmness of certain set-valued mappings.
>
> We mention that there is also a weaker constraint qualification in [8, (6)],
> which is the weakest constraint qualification under which local minimizers
> are M-stationary. An advantage is that the proof of M-stationarity under
> this constraint qualification is very simple, but on the other hand the
> proof that MPCC-GCQ implies this constraint qualification (or that this
> constraint qualification is satisfied for MPCCs with affine data) relies on
> deeper results from variational analysis. Since MPCC-GCQ and MPCC-ACQ (which
> trivially implies MPCC-GCQ) are used more frequently, we focus on MPCC-GCQ
> in this article.
>
> In this paper we want to present a new proof for the result from [5] that
> M-stationarity holds for local minimizers under MPCC-GCQ. Our new proof does
> not rely on advanced theory such as the properties of limiting normal cones.
> Our proof is significantly simpler than any existing proofs that we are
> aware of. The main ingredient of the new proof is a result which can be
> found in Lemma 3.3. This result was already conjectured in [12, Section
> 4.4.2], and, to the best of our knowledge there has not been a proof of this
> conjecture so far. With the knowledge that Lemma 3.3 holds, the rest of the
> proof of M-stationarity under MPCC-GCQ will not be particularly surprising
> for readers familiar with the implications of MPCC-GCQ. For the convenience
> of the reader we give a self-contained presentation, which only requires
> familiarity with the basic theory of nonlinear optimization. Since the
> constraint qualification in [8, (6)] is the weakest constraint qualification
> under which local minimizers are M-stationary, the new proof also leads to a
> completely elementary proof that MPCC-GCQ implies [8, (6)].
>
> The structure of this paper is as follows: In Section 2, we introduce
> classical definitions related to MPCCs. Then we use MPCC-GCQ to construct
> various multipliers that satisfy some auxiliary stationarity systems, see
> Proposition 3.1. Afterwards, these multipliers are combined into a
> multiplier which is M-stationary with the help of Lemma 3.3. The main result
> is then stated in Theorem 3.5. Finally, we discuss conclusions and
> perspectives in Section 4.
>
> ##  2 Definitions
>
> It will be convenient to work with the index sets
>
> $\displaystyle I^{l}$ $\displaystyle:=\\{1,\ldots,l\\},\qquad
> I^{m}:=\\{1,\ldots,m\\},\qquad I^{p}:=\\{1,\ldots,p\\},$ $\displaystyle
> I^{g}(\bar{x})$ $\displaystyle:=\\{i\in I^{l}\,|\,g_{i}(\bar{x})=0\\},$
> $\displaystyle I^{+0}(\bar{x})$ $\displaystyle:=\\{i\in
> I^{p}\,|\,G_{i}(\bar{x})>0\,\land\,H_{i}(\bar{x})=0\\},$ $\displaystyle
> I^{0+}(\bar{x})$ $\displaystyle:=\\{i\in
> I^{p}\,|\,G_{i}(\bar{x})=0\,\land\,H_{i}(\bar{x})>0\\},$ $\displaystyle
> I^{00}(\bar{x})$ $\displaystyle:=\\{i\in
> I^{p}\,|\,G_{i}(\bar{x})=0\,\land\,H_{i}(\bar{x})=0\\},$
>
> where $\bar{x}\in\mathbb{R}^{n}$ is a feasible point of (MPCC). Note that
> $I^{+0}(\bar{x})$, $I^{0+}(\bar{x})$, $I^{00}(\bar{x})$ form a partition of
> $I^{p}$. We continue with the definition of M-, A- and S-stationarity.
>
> ######  Definition 2.1.
>
> Let $\bar{x}\in\mathbb{R}^{n}$ be a feasible point of (MPCC). We call
> $\bar{x}$ an _M-stationary_ point of (MPCC) if there exist multipliers
> $\bar{\lambda}\in\mathbb{R}^{l}$, $\bar{\eta}\in\mathbb{R}^{m}$,
> $\bar{\mu},\bar{\nu}\in\mathbb{R}^{p}$ with
>
> (1a) $\displaystyle{\nabla f(\bar{x})+\sum_{i\in
> I^{l}}\bar{\lambda}_{i}\nabla g_{i}(\bar{x})+\sum_{i\in
> I^{m}}\bar{\eta}_{i}\nabla h_{i}(\bar{x})-\sum_{i\in
> I^{p}}\big{(}\bar{\mu}_{i}\nabla G_{i}(\bar{x})+\bar{\nu}_{i}\nabla
> H_{i}(\bar{x})\big{)}}$ $\displaystyle=0,$ (1b) $\displaystyle\forall i\in
> I^{g}(\bar{x}):$ $\displaystyle\bar{\lambda}_{i}$ $\displaystyle\geq 0,$
> (1c) $\displaystyle\forall i\in I^{l}\setminus I^{g}(\bar{x}):$
> $\displaystyle\bar{\lambda}_{i}$ $\displaystyle=0,$ (1d)
> $\displaystyle\forall i\in I^{+0}(\bar{x}):$ $\displaystyle\bar{\mu}_{i}$
> $\displaystyle=0,$ (1e) $\displaystyle\forall i\in I^{0+}(\bar{x}):$
> $\displaystyle\bar{\nu}_{i}$ $\displaystyle=0,$ (1f) $\displaystyle\forall
> i\in I^{00}(\bar{x}):$
> $\displaystyle(\bar{\mu}_{i}>0\land\bar{\nu}_{i}>0)\lor\bar{\mu}_{i}\bar{\nu}_{i}$
> $\displaystyle=0.$
>
> If the multipliers $\bar{\lambda},\bar{\eta},\bar{\mu},\bar{\nu}$ only
> satisfy (1a)–(1e) and $\bar{\mu}_{i}\geq 0\lor\bar{\nu}_{i}\geq 0$ holds for
> all $i\in I^{00}(\bar{x})$, then $\bar{x}$ is called an _A-stationary_ point
> of (MPCC). If, additionally, $\bar{\mu}_{i}\geq 0\land\bar{\nu}_{i}\geq 0$
> holds for all $i\in I^{00}(\bar{x})$, then $\bar{x}$ is called a _strongly
> stationary_ or _S-stationary_ point of (MPCC).
>
> These stationarity conditions can be found in [13, Definitions 2.5–2.7].
> Other known stationarity conditions B-, W- and C-stationarity, see [13,
> Definitions 2.2–2.4].
>
> In preparation for the definition of MPCC-GCQ we define some cones.
>
> ######  Definition 2.2.
>
> Let $\bar{x}\in\mathbb{R}^{n}$ be a feasible point of (MPCC).
>
>   1. (a)
>
> We define the _tangent cone_ of (MPCC) at $\bar{x}$ via
>
>
> $\mathcal{T}(\bar{x}):=\left\\{d\in\mathbb{R}^{n}\nonscript\;\middle|\nonscript\;\begin{aligned}
> &\exists\\{x_{k}\\}_{k\in\mathbb{N}}\subset
> F,\,\exists\\{t_{k}\\}_{k\in\mathbb{N}}\subset(0,\infty):\\\ &\qquad
> x_{k}\to\bar{x},\;t_{k}\downarrow 0,\;t_{k}^{-1}(x_{k}-\bar{x})\to
> d\end{aligned}\right\\},$
>
> where $F\subset\mathbb{R}^{n}$ denotes the feasible set of (MPCC).
>
>   2. (b)
>
> We define the _MPCC-linearized tangent cone_
> $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})\subset\mathbb{R}^{n}$ at
> $\bar{x}$ via
>
>
> $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x}):=\left\\{d\in\mathbb{R}^{n}\nonscript\;\middle|\nonscript\;\begin{aligned}
> \nabla g_{i}(\bar{x})^{\top}d&\leq 0\qquad\forall i\in I^{g}(\bar{x}),\\\
> \nabla h_{i}(\bar{x})^{\top}d&=0\qquad\forall i\in I^{m},\\\ \nabla
> G_{i}(\bar{x})^{\top}d&=0\qquad\forall i\in I^{0+}(\bar{x}),\\\ \nabla
> H_{i}(\bar{x})^{\top}d&=0\qquad\forall i\in I^{+0}(\bar{x}),\\\ \nabla
> G_{i}(\bar{x})^{\top}d&\geq 0\qquad\forall i\in I^{00}(\bar{x}),\\\ \nabla
> H_{i}(\bar{x})^{\top}d&\geq 0\qquad\forall i\in I^{00}(\bar{x}),\\\ (\nabla
> G_{i}(\bar{x})^{\top}d)(\nabla H_{i}(\bar{x})^{\top}d)&=0\qquad\forall i\in
> I^{00}(\bar{x})\end{aligned}\right\\}.$
>
>

>
> Note that in general $\mathcal{T}(\bar{x})$ and
> $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$ are nonconvex cones.
>
> We also recall that the polar cone $C^{\circ}$ of a set
> $C\subset\mathbb{R}^{n}$ is defined via
>
> $C^{\circ}:=\\{d\in\mathbb{R}^{n}\nonscript\;|\nonscript\;d^{\top}y\leq
> 0\quad\forall y\in C\\}.$
>
> Now we are ready to give the definition of MPCC-GCQ, which can also be found
> in [5, (41)], where it is called MPEC-GCQ.
>
> ######  Definition 2.3.
>
> Let $\bar{x}\in\mathbb{R}^{n}$ be a feasible point of (MPCC). We say that
> $\bar{x}$ satisfies the _MPCC-tailored Guignard constraint qualification_ ,
> or _MPCC-GCQ_ , if
>
>
> $\mathcal{T}(\bar{x})^{\circ}=\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})^{\circ}$
>
> holds. Additionally, if
> $\mathcal{T}(\bar{x})=\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$ holds
> then we say that $\bar{x}$ satisfies _MPCC-ACQ_.
>
> Clearly, MPCC-ACQ implies MPCC-GCQ. We mention that there are also other
> stronger constraint qualifications (such as MPCC-MFCQ if $g$, $h$, $G$, $H$
> are continuously differentiable, defined in [3, Definition 2.1]) which imply
> MPCC-ACQ or MPCC-GCQ and are sometimes easier to verify, see e.g. [13,
> Theorem 3.2]. In particular, we emphasize that MPCC-GCQ (and MPCC-ACQ) are
> satisfied at every feasible point of (MPCC) if the functions $g$, $h$, $G$,
> $H$ are affine, see [3, Theorem 3.2].
>
> ##  3 M-stationarity under MPCC-GCQ
>
> We start with a Proposition that generates several multipliers which satisfy
> a slightly stronger stationarity condition than A-stationarity. The result
> can also be obtained from the proof of [3, Theorem 3.4], with the minor
> difference that we only require MPCC-GCQ and not MPCC-ACQ.
>
> ######  Proposition 3.1.
>
> Let $\bar{x}\in\mathbb{R}^{n}$ be a local minimizer of (MPCC) that satisfies
> MPCC-GCQ and let $\alpha\in\\{1,2\\}^{p}$ be given. Then there exist
> multipliers $\lambda^{\alpha}\in\mathbb{R}^{l}$,
> $\eta^{\alpha}\in\mathbb{R}^{m}$,
> $\mu^{\alpha},\nu^{\alpha}\in\mathbb{R}^{p}$ with
>
> (2a) $\displaystyle{\nabla f(\bar{x})+\sum_{i\in
> I^{l}}\lambda_{i}^{\alpha}\nabla g_{i}(\bar{x})+\sum_{i\in
> I^{m}}\eta_{i}^{\alpha}\nabla h_{i}(\bar{x})-\sum_{i\in
> I^{p}}\big{(}\mu_{i}^{\alpha}\nabla G_{i}(\bar{x})+\nu_{i}^{\alpha}\nabla
> H_{i}(\bar{x})\big{)}}$ $\displaystyle=0,$ (2b) $\displaystyle\forall i\in
> I^{g}(\bar{x}):$ $\displaystyle\lambda_{i}^{\alpha}$ $\displaystyle\geq 0,$
> (2c) $\displaystyle\forall i\in I^{l}\setminus I^{g}(\bar{x}):$
> $\displaystyle\lambda_{i}^{\alpha}$ $\displaystyle=0,$ (2d)
> $\displaystyle\forall i\in I^{+0}(\bar{x}):$ $\displaystyle\mu_{i}^{\alpha}$
> $\displaystyle=0,$ (2e) $\displaystyle\forall i\in I^{0+}(\bar{x}):$
> $\displaystyle\nu_{i}^{\alpha}$ $\displaystyle=0,$ (2f)
> $\displaystyle\forall i\in I^{00}(\bar{x}),\;\alpha_{i}=1:$
> $\displaystyle\quad\mu_{i}^{\alpha}$ $\displaystyle\geq 0,$ (2g)
> $\displaystyle\forall i\in I^{00}(\bar{x}),\;\alpha_{i}=2:$
> $\displaystyle\quad\nu_{i}^{\alpha}$ $\displaystyle\geq 0.$
>
> ######  Proof 3.2.
>
> From Definition 2.2 (a) and the fact that $\bar{x}$ is a local minimizer of
> (MPCC) it can be concluded that the condition
>
> $\nabla f(\bar{x})^{\top}d\geq 0\qquad\forall\,d\in\mathcal{T}(\bar{x})$
>
> is satisfied. Using polar cones and MPCC-GCQ, we obtain
>
> $-\nabla
> f(\bar{x})\in\mathcal{T}(\bar{x})^{\circ}=\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})^{\circ}.$
>
> Furthermore, we define the cone
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})\subset\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$
> via
>
>
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x}):=\left\\{d\in\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})\nonscript\;\middle|\nonscript\;\begin{aligned}
> (\alpha_{i}=1\Rightarrow\nabla H_{i}(\bar{x})^{\top}d&=0)\;&&\forall i\in
> I^{00}(\bar{x}),\\\ (\alpha_{i}=2\Rightarrow\nabla
> G_{i}(\bar{x})^{\top}d&=0)\;&&\forall i\in
> I^{00}(\bar{x})\end{aligned}\right\\}.$
>
> Using the definition of polar cones, the inclusion
> $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})^{\circ}\subset\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})^{\circ}$
> follows from
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})\subset\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$.
> In particular, we have $-\nabla
> f(\bar{x})\in\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})^{\circ}$.
> Note that the condition $(\nabla G_{i}(\bar{x})^{\top}d)(\nabla
> H_{i}(\bar{x})^{\top}d)=0\;\forall i\in I^{00}(\bar{x})$ from
> $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$ is redundant in
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})$, and therefore
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})$ is a convex and
> polyhedral cone (unlike $\mathcal{T}_{\text{MPCC}}^{\text{lin}}(\bar{x})$).
> Thus, one can calculate its polar cone (e.g. using Farkas’ Lemma), which
> results in
>
>
> $\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})^{\circ}=\left\\{\begin{aligned}
> &\sum_{i\in I^{g}(\bar{x})}\lambda_{i}^{\alpha}\nabla
> g_{i}(\bar{x})+\sum_{i\in I^{m}}\eta_{i}^{\alpha}\nabla h_{i}(\bar{x})\\\
> &\quad-\sum_{i\in I^{0+}(\bar{x})\cup I^{00}(\bar{x})}\mu_{i}^{\alpha}\nabla
> G_{i}(\bar{x})\\\ &\quad-\sum_{i\in I^{+0}(\bar{x})\cup
> I^{00}(\bar{x})}\nu_{i}^{\alpha}\nabla
> H_{i}(\bar{x})\end{aligned}\nonscript\;\middle|\nonscript\;\begin{aligned}
> \lambda_{i}^{\alpha}&\geq 0,\quad i\in I^{g}(\bar{x}),\\\
> \eta_{i}^{\alpha}&\in\mathbb{R},\quad i\in I^{m},\\\
> \mu_{i}^{\alpha}&\in\mathbb{R},\quad i\in I^{0+}(\bar{x})\cup
> I^{00}(\bar{x}),\\\ \nu_{i}^{\alpha}&\in\mathbb{R},\quad i\in
> I^{+0}(\bar{x})\cup I^{00}(\bar{x}),\\\ \mu_{i}^{\alpha}&\geq
> 0,\quad\text{if}\;\alpha_{i}=1,\,i\in I^{00}(\bar{x}),\\\
> \nu_{i}^{\alpha}&\geq 0,\quad\text{if}\;\alpha_{i}=2,\,i\in
> I^{00}(\bar{x})\end{aligned}\right\\}.$
>
> Then the result follows from $-\nabla
> f(\bar{x})\in\mathcal{T}_{\text{NLP}(\alpha)}^{\text{lin}}(\bar{x})^{\circ}$
> by setting the remaining components of the multipliers (i.e.
> $\lambda_{i}^{\alpha}$ for $i\in I^{p}\setminus I^{g}(\bar{x})$,
> $\mu_{i}^{\alpha}$ for $i\in I^{+0}(\bar{x})$, $\nu_{i}^{\alpha}$ for $i\in
> I^{0+}(\bar{x})$) to zero.
>
> We mention that if $\bar{x}$ satisfies (2) for some $\alpha\in\\{1,2\\}^{p}$
> and suitable multipliers, then $\bar{x}$ is an A-stationary point of (MPCC).
> However, the statement of Proposition 3.1 is stronger than A-stationarity,
> namely for each index in $I^{00}(\bar{x})$ we can choose whether
> $\mu_{i}^{\alpha}$ or $\nu_{i}^{\alpha}$ is nonnegative. Note that (1a)–(1e)
> are already satisfied by all $2^{p}$ possible choices for the multipliers
> and any convex combination of these. Thus, the question naturally arises
> whether a convex combination of these multipliers can be found that also
> satisfies (1f). As the next result shows, this is indeed possible. The
> following Lemma was already stated as a conjecture in [12, Section 4.4.2].
> To the best of our knowledge, this conjecture has not been proven before.
>
> ######  Lemma 3.3.
>
> Let $\hat{I}\subset I^{p}$ be an index set. For all
> $\alpha\in\\{1,2\\}^{p}$, let points $(\mu^{\alpha},\nu^{\alpha})\in
> A^{\alpha}$ be given, where the set $A^{\alpha}$ is described via
>
>
> $A^{\alpha}:=\\{(\mu,\nu)\in\mathbb{R}^{2p}\nonscript\;|\nonscript\;\mu_{i}\geq
> 0\;\text{if}\;\alpha_{i}=1,\,\nu_{i}\geq
> 0\;\text{if}\;\alpha_{i}=2\quad\forall i\in\hat{I}\\}.$
>
> Then there exists a point $(\bar{\mu},\bar{\nu})$ in the set
>
>
> $B:=\operatorname{conv}\big{\\{}(\mu^{\alpha},\nu^{\alpha})\nonscript\;\big{|}\nonscript\;\alpha\in\\{1,2\\}^{p}\\}\subset\mathbb{R}^{2p}$
>
> of convex combinations of these points, such that for all $i\in\hat{I}$ we
> have the condition
>
> (3) $(\bar{\mu}_{i}>0\land\bar{\nu}_{i}>0)\lor\bar{\mu}_{i}\bar{\nu}_{i}=0.$
>
> ######  Proof 3.4.
>
> Let us choose points $(\hat{\mu}^{\alpha},\hat{\nu}^{\alpha})\in B\cap
> A^{\alpha}$, a vector $\beta\in\\{1,2\\}^{p}$, and points
> $\bar{\mu},\bar{\nu}\in\mathbb{R}^{p}$ that satisfy
>
> (4) $\displaystyle(\hat{\mu}^{\alpha},\hat{\nu}^{\alpha})$
> $\displaystyle\in\operatorname*{arg\,min}_{(\mu,\nu)\in B\cap
> A^{\alpha}}\,\lVert(\mu,\nu)\rVert_{2}^{2}\qquad\forall\alpha\in\\{1,2\\}^{p},$
> (5) $\displaystyle\beta$
> $\displaystyle\in\operatorname*{arg\,max}_{\alpha\in\\{1,2\\}^{p}}\;\lVert(\hat{\mu}^{\alpha},\hat{\nu}^{\alpha})\rVert_{2}^{2},$
> (6) $\displaystyle(\bar{\mu},\bar{\nu})$
> $\displaystyle:=(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\in\mathbb{R}^{2p}.$
>
> These choices are possible because the sets $B\cap A^{\alpha}$ is compact
> and nonempty (the nonemptiness follows from $(\mu^{\alpha},\nu^{\alpha})\in
> B\cap A^{\alpha}$) and the set $\\{1,2\\}^{p}$ is finite. Furthermore, we
> have $(\bar{\mu},\bar{\nu})\in B$, i.e. it is a convex combination as
> claimed.
>
> It remains to show that our choice $(\hat{\mu}^{\beta},\hat{\nu}^{\beta})$
> for $(\bar{\mu},\bar{\nu})$ satisfies (3). By contradiction, we assume that
> there exists an $i\in\hat{I}$ such that (3) is not satisfied, i.e.
> $\hat{\mu}^{\beta}_{i}\neq 0$, $\hat{\nu}^{\beta}_{i}\neq 0$, and
> $\hat{\mu}^{\beta}_{i}<0\lor\hat{\nu}^{\beta}_{i}<0$ hold. Without loss of
> generality we can assume that $\beta_{i}=1$ holds (otherwise one would
> exchange the roles of $\mu$ and $\nu$ in the rest of the proof). Therefore,
> we have $\hat{\mu}^{\beta}_{i}\geq 0$ due to
> $(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\in A^{\beta}$. Since (3) is not
> satisfied this implies $\hat{\mu}^{\beta}_{i}>0$ and
> $\hat{\nu}^{\beta}_{i}<0$. We define
>
>
> $\gamma\in\\{1,2\\}^{p},\qquad\gamma_{j}:=\begin{cases}2&\;\text{if}\;j=i,\\\
> \beta_{j}&\;\text{if}\;j\in I^{p}\setminus\\{i\\}\end{cases}\quad\forall
> j\in I^{p}.$
>
> Due to $\hat{\mu}^{\beta}_{i}>0$ we can choose $t\in(0,1)$ such that the
> convex combination
>
>
> $(\mu^{t},\nu^{t}):=t(\hat{\mu}^{\gamma},\hat{\nu}^{\gamma})+(1-t)(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\in\mathbb{R}^{2p}$
>
> still satisfies $\mu^{t}_{i}>0$. Since $\gamma_{j}=\beta_{j}$ holds for
> $j\neq i$ we also have $(\mu^{t},\nu^{t})\in A^{\beta}\cap B$. However,
> $\hat{\nu}^{\gamma}_{i}\geq 0$ implies
> $(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\neq(\hat{\mu}^{\gamma},\hat{\nu}^{\gamma})$.
> Thus, by also using (5), we have
>
>
> $\lVert(\mu^{t},\nu^{t})\rVert_{2}^{2}<\max\Big{\\{}\lVert(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\rVert_{2}^{2},\lVert(\hat{\mu}^{\gamma},\hat{\nu}^{\gamma})\rVert_{2}^{2}\Big{\\}}=\lVert(\hat{\mu}^{\beta},\hat{\nu}^{\beta})\rVert_{2}^{2}.$
>
> Due to $(\mu^{t},\nu^{t})\in B\cap A^{\beta}$ this is a contradiction to
> (4), which completes the proof.
>
> Instead of the function $(\mu,\nu)\mapsto\lVert(\mu,\nu)\rVert_{2}^{2}$, any
> strictly convex function on $\mathbb{R}^{2p}$ would have worked in the
> proof.
>
> We mention that it was recognized already in [12, Section 4.4.2] that this
> Lemma would significantly simplify the already existing proofs for
> M-stationarity. We further mention that the idea to combine various
> multipliers of the form $(\mu^{\alpha},\nu^{\alpha})$ was also used for the
> concept of $\mathcal{Q}$-stationarity in [1].
>
> A straightforward combination of Propositions 3.1 and 3.3 yields the desired
> M-stationarity result.
>
> ######  Theorem 3.5.
>
> Let $\bar{x}\in\mathbb{R}^{n}$ be a local minimizer of (MPCC) that satisfies
> MPCC-GCQ. Then $\bar{x}$ is an M-stationary point.
>
> ######  Proof 3.6.
>
> For all $\alpha\in\\{1,2\\}^{p}$, let
> $(\lambda^{\alpha},\eta^{\alpha},\mu^{\alpha},\nu^{\alpha})\in\mathbb{R}^{l+m+2p}$
> be the multipliers generated by Proposition 3.1. By applying Lemma 3.3 with
> $\hat{I}=I^{00}(\bar{x})$, we find a convex combination
> $(\bar{\lambda},\bar{\eta},\bar{\mu},\bar{\nu})\in\mathbb{R}^{l+m+2p}$ of
> these multipliers such that (1f) is satisfied. The conditions (1a)–(1e)
> follow from (2a)–(2e) by convexity.
>
> ##  4 Conclusion and outlook
>
> We provided a new proof for the M-stationarity of local minimizers of MPCCs
> under MPCC-GCQ. Although this result was already known, the new proof uses
> only basic and well-known tools from nonlinear programming theory. This new
> elementary proof for M-stationarity was enabled by proving a (to the best of
> our knowledge previously open) conjecture from [12] in Lemma 3.3.
>
> In the future, it would also be interesting to apply this approach to other
> problem classes from disjunctive programming and to investigate to what
> extend the ideas from this paper can be generalized.
>
> In Sobolev or Lebesgue spaces, the limiting normal cone turned out to be not
> as effective as in finite dimensional spaces for obtaining stationarity
> conditions for complementarity-type optimization problems, see [9, 10].
> Thus, it would be interesting to know whether the new elementary method from
> this paper can provide ideas for possible approaches for better stationarity
> conditions of complementarity-type optimization problems in Sobolev and
> Lebesgue spaces.
>
> ## References
>
>   * [1] M.Benko and H.Gfrerer, On estimating the regular normal cone to
> constraint systems and stationarity conditions, _Optimization_ 66 (2016),
> 61–92, doi:10.1080/02331934.2016.1252915.
>   * [2] M.Benko and H.Gfrerer, New verifiable stationarity concepts for a
> class of mathematical programs with disjunctive constraints, _Optimization_
> 67 (2017), 1–23, doi:10.1080/02331934.2017.1387547.
>   * [3] M. L.Flegel and C.Kanzow, Abadie-type constraint qualification for
> mathematical programs with equilibrium constraints, _Journal of Optimization
> Theory and Applications_ 124 (2005), 595–614, doi:10.1007/s10957-004-1176-x.
>   * [4] M. L.Flegel and C.Kanzow, A direct proof for M-stationarity under
> MPEC-GCQ for mathematical programs with equilibrium constraints, in
> _Optimization with Multivalued Mappings_ , volume 2 of Springer Optim.
> Appl., Springer, New York, 2006, 111–122, doi:10.1007/0-387-34221-4_6.
>   * [5] M. L.Flegel, C.Kanzow, and J. V.Outrata, Optimality conditions for
> disjunctive programs with application to mathematical programs with
> equilibrium constraints, _Set-Valued Analysis_ 15 (2007), 139–162,
> doi:10.1007/s11228-006-0033-5.
>   * [6] H.Gfrerer, Optimality conditions for disjunctive programs based on
> generalized differentiation with application to mathematical programs with
> equilibrium constraints, _SIAM Journal on Optimization_ 24 (2014), 898–931,
> doi:10.1137/130914449.
>   * [7] H.Gfrerer, Linearized M-stationarity conditions for general
> optimization problems, _Set-Valued and Variational Analysis_ 27 (2018),
> 819–840, doi:10.1007/s11228-018-0491-6.
>   * [8] L.Guo and G. H.Lin, Notes on some constraint qualifications for
> mathematical programs with equilibrium constraints, _Journal of Optimization
> Theory and Applications_ 156 (2012), 600–616, doi:10.1007/s10957-012-0084-8.
>   * [9] F.Harder and G.Wachsmuth, The limiting normal cone of a
> complementarity set in Sobolev spaces, _Optimization_ 67 (2018), 1579–1603,
> doi:10.1080/02331934.2018.1484467.
>   * [10] P.Mehlitz and G.Wachsmuth, The limiting normal cone to pointwise
> defined sets in Lebesgue spaces, _Set-Valued and Variational Analysis_ 26
> (2018), 449–467, doi:10.1007/s11228-016-0393-4.
>   * [11] S.Scheel and S.Scholtes, Mathematical programs with complementarity
> constraints: stationarity, optimality, and sensitivity, _Mathematics of
> Operations Research_ 25 (2000), 1–22, doi:10.1287/moor.25.1.1.15213.
>   * [12] M.Schinabeck, _Constraint Qualifications und
> Optimalitätsbedingungen für MPECs_ , Diploma thesis, University of
> Regensburg, Germany, 2009.
>   * [13] J. J.Ye, Necessary and sufficient optimality conditions for
> mathematical programs with equilibrium constraints, _Journal of Mathematical
> Analysis and Applications_ 307 (2005), 350 – 369,
> doi:10.1016/j.jmaa.2004.10.032.
>