An approach to handle an orthogonal projection onto a nonconvex set

147 Views Asked by At

I have a composite problem in hand, which can be expressed as \begin{align} \min_{x \in \mathbb{R}^n} \ \ h(x) + I_{C}(x), \end{align} where $h(x)$ is $L$-smooth and $I_{C}(x)$ is an indicator function to a non-convex set, i.e., $I_{C}(x)=0$ if $x \in C$ else $+\infty$. The set $C:= \{x \in \mathbb{R}^n \mid f(x) - g(x) \leq 0 \}$, where both $f:\mathbb{R}^n \rightarrow \mathbb{R}$ and $g:\mathbb{R}^n \rightarrow \mathbb{R}$ are closed convex proper functions.

To solve such a composite problem, I can use an iterative proximal gradient scheme. However, in general, I do not know an orthogonal projection onto such a non-convex set $C$.

To this end, I have done a "trick". Specifically, I have created a set, i.e., $D^k:= \{x \in \mathbb{R}^n \mid f(x) - g(x^{k}) \leq 0 \}$, which uses the update $x^k$ corresponding to the previous iteration $k$. So, I can "view" this new set as a convex set when updating the current iterate $x^{k+1} = P_{D^k}\left( x - t_k\nabla h(x^k) \right)$ and know the orthogonal projection onto such a set $P_{D^k}$. Apparently, the solution looks promising

My questions are: I have a feeling that such a trick might have been done before and more rigorously. However, I do not know any references. Can anyone point me to a good set of references? or/and can we say anything about the optimality?

Comments/feedback are welcome.