4
$\begingroup$

$\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 form $|fg|$.

  • 1
    If there were an easy answer to that the world would be in a better state. It's all about "trade-off".2012-09-27
  • 0
    @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.2012-09-27

1 Answers 1

2

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}$$

  • 0
    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.2012-09-27
  • 0
    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.2012-09-27
  • 0
    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.2012-09-27
  • 0
    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.2012-09-27
  • 0
    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.2012-09-27
  • 0
    But I'm trying to find joint minimization forms that produce good results for the individual cases. I've already point out that there are joint minimization problems that do not do this necessarily do this. HENCE, if not all joint minimization problems produce good individual results THEN that means some are better. Simple as that. I'm looking for some way to quantify what this behavior. E.g., you say x, y, and z are possible functional forms for joint minimization and I say: "z is not good to also produce good individual minimization results"... and you say "it's impossible to find one".2012-09-27
  • 0
    YET, since z is much worse than x and y(say) THIS means there is some ordering that exists. It may not be well defined to some degree but in this case z < x and z < y. I've already pointed out that I want a joint minimization problem WHO's solution tries to minimize the individual minimization problems well. You've given a number of functional forms to represent the joint minimization as I have proven, some do a better job than others. Do you have any clue as to how to compare these functional forms to determine which ones do better a better job?2012-09-27
  • 0
    (BTW, x and y may not be comparable which is what you think your trying to get me to understand BUT z and x and z and y definitely are which is what I'm trying to get you to understand)2012-09-27
  • 0
    One more try. Suppose $f(p_1)=10$ and $g(p_1)=10$, while $f(p_2)=9$ and $g(p_2)=20$. Do you want $p_1$, or $p_2$? Suppose $f(p_3)=1$ and $g(p_3)=11$. Do you want $p_1$, or $p_3$? Suppose $f(p_4)=5$, and $g(p_4)=c$. How small does $c$ have to be before you decide that $p_4$ is better than $p_1$? You cannot determine which forms do better until you can explain what, precisely, "better" means to you.2012-09-27
  • 0
    Again, your missing the point. SOME FORMS DO NOT WORK AT ALL! If that is the case, which it is as $|fg|$ proves this, then this means there are AT LEAST forms that are better than others. It may mean that there is a spectrum from good to bad. The whole point of the post was to find about how the "forms" fit into this "spectrum". Your getting hung up on trying to prove something equivalent that a saddle point doesn't have an extrema and missing the point that I'm trying to quantify the relationship between points near the saddle point and those that aren't.2012-09-27
  • 0
    Just because some forms are not much different than others when it comes to the joint optimization problem does not prove that all forms are not much different. Again, I've already pointed out that $|fg|$ from your list of examples is bad and one case(and there are an infinite number). You need to look at the big picture and take the set of all "forms" and realize that some are truly "bad"... and I'm asking if there is a general way to "group" the good, bad, and ugly. (not necessarily a total order but a partial order)2012-09-27
  • 0
    There is no way to group them into good/bad/ugly until you have given a precise mathematical specification to those terms. If you don't know what you want, you can't tell whether you have it.2012-09-27
  • 0
    Well,I have mentioned what I mean plenty of times. Ugly came from the |fg| example. Bad came from the "closeness" to the individual problems. You want me to give you exact meaning but I'm the one that asked the question. Essentially what it boils down to is categorization and I have categorized them informally... not much more I can do, else I wouldn't be asking the questions. It should be rather intuitive to you, though, that there is some partial ordering that exists.2012-09-28
  • 0
    Have you had a look at the examples I added to my answer?2012-09-28