0

Suppose we have a $\alpha$-strongly convex function $f(x)$; and another function $g(x)$ with $L$-Lipschitz continuous gradient; and $\alpha>L$.

Is it true that $g(x)+f(x)$ is $(\alpha-L)$-strongly convex?

Similarly, is it true that $g(x)-f(x)$ is $(\alpha-L)$-strongly concave?

Any good references would be greatly appreciated, thanks!

Rodrigo de Azevedo
  • 1
Zang San
  • 61
  • 3

1 Answers1

0

Note that since $g$ has an $L$-Lipschitz gradient, we have that $\frac{L}{2}x^Tx-g(x)$ is convex. (Check this by showing that the gradient of $h(x)=\frac{L}{2}x^Tx-g(x)$ is monotone, i.e. $\langle h(x)-h(y),x-y\rangle \geq 0 \ \forall x,y$). In particular, since $\nabla (-g)=-\nabla g$ which is also Lipschitz, $\frac{L}{2}x^Tx+g(x)$ is also convex. Thus $$ f(x)+g(x)-\frac{\alpha-L}{2}x^Tx=f(x)-\frac{\alpha}{2}x^Tx+\frac{L}{2}x^Tx+g(x) $$ is a sum of convex functions and therefore convex, so $f+g$ is indeed $\alpha-L$ strongly convex.

Similarly, we have $$ g(x)-f(x)+\frac{\alpha-L}{2}x^Tx=-(\frac{L}{2}x^Tx-g(x)+f(x)-\frac{\alpha}{2}x^Tx) $$ We know that $\frac{L}{2}x^Tx-g(x)+f(x)-\frac{\alpha}{2}x^Tx$ is convex as a sum of convex functions, so that $-(\frac{L}{2}x^Tx-g(x)+f(x)-\frac{\alpha}{2}x^Tx)$ is concave, and hence $g-f$ is $\alpha-L$ strongly concave.

Paul Gullesh
  • 786
  • thank you so much! I was wondering if would there be any references for the results. I have searched several books, but they seem all consider properties of one function f(x) instead of summation of two functions with some properties respectively. – Zang San May 28 '23 at 15:10
  • I am not aware of a reference that deals explicitly with sums of convex functions. A good introduction to convex analysis can be found for instance in these notes. – Paul Gullesh May 28 '23 at 19:21
  • okay. thank you again for your kind help! – Zang San May 29 '23 at 00:32