Calculating the projection of a point onto a set given by complementarity constraints

optimizationprojection

Let us start with arbitrarily smooth functions $H, G : \mathbb{R}^{n} \rightarrow \mathbb{R}$. I have point $\boldsymbol{y} \in B[\boldsymbol{x}^{*}, \delta]\subset \mathbb{R}^{n}$ satisfying $H(\boldsymbol{y} ) < 0$ and $ G( \boldsymbol{y}) < 0$. I want to orthogonally project it onto the set $$\Omega = \{\ \boldsymbol{x} \in \mathbb{R}^n \ :\ H(\boldsymbol{x} )\geq 0 \text{ and } G( \boldsymbol{x}) \geq 0 \text{ and } H(\boldsymbol{x} ) G( \boldsymbol{x}) \leq 0 \}.$$ I know that, for at least a converging sequence $\{\boldsymbol{y}^{k}\}_{k\in\mathbb{N}}$ of points satisfying $H(\boldsymbol{y}^{k} ) < 0$ and $ G( \boldsymbol{y}^k) < 0 $, it holds $\boldsymbol{y}^{k}\rightarrow \boldsymbol{x}^{*}$, in which $G(\boldsymbol{x}^{*}) = 0$ and $H(\boldsymbol{x}^{*}) = 0$. I want to know there is a solution/minimizer $\boldsymbol{y}^{*}$ of the projection of $\boldsymbol{y}$ onto $\Omega$ , i.e., a minimizer $\boldsymbol{y}^{*}$ of the problem $$\min_{\boldsymbol{x} \in \Omega }\|\boldsymbol{y} – \boldsymbol{x}\|,$$ that satisfies $H(\boldsymbol{y}^{*}) = 0$ and $G(\boldsymbol{y}^{*}) = 0.$ Here, you can start this problem with $\delta>0$ arbitrarily small without any problem, if needed.

This issue relates to the local behavior of an external penalty method applied to a mathematical program with complementarity constraints (MPCC). Solving it, would help me to understand better how this MPCC programs behaves locally close to a degenerate solution. Here I think the fact that I am applying an external penalty method does not need to be considered too much, and that's why I have not introduced it in details.

Best Answer

Taking $$ H(x,y) = (x^2+y^2+2x)^2 - 4 (x^2 + y^2)^2, \\ G(x,y) = (x^2+y^2+2x)^2 - 2 (x^2 + y^2)^2,$$ for all $x, y\in \mathbb{R}$, the origin is an inward pointed corner, which means that the projection of $z\in\mathbb{R}^{2}$, say $w \in\mathbb{R}^{2}$, such that $H(z)>0, G(z)>0$ could never be such that $H(w) = G(w) = 0$, i.e., $w=0.$

Related Question