Convex objective that is the sum of non convex functions

Question

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)));

Answer 1

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$