public class FiniteGradientDescent extends Object implements RunTimeLimit
MultiDimNumFunction
.
This method will approximate the gradient for each dimension at each incumbent solution.
The user can set the maximum number of iterations.
The user can also set maximum and minimum bounds for each variable.
By default, these bounds are set to Double.POSITIVE_INFINITY
and
Double.NEGATIVE_INFINITY
.
The user can change these bounds with the method double[])
.
Modifier and Type | Class and Description |
---|---|
static class |
FiniteGradientDescent.Results |
Modifier and Type | Field and Description |
---|---|
protected FiniteGradientDescent.Results |
bestResults
Contains the best results or null if optimization has not been executed.
|
static int |
FINITE_GRADIENT_CENTRAL
Select method of finite gradient approximation.
|
static int |
FINITE_GRADIENT_FORWARD
Select method of finite gradient approximation.
|
protected MultiDimNumFunction |
func
Score function to minimize.
|
protected int |
gradientMethod
The method to use to estimate the gradient.
|
protected int |
lastRunTimeSec
Contains the execution of the last optimization run.
|
protected double[] |
maxBounds
Set the maximum value for each variable.
|
protected double |
maxDistance
Maximum moving distance (after multiplying the gradient).
|
protected int |
maxIterations
Maximum number of iterations.
|
protected int |
maxItNoImprCorrect
Set the maximum number of iterations that gave no improvement
over incumbent best solution.
|
protected long |
maxItNoImprTol
Maximum consecutive no improvement tolerance.
|
protected int |
maxNumRestart
Set maximum number of times to restart gradient search with startDistMult, but
at the current best solution.
|
protected double[] |
minBounds
Set the minimum value for each variable.
|
protected double |
minDistance
The minimum distance (before multiplying by the gradient)
to move at each iteration.
|
static int |
OPTIM_METHOD_QUASINEWTON
Select the quasi-newton method for optimization.
|
static int |
OPTIM_METHOD_SP
Select the simultaneous perturbations method combined with line search.
|
static int |
OPTIM_METHOD_STANDARD
Select the standard gradient descent method using only the 1st derivative
estimation (with finite difference).
|
protected int |
optimMethod
Selects the optimization method
OPTIM_METHOD_STANDARD or OPTIM_METHOD_QUASINEWTON . |
protected int |
optTimeLimitSec
Set maximum time limit in seconds.
|
protected double |
relTol
The maximum relative tolerance level.
|
static int |
SIMUL_PERTURBATIONS
Select the simultaneous perturbation method to estimate the gradient.
|
protected double |
startDistMult
Set the starting distance multiplier.
|
protected boolean |
useManualRelocation
Choose to enable the manual relocation method for the standard gradient descent.
|
Constructor and Description |
---|
FiniteGradientDescent(MultiDimNumFunction f,
double startDistMult,
int maxIt,
double relTol)
Constructor with the given function and maximum number of iterations.
|
Modifier and Type | Method and Description |
---|---|
protected static double |
adjustSearchDirLength(double[] x,
double[] dir,
double[] max,
double[] min,
double length)
Adjust the search direction length if the next solution is over the bounds.
|
protected static boolean |
adjustSolutionBounds(double[] x,
double[] max,
double[] min)
Adjust the solution vector x so that it stays within bounds.
|
boolean |
checkInBounds(double[] x)
If maximum and minimum bounds have been defined, this method will check
if the given point x is inside the bounds.
|
protected double[] |
computeFiniteGradient(double xScore,
double[] x,
double delta)
Compute the "forward" gradient at current solution .
|
protected double[] |
computeFiniteGradient2(double[] x,
double delta)
Computes the "central" gradient around current solution .
|
protected double[] |
computeGradientSP(double[] x,
double delta,
RandomStream rs,
double subgNumRatio,
int subgMaxNum)
Estimates the gradient at current solution with simultaneous perturbations.
|
static double |
computeMaxAbsDiff(double[] x1,
double[] x2)
Return the maximum absolute (absolute value) difference between the elements of the
two given vectors.
|
FiniteGradientDescent.Results |
getBestResults() |
int |
getGradientMethod()
Get the method to approximate the gradient, refer to the constant variables of this class.
|
int |
getLastRunTimeSec()
Get the run time in seconds of the last execution.
|
double[] |
getMaxBounds()
Get the maximum bound of each variable.
|
double |
getMaxDistance()
Get the maximum moving distance.
|
int |
getMaxItNoImprCorrect()
Get the threshold of consecutive iterations without improving the incumbent
best solution.
|
long |
getMaxItNoImprTol()
Get the maximum tolerance on the
number of consecutive iterations without improving the incumbent best solution.
|
int |
getMaxNumRestart()
Get the maximum number of optimization restarts.
|
double[] |
getMinBounds()
Get the minimum bound of each variable.
|
double |
getMinDistance()
Get the minimum moving distance.
|
int |
getOptimizationMethod()
Get the optimization method to be used, refer to the constant variables of this class.
|
int |
getTimeLimitSec()
Get the time limit in seconds.
|
boolean |
getUseManualRelocation()
Determine if the manual relocation method will be executed in the standard
gradient method.
|
void |
init(MultiDimNumFunction f,
double startDistMult,
int maxIt,
double relTol) |
protected FiniteGradientDescent.Results |
manualRelocation(double[] currSolution,
double currScore,
FiniteGradientDescent.Results currBestSol)
This method allows the user to manually relocate the incumbent solution if
the gradient search method converged to a solution.
|
FiniteGradientDescent.Results |
optimize(double[] startPoint)
Execute the finite gradient descent minimization method.
|
protected FiniteGradientDescent.Results |
optimizeQN(double[] startPoint)
Use Quasi-Newton method to optimize using gradients,
use the Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula to
estimate the inverse of the Hessian matrix.
|
FiniteGradientDescent.Results |
optimizeSP(double[] startPoint)
Execute the gradient descent minimization using the Simultaneous Perturbations (SP)
to estimate the gradient and line search with the golden ratio search.
|
FiniteGradientDescent.Results |
optimizeStd(double[] startPoint)
Execute the finite gradient descent minimization using the standard method with
only the first-order derivative estimation.
|
void |
setBounds(double[] maxb,
double[] minb)
Set the maximum and minimum bounds for each variable of the function.
|
void |
setDistances(double maxDist,
double minDist)
Set the maximum and minimum moving distances.
|
void |
setGradientMethod(int m)
Set the method to approximate the gradient, refer to the constant variables of this class.
|
void |
setMaxDistance(double d)
Set the maximum moving distance.
|
void |
setMaxItNoImprCorrect(int m)
Set the threshold of consecutive iterations without improving the
incumbent best solution.
|
void |
setMaxItNoImprTol(long t)
Set the maximum tolerance on the
number of consecutive iterations without improving the incumbent best solution.
|
void |
setMaxNumRestart(int num)
Set the maximum number of optimization restarts.
|
void |
setMinDistance(double d)
Set the minimum moving distance.
|
void |
setOptimizationMethod(int m)
Set the optimization method to use, refer to the constant variables of this class.
|
void |
setTimeLimitSec(int sec)
Set the time limit in seconds.
|
void |
setUseManualRelocation(boolean b)
Set to use the manual relocation method or not when the standard gradient method
converges.
|
protected boolean |
updateBestResults(double[] x,
double score)
Internal method to update the bestResults if the score is lower than the current
best results.
|
public static final int FINITE_GRADIENT_CENTRAL
public static final int FINITE_GRADIENT_FORWARD
public static final int SIMUL_PERTURBATIONS
public static final int OPTIM_METHOD_STANDARD
public static final int OPTIM_METHOD_QUASINEWTON
public static final int OPTIM_METHOD_SP
protected int optimMethod
OPTIM_METHOD_STANDARD
or OPTIM_METHOD_QUASINEWTON
.protected int maxIterations
protected double relTol
protected double minDistance
protected double startDistMult
protected long maxItNoImprTol
protected double maxDistance
protected int maxItNoImprCorrect
protected int maxNumRestart
protected double[] maxBounds
protected double[] minBounds
protected FiniteGradientDescent.Results bestResults
protected MultiDimNumFunction func
protected int gradientMethod
protected boolean useManualRelocation
manualRelocation(double[], double, umontreal.iro.lecuyer.ccoptim.util.FiniteGradientDescent.Results)
.protected int optTimeLimitSec
protected int lastRunTimeSec
public FiniteGradientDescent(MultiDimNumFunction f, double startDistMult, int maxIt, double relTol)
f
- the multi-dimensional numerical function.startDistMult
- set the starting move distance multiplier. The user should set
this value depending of the size of the variables in the problem. If the variables
are expected to be small numbers, then set this multiplier smaller.maxIt
- the maximum number of iterations.relTol
- the relative tolerance level, the algorithm stops when the
relative moving distance of all dimensions is less than this value.public void init(MultiDimNumFunction f, double startDistMult, int maxIt, double relTol)
public void setMaxDistance(double d)
d
- the maximum moving distance.public double getMaxDistance()
public void setMinDistance(double d)
d
- the minimum moving distance.public double getMinDistance()
public void setDistances(double maxDist, double minDist)
maxDist
- the maximum moving distance.minDist
- the minimum moving distance.public void setMaxNumRestart(int num)
num
- the maximum number of optimization restarts.public int getMaxNumRestart()
public void setBounds(double[] maxb, double[] minb)
maxb
- the maximum bound for each variable of the function, or set
null for Double.POSITIVE_INFINITY
.minb
- the maximum bound for each variable of the function, or set
null for Double.NEGATIVE_INFINITY
.public double[] getMaxBounds()
public double[] getMinBounds()
public void setMaxItNoImprCorrect(int m)
m
- the threshold of consecutive iterations without improving the
incumbent best solution.public int getMaxItNoImprCorrect()
public void setMaxItNoImprTol(long t)
Long.MAX_VALUE
.t
- the maximum tolerance on the number of consecutive iterations without
improving the incumbent best solution.public long getMaxItNoImprTol()
public void setGradientMethod(int m)
m
- the method for approximating the gradient.public int getGradientMethod()
public void setOptimizationMethod(int m)
m
- the optimization method.public int getOptimizationMethod()
public void setTimeLimitSec(int sec)
RunTimeLimit
setTimeLimitSec
in interface RunTimeLimit
sec
- the time limit in seconds.public int getTimeLimitSec()
RunTimeLimit
getTimeLimitSec
in interface RunTimeLimit
public int getLastRunTimeSec()
RunTimeLimit
getLastRunTimeSec
in interface RunTimeLimit
protected boolean updateBestResults(double[] x, double score)
x
- the new solution.score
- the corresponding score value.public FiniteGradientDescent.Results optimize(double[] startPoint)
startPoint
- the starting solution vector, or set to null for
initial solution 0.public FiniteGradientDescent.Results optimizeStd(double[] startPoint)
startPoint
- the starting solution vector, or set to null for
initial solution 0.protected FiniteGradientDescent.Results optimizeQN(double[] startPoint)
startPoint
- the starting point or null for point 0 as starting point.public FiniteGradientDescent.Results optimizeSP(double[] startPoint)
startPoint
- the starting solution vector, or set to null for
initial solution 0.protected static boolean adjustSolutionBounds(double[] x, double[] max, double[] min)
x
- the solution vector to adjust.max
- the maximum bound for each element of the solution vector.min
- the minimum bound for each element of the solution vector.protected static double adjustSearchDirLength(double[] x, double[] dir, double[] max, double[] min, double length)
x
- the current solution.dir
- the direction of the search.max
- the maximum bound for each element of the solution vector.min
- the minimum bound for each element of the solution vector.length
- the proposed move length, cannot be negative.protected FiniteGradientDescent.Results manualRelocation(double[] currSolution, double currScore, FiniteGradientDescent.Results currBestSol)
The gradient search method will continue if the returned value is not null. Otherwise, the gradient search algorithm will stop. Note that the converged solution is not necessarily the current best solution. It just means that the search algorithm is stuck since it cannot move anymore.
If this method improves over the current best solution, then it must update the
best results variable with the function double)
.
If the relocated solution does not improve the best solution, then the gradient
search algorithm is subject to the no improvement conditions.
Note : This method is not implemented by default and will return null. The user must extend this class to implement his relocation method.
currSolution
- the current incumbent solution that converged.currScore
- the score of the current solution.currBestSol
- the current best solution found.FiniteGradientDescent.Results
object or
null to stop the algorithm. The results (if not null) must
contain both the solution vector and the associated score to avoid re-evaluating
this solution.public void setUseManualRelocation(boolean b)
b
- set to true to use the manual relocation method.public boolean getUseManualRelocation()
public boolean checkInBounds(double[] x)
x
- the point to verify if it is inside the maximum and minimum bounds.public static double computeMaxAbsDiff(double[] x1, double[] x2)
x1
- the first vector.x2
- the second vector.IllegalArgumentException
- the two vectors must have the same size.protected double[] computeFiniteGradient(double xScore, double[] x, double delta)
If the max bound equals the min bound for a variable, the gradient is automatically 0 and no simulation is executed for that dimension. If the evaluating point is above the max bound (because we use forward gradient), the distance is adjusted so the point stays within the bounds. If a variable is at maximum bound, we will use the backward gradient.
The parameter delta is to control the distance of the finite difference. We use a forward finite difference method : gi = [f ( + δ) - f (x)]/δ, where gi is the gradient for dimension i, f is the function, δ is the distance, is a unity vector with 1 at index i and 0 for the rest.
xScore
- the value at current solution .x
- the current solution vector.delta
- the difference distance, has to be positive.protected double[] computeFiniteGradient2(double[] x, double delta)
If the max bound equals to the min bound for a variable, the gradient is 0 by default and no simulation is executed for this dimension. If the evaluation point exceeds the max or min bound, the method will adjust the distance so the point stays within the bounds.
The parameter delta
is to control the distance of the finite difference.
We use a central finite difference method :
gi = [f ( + δ) - f ( - δ)]/(2δ),
where gi is the gradient for dimension i, f is the function, δ is the
distance and is a unity vector with 1 at index i and 0 for the rest.
x
- the current solution vectordelta
- the difference distance, has to be positiveprotected double[] computeGradientSP(double[] x, double delta, RandomStream rs, double subgNumRatio, int subgMaxNum)
If the max bound equals the min bound for a variable, the gradient is automatically 0. The variables are truncated to stay within the limit bounds.
The parameter delta
is to control the distance of the finite difference.
A random direction vector Δ is generated with a Bernoulli distribution.
Direction of variable i is
Δi = 1 with probability 0.5 and
Δi = - 1
with probability 0.5.
The gradient of variable i is :
gi = [f ( + δΔ) - f ( - δΔ)]/(2δΔi),
where gi is the gradient for variable i, f is the function, δ is the
distance.
x
- the current solution vectordelta
- the difference distance, has to be positivers
- the random stream to use to generate the Bernoulli variablessubgNumRatio
- select the number of simulations to generate the average subgradient,
the number if the ratio of the number of variables. The ratio must be greater than 0 but
not over 1. The number of simulations will be subject to the subgMaxNum limit.subgMaxNum
- the maximum number of simulations to generate the average subgradientpublic FiniteGradientDescent.Results getBestResults()