8
$\begingroup$

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?

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

2 Answers 2

2
$\begingroup$

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).$$

$\endgroup$
1
  • $\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$
    – JNM
    Dec 2, 2015 at 21:23
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.