Oct
5

## Is NAG Toolbox Faster Than MATLAB's Fsolve?

Walking Randomly is a blog I visit frequently devoting to share some fun stuff like how to use things like Matlab, Mathematica, Python, Condor, Beowulf clusters etc. Recently, I was reading a blog post on how to replace MATLAB's fsolve function with the NAG Toolbox for MATLAB in order to get quite dramatic speed gains and thought I'd try it out for myself with a practical example in finance.

To make good use of fsolve, the example is to solve the Markowitz problem by finding an optimal portfolio with minimum variance for a targeted return, mathematically, for a portfolio of n risky assets we want to find the solution to:

subject to

here r-bar is a fixed pre-desired level for expected rate of return, and a solution is any portfolio that minimizes the objective function (variance) and offers expected rate r-bar. This is an example of what is called a quadratic program, an optimization problem with a quadratic objective function, and linear constraints. By introducing Lagrange multipliers and taking the first derivative a solution to our Markowitz problem is found by finding a solution to the set of n + 2 linear equations

In the end, the problem falls into the standard framework of linear algebra, and amounts to computing the inverse of a matrix: solve Ax = b, and finally fsolve can be used directly.

To make the problem bigger, I set up a pool with 500 assets, randomly simulate 5-year return and optimize my portfolio under a given target return. 500 assets may be too many for most applications but the set-up of this example is fair enough as we usually have to impose other constraints in reality such as the maximum or minimum weights allocated to a certain industry, etc.

I performed the calculations tic; fsolve_markowitz_MATLAB(); toc on a computer running Windows XP, MATLAB 2008b and got the following timings (averaged over 10 runs): 3.35 seconds.

So Michael, are you able to speed up my example for 19.7 times faster?

Hot posts:

15 Incredibly Stupid Ways People Made Their Millions

Online stock practice

Ino.com: Don't Join Marketclub until You Read This MarketClub Reviews

World Changing Mathematical Discoveries

Value at Risk xls

Random posts:

Constant Maturity Swap (CMS) option pricing

Inverse Graphing Calculator

Numerical Simulation of Stochastic Differential Equations

Independent Components Analysis

14 Critical Lessons Every Trader Should Know

To make good use of fsolve, the example is to solve the Markowitz problem by finding an optimal portfolio with minimum variance for a targeted return, mathematically, for a portfolio of n risky assets we want to find the solution to:

subject to

here r-bar is a fixed pre-desired level for expected rate of return, and a solution is any portfolio that minimizes the objective function (variance) and offers expected rate r-bar. This is an example of what is called a quadratic program, an optimization problem with a quadratic objective function, and linear constraints. By introducing Lagrange multipliers and taking the first derivative a solution to our Markowitz problem is found by finding a solution to the set of n + 2 linear equations

In the end, the problem falls into the standard framework of linear algebra, and amounts to computing the inverse of a matrix: solve Ax = b, and finally fsolve can be used directly.

To make the problem bigger, I set up a pool with 500 assets, randomly simulate 5-year return and optimize my portfolio under a given target return. 500 assets may be too many for most applications but the set-up of this example is fair enough as we usually have to impose other constraints in reality such as the maximum or minimum weights allocated to a certain industry, etc.

function MarkowitzWeight = fsolve_markowitz_MATLAB()

RandStream.setDefaultStream (RandStream('mt19937ar','seed',1));

% simulate 500 stocks return

SimR = randn(1000,500);

r = mean(SimR); % use mean return as expected return

targetR = 0.02;

rCOV = cov(SimR); % covariance matrix

NumAsset = length(r);

options=optimset('Display','off');

startX = [1/NumAsset*ones(1, NumAsset), 1, 1];

x = fsolve(@fsolve_markowitz,startX,options, r, targetR, rCOV);

MarkowitzWeight = x(1:NumAsset);

end

function F = fsolve_markowitz(x, r, targetR, rCOV)

NumAsset = length(r);

F = zeros(1,NumAsset+2);

weight = x(1:NumAsset); % for asset weights

lambda = x(NumAsset+1);

mu = x(NumAsset+2);

for i = 1:NumAsset

F(i) = sum(weight.*rCOV(i,:))-lambda*r(i)-mu;

end

F(NumAsset+1) = sum(weight.*r)-targetR;

F(NumAsset+2) = sum(weight)-1;

end

RandStream.setDefaultStream (RandStream('mt19937ar','seed',1));

% simulate 500 stocks return

SimR = randn(1000,500);

r = mean(SimR); % use mean return as expected return

targetR = 0.02;

rCOV = cov(SimR); % covariance matrix

NumAsset = length(r);

options=optimset('Display','off');

startX = [1/NumAsset*ones(1, NumAsset), 1, 1];

x = fsolve(@fsolve_markowitz,startX,options, r, targetR, rCOV);

MarkowitzWeight = x(1:NumAsset);

end

function F = fsolve_markowitz(x, r, targetR, rCOV)

NumAsset = length(r);

F = zeros(1,NumAsset+2);

weight = x(1:NumAsset); % for asset weights

lambda = x(NumAsset+1);

mu = x(NumAsset+2);

for i = 1:NumAsset

F(i) = sum(weight.*rCOV(i,:))-lambda*r(i)-mu;

end

F(NumAsset+1) = sum(weight.*r)-targetR;

F(NumAsset+2) = sum(weight)-1;

end

I performed the calculations tic; fsolve_markowitz_MATLAB(); toc on a computer running Windows XP, MATLAB 2008b and got the following timings (averaged over 10 runs): 3.35 seconds.

So Michael, are you able to speed up my example for 19.7 times faster?

**People viewing this post also viewed:**

Hot posts:

Random posts:

VoR

2010/10/05 11:23 [Add/Edit reply] [Clear reply] [Del comment] [Block]

I have added a blog post to this debate. Please see:http://rationalize-this.blogspot.com/

abiao

2010/10/05 12:40 [Add/Edit reply] [Clear reply] [Del comment] [Block]

Thanks, VoR, that's another way to speed up, I admit I should have used vectorization in Matlab. The main purpose of this post is to test the optimization (fsolve vs c05nb) for given codes, replacing one with each other.

VoR

2010/10/06 12:59 [Add/Edit reply] [Clear reply] [Del comment] [Block]

Yes, I see that. But it is also important to note that I got a different solution.

abiao

2010/10/06 15:34 [Add/Edit reply] [Clear reply] [Del comment] [Block]

The difference is too small to be paid attention, I guess, 1E-11, it may be due to the setting of your Matlab.

Pages: 1/1 1