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)

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)

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)

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)

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)

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)

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)

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)

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)