Search code examples
algorithmoptimizationmax

Maximum the result from multiple functions which share an input amount

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!

Solution

  • 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.