# Non Smooth Convex Optimization

I want to solve an optimization of the form $$\underset{x}{\min}f(x) + g(x),$$ where $$f(x)$$ is $$\mu$$-strongly convex and differentiable with a Lipschitz continuous gradient (with Lipschitz constant $$L$$), whereas $$g(x)$$ is convex, continuous, and $$M$$-Lipschitz, but not differentiable. I am using sub-gradient update of the form $$x_{k+1}=x_k-\alpha_k(\nabla f(x_k) + z_k),$$ where $$z_k\in \partial g(x_k)$$, and $$\left\|z_k\right\|\leq M$$ for all $$k$$. In my case, I cannot compute the proximal operator for $$g$$. What kind of convergence guarantees and convergence rates can be shown for this problem?

• Given that the nonsmooth $g(x)$ can be arbitrarily larger in magnitude than the smooth $f(x)$, you really can't expect to do any better than you could with subgradient descent on a non-smooth convex function for which the results are well known. Smoothing approaches might be applicable depending on $g(x)$. Oct 2, 2019 at 21:55

If you have an upper estimate for the minimal value of $$f+g$$ you could use a subgradient projection algorithm (e.g. section 29.6, Bauschke & Combettes' 2017 book). Suppose $$C = \{x\ | \ f(x) + g(x) \leq \xi\} \neq \varnothing$$ for some estimate $$\xi \in \mathbb{R}$$. Let $$s(x)$$ be any selection of $$\partial(f+g)$$. For instance, you could iterate $$x_{n+1} = \begin{cases} x_n + \frac{\xi - (f(x_n) + g(x_n))}{\|s(x_n)\|^2}s(x_n) &\mbox{if }f(x_n)+g(x_n) > \xi\\ x_n, &\mbox{otherwise.} \end{cases}$$

This algorithm guarantees weak convergence to a point in $$C$$ with your hypotheses.

BTW, this setup would be perfect for Douglas Rachford splitting if you had a reasonable way to approximate $$\text{prox}_g$$. Douglas-Rachford also has nice convergence guarantees.