org.akutan.optimization
Class SimulatedAnnealing

java.lang.Object
  org.akutan.optimization.SimulatedAnnealing

All Implemented Interfaces:

Solver

Direct Known Subclasses:

SimulatedAnnealing2

public class SimulatedAnnealing
extends java.lang.Object
implements Solver

Class implements a simple Simulated Annealing algorithm from Chang et al, "Heuristics for Cardinality Constrained Portfolio Optimization", Computers & Operations Research, 27 (2000), 1271-1302.

Since:

18 September 2007

Field Summary

protected double	_cMove Initial relative move in an asset per iteration
protected double	_epsilon Minimum required fraction for an asset in the solution
protected double	_moveSize Current step
protected cern.colt.matrix.DoubleMatrix1D	_mu Returns and covariances for the assets
protected int	_order Number of assets required
protected cern.jet.random.engine.RandomEngine	_twister Random engine shared across all activities
protected cern.colt.matrix.DoubleMatrix2D	_V

Constructor Summary

SimulatedAnnealing(int order, double epsilon, cern.colt.matrix.DoubleMatrix1D mu, cern.colt.matrix.DoubleMatrix2D V)
Constructs a SimulatedAnnealing problem where the solution will have a number of active assets exactly equal to order.

Method Summary

SASolution	anneal(double lambda) Performs the simulated annealing optimization and returns a solution
protected SASolution	decide(SASolution s, double lambda) Original decision rule is random
void	dumpPoints() Dumps out the list of solution points
protected void	evaluate(SASolution sl, double lambda) Called to evaluate a potential solution
double	getEpsilon() Returns epsilon (min allocation to an asset)
protected java.util.List<SASolution>	initialGuess() Constructs a set of initial crystals which represent potentially valid solutions.
double	move(SASolution s, boolean up, int ptr) Called to move the specified asset up/down as directed
java.util.List<SolvedPoint>	solve(java.util.List<Constraint> constraints, org.akutan.optimization.ProgressIndicator progress) Called to solve for the efficient frontier subject to the constraints supplied by the caller.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

_order

protected int _order

Number of assets required

_epsilon

protected double _epsilon

Minimum required fraction for an asset in the solution

_cMove

protected final double _cMove

Initial relative move in an asset per iteration

See Also:

Constant Field Values

_moveSize

protected double _moveSize

Current step

_twister

protected final cern.jet.random.engine.RandomEngine _twister

Random engine shared across all activities

_mu

protected final cern.colt.matrix.DoubleMatrix1D _mu

Returns and covariances for the assets

_V

protected final cern.colt.matrix.DoubleMatrix2D _V

Constructor Detail

SimulatedAnnealing

public SimulatedAnnealing(int order,
                          double epsilon,
                          cern.colt.matrix.DoubleMatrix1D mu,
                          cern.colt.matrix.DoubleMatrix2D V)

Constructs a SimulatedAnnealing problem where the solution will have a number of active assets exactly equal to order.

Parameters:

order - Number of assets required in the solution

mu - Vector of expected returns

V - Covariance matrix of the assets

Method Detail

initialGuess

protected java.util.List<SASolution> initialGuess()

Constructs a set of initial crystals which represent potentially valid solutions.

Returns:

A list of initial guesses

getEpsilon

public double getEpsilon()

Returns epsilon (min allocation to an asset)

Returns:

The value of epsilon set into the problem

evaluate

protected void evaluate(SASolution sl,
                        double lambda)

Called to evaluate a potential solution

Parameters:

sl - Potential solution

lambda - Used in the calculation of the scaling factor

solve

public java.util.List<SolvedPoint> solve(java.util.List<Constraint> constraints,
                                         org.akutan.optimization.ProgressIndicator progress)

Called to solve for the efficient frontier subject to the constraints supplied by the caller.

Specified by:

solve in interface Solver

Parameters:

constraints - List of additional constraints

Returns:

List of points on the efficient frontier

anneal

public SASolution anneal(double lambda)

Performs the simulated annealing optimization and returns a solution

Parameters:

lambda - Parameter to the simulated annealing algorithm

Returns:

Manages the optimization process and returns a solution.

decide

protected SASolution decide(SASolution s,
                            double lambda)
                     throws java.lang.CloneNotSupportedException

Original decision rule is random

Parameters:

s - Solution to be examined

lambda - Parameter to the algorithm

Returns:

A new solution based on the input solution and some random actions

Throws:

java.lang.CloneNotSupportedException

move

public double move(SASolution s,
                   boolean up,
                   int ptr)

Called to move the specified asset up/down as directed

Parameters:

s - The solution in which the asset is to be moved

up - true indicate increase the assets weight

ptr - Index of the asset to move

Returns:

New weight of the asset

dumpPoints

public void dumpPoints()

Dumps out the list of solution points