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?

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

2 Answers 2

Reset to default
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).$$

Improve this answer
$\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
    Commented 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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .