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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.