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, init_betas, bounds, variable_names, parameters=None)

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.

• init_betas (ndarray) – 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 will be ignored.

• 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)

biogeme.optimization.bfgs_trust_region_for_biogeme(fct, init_betas, bounds, variable_names, parameters=None)

Optimization interface for Biogeme, based on Newton method with TR.

Parameters:

• fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.

• init_betas (ndarray) – 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 will be ignored.

• 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)

biogeme.optimization.bio_bfgs(fct, init_betas, bounds, variable_names, parameters=None)

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.

• init_betas (ndarray) – 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, init_betas, bounds, variable_names, parameters=None)

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.

• init_betas (ndarray) – 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, init_betas, bounds, variable_names, parameters=None)

Optimization interface for Biogeme, based on Newton method.

Parameters:

• fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.

• init_betas (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 will be ignored.

• 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:

named tuple:

• betas is the solution found,

• message is a dictionary reporting various aspects related to the run of the algorithm.

• convergence is a bool which is True if the algorithm has converged

Return type:

OptimizationResults

biogeme.optimization.newton_trust_region_for_biogeme(fct, init_betas, bounds, variable_names, parameters=None)

Optimization interface for Biogeme, based on Newton method with TR.

Parameters:

• fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.

• init_betas (ndarray) – 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 will be ignored.

• 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:

named tuple:

• betas is the solution found,

• message is a dictionary reporting various aspects related to the run of the algorithm.

• convergence is a bool which is True if the algorithm has converged

Return type:

OptimizationResults

biogeme.optimization.scipy(fct, init_betas, bounds, variable_names, parameters=None)

Optimization interface for Biogeme, based on the scipy minimize function.

Parameters:

• fct (algorithms.functionToMinimize) – object to calculate the objective function and its derivatives.

• init_betas (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 (Any | None) – dict of parameters to be transmitted to the optimization routine. See the scipy documentation.

Return type:

OptimizationResults

Returns:

named tuple:

• betas is the solution found,

• message is a dictionary reporting various aspects related to the run of the algorithm.

• convergence is a bool which is True if the algorithm has converged

Return type:

OptimizationResult

Parameters:

• fct (FunctionToMinimize)

• init_betas (ndarray)

• bounds (list[tuple[float, float]])

• variable_names (list[str])

• parameters (dict(string:float or string))

biogeme.optimization.simple_bounds_newton_algorithm_for_biogeme(fct, init_betas, bounds, variable_names, parameters=None)

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.

• init_betas (ndarray) – 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 will be ignored.

• 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)