3
$\begingroup$

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?

Can anyone, please, enlighten me?


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?
$\endgroup$
4
$\begingroup$
  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|<x_1$) 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you see any reason why this condition is preferred over convexity? $\endgroup$ – independentvariable Apr 17 at 21:15
  • $\begingroup$ I mean in general, we can say that the function is convex so (0.5, 0) is a global minimizer, right? $\endgroup$ – independentvariable Apr 17 at 21:27
  • 1
    $\begingroup$ 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. $\endgroup$ – TheSimpliFire Apr 18 at 9:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.