Obvious claim about Kurdyka-Łojasiewicz inequality

convex-analysisnon-convex-optimizationoptimization

Let $H$ be a hilbert space and $f$ a closed, proper, convex function from $H$ to $\mathbb{R}\cup\infty$. We write $[f < \mu]$ to denote the set $\{x\in H: f(x)<\mu\}$, $d$ for the hausdorff distance, and $\partial$ for the subdifferential. Let $r_0>0$ and set,

$$K(0,r_0) = \{\phi\in C^0[0,r_0)\cap C^1(0,r_0), \phi(0)=0, \phi\mbox{ is concave and }\phi'>0\}$$

Then we say the function $f$ satisfies the K-L inequality locally at $\bar{x}\in dom(f)$ if there exists $r_0>0$, $\phi\in K(0,r_0)$, and $\varepsilon>0$ such that

$$\phi'(f(x)-f(\bar{x}))d(0,\partial f(x))\geq 1$$

for all $x\in B(\bar{x},\varepsilon)\cap [f(\bar{x})<f(x)<f(\bar{x})+r_0]$.

The paper I am reading claims that if $\bar{x}$ is not a minimizer of $f$ then the KL inequality is obviously satisfied at $\bar{x}$. I don't see it, can someone explain why it's true/obvious?

Best Answer

Lemma: for convex, closed $f$, if $\bar{x} \in \mathrm{dom}f$ is not critical, there is a $c > 0$ such that $\| x - \bar{x} \| + \| f(x) - f(\bar{x}) \| < c \Rightarrow d(0, \partial f(x)) \geq c. $

Proof: By Lemma 2, which is applicable to critical points of any proper lsc function, after noticing that:

  • all critical points of convex functions are also minimizers
  • the convex subdifferential is closed.

Based on that lemma, you can define the "neighbourhood" $B\left(\bar{x}, \frac{c}{2}\right) \cap \left[f(\bar{x}) < f(x) < f(\bar{x}) + \frac{c}{2}\right]$, in which $d(0, \partial f(x)) \geq c$, and set $\phi(s) = \frac{1}{c} s$ with $\phi'(f(x) - f(\bar{x})) = c^{-1}$.

Related Question