{"id":8167,"date":"2012-08-20T09:51:05","date_gmt":"2012-08-20T08:51:05","guid":{"rendered":"https:\/\/www.portfolioprobe.com\/?p=8167"},"modified":"2012-08-21T11:00:54","modified_gmt":"2012-08-21T10:00:54","slug":"another-comparison-of-heuristic-optimizers","status":"publish","type":"post","link":"https:\/\/www.portfolioprobe.com\/2012\/08\/20\/another-comparison-of-heuristic-optimizers\/","title":{"rendered":"Another comparison of heuristic optimizers"},"content":{"rendered":"

A herd of heuristic algorithms is compared using a portfolio optimization.<\/p>\n

Previously<\/h2>\n

“A comparison of some heuristic optimization methods”<\/a> used two simple and tiny portfolio optimization problems<\/a> to compare a number of optimization functions in the R language<\/a>.<\/p>\n

This post expands upon that by using a portfolio optimization problem that is of a realistic size (but still with an unrealistic lack of constraints).<\/p>\n

Test case<\/h2>\n

The optimization problem is to select 30 assets out of a universe of 474 and find their best weights.\u00a0 The weights must be non-negative and sum to 1.\u00a0 The integer constraint is binding — more than 30 assets in the portfolio can give a better utility.\u00a0 The utility is mean-variance.<\/p>\n

Each optimizer was run 100 times.\u00a0 To have a fair comparison the amount of time that each run took was controlled to be about 1 kilosecond.\u00a0 (There are a couple that also have runs that take much less time.)<\/p>\n

The timings are not all particularly close to 1000 seconds, but they are probably all close enough that the picture is minimally distorted.<\/p>\n

Besides, the timing (on Windows) seems dodgy.\u00a0 It is supposed to be timing only the compute time (not elapsed time), but the timings don’t seem to be following a constant plus noise model.\u00a0 Figure 1 shows an example of the timing.<\/p>\n

Figure 1: The compute time reported for genopt<\/code> in the order of the runs. \"\"<\/a>The timings are a bit suspect, but should be good enough.<\/p>\n

The optimizers<\/h2>\n

Most of the optimizers used in “A comparison of some heuristic optimization methods”<\/a> are also used here.\u00a0 The exception is the functions from NMOF<\/code> because they don’t have explicit box constraints (there is a mechanism for imposing constraints though).\u00a0 The only unconstrained method that was run was the SANN<\/code> method of the optim<\/code> function.<\/p>\n

Three methods were added.<\/p>\n

pso package<\/h3>\n

The psoptim<\/code> function from pso<\/code><\/a> implements a particle swarm algorithm.<\/p>\n

nloptr package<\/h3>\n

The Controlled Random Search (CRS) method was done via the nloptr<\/code> function in the nloptr<\/code> package<\/a>.<\/p>\n

This has the unexpected behavior of not respecting default values of arguments in the function to be optimized.\u00a0 You need to specify additional arguments to the function even when they have default values.<\/p>\n

cmaes package<\/h3>\n

The Covariance Matrix Adapting Evolutionary Strategy is implemented in the cmaes<\/code> package<\/a>.<\/p>\n

When the version from CRAN (1.0-11) was used on this problem, it got nowhere.\u00a0 The results presented here are from an R-forge version.\u00a0 Apparently the difference is the default values for control variables.\u00a0 Adjusting default values is a work in progress.<\/p>\n

Results<\/h2>\n

Portfolio Probe<\/a> consistently gets the same (best) answer in about 3 to 4 seconds.<\/p>\n

Figure 2 shows the distribution of deficiencies from the best answer for the methods.<\/p>\n

Figure 2: Difference in utility from optimal (ordered by median). \"\"<\/a>The methods “soma(54)” and “psoptim(55)” are sets of runs where the time was significantly less than 1000 seconds.\u00a0 The number in parentheses is the mean time in seconds for the runs.<\/p>\n

Figure 3 has the same information as Figure 2, but the sign of the numbers is changed and the plot is on the logarithmic scale.<\/p>\n

Figure 3: Logarithm of negative difference in utility from optimal (ordered by median). \"\"<\/a><\/p>\n

Comments<\/h2>\n

Private correspondence with Enrico Schumann<\/a> improved this section.<\/p>\n

Defaults<\/h3>\n

This is not a comparison of algorithms.\u00a0 This is a comparison of algorithms with their mildly modified default values on one<\/strong> problem.<\/p>\n

The importance of default parameters is evident with cmaes<\/code>.\u00a0 The CRAN set didn’t even get out of the starting gate.\u00a0 The set that was used didn’t compare very favorably with the other optimizers.\u00a0 But it seems certain that there is a set of control parameters for it that would do very well.<\/p>\n

Applications matter<\/h3>\n

The problem that is being solved has an effect on which algorithms (plus control parameters) work best.\u00a0 There is not a uniformly best algorithm.<\/p>\n

Experimentation is useful<\/h3>\n

Experimenting with different algorithms and their settings is likely to pay off if you are doing the same sort of optimization repeatedly.<\/p>\n

What is good enough?<\/h3>\n

There is almost always a point at which moving to a more optimal answer is not of practical relevance.\u00a0 That point will of course depend on the actual problem.<\/p>\n

“What is good enough for portfolio optimization?” is an excellent question that I don’t think anyone has a good answer to.\u00a0 It does obviously depend on the quality of the inputs — if the inputs are complete garbage, then it doesn’t matter how close to optimal you are.\u00a0 (The correct answer in that case is not to trade at all.)<\/p>\n

Clustering<\/h3>\n

Both soma<\/code> and psoptim<\/code> (and perhaps others) get relatively good answers within a minute, but then they never seal the deal, so to speak.\u00a0 They don’t get especially close to the best objective.<\/p>\n

You may naively think that the longer runs would be scattered between where they are after a minute and the best solution.<\/p>\n

Given:<\/p>\n