Friday, February 5, 2010

Question about function... optimization?

Computer science people, I am looking to be pointed in the right direction. I am looking for a solution to a problem, and I think the answer might lie in an area of Computer Science/Statistics/O.R. that I know very little about. Here's the deal:

I have two mathematical functions, f_1 and f_2. Both functions intersect with the Y axis at exactly two points (and basically what happens below the Y axis can be ignored). f_1 is fixed; it's input. But f_2 is defined in terms of two parameters that I can tweak. Here's what I am trying to answer:

How can I pick the two parameters of f_2 so that the area under f_2 is as large as possible and yet still contained entirely within the area under f_1? 

I have come up with sort of a brute-force algorithm that I think will solve the problem, but if there's a 'best' or well-known way to solve this class of problems I'd like to learn more about it. I have heard about topics like 'function optimization.' Is this relevant? Also, because what I am doing is sort of a surprise, I'd like to hide most of the details, but I can give more if that will help the quality of your responses.

5 comments:

  1. SIGBOVIK surprise or I'm-totally-gonna-get-best-OOPSLA-paper surprise or I AM YOUR NEW ROBOT OVERLORD surprise?

    I don't have any idea, beyond vague notions like hill-climbing that only work if there aren't a lot of global maximums. If you want me to explain my vague notions on what hill-climbing does I can.

    ReplyDelete
  2. I actually know a decent amount about optimization, but I think I need more details about your problem to do anything with this. Do you mean "intersect the x axis at two points"? Is f_2 continuous, and does it have a closed form? How is f_2 specified, if not?

    This sounds like a convex optimization problem, in general, but I don't know enough to be sure. Convex optimization problems are "easy."

    ReplyDelete
  3. Okay, awesome! So let's see:

    f_1 is easy. It's just a quadratic equation. When I say it intersects the x-axis in two points, I mean that it looks like the quadratic equation in this image:
    http://www.freemathhelp.com/images/lessons/graph14.gif
    and I really don't care what happens to it below y=0. In fact, I'll assume x=0 whenever y<=0. So I am just trying to say that it creates an enclosed area above the x axis. Maybe that doesn't matter...

    f_2 is more interesting. It's actually defined in terms of a bunch a samples. For various x values I have sampled y values. For each of these samples, x>=0 and y>=0. Even though the function data comes from samples, I have it figured out so that you can ask for any x. If an x is in between two sample values, I do a linear estimate from the slope of the two adjacent samples. Above and below my samples in x, y is always 0. Hopefully you're with me so far.

    Last but not least, there are two parameters of f_2 that I can tweak, even though f_2 is defined in terms of samples. One parameter is an x offset. I can shift the entire function left or right arbitrarily. The second parameter is a little harder to describe, but it's basically a stretch operation in the x axis. I can grow or shrink the distance between each of the samples uniformly.

    Again, the problem is to select the shift and x-stretch for f_2 so that the area under f_2 is maximized without escaping the area of f_1. My memory of calculus tells me I want to minimize (integral(f_1) - integral(f_2)).

    Hopefully this makes a little more sense. If not, I can draw a picture! Thanks!

    ReplyDelete
  4. Now that you reminded me, definitely a SIGBOVIK submission!

    ReplyDelete
  5. Oh, this actually sounds easy. So f1 is a parabola. f2 is a piecewise linear function of 3 variables. But the 3 variables are of two different kinds - x and the shift/scaling factors. I'll call the last two "parameters."

    So f1 = ax^2 + bx + c. Easy enough.

    f2 = m12 * (x - \beta * (x1 + \alpha)) + y1 when x1 < x <= x2,
    m23 * (x - \beta * (x1 + \alpha)) + y2 when x2 < x <= x3,
    etc.

    where (x1, y1) is the first sample, etc. and m12 is the slope between samples 1 and 2 (y2 - y1)/(x2 - x1). \alpha is your horizontal shift factor, and \beta is your horizontal scaling factor.

    I think the above description is right, although it might have bugs. Probably worth graphing a few versions and seeing if it's right.

    What you actually want is integral(f_1 - f_2)dx. The distinction is pretty important - you want the xs to line up right. Then you'll have to differentiate wrt alpha and beta. Then find critical points (where both derivatives are zero), then check the determinant of the Hessian for concavity. That should give you all the maximums.

    I think that's easy enough to do in Mathematica (probably like an hour or so of tweaking). But it's all regular calculus stuff. But if you're going to use Mathematica anyways, I think it has a max function :).

    It's been awhile since I've done any of this, so I'd check what I said (and your results) for sanity. I also haven't used Mathematica in awhile either.

    ReplyDelete