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.bfgs_linesearch_for_biogeme(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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.bfgs_trust_region_for_biogeme(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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.bio_bfgs(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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 algorithm
- Return type:
numpay.array, dict(str:object)
- biogeme.optimization.bio_newton(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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.newton_linesearch_for_biogeme(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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.newton_trust_region_for_biogeme(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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, variable_names, 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
variable_names (list(str)) – names of the variables. Ignored here. Included to comply with the syntax.
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.simple_bounds_newton_algorithm_for_biogeme(fct, initBetas, bounds, variable_names, 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.
variable_names (list(str)) – names of the variables.
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 infeasible solutiona 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)