Define function $f^i := h^i - g^i$ where $f^i$, $g^i$ are real valued convex functions for all $i = 1, ..., 10$.

Does there exist real valued convex functions $h$, $g$ where $h - g = \max_{i} f^i$?

I don't even know how to even approach this problem.


Yes, the class of DC functions (difference-convex, or delta-convex as they are sometimes called) is a lattice: it's closed under taking pointwise max or min. It suffices to show that for any two DC functions $f_1, f_2$ their maximum $\max(f_1, f_2)$ is also DC.

Note that $\max(f_1, f_2) = \frac12|f_1+f_2| + \frac12|f_1-f_2|$, where both $f_1 \pm f_2 $ are DC. Thus, it suffices to show that the absolute value of a DC function is DC.

If $f$ is DC, then from $f = h-g$ we get $\max(f, 0) = \max(h, g) - g$, hence $\max(f, 0)$ is also DC.

And then $|f| = \max(f, 0) + \max(-f, 0)$ is DC as well.

This proof, and much more, can be found in On difference convexity of locally Lipschitz functions by Miroslav Bačak and Jonathan M. Borwein.

  • $\begingroup$ Is it possible, in general, to determine $h$ and $g$ based on all the $h^i$ and $g^i$? $\endgroup$ – master_goon Jul 23 '18 at 21:58
  • $\begingroup$ Yes, by following the steps given above. It's all constructive. Of course, $h, g$ are not uniquely determined: one can add any convex function to both of them. $\endgroup$ – user357151 Jul 23 '18 at 22:19

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.