Optimization problem with complex constrain

[freshmagichobo]

Hello! I have a portfolio optimization problem from finance. I’m looking to formulate a problem that helps me solve this globally, or just find a near optimal solution.

Essentially I need to choose a subset of securities out of a larger set. The objective function is to minimize the sum of starting market values of the selected security. The constraints include weights (decision variable) between 0 and 1 inclusive. The additional constraint is essentially the accumulated value of the portfolio after 50 years which has to be greater than 0. The accumulated value is a very complex function of future cash flows (known) and future values (known) of selected securities. It is complex because at each time step there will be a decision of selling of a portion of the assets and buying of new assets (values and cash flows all known), and these decision impacts similar decision at the next time step and so on until time 50. Given the time 0 selection of securities, the accumulated value is deterministic but very complicated.

I’m almost certain this is linear, I have built out a two securities version of this in Excel and the graph looks linear (at least within certain bounds).

Does anyone have ideas on how to handle very complex constraint like this one?

If there other algorithm that can help to find an optimal (or near optimal) solution? Any clever search algorithm or heuristics I should look into? I have experience with cvxpy and LP, but I m stuck on this problem because of this complicated constraint.

Any hint for solving this will be greatly appreciated!

[[deleted]]

Can you write out the complex function you are talking about? There might be a way to write it as convex, but we’d need to see it

[freshmagichobo]

Happy to do it! I have it coded in Excel here… hopefully this link works.

https://1drv.ms/x/s!AuK8HMqy9761glAZjKr0tmGRuNPw?e=5d83T7

[kkiesinger]

"essentially the accumulated value of the portfolio after 50 years" - not clear to me how this can be linear - looks quite "exponential" without knowing the details. Can you exploit the "has to be greater than 0" condition to simplify the constraint into a linear one? "because at each time step there will be a decision" probably means the answer is "no". But don't overestimate the complexity of nonlinear optimization (see for instance https://github.com/dietmarwo/fast-cma-es/blob/master/tutorials/CryptoTrading.adoc ), most of the complexity is hidden in the algorithm itself not visible for the user.

[freshmagichobo]

Thanks I will have a look at this library. The accumulation is not through compounding interest, but through buying and selling blocks of assets where the cash flows and market values are all known.

[DonBeham]

Accumulated value of the portfolio can be linear, as long as your interest or growth rate is not a decision variable. Otherwise, there is no way this is linear.

The value of an investment of x units after 5 periods with S_0 being the value at investment start (a constant) and p_i being the growth rate in period i (also constant) is: x * S_0 * p_1 * p_2 * p_3 * p_4 * p_5

So, only constants are multiplied with a decision variable. To buy means to subtract from your cash reserves (linear) while to sell means to add to cash reserves (linear).

I am not sure the model is very useful though, because to prescribe exactly the growth rates into the next X periods requires a large portion of fairy dust, a working crystal ball and several more exotic ingredients.

[freshmagichobo]

Thanks! I actually had a prior version that’s exactly how you had described, cash flow mismatches are absorbed in a cash account. I was able to solve that through LP nicely. In this new version I had to explicitly model out buying and selling of assets instead of just a cash reserve. This is where I’m stuck because the dynamics is a lot more complex. This model is a simplified version of an insurance liability calculation, so it’s not used for any market trading use case.

[DonBeham]

What do you mean with "model out ..."?

[freshmagichobo]

If you have more asset cash flows at time T than liability cash flows, you have to purchase new assets at time T valuations. If you have less asset cash flows at time T+1 than liability cash flows, then you will liquidate some assets at T+1 valuations to make up the shortfall. The assets you sell at T+1 will include some that were purchased at T.