Optimization
Optimization algorithms for Biogeme
biogeme.optimization module
Optimization algorithms for Biogeme
- author
Michel Bierlaire
- date
Mon Dec 21 10:24:24 2020
- biogeme.optimization.bfgsLineSearchForBiogeme(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on BFGS quasi-Newton method with LS.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
maxiter: the maximum number of iterations (default: 100).
- initBfgs: the positive definite matrix that initalizes the BFGS updates. If None, the identity matrix is used. Default: None.
- Returns
tuple x, messages, where
x is the solution found,
messages is a dictionary reporting various aspects related to the run of the algorithm.
- Return type
numpy.array, dict(str:object)
- Raises
biogeme.exceptions.biogemeError – if bounds are imposed on the variables.
- biogeme.optimization.bfgsTrustRegionForBiogeme(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on Newton method with TR.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
maxiter: the maximum number of iterations (default: 100).
dogleg: if True, the trust region subproblem is solved using the Dogleg method. If False, it is solved using the truncated conjugate gradient method (default: False).
radius: the initial radius of the truat region (default: 1.0).
initBfgs: the positive definite matrix that initalizes the BFGS updates. If None, the identity matrix is used. Default: None.
- Returns
tuple x, messages, where
x is the solution found,
messages is a dictionary reporting various aspects related to the run of the algorithm.
- Return type
numpy.array, dict(str:object)
- Raises
biogeme.exceptions.biogemeError – if bounds are imposed on the variables.
- biogeme.optimization.bioBfgs(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on BFGS quasi-Newton method with simple bounds.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
steptol: the algorithm stops when the relative change in x is below this threshold. Basically, if p significant digits of x are needed, steptol should be set to 1.0e-p. Default: \(10^{-5}\)
cgtolerance: when the norm of the residual is below that threshold, the conjugate gradient algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
infeasibleConjugateGradient: if True, the conjugate gradient algorithm may generate until termination. The result will then be projected on the feasible domain. If False, the algorithm stops as soon as an infeasible iterate is generated (default: False).
maxiter: the maximum number of iterations (default: 1000).
radius: the initial radius of the truat region (default: 1.0).
eta1: threshold for failed iterations (default: 0.01).
eta2: threshold for very successful iteration (default 0.9).
enlargingFactor: factor used to enlarge the trust region during very successful iterations (default 10).
- Returns
x, messages
x is the solution generated by the algorithm,
messages is a dictionary describing information about the lagorithm
- Return type
numpay.array, dict(str:object)
- biogeme.optimization.bioNewton(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on Newton’s method with simple bounds.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
steptol: the algorithm stops when the relative change in x is below this threshold. Basically, if p significant digits of x are needed, steptol should be set to 1.0e-p. Default: \(10^{-5}\)
cgtolerance: when the norm of the residual is below that threshold, the conjugate gradient algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
infeasibleConjugateGradient: if True, the conjugate gradient algorithm may generate until termination. The result will then be projected on the feasible domain. If False, the algorithm stops as soon as an infeasible iterate is generated (default: False).
maxiter: the maximum number of iterations (default: 1000).
radius: the initial radius of the truat region (default: 1.0).
eta1: threshold for failed iterations (default: 0.01).
eta2: threshold for very successful iteration (default 0.9).
enlargingFactor: factor used to enlarge the trust region during very successful iterations (default 10).
- Returns
x, messages
x is the solution generated by the algorithm,
messages is a dictionary describing information about the lagorithm
- Return type
numpay.array, dict(str:object)
- biogeme.optimization.newtonLineSearchForBiogeme(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on Newton method.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
maxiter: the maximum number of iterations (default: 100).
- Returns
tuple x, nit, nfev, message, where
x is the solution found,
messages is a dictionary reporting various aspects related to the run of the algorithm.
- Return type
numpy.array, dict(str:object)
- Raises
biogeme.exceptions.biogemeError – if bounds are imposed on the variables.
- biogeme.optimization.newtonTrustRegionForBiogeme(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on Newton method with TR.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell, u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
maxiter: the maximum number of iterations (default: 100).
dogleg: if True, the trust region subproblem is solved using the Dogleg method. If False, it is solved using the truncated conjugate gradient method (default: False).
radius: the initial radius of the truat region (default: 1.0).
- Returns
tuple x, messages, where
x is the solution found,
messages is a dictionary reporting various aspects related to the run of the algorithm.
- Return type
numpy.array, dict(str:object)
- Raises
biogeme.exceptions.biogemeError – if bounds are imposed on the variables.
- biogeme.optimization.scipy(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on the scipy minimize function.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the beta parameters
bounds (list(tuple)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter
parameters – dict of parameters to be transmitted to the optimization routine. See the scipy documentation.
- Returns
x, messages
x is the solution generated by the algorithm,
messages is a dictionary describing several information about the algorithm
- Return type
numpay.array, dict(str:object)
- biogeme.optimization.simpleBoundsNewtonAlgorithmForBiogeme(fct, initBetas, bounds, parameters=None)[source]
Optimization interface for Biogeme, based on variants of Newton method with simple bounds.
- Parameters
fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.
initBetas (numpy.array) – initial value of the parameters.
bounds (list(tuples)) – list of tuples (ell,u) containing the lower and upper bounds for each free parameter. Note that this algorithm does not support bound constraints. Therefore, all the bounds must be None.
parameters (dict(string:float or int)) –
dict of parameters to be transmitted to the optimization routine:
tolerance: when the relative gradient is below that threshold, the algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
steptol: the algorithm stops when the relative change in x is below this threshold. Basically, if p significant digits of x are needed, steptol should be set to 1.0e-p. Default: \(10^{-5}\)
cgtolerance: when the norm of the residual is below that threshold, the conjugate gradient algorithm has reached convergence (default: \(\varepsilon^{\frac{1}{3}}\));
proportionAnalyticalHessian: proportion (between 0 and 1) of iterations when the analytical Hessian is calculated (default: 1).
infeasibleConjugateGradient: if True, the conjugate gradient algorithm may generate until termination. The result will then be projected on the feasible domain. If False, the algorithm stops as soon as an infeasible iterate is generated (default: False).
maxiter: the maximum number of iterations (default: 1000).
radius: the initial radius of the trust region (default: 1.0).
eta1: threshold for failed iterations (default: 0.01).
eta2: threshold for very successful iteration (default 0.9).
enlargingFactor: factor used to enlarge the trust region during very successful iterations (default 10).
- Returns
x, messages
x is the solution generated by the algorithm,
messages is a dictionary describing information about the lagorithm
- Return type
numpay.array, dict(str:object)