0
$\begingroup$

I want to solve

$\min_x f(x) + g(x)$

where $f + g$ is convex and but, for example, $g$ is non convex. To make matters simpler, let us say that $g$ is concave.

If I use a splitting method, like ADMM, and assuming that I can compute the proximal operator for $f$ and $g$ exactly, can I guarantee that ADMM is going to converge to the optimum?

To be concrete, regarding using ADMM, what happens if we use the decomposition

$\min_{x,y,z} f(x) + g(y)$ subject to $x=z, y = z$

I know people have looked at non-convex ADMM, but this does not seem to be as hard as these problems. Are there any references for this type of problem?

I did a quick experiment with the objective $f(x) = x^2$ and $g(x) = -0.5(x-1)^2$. The minimum is $-1$. If I run ADMM, using the above decomposition, for $50$ iterations and plot the error versus $\rho$, the penalty parameter, I get the following plot

Sometimes it converges, other times it does not, depending on the tunnig

The Matlab code to produce the plot is

evol = []; for rho = 0.1:0.1:10 n_1 = randn; n_2 = randn; u_1 = randn; u_2 = randn; for i =1:50 x_1 = rho*n_1/(2 + rho); x_2 = (rho*n_2 - 1) / (rho - 1); z = 0.5*(x_1 + u_1 + x_2 + u_2); u_1 = u_1 + (x_1 - z); u_2 = u_2 + (x_2 - z); n_1 = z - u_1; n_2 = z - u_2; end evol = [evol, z]; end plot(0.1:0.1:10,log(abs(evol + 1)));
$\endgroup$
5
  • $\begingroup$ ADMM deals with constraints and has several variants/forms. Here you have no constraints and you do not specify the precise method you will use. $\endgroup$ Commented Mar 31, 2018 at 16:34
  • $\begingroup$ It seems that you have already found that it does not always converge. Are you looking for bounds on $\rho$ that can guarantee convergence? At the very least, $\rho$ should be large enough that the $x$-updates are convex minimizations; for example, in this case we need $\rho > 1$. However, from the graph it appears that this only necessary but not sufficient. $\endgroup$ Commented Mar 31, 2018 at 17:03
  • $\begingroup$ Yes, it would be good to have some sort of theory backing what I observe for this simple example but for more general cases. The plot does suggest the conjecture that, as long as the $x$-updates are convex, that ADMM will converge. Is this something that has been proved or is easy to prove? $\endgroup$ Commented Mar 31, 2018 at 17:10
  • $\begingroup$ Rahul, why do you say it is not sufficient? $\endgroup$ Commented Mar 31, 2018 at 17:13
  • $\begingroup$ Because it looks like there is one data point with $\rho$ slightly greater than 1 that has large error. Anyway, you should write @<username> if you want someone to be notified of your comment, just saying <username> doesn't work. $\endgroup$ Commented Apr 1, 2018 at 13:44

1 Answer 1

Reset to default
4
$\begingroup$

Here is an approach when the $f$ function is strongly convex with sufficiently large $c$: Let $f$ be $c$-strongly convex for $c>0$. Let $b>0$ be a parameter such that $g(x)+ (b/2)||x||^2$ is convex. Suppose that $c>b$.

Since $g(x) + (b/2)||x||^2$ is convex, it follows that $g(x) + (b/2)||x-v||^2$ is also convex for any constant vector $v$ (since the two functions differ by an affine function of $x$). Suppose we know how to do minimizations of the form $$\min_x \left[\underbrace{f(x)}_{\mbox{convex}} + \underbrace{g(x) + (b/2)||x-v||^2}_{\mbox{convex}}\right]$$ For example, suppose we can do this via some separation method. So then we can do this:

  • Step 1: Define $v[-1]$ as any point in the domain.

  • Step 2: For each $k \in \{0, 1, 2, ...\}$ find:

    $$ v[k] = \arg\min_x\left[f(x) + g(x) + (b/2)||x-v[k-1]||^2\right] $$

Claim:

If $c>b$, and if $x^*$ is a solution to $\min_x [f(x)+ g(x)]$, then $$ ||v[k]-x^*||^2 \leq (b/c)^k||v[-1]-x^*||^2 \quad, \forall k \in \{0, 1, 2, ...\} $$ and so error decays exponentially fast. The proof of this claim relies on this lemma:

Lemma (minimizing strongly convex functions):

If $h(x)$ is $c$-strongly convex and $x_{min}$ minimizes $h$, then for any point $y$ in the domain we have: $$ h(x_{min}) \leq h(y) - \underbrace{(c/2)||y-x_{min}||^2}_{\mbox{quadratic pushback}} $$

For a simple proof of this lemma, see, for example, Corollary 1 on page 5 here:

http://ee.usc.edu/stochastic-nets/docs/fast-convex-optimization-SIAM.pdf

Proof of claim:

At step $k \in \{0, 1, 2, ...\}$ we have that $v[k]$ is minimizes: $$\underbrace{f(x)}_{\mbox{$c$-strongly convex}} + \underbrace{g(x) + (b/2)||x-v[k-1]||^2}_{\mbox{convex}}$$ Since the sum of a $c$-strongly convex function and a convex function is $c$-strongly convex, we get by the lemma (using $y=x^*$ and $x_{min} = v[k]$): \begin{align} &f(v[k]) + g(v[k]) + (b/2)||v[k]-v[k-1]||^2 \\ &\leq f(x^*) + g(x^*) + (b/2)||x^*-v[k-1]||^2 - (c/2)||x^*-v[k]||^2 \end{align} However, since $x^*$ minimizes $f(x) + g(x)$ over the domain, and $v[k]$ is in the domain, we have: $$ f(v[k])+g(v[k]) \geq f(x^*) + g(x^*) $$ Substituting this into the previous inequality gives: $$ (b/2)||v[k]-v[k-1]||^2 \leq (b/2)||x^*-v[k-1]||^2 - (c/2)||x^*-v[k]||^2$$ Since $(b/2)||v[k]-v[k-1]||^2 \geq 0$, it follows that $$ ||x^*-v[k]||^2 \leq (b/c)||x^*-v[k-1]||^2$$ The above holds for all $k \in \{0, 1, 2, ...\}$ and the result follows. $\Box$

$\endgroup$
5
  • $\begingroup$ In your example $f(x)=x^2$ and $g(x) = -0.5(x-1)^2$, we have $f$ is $2$-strongly convex (so $c=2$) and $g$ has a $b$ parameter of $1$. So indeed $c>b$. $\endgroup$ Commented Mar 31, 2018 at 21:27
  • $\begingroup$ You can't divide $b$ by 2 and still claim the function is convex. Other than that, the proof checks out. $\endgroup$ Commented Mar 31, 2018 at 23:51
  • $\begingroup$ @LinAlg I started writing my answer with "$b$" and then changed to "$b/2$" to be compatible with the definition of strong convexity. Thanks for noticing there were still places to change "$b$" to "$b/2$", I think I've fixed those places now. $\endgroup$ Commented Apr 1, 2018 at 1:31
  • $\begingroup$ +1. Good work, namesake! $\endgroup$ Commented Apr 1, 2018 at 15:53
  • $\begingroup$ Another way in the case $f$ is $c$-strongly convex and $g$ is such that $g(x) + (b/2)||x||^2$ is convex, with $c \geq b$, is to define $r(x) = f(x) - (b/2)||x||^2$, $s(x) = g(x) + (b/2)||x||^2$, and note that $f(x) + g(x) = r(x) + s(x)$, where $r$ and $s$ are both convex. Then run a separation algorithm over $r(x) + s(x)$. If $c>b$ you can change the coefficient of $||x||^2$ to separate into a sum of two strongly convex functions. $\endgroup$ Commented Apr 2, 2018 at 16:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.