0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what you describe as "the following mapping" is completely unclear. What is the mapping? What is mapped to what? $\endgroup$ – miracle173 Jul 20 '17 at 6:50
  • $\begingroup$ 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) \}$$ $\endgroup$ – miracle173 Jul 20 '17 at 7:08
  • $\begingroup$ Please add more context. $\endgroup$ – miracle173 Jul 20 '17 at 7:12
  • $\begingroup$ 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? $\endgroup$ – Rachel Jul 20 '17 at 7:18
  • $\begingroup$ 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? $\endgroup$ – miracle173 Jul 20 '17 at 7:28
1
$\begingroup$

The proximal minimization algorithm (iterating the mapping you wanted to describe) is the application to optimization of the so-called proximal point algorithm for finding zeroes of monotone operators.

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.

$\endgroup$

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.