4
$\begingroup$

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.

$\endgroup$
  • 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$ – Brian Borchers Dec 18 '15 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 Dec 18 '15 at 16:00
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @ChristianClason Sorry, typo, that's meant to be $\epsilon/x^2$. Does it look correct to you now? $\endgroup$ – Kirill Dec 20 '15 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$ – Christian Clason Dec 20 '15 at 11:32
  • $\begingroup$ @Kirill Thanks for constructing the counter example which clarifies my question! $\endgroup$ – kaiwu Dec 20 '15 at 13:20

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.