Choose $w_1,w_2, \dots, w_n$ such that $f_1(w_1x) + f_2(w_2x) + \dots + f_n(w_nx)$ is maximized

Question

I have a real world portfolio optimization problem here where I have problem finding the right approximation algorithm to tackle.

Choose $w_1,w_2, \dots, w_n$ (weights) such that

$f_1(w_1x) + f_2(w_2x) + \dots + f_n(w_nx)$ is maximized

where each function $f_1, f_2, \dots, f_n$ is an increasing concave function (that represents returns), $x$ is a constant and $w_1 + w_2 + \dots + w_n = 1$ and each $w_i \geq 0$.

Does anyone have any idea which is the right step I should take to do more research?

As a side note, functions $f_1, f_2, \dots, f_n$ can be queried with near 0 latency.

Answer 1

Assuming $x\gt 0$ and calling $u_k = x w_k$ we have analogously the problem

$$ \max_{u}\sum_k f_k(u_k)\ \ \ \text{s. t.}\ \ \ \cases{\sum_{k}u_k = x\\ u_k \ge 0} $$

This problem can be easily numerically solved with the use of dynamic programming (Richard Bellman)

Calling $F(u_1,u_2,\cdots, u_n) = \sum_k f_k(u_k)$ and $\phi_n(x) = \max_{u}F(u_1,u_2,\cdots, u_n)$ we have the recurrence relation

$$ \phi_n(x) = \max_{0\le u\le x}\left(f_n(u)+\phi_{n-1}(x-u)\right),\ \ \ \phi_1(x) = f_1(x) $$

NOTE

A detailed algorithm to implement this procedure can be found in

Applied Dynamic Programming

by Richard Bellman and Stuart E. Dreyfus

Princeton University Press Princeton, New Jersey

ISBN 0-691-07913-7

In the 1962 edition the flow-chart is located between pages 21 to 26. Follows a script in python which implements the flow-chart.

"""
@author: Cesareo
"""
import numpy as np
import matplotlib.pyplot as plt


rhomin  = 0
rhomax  = 10
infty   = 1000000000
nstages = 3
xmax    = 30
phi_0   = xmax*[0]
phi_1   = xmax*[0]
indu    = xmax*[0]
VOID    = -1

np.random.seed(7)
k0 = []
rho = []
npts = 2

for j in range(nstages):
    k0.append(sorted(list(np.random.uniform(0,xmax,npts))))
    rho.append(list(np.random.uniform(rhomin,rhomax,npts)))


def f(i,j):
    x = j
    k0i = k0[i]
    rhoi = rho[i]
    for u in range(npts):
        if x <= k0i[u]:
            return rhoi[u]
    return rhoi[npts-1]


tt = list(np.linspace(0, xmax-1, xmax))
ff = xmax*[0]

for j in range(nstages):
    for i in range(xmax):
        ff[i] = f(j,i)        
    plt.plot(tt,ff)

plt.ylabel('functions')
plt.show()


indux = []
iu = VOID
for s in range(nstages):
    indu = xmax*[0]
    for x in range(1, xmax):
        beta = -infty
        for u in range(x):
            alpha = f(s,u) + phi_0[x - u]
            if alpha >= beta:
                beta = alpha
                iu = u
        phi_1[x] = beta
        indu[x] = iu
    indux.append(indu)
    for j in range(xmax):
        phi_0[j] = phi_1[j]
    
beta = -infty
for i in range(xmax):
    if phi_1[i] > beta:
        beta = phi_1[i]
        u0 = i

remain = xmax
tot = u0
sol = []
valtot = 0
for i in range(nstages):
    val = f(nstages-i-1,u0)
    valtot += val
    sol.append([u0, val])
    remain -= u0
    u0 = indux[nstages-i-2][remain]
    tot += u0

plt.plot(tt,phi_1)
plt.ylabel('phi_n(x)')
plt.show()

tot = 0
for j in range(nstages):
    for i in range(xmax):
        ff[i] = f(j,i)        
    plt.plot(tt,ff)
    (u0, val) = sol[nstages-j-1]
    tot += val
    xx = [u0, u0]
    yy = [0, val]
    plt.plot(xx, yy, 'k:')

plt.ylabel('solution')
plt.show()

print('solution')
tot = 0
for i in range(nstages):
    (x, val) = sol[nstages-i-1]
    tot += val
    print([nstages-i-1, x, val])
print('--------------------------')
print(tot)

Answer 2

We'll assume functions $f_i$ have continuous derivatives.
Then, the $f_i$ being concave, each derivative $f'_i$ is a decreasing function.

Let's show that the maximum of $F(w) = \sum_{i=1}^n f_i(w_ix)$ exists and is attained for $w^*$ such that:

• all $w^*_i \ne 0$ or $1$ verify $f'_i(w^*_ix) = C$, constant;
• if $w^*_i = 0$, $f'_i(w^*_ix) \le C$;
• if $w^*_i=1, \forall j \ne i, w^*_j = 0$ and $f'_j(w^*_jx) \le f'_i(w^*_ix)$.

The maximum exists and is attained because $\sum_{i=1}^n f_i(w_ix)$ is continuous on a compact domain: intersection of $[0,1]^n$ with the hyperplane $\sum_{i=1}^n w_i = 1$. (The maximum value is unique, but the maximum point needs not be unique, as the $f_i$ may have line segments).

For any $j \ne k$ two indices such that $w^*_j$ and $w^*_k \ne 0$ and $1$, and $\varepsilon > 0$,
pose $w$ such that $w_j = w^*_j + \varepsilon, w_k = w^*_k - \varepsilon$, and $w_i = w^*_i$ for $i \ne j, k$.
This preserves $\sum_{i=1}^n w_i = 1$.
$\lim_{\varepsilon \rightarrow 0}\frac {F(w)-F(w^*)} \varepsilon = f'_j(w^*_jx) - f'_k(w^*_kx) $
As $w^*$ is a maximum, $\lim_{\varepsilon \rightarrow 0}\frac {F(w)-F(w^*)} \varepsilon = 0$, so $f'_j(w^*_jx) = f'_k(w^*_kx)$.

For $i$ such that $w^*_i = 0$, increasing $w^*_i$ while decreasing some $w^*_j$ must decrease $F$, so $f'_i(w^*_ix) \le f'_j(w^*_jx)$.

For $i$ such that $w^*_i = 1$, decreasing $w^*_i$ while increasing some $w^*_j$ must decrease $F$, so $f'_j(w^*_jx) \le f'_i(w^*_ix)$.

Solving the problem is then finding points $(w_ix)$ where $f'_i$ values are equal (or, if such derivative value does not exist for an $f'_i$, the point is rejected to the interval end where the derivative is closest to the common value), and whose sum is $x$.
Numerically, this is a nice linear search on $C = f'_i(w_ix)$, and on each $f_i$ it is a linear search too, because $f'_i$ is decreasing. It can be organized as follows (other ways are possible, depending upon the $f_i$ shape):

• Compute $A$ the minimum derivative value for all $i$, and $B$ the maximum derivative value for all $i$. These are $A=\min_{i=1}^n f'(x)$ and $B=\max_{i=1}^n f'(0)$, respectively.
• Begin with $A_0=A, B_0 = B, C_0 = \frac {A+B} 2$ and then explore by dichotomy:
• For each $i$, compute $w_i$ such that $f'_i(w_ix) = C_k$, or $f'_i(w_ix)$ closest to $C_k$ (for $w_i = 0$ or $1$). This can be done by dichotomy, the $f'_i$ being decreasing. It supposes having a sufficiently precise method to estimate the derivative, by computing $f_i$ for 2 close points, or any other mean.
• If $\sum_{i=1}^n w_i > 1$, take $C_{k+1} = \frac {C_k+B_k} 2, A_{k+1}=C_k, B_{k+1}=B_k$; otherwise $C_{k+1} = \frac {A_k+C_k} 2, A_{K+1}=A_K, B_{K+1}=C_K$

The complexity is $O(nMP)$, where $n$ is the number of functions $f_i$, $M$ the number of dichotomy steps to explore with $C_k$ the range of derivative values, and $P$ the number of dichotomy steps to find $w_i$ such that $f'_i(w_ix) = C_k$; so it is linear in $n$.

If the $f_i$ never change, while $x$ changes at each run, one may first construct offline an index of tuples $(u_i)$ such that the $f'_i(u_i)$ are all equal, and store $F(u)=\sum_{i=1}^n f_i(u_i)$, then use that to accelerate the resolution for each run. But given the low complexity $O(nMP)$ it is probably not worth the trouble.

Answer 3

Your problem is an instance of convex optimization problem. To formulate it as such, define a function operating on a vector $\vec w = (w_1,\cdots, w_{n-1})$ as $g(\vec w) = - \sum_{j=1}^{n} f_j(w_j x)$, where $w_n = 1 - \sum_{j=1}^{n-1} w_j$. Now $$ \begin{cases} \text{minimize } g(\vec w)\\ \text{subject to } w_j \geq 0\text{ for }j=1,\dots,n-1\text{ and } \sum_{j=1}^{n-1} w_j \leq 1 \end{cases} $$ is a textbook example of a convex optimization problem (e.g. "Convex Optimization" by Stephen Boyd and Lieven Vandenberghe is an example of a textbook).

The exact package you would use depends on your requirements, e.g. what programming language do you prefer to use, is it one-off task or do you implement a production job, etc. For example, in Python you could use scipy.optimize.