We have a simple problem, namely minimizing: $$f(x) = x_1^2 + x_2^2 - x_1.$$

The gradient is $$\nabla f(x) = \begin{bmatrix} 2x_1 - 1 \\ 2x_2 \end{bmatrix},$$ hence the unique stationary point is: $$x_* = (\frac{1}{2}, 0)$$. Now, I have a simple introduction to OR level question asking me why this is globally optimal.

My typical answer is to show that $$f(x)$$ is convex, e.g.,: $$\nabla^2 f(x) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \succ 0,$$ therefore a local minimizer is a global minimizer.

However, in some engineering course-notes, the proof of global optimality is:

It is also a global minimizer since the function $$f$$ is $$C^1$$ and radially unbounded, therefore the global minimizer is a stationary point.

1. What is $$C^1$$?

2. What does radial unboundedness imply here?

Edit: I think they are using the fact that $$\lim\limits_{k \to \infty} \|x_k\|=\infty \implies \lim\limits_{k \to \infty} f(x_k) = \infty$$. Hence, all level sets of $$f$$ are compact. Hence the global minimum exists in $$\mathbb{R}^2$$. And the unique stationary point is also globally optimum. But the main question is,

1. Why not show convexity and go in this way?

1. The notation $$C^1$$ means $$f'$$ is continuous (on $$\Bbb R$$ as the interval is not stated). In general $$C^k(a,b]$$ means that all of $$f',f'',\cdots,f^{(k)}$$ are continuous on $$(a,b]$$.

2. You are correct that radial unboundedness means that $$f\to\infty$$ as $$\|x\|\to\infty$$. This method is essentially that for Lyapunov stability.

3. Ahmadi and Jungers (2018)1 proved that if a function $$f$$ satisfies $$f(0)=0$$ and is positive for all $$x_i\ne0$$ then its convexity implies its radial unboundedness. However, notice that $$f$$ is not always positive for all $$x_1,x_2\ne0$$ (choose $$x_1=1/2$$ and any $$|x_2|) so the second criterion is not satisfied.

Reference

[1] Ahmadi, A. A., Jungers, R. M. (2018). SOS-Convex Lyapunov Functions and Stability of Difference Inclusions. CoRR abs/1803.02070.

• Thanks for your answer. Do you see any reason why this condition is preferred over convexity? Apr 17, 2020 at 21:15
• I mean in general, we can say that the function is convex so (0.5, 0) is a global minimizer, right? Apr 17, 2020 at 21:27
• Yes, I suppose the solution provided is alternative. Of course the other condition required is that the domains of $\boldsymbol x$ are convex which is clearly the case here. Apr 18, 2020 at 9:53