Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.