tag:blogger.com,1999:blog-5382571416341492754.post8154157752037980003..comments2020-05-08T14:39:44.398-04:00Comments on Blogface.org: Question about function... optimization?Nelshttp://www.blogger.com/profile/07085287093689227850noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5382571416341492754.post-66890362261498693632010-02-06T13:25:19.000-05:002010-02-06T13:25:19.000-05:00Oh, this actually sounds easy. So f1 is a parabol...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."<br /><br />So f1 = ax^2 + bx + c. Easy enough.<br /><br />f2 = m12 * (x - \beta * (x1 + \alpha)) + y1 when x1 < x <= x2,<br /> m23 * (x - \beta * (x1 + \alpha)) + y2 when x2 < x <= x3,<br /> etc.<br /><br />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.<br /><br />I think the above description is right, although it might have bugs. Probably worth graphing a few versions and seeing if it's right.<br /><br />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.<br /><br />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 :).<br /><br />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.lordspaznoreply@blogger.comtag:blogger.com,1999:blog-5382571416341492754.post-85564344668982994852010-02-06T13:19:24.000-05:002010-02-06T13:19:24.000-05:00Now that you reminded me, definitely a SIGBOVIK su...Now that you reminded me, definitely a SIGBOVIK submission!nolacoasternoreply@blogger.comtag:blogger.com,1999:blog-5382571416341492754.post-34596831909970291992010-02-06T12:18:20.000-05:002010-02-06T12:18:20.000-05:00Okay, awesome! So let's see:
f_1 is easy. It&...Okay, awesome! So let's see:<br /><br />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:<br />http://www.freemathhelp.com/images/lessons/graph14.gif<br />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...<br /><br />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. <br /><br />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.<br /><br />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)).<br /><br />Hopefully this makes a little more sense. If not, I can draw a picture! Thanks!nolacoasternoreply@blogger.comtag:blogger.com,1999:blog-5382571416341492754.post-3387234082273814972010-02-06T00:19:22.000-05:002010-02-06T00:19:22.000-05:00I actually know a decent amount about optimization...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?<br /><br />This sounds like a convex optimization problem, in general, but I don't know enough to be sure. Convex optimization problems are "easy."lordspaznoreply@blogger.comtag:blogger.com,1999:blog-5382571416341492754.post-83048345432579765302010-02-05T17:33:09.000-05:002010-02-05T17:33:09.000-05:00SIGBOVIK surprise or I'm-totally-gonna-get-bes...SIGBOVIK surprise or I'm-totally-gonna-get-best-OOPSLA-paper surprise or I AM YOUR NEW ROBOT OVERLORD surprise?<br /><br />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.simrobnoreply@blogger.com