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?

  • $\begingroup$ Might not be always possible / easy. Are your f's differentiable? $\endgroup$ – Suvrit Nov 18 '11 at 10:20
  • $\begingroup$ Do you have access to the (sub)gradients of $f_1^*$ and $f_2^*$ ? $\endgroup$ – F_G Nov 18 '11 at 12:50
  • $\begingroup$ 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. $\endgroup$ – 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).$$

  • $\begingroup$ 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. $\endgroup$ – 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:



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.