Allocation optimization problem

Question

Imagine that I have $1$ million dollars which I want to invest. I have a set of $N$ elements in which I can put the money and obtain a revenue. Each element has a function that determines how much money I have earn based on the invested money on that item.

For example: if I put $\$1000$, I get $\$1200$, if I put $\$2000$, I get $\$3000$.

With more money, there is always more return. Each element has its own different function.

So the question is what algorithm/strategy can I use to allocate the money in order to find the best return of investment?

Answer 1

Formally, indicating with $f_i$ the return function for the element $i \in N$, with $x_i$ the quantity allocated to $i$, and with $C$ your capital (i.e. 1 million) you have to solve the following problem:

$$\max \sum_{i=1}^N f_i(x_i) \;\;s.t.$$

$$\sum_{i=1}^N x_i = C$$

If you know the $f_i$ then you can try to use the Lagrange multipliers method (http://en.wikipedia.org/wiki/Lagrange_multiplier).

If otherwise the $f_i$ are unknown analytically (for example, the return is given by the result of a simulation), then you may look for heuristics (i.e. genetic algorithms, simulated annealing, or some kind of descent algorithms).

Answer 2

Simplex algorithm

http://en.wikipedia.org/wiki/Simplex_algorithm

assuming if all the functions that define the return on each investment are linear because

the result return on investment will be defined by these functions.

If they are non-linear there is whole host of other methods in Non-linear optimization

and the method you pick for non-linear programming depends on the type of return on investment function and there are lots of different methods.