Sampling problem in portfolio optimization

Question

In a summary I am trying to do the following

1. Bond Subset 1 : Get list of USD Bonds --> Filter out Bonds which have YTM > y% DUR > 10 Y etc. .. This gives us Bonds which we are interested in. So in the end we will have a subset of these Bonds in final portfolio
2. Bond Subset 2 : List of Bonds which we surely need to include . Unlike previous subset these bonds should definitely include in final portfolio
3. Constraints :
   a. Match Total Duration and Key Rate Duration : Given the DV01 profile of the client’s liability the resulting portfolio should match this profile with +- X% deviation b. Apply Sector Constraints : Total in Financial Sector <= 0.25 of Total etc. .. c. Lower and Upper Limits of investment in single security d. Maximum Number of securities in resulting portfolio = N
4. Objective : Achieve Yield = Y % or Maximize Yield

So I created a set of inequalities to satisfy these contraints and I have my objective function defined as well. I am using matlab fmincon to achieve this.

Problem fmincon tries to include all bonds in the optimization and the results is such that constraints are not satisfied. I need to be able to selectively pick or remove bonds from the Subset 1. Which means that I need the solver to have variable number of variables. To solve this problem I am looking at finding best way to sample subsets of Bonds 1 and run solver on this so that I am left with portfolio with satisfies the contraints. Does anyone have any ideas on such a sampling problem in portfolio optimization. (Please dont suggest considering all combinations of bonds possible to find subsets for which constraints are satisfied and I get max yeild, since performance of the code is very important here and number of securities are about 1000 )

Answer 1

If I understand you correctly, then you have a filter defined for your portfolio that is defined by "1.".

A) So you either filter out these bonds before you start anything that has to do with the optimization. This should be the way to go if you are interested in speeding up your program.

B) If you want to do everything in the optimization, then you need constraints of the form $$ w_i = 0 \text{ if asset }i \text{ does not pass the filter} $$ doing this you have all bonds in you optimization universe but you have unnecessarily many variables.

E.g. If your univers is $10^6$ bonds and only $20\%$ satisfy the filter then using A) you only have 200 000 variables and using B) you have $10^6$ variables and 800 000 with a trivial constraint.

Another issue is that your problem is very big ...

EDIT After some comments by the OP: What you want to do is an optimization with cardinality constraint. Such constraints are difficult to handle. With these you leave the realm of continuous optimization and you enter mixed-integer quadratic programs. You either need some heuristics that you believe in or better you look for a (most of the time) commercial solver that can handle integer constraints.

What you do is you introduce additional variables $k_i,i=1,\ldots,n$ and the constraints $$ k_i \in \{0,1\} \\ w_i \le k_i \\ \sum k_i \le K $$ for some integer $K$. The objective function is unchanged.

Answer 2

I would use a Metropolis Monte Carlo / simulated annealing approach to solve your problem.

Start with an arbitrary fully invested portfolio which satisfies constraints (2), (3) and the cardinality constraint $N \le K$. Then choose one of the following trial moves:

1. Select two bonds $i,j$ at random and perform a random weight shift $w_i \rightarrow w_i + \delta w$, $w_j \rightarrow w_j - \delta w$, or
2. Remove a bond at random and rescale the portfolio weights to $\sum w_i = 1$, or
3. add a new bond to the portfolio and rescale weights

After each of these trial moves, check if all the constraints are satisfied, and use the Metropolis condition to accept the trial configuration with probability $\min(1,\exp((o_{trial} - o_{old})/T))$. $o_{trial}, o_{old}$ is the objective function and $T$ is a 'temperature' which is initialized such that the exponential of the Metropolis condition is of order 1. $T$ is gradually reduced until the portfolio is 'frozen' into an optimal or near-optimal configuration. This terminates the optimization.

Remarks: trial move 1 should be choosen much more frequently (perhaps 90%), and if the portfolio is long-only then this restricts the possible trial moves in 1.

Answer 3

Assume that instead of a possible portfolio of 1000 bonds, the portfolio may only contain M bonds. The input vector then needs to contain both the weightings and the choice of bonds, but how can you present the choice of bonds as an input vector?

Consider sorting the candidate bonds by Macaulay duration. Given a single Macaulay duration value, then, you could locate the nearest 2 bonds to that duration, and weight each of them according to the closeness of the duration match. E.g. I want 2.75y duration and I have bonds with durations of 2y and 3y, so weight them 75% 3y and 25% 2y.

The input vector is then a set of duration values, and a set of weights, like this:

dur   wt
1.0   0.25
2.75  0.5
5     0.15
25    0.1

That would become a portfolio like this (I'm putting in rough numbers):

dur   wt
0.97  0.24
1.2   0.01
2.0   0.125
3.0   0.375
5.0   0.15
20    0.005
25.1  0.095

If you're keen to minimise the size of the portfolio, then you can filter out values below some threshold when you score the portfolio with your objective function.

I've avoided just picking the nearest bond to a given duration here because minimisers generally work best with smooth objective functions; if the trial vector shifts slightly and a different bond is selected, the jump is sudden rather than smooth and may represent a local maximum. This way there is a smooth transition between selecting the 2yr vs the 2.5yr bond.

You can replace the Macaulay duration with any linear scale which measures the set of bonds; it is going to be used fairly blindly by the minimisation algorithm as a black box. The key is to have a way to move a pointer smoothly along the spectrum of bonds.

One interesting possibility is to include a penalty dependent on the number of bonds in use; if you can quantify the value of having of 5 bonds over 10, then you can include that. A small penalty permits the minimiser to initially concentrate on getting to the right area of the search space, and then later to optimise the tradeoffs that suit the smaller detail, e.g. eliminating a bond from the portfolio by raising the weights of the values around it. Again, make the penalty smooth; perhaps the total bond count plus the smallest non-zero weight.