1
$\begingroup$

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.

$\endgroup$

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.