# Is there an example where the proximal method diverges?

This is a question that it is not homework but I would like clear.

I have this Proximal interpretation, that is: the solution of the problem is a fixed point of the following mapping: $$x^{\ast} \in \ \ \arg \min_{x \in X_{\text{adm}}} \{\ \frac{1}{2}||x-x^{\ast}||^{2} + \gamma \ \ f(x) \} \ , \ \gamma >0$$

with $$X_{\text{adm}} = \{\ x \in \mathbb{R^n} | x \geq 0 \ , \ A_{\text{eq}}x=b_{\text{eq}}, A_{\text{ineq}}x=b_{\text{ineq}} \}$$ These $A$'s can be interpreted as constrains and it is compact and convex subset of $\mathbb{R^n}$.

Here I suppose that $f(x)$ is convex and differentiable with the gradient satisfying the Lipschitz condition.

Does this proximal method always converge? , i.e , does the proximal interpretation diverge?

I think that yes it divenges but maybe someone can hit me with some example?

I want to understand this because I'm going to study the Proximal Gradient method. Thanks for your help and time.

• what you describe as "the following mapping" is completely unclear. What is the mapping? What is mapped to what? – miracle173 Jul 20 '17 at 6:50
• I googled web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf and I assume your mapping is $$^{\ast}: v \to v^{\ast}$$ and is defined as $$v^{\ast} = \ \ \arg \min_{x \in X_{\text{adm}}} \{\ \frac{1}{2}||x-v||^{2} + \gamma \ \ f(x) \}$$ – miracle173 Jul 20 '17 at 7:08
• Please add more context. – miracle173 Jul 20 '17 at 7:12
• Given $x_i \in X$, define the iteration: $$x_{i+1} = \arg\min_{x\in X}\left[f(x) + \frac{1}{2t}||x-x_i||^2\right]$$ If we suppose $f(x)$ is a convex function over the convex set $X$ and has a global minimum $x^* \in X$. If $x_{i+1}=x_i$, then $x_{i+1}$ minimizes $f(x)$ over $X$. But I want to know if is it necessary in general the global minimum for the convergence? – Rachel Jul 20 '17 at 7:18
• So my assumption was right. You should modify your post. Maybe you add your comment. As far as I understand you want to know if the sequence $x_i$ always converges. Is this right? What paper/book do you study? – miracle173 Jul 20 '17 at 7:28

Its convergence to a solution is ensured under basically no assumptions on the (nonzero) stepsize $\gamma$, as stated in Theorem 4 of Rockafellar, “Monotone operators and the proximal point algorithm”, 1976.
So there’s no counterexample showing divergence. You don’t even need smoothness of $f$ really.