org.akutan.optimization
Class SimulatedAnnealing

java.lang.Object
  extended by 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