# Technique for maximising the product/sum of multiple single variable functions given a linear constraint (general problem)

Today we used a techique in our optimisation class for which I am wondering if it can be generalised. In our case we had three functions and wanted to maximise their sum. The problem looked like this: Maximise the function $$2x_1^2 + 2x_2 + 4x_3 - x_3^2$$ given the contraints $$2x_1 + x_2 + x_3 \leq 4$$ $$x_1 \ge 0, x_2 \ge 0, x_3 \ge 0.$$

We contructed a recursive method for solving the problem. Let $$f_2(x) = 2x$$, so we identify $$f_2(x)$$ with the $$x_2$$ portion of our multivariable function. We the let $$f_1(x) = max(2y^2 + f_2(x-2y) \mid 0 \le y \le \frac{x}{2})$$. And finally we let $$f_3(x) = max(f_1(x-z) + 4z-z^2 \mid 0 \le z \le x)$$. The optimum is achieved at $$f_3(4)$$. First we calculate the function $$f_1(x) = 2x$$ and finally we calculate the optimum of our function $$f_3(x) = max(2(x-z) + 4z-z^2 \mid 0 \le z \le x)$$ by taking its derivative. We find the optimum at $$z = 1$$ and finally get the values $$x_1 = 0, x_2 = 3, x_3 = 1$$.

Suppose we have $$n$$ functions $$f_1(x_1), f_2(x_2)...f_n(x_n) \in C^1(\mathbb{R})$$. Given a linear constraint in the form of $$a_1x_1 + a_2x_2 + ... +a_nx_n \leq b$$ where $$a_1, a_2, ...a_n, b \in \mathbb{R}$$ we want to maximise/minimise either the product $$f_1(x_1) f_2(x_2)\cdots f_n(x_n)$$ or the sum $$f_1(x_1)+f_2(x_2)+... +f_n(x_n)$$. My question is: Can we use the same technique for solving this more genereal version of the problem, if so, why? If not, what would some additional constraints be?

• Sorry there was a typo, the answer was indeed x = (0, 3, 1). Apr 14, 2023 at 5:38

The problem of optimizing a quadratic function subject to linear constraints is called quadratic programming. Your example with a separable quadratic function of nonnegative variables and a single linear constraint with positive coefficients can be solved via dynamic programming. So can your generalization to optimization of a separable function. When the variables are required to take integer variables, this is known as a knapsack problem, with the most common variant using linear functions $$f_i$$.