# Is it possible to solve the argument maximization problem $\arg\max_x \langle x,l \rangle −f_1(x)−f_2(x)$ via convex duality?

I am attempting to solve the argument maximization problem

$$\arg\sup_x \{ \langle x,l \rangle − f_1(x)−f_2(x) \} \ \ \ \ \ \ \ \ \ \ (1)$$

where the functions $f_1$ and $f_2$ are concave but difficult to evaluate but their convex conjugates $f^∗_1$ and $f^∗_2$ are easy to evaluate. We can further assume that $f^∗_1$ and $f^∗_2$ are differentiable and that we can evaluate their gradients. Since the sum operation is dual to the infimal convolution (or epi-sum) operation

$$(g\#h)(x) = \inf_w \{ g(x−w) + h(w) \}$$

the standard maximization problem is easy to compute by duality using the identity

$$\sup_x\{⟨x,l⟩−f_1(x)−f_2(x)\}=\inf_w \ \{ f^*_1(l−w) + f^∗_2(w) \}.$$

Is it possible to compute the solution to problem $(1)$ is an analogous manner, making only calls to the conjugate functions $f^∗_1$ and $f^∗_2$ or their gradients?

-
Might not be always possible / easy. Are your f's differentiable? – Suvrit Nov 18 '11 at 10:20
Do you have access to the (sub)gradients of $f_1^*$ and $f_2^*$ ? – F_G Nov 18 '11 at 12:50
Good question. We can assume that $f^∗_1$ and $f^∗_2$ are differentiable and that we can evaluate their gradients. I have edited my question accordingly. – John Maidens Nov 18 '11 at 23:12

there is a clean answer for your question the trick is that $x(x^*)=\nabla f^*(x^*)$ ! where $x^*$ is the conjugate variable. this trick help you to write your problem as $$arg \sup_x\{⟨x,l⟩−f_1(x)−f_2(x)\}=\nabla_{l} (g\#h).$$

-
Thanks Behrad. This in indeed a useful trick, but what was not clear (at least to me) is whether the gradient of g#h can be computed in terms of the (sub)gradients of g and h. It turns out that it can. I will post the solution below. – John Maidens Dec 2 '15 at 21:23

I ultimately did find a solution to this problem. First, you compute the solution $\bar{w}$ to

$$\bar{w} \in \arg\inf_w f^*_1(\ell - w) + f_2^*(w).$$

A solution $\bar{x}$ to (1) can then be computed by choosing

$$\bar{x} \in \partial f_1^*(\ell-\bar{w}) \cap \partial f_2^*(\bar{w})$$

where $\partial f$ denotes the subgradient of $f$. A proof of this fact appears as part of Theorem 15 in this JMLR paper:

http://jmlr.org/papers/volume8/rifkin07a/rifkin07a.pdf

-