MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
    
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).$$

share|cite|improve this answer
    
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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