# Allocation optimization problem

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?

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

• Thanks! In my case, the functions are well-known. They are pre-defined curves. So i think Lagrange multipliers could work. I'll take a look at them now. Thanks! – Herno Sep 22 '13 at 15:32
• I'd like to ask a small question. What would happen if for example, each "return of investment" function also depends on the quantity allocated in other elements. Example: i put 100 in element A and 30 in element B. The function that calculates the return value in B depends in the allocated 30. But now it also must take into account the $100 that i placed in A. Can this problem be solved with Lagrange too? Thanks – Herno Sep 23 '13 at 2:09 • I think so, in this case the$f_i$will be multi-dimensional functions$f_i(x_1, x_2,\dots,x_i,\dots,x_N)$. For example, with two items the function$f_1$can be like$\alpha\cdot x_1 - \beta \cdot x_2$where$\alpha$and$\beta$are suitable coefficients. Similarly for$f_2\$. – Libra Sep 23 '13 at 11:26
• Last one. Could i add maximum and minimum allocation for each element? Does Lagrange support this? – Herno Sep 23 '13 at 17:56
• Yes, I think so, they are just constraints :-) – Libra Sep 26 '13 at 18:27

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.

• Yes simplex would work perfectly if the functions were linear, but in this case the Functions are curves. I really don't know a method for such optimization. Thanks for the answer! – Herno Sep 22 '13 at 15:29
• as i said we need to know what are those functions so we can formulate a final function for return on investment. As you might expect in Non-linear optimization there are lots of restrictions on what method you can use based on the conditions of function . MATLAB is the best one to use it by hand. – MRK Sep 22 '13 at 15:32
• We can assume the the functions are random curves. They are curves, but not a specific one like a logaritmic curve. Let's say you start with a set of N random functions with different beahviour, but they are rolled only once. Is it possible to optimize a set of random functions? – Herno May 29 '14 at 0:50