stationarity of a nonconvex-constrained problem

111 Views Asked by At

Suppose I want to solve

min $f(x)$ subject to $x\in \mathcal C$

where $\mathcal C$ is nonconvex, and $f$ is smooth and convex. What would be an appropriate definition for stationarity?

If $\mathcal C$ were convex, the one that pops to mind is like a normal cone constraint: $x^*$ is stationary if

$$ -\langle\nabla f(x^*),x-x^*\rangle \leq 0,\;\forall x\in \mathcal C.$$

So an easy approach may be to just replace $\mathcal C$ with the convex hull of $\mathcal C$. However, this is clearly a bad idea for most hard nonconvex problems. Take $\mathcal C = \{-1,1\}$ and $f(x) = x^2$. Then either -1 or 1 are minimal solutions, but are not stationary points according to this definition.

1

There are 1 best solutions below

9
On

For stationarity, you only need to check locally feasible directions. So I think you might be able to use a definition like this: There exists a $\delta>0$ such that \begin{align} f'(x; d)\geq 0, \end{align} for all feasible local perturbation directions $\|d\|\leq \delta$. Note that $f'(x; d)$ is the directional derivative, which if the function is smooth becomes $\nabla f(x)^T d$. Feasible local perturbations are the ones for which $x+d \in C$. You might want to think a bit more about this, as in the case where the set is non-convex some weird stuff could happen. Plus, I am not sure if this would be easy to check if the set is really weird.