0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .