Stationary point in non-convex constrained optimization

Question

1s question: definition of stationary point for constrained optimization

As far as I know, a stationary point of a constrained optimization problem is a stationary point of the Lagrangian (that has to be differentiable).

Now consider the problem \begin{equation} \min_{x\in X} F(x) \end{equation} where $F:\mathbb{R}^p\to \mathbb{R}$ is differentiable but possibly non-convex, $X\subset \mathbb{R}^p$ is a closed convex set.

It is easy to obtain the following first-order optimality condition, where $x^*$ is a local minimizer: $$\nabla F(x^*)^\top(x-x^*) \ge 0\quad\forall x\in X. \qquad (*)$$ In several references that I read (such as this one), $x^*$ is called a stationary point if and only if it satisfies the above condition.

My question is: Is this definition of stationary point widely accepted? Is there any reliable reference on that? And, is there a similar definition if $f$ is non-differentiable?

2nd question: Stationary point vs. Nash (equilibrium) point

Consider now that $F(x)$ takes the form $$F(x_1,...,x_n)= f(x_1,...,x_n) + \sum_{i=1}^n r_i(x_i)$$ where $f:\mathbb{R}^p\to \mathbb{R}$ is a differentiable multi-convex function, $r_i:\mathbb{R}^{p_i}\to \mathbb{R}$ are extended-value convex functions. Also, $X$ is a closed multi-convex set. (Roughly speaking, the problem of minimizing over one block while the others are fixed is a convex problem.)

This problem is considered in this paper.

Nash equilibrium (eq. (2.3) in the paper, reformulated): $$x_i^* = \arg\min_{x_i} F(x_1^*,.\ldots.,x_{i-1}^*,x_i,x_{i+1}^*,\ldots,x_n^*) \qquad (2.3),$$ which is equivalent to (eq. (2.4) in the paper): $$\left(\nabla_{x_i}f(x^*) + p_i^*\right)^\top (x_i - x_i^*) \ge 0 \quad\forall x_i \qquad (2.4),$$ where $p_i^*\in\partial r_i(x_i^*)$.

In Remark 2.2 (right after equation (2.4)), the authors stated that:

In general, the condition (2.4) is weaker than the first-order optimality condition. For our problem, a critical point must be a Nash point, but a Nash point is not necessarily a critical point.

I am not sure how the authors defined 'critical point' (= 'stationary point') in this case, because if it's the same as in my first question, then I think for this problem, a Nash point must be a stationary point, given that $r_i$ are differentiable.

Indeed, assume that $x^*$ is a Nash point, we have $$\nabla F(x^*)^\top (x - x^*) = \sum_{i=1}^n \left(\nabla_{x_i}f(x^*) + \nabla r_i(x_i^*)\right)^\top (x_i - x_i^*).$$ Since each term in the sum is non-negative according to $(2.4)$, we must have $\nabla F(x^*)^\top (x - x^*) \ge 0$, i.e., $x^*$ is a stationary point according to the definition $(*)$.

What do you think?

Thanks a lot for your discussion.

Answer 1

A formal definition of the first or second order stationary point can be found in [1]. According to this source:

If $x^*\in X$ is a local minimum of the function $f$ over the convex set $X$, then $$\nabla f(x^*)(x-x^*)\geq 0\quad \forall x \in X$$ and $$(x-x^*)^T\nabla^2 f(x^*)(x-x^*) \geq 0 \quad x \in X~~s.t.~~ \nabla f(f^*)^T(x-x^*)=0$$

In non-convex optimization we are interested in approximate second order stationary points [2].

We call $x^*\in X$, a $(\epsilon, \gamma)$- second order stationary point, if the following two conditions are satisfied $$\nabla f(x^*)(x-x^*)\geq -\epsilon\quad \forall x \in X$$ and $$(x-x^*)^T\nabla^2 f(x^*)(x-x^*) \geq -\gamma \quad x \in X~~s.t.~~ \nabla f(f^*)^T(x-x^*)=0$$

^{[1] Bertsekas, Dimitri P. "Nonlinear programming." Journal of the Operational Research Society 48.3 (1997): 334-334.}

^{[2] Mokhtari, Aryan, Asuman Ozdaglar, and Ali Jadbabaie. "Escaping saddle points in constrained optimization." arXiv preprint arXiv:1809.02162 (2018).}

PS:I do not know about Nash (equilibrium) points yet. Maybe in the future or another user can add more info.