Home > Back-end >  Maximum the result from multiple functions which share an input amount
Maximum the result from multiple functions which share an input amount

Time:10-21

enter image description here

I have multiple functions as shown in the image. For a fixed x value, I need to distribute it into f, g, and h functions for getting the maximum output (y). In other words, having a fixed x value, find a, b, and c in which these conditions are satisfied:

  1. a b c = x
  2. a >= 0 and b >= 0 and c >= 0
  3. f(a) g(b) h(c) has max value.

Given the functions are continuous and monotonic. How should I write code to find out a, b, and c? Thanks in advance!

CodePudding user response:

Under appropriate assumptions, if the maximum has a > 0 and b > 0 and c > 0, then a necessary condition is f'(a) = g'(b) = h'(c). Intuitively, if one of these derivatives was greater than the others, then we could effect an improvement by increasing the corresponding variable a little bit and decreasing another variable by the same amount. Otherwise, the maximum has a = 0 or b = 0 or c = 0, and we have a lower dimensional problem of the same type.

The algorithm is to loop over all seven possibilities for whether a, b, c are zero (assuming x > 0 to avoid the trivial case), then solve the equations a b c = x and f'(a) = g'(b) = h'(c) (omitting the variables that are zero) to find the candidate solutions, then return the maximum.

CodePudding user response:

Even if you only had 2 functions f and g, you would be looking for the x that maximises the maximum of a :-> f(a) g(x-a) on [0,x], which is a sum of an increasing and a decreasing function, so you can't have any guarantee about it.

Still if these functions are given to you as closed form expressions, you can compute u(a)=f(a) g(x-a) and try to find the maximum (under sufficient assumptions, you will have u'(a) = 0 and u''(a) <= 0 for instance).

Going back to the 3 functions case, if it's possible you can compute for every a, v(a) = max_{b in [0, x-a]} ( g(b) h(x-a-b) ), and then compute the max of (f v)(a), or do with b or c first if it works better, but in the general case there is no efficient algorithm.

  • Related