share
MathematicsCalculating the projection of a point onto a set given by complementarity constraints
[0] [1] R. W. Prado
[2021-11-05 17:52:16]
[ optimization projection ]
[ https://math.stackexchange.com/questions/4297785/calculating-the-projection-of-a-point-onto-a-set-given-by-complementarity-constr ]

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.

(1) Isn't the last part of the condition $H(\boldsymbol{x}) \geq 0 \text{ and } G( \boldsymbol{x}) \geq 0 \text{ and } H(\boldsymbol{x} ) G( \boldsymbol{x}) \leq 0$ a more complicated way of saying that one of $G(\boldsymbol{x})$ or $H(\boldsymbol{x})$ must be zero? - Keeley Hoek
It is a more complicated way of saying that one is non-negative and the other zero. I'm not sure if writing it as a union of sets would help to find an easier solution. Several MPCC (program with complementarity constraints) are written this way, and changing the notation would change the spirit. I suggest to you to look for this term. =) - R. W. Prado
If someone finds a heart-shaped set that could be written in this way, probably it would be the solution for proving this result false. The point located in the inward pointed corner is a problem for sure. - R. W. Prado
[0] [2021-11-12 23:07:38] R. W. Prado [ACCEPTED]

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.$


1