Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\DeclareMathOperator*{\argmin}{arg\,min}$ Suppose I have to jointly minimize two functions. The solution to the joint minimization does not necessarily minimize each function individually but sort of best one can get for both cases together.

e.g., $\argmin_p f(t; p)$ and $\argmin_p g(t; p)$ could be two minimization problems. Suppose though I am looking for a $p$ that minimizes them "jointly".

This seems to be rather vague though? Is there any way to make this more exact? e.g., what could "joint minimization" or "simultaneous minimization" mean? Remember, the goal is to find a p that sort of minimizes both individually but it might not work perfectly for each individual case.


The joint minimization should minimize each individual minimization problem "well".

Suppose $\min_p J(f(t; p), g(t;p))$ is the joint minimization with solution p and $\min_p f(t; p)$ and $\min_p g(t; p)$ have solutions $p1$ and $p2$ respectively.

Then we would want $p$ to be close to $p1$ and $p2$ in some sense. Obviously is it were equal then it will would have solved each individual minimization problem. This doesn't necessarily work well though as maybe there is another solution $p^*$ that is almost a solution to the joint problem BUT provides better results to each individual solution.

That is, I don't think joint minimization says much about how it's solution minimizes the individual problems. (maybe it would be way off)

for example, suppose $f(t) = t^2$ and $g(t) = 1/t^2$ then the joint distribution $|fg| = 1$ has the whole real line the solution. Which, if we were using numerical methods, maybe end up with t = 10^10 for a solution. But $10^10$ is a really bad solution for the minimization problem on $f$ while it is ok for g.

Therefor, there seems to be some other criteria that needs to be added to get a better overall solution. Something like:

$$\argmin_{p1} f(t; p1)$$ $$\argmin_{p2} g(t; p2)$$ $$\argmin_p J(f(t; p), g(t;p))$$ $$\min_{p^*} |p1 - p| + |p2 - p|$$

The above is a bit sloppy but the idea is that we make sure our solutions to the individual problems are "close" to the joint problem if possible). This, at the very least prevents joint problems of the from $|fg|$.

share|improve this question
1  
If there were an easy answer to that the world would be in a better state. It's all about "trade-off". –  Christian Blatter Sep 27 '12 at 8:03
    
@ChristianBlatter The issue is not so much about which is best but which will absolutely not work. Some interpretations of "joint minimization" simply make know sense and others seem to be preferred for a more general, unbiased case. The whole point of a joint minimization, I believe, is to minimize the individual cases well but leaving "wiggle" room. But the the solution will be worthless if the "wiggle" room is too great since it's solution will not work at all for the individual cases. Therefore, it seems having such an interpretation would limit possible choices for a joint function. –  AbstractDissonance Sep 27 '12 at 8:39
add comment

1 Answer

There are many ways to make it more exact. However, there are many different ways to make it more exact, and they lead to different answers, and there is no abstract sense in which one of these answers is better than the others.

So, some examples: you could try to minimize $f^2+g^2$ (this is very popular, under the name, "least squares", or "ell-two norm"), or you could try to minimize $|f+g|$, or more generally $\root q\of{f^q+g^q}$ for some chosen number $q$, $1\le q\lt\infty$; you could try to minimize $\max(f,g)$, or $\sqrt{|fg|}$, or the harmonic mean $2fg/(f+g)$. Each of these has its uses. You have to decide which one gives results the closest to what you are trying to get.

The ones I've given have been symmetric in $f$ and $g$. In case it's more important to minimize one than the other, there are weighted versions of all of these, like minimizing $f^2+17g^2$, or $|39f+g|$, and so on, and so forth.

EDIT: Let's look at an example. Let $f(x)=|x|$, $g(x)=|4-2x|$, and try to jointly minimize on $[0,2]$. Here are some candidates: $$\matrix{x&f(x)&g(x)&\max&f^2+g^2&f+g&{\rm features}\cr4/3&4/3&4/3&1.33&3.56&2.67&{\rm minimizes\ maximum}\cr8/5&8/5&4/5&1.6&3.2&2.4&{\rm minimizes\ }f^2+g^2\cr2&2&0&2&4&2&{\rm minimizes\ }f+g\cr}$$

share|improve this answer
    
It seems, though, in some cases, it does not work well though: $\sqrt{|fg|}$ could allow for any possible h which gives f(h) = 0 but g(h) is $\infty$... which is obviously not minimizing g alone. I agree there are many different possible results but which ones can be proved to also minimize the individual minimization problems "well". e.g., maybe "$|f(h1) - f(h) + (g(h2) - g(h))|$" is small... would would then exclude $\sqrt{|fg|}$. (h1 and h2 would be the optimal solutions for the individual equations). Hopefully this makes some sense. –  AbstractDissonance Sep 27 '12 at 6:28
    
It depends a bit on what you know about $f$ and $g$. You can rectify the problem with $\sqrt{|fg|}$ by modifying it to $\sqrt{1+|fg|}$. "proved to also minimize the individual minimization problems well" is precisely the thing you can't do until you have decided what you desire from a solution. Most of the formulas I've given won't be small unless both functions are small. –  Gerry Myerson Sep 27 '12 at 7:08
    
I think you mean something like $(1 + |f|)(1 + |g|)$ as the case still occurs with $1 + |fg|$. The issue comes from multiplication by 0 as 0 times anything is still 0. When I was looking into this I first thought of using the additive case f + g with f and g >= 0 but decided to use $|1 + f||1 + g|$ but I can't recall what the problem with addition was. I also "absorb" the weighting into the functions so $f^2 + a g^2 \equiv f^2 + g^2$. What would be nice to have is a joint function that can be proven to minimize the individual cases the best(if one exists) as that is what I'm looking for. –  AbstractDissonance Sep 27 '12 at 8:43
    
You keep talking about minimizing the individual cases, and I keep telling you it can't be done, at least not until you can figure out with mathematical precision what you mean by that phrase. Maybe this will help you organize your thoughts: would you rather have 10 and 10, or 9 and 20? 10 and 10, or 1 and 11? For what values of $x$, if any, is 10 and 10 better than 5 and x? Once you can answer that kind of question --- and only once you can answer that kind of question --- then you can begin to talk about "proving" things. Until then, it's babble. –  Gerry Myerson Sep 27 '12 at 10:34
    
No, You must be misunderstanding me. It is obvious the individual cases can be minimized as they are individual problems and they both have solutions. Surely you get that. argmin f(x) and argmin g(x) both have solutions(in general)... but are not related in any way. Now if we have some sort of joint minimization problem AND WE WANT for it also to try and do it's best to solve the individual problems THEN some functional forms are better than others. Your your to get across to me that there are many possible definitions of the joint minimization by itself. I know that. –  AbstractDissonance Sep 27 '12 at 11:36
show 9 more comments

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.