Does a closed convex function with open domain tend to infinity as it approaches the boundary?

136 Views Asked by At

If we have a closed differentiable convex function $f$ with open domain, given a sequence $\{x_{k}\}$ such that:

$$ \{x_{k}\} \subset \text{dom}f: \: x_{k} \rightarrow \bar{x} $$

where $\bar{x} \in \partial(\text{dom}f)$, do we have $f(x_{k}) \rightarrow +\infty$?

The motivation for this question comes from a theorem stated in Nesterov's convex optimisation book:

Theorem 4.1.4 - Let $f$ be a self-concordant function. Then for any point $\bar{x} \in \partial(\text{dom}f)$ and any sequence as above, we have $f(x_{k}) \rightarrow \infty$.

Proof:
Note that the sequence $\{f(x_{k})\}$ is bounded below:

$$ f(x_{k}) \geq f(x_{0}) + \langle f'(x_{0}), x_{k} - x_{0}\rangle $$

Assume that it is bounded from above. Then it has a limit point $\bar{f}$. Of course we can think of $\bar{f}$ as the unique limit point of the sequence. Therefore:

$$ z_{k} = (x_{k}, f(x_{k})) \rightarrow \bar{z} = (\bar{x}, > f(\bar{x})) $$

Note that $z_{k} \in \text{epi}f$, but $\bar{z} \not\in \text{epi}f$ since $\bar{x} \not\in \text{dom}f$. This is a contradiction because $f$ is closed.

I understand that Nesterov shows by contradiction that the sequence $\{f(x_{k})\}$ is unbounded above and bounded below. But why is this enough to imply that the sequence tends to infinity?

Nesterov defines a self-concordant function as a closed convex function with open domain for which the following inequality holds:

$$ |D^{3}f(x)[u, u, u]| \leq M_{f}\|u\|^{\frac{3}{2}}_{f''(x)} $$

for some $M_{f} > 0$. but I do not think this inequality is relevant to the proof as it is not used anywhere explicitly.

EDIT:

I think the proof of this fact is relatively simple. To start, we can find an $N \in \mathbb{N}$, such that

$$ \forall k > N,\; \|x_{k} - x^{*}\| \leq \epsilon $$

for any $\epsilon > 0$. Thus we have

$$ \forall m, n \geq N, \; \|x_{m} - x_{n}\| = ||x_{m} - \bar{x} + \bar{x} - x_{n}\| \leq \|x_{m} - \bar{x}\| + \|x_{n} - \bar{x}\| \leq 2\epsilon $$

Moreover, since $f$ is unbounded, for any $r \in \mathbb{R}$ there must exist an $m > N$ such that $f(x_{m}) > r$ (otherwise we know the sequence would be bounded above). Since $f$ is continuous, we can choose $\epsilon$ sufficiently small such that:

$$ \|x_{m} - x_{n}\| \leq 2\epsilon \implies \|f(x_{m}) - f(x_{n})\| \leq \delta $$

for any $\delta > 0$. Since $m > N$ we have

$$ \forall n \geq N, \|x_{n} - x_{m}\| \leq 2\epsilon \implies \|f(x_{n}) - f(x_{m})\| \leq \delta \implies f(x_{n}) \geq f(x_{m}) - \delta > r - \delta $$

Thus for all $n > N$ we have that $f(x_{n}) > r - \delta$. Note that we are free to choose $\delta$, so for any real number $s > 0$, we can find an $N \in \mathbb{N}$ such that $f(x_{n}) > s$ for all $n > N$. Hence the sequence tends to infinity. I think this proof is correct but I would appreciate if someone could check it?