I encounter an optimization problem. The simplified version is like following:

Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. $F(x)>0$). The hessian matrix of $F(x)$ is positive definite. However $F(x)$ is not a strongly convex function, namely we can not assume the hessian matrix $H(x)\succ m I_n$.

Suppose for the sequence $\{\mathbf{x}_k\}_{k=1}^\infty$, the gradients of the $F(x)$ converge to zero: \begin{equation} \lim_{k\rightarrow\infty} \|\mathbf{g}_k\|_2 = 0,\text{ and }F(x_{k+1})\le F(x_{k}), k=0,1,... \end{equation} where $\mathbf{g}_k=\frac{\partial F}{\partial x} |_{x=x_k}$. Do we have the following result \begin{equation} \lim_{k\rightarrow\infty} F(x_{k}) = \inf _{x\in\mathbf{R}^n} F(x)? \end{equation}

I expect $\lim_{k\rightarrow\infty} F(x_k) = \inf_{x\in\mathbf{R}^n} F(x)$. However, I can not find proofs for this result. There are some results about this problem. But unfortunately, either assume the optimum point of $F(x)$ is attainable, namely, there exists $x^*\in\mathbf{R}^n$, such that $F(x^*) = \inf F(x)$ or there exists $x^*\in\mathbf{R}^n$, such that $\lim_{k\rightarrow\infty} x_k=x^*$.

Could any one help me to solve this problem or give me some comments? Thanks for your help.

  • 1
    $\begingroup$ Your posting doesn't clearly state what it is that you're trying to prove and what you're willing to assume. You also haven't told us how the sequence $\bf{x}_{k}$ is generated. Could you clarify the question? $\endgroup$ Commented Dec 18, 2015 at 15:34
  • $\begingroup$ @BrianBorchers Hi, I have revised my question. Hopefully, it is more clear now. When I consider this problem, I encounter trouble that the sequence of $x_k$ may approach $\infty$, namely $\lim_{k\rightarrow\infty} x_k=\infty$. For example for the function $F(x)=\exp(−x)$. For sure, for the function $F(x)=\exp(-x)$, the result in the question is correct. But for general smooth, lower bounded, convex function, do we also have the result correct? $\endgroup$
    – kaiwu
    Commented Dec 18, 2015 at 16:00

1 Answer 1


What about $$ F(x,y) = \frac{x^2}{y} + \frac{\epsilon}{x^2}, \qquad \nabla F(x,y) = \Big( \frac{2x}{y}-\frac{2\epsilon}{x^3}, -\frac{x^2}{y^2} \Big), \qquad x,y>0$$ with the sequence $(x_k,y_k) = (k, k^2)$? Here $\epsilon$ is a small positive real number that makes the Hessian positive definite instead of semidefinite.

Then $F(x_k,y_k) = 1+\epsilon k^{-2}$ does not converge to the global infimum $\inf F(x,y) = 0$, but the sequence of gradients $$\mathbf{g}_k = \Big(\frac2k-\frac{2\epsilon}{k^3}, -\frac{1}{k^2}\Big)$$ converges to zero.

Informally speaking, the usual proof of convergence based on the inequality $f(y)\geq f(x) + \nabla f(x)^T(y-x)$ would not apply here because while the gradients converge as $k^{-1}$ (not fast enough), the distance between $x_k$ and the closest minimum at $x=0$ diverges as $k$.

  • $\begingroup$ @ChristianClason Sorry, typo, that's meant to be $\epsilon/x^2$. Does it look correct to you now? $\endgroup$
    – Kirill
    Commented Dec 20, 2015 at 11:28
  • $\begingroup$ Yes, that's it. Without convergence (or at least boundedness) of the iterates, the result the OP is looking for won't hold. $\endgroup$ Commented Dec 20, 2015 at 11:32
  • $\begingroup$ @Kirill Thanks for constructing the counter example which clarifies my question! $\endgroup$
    – kaiwu
    Commented Dec 20, 2015 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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