An adaptive Monte Carlo algorithm for computing mixed logit estimators

Researchers and analysts are increasingly using mixed logit models for estimating responses to forecast demand and to determine the factors that affect individual choices. However the numerical cost associated to their evaluation can be prohibitive, the inherent probability choices being represented by multidimensional integrals. This cost remains high even if Monte Carlo or quasi-Monte Carlo techniques are used to estimate those integrals. This paper describes a new algorithm that uses Monte Carlo approximations in the context of modern trust-region techniques, but also exploits accuracy and bias estimators to considerably increase its computational efficiency. Numerical experiments underline the importance of the choice of an appropriate optimisation technique and indicate that the proposed algorithm allows substantial gains in time while delivering more information to the practitioner. Fabian Bastin: Research Fellow of the National Fund for Scientific Research (FNRS)     

A Globally Convergent Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds

We consider the global and local convergence properties of a class of Lagrangian barrier methods for solving nonlinear programming problems. In such methods, simple bound constraints may be treated separately from more general constraints. The objective and general constraint functions are combined in a Lagrangian barrier function. A sequence of such functions are approximately minimized within the domain defined by the simple bounds. Global convergence of the sequence of generated iterates to a first-order stationary point for the original problem is established. Furthermore, possible numerical difficulties associated with barrier function methods are avoided as it is shown that a potentially troublesome penalty parameter is bounded away from zero. This paper is a companion to previous work of ours on augmented Lagrangian methods.

     

Numerical experiments with the LANCELOT package (release A) for large-scale nonlinear optimization

In this paper, we describe the algorithmic options of Release A of LANCELOT, a Fortran package for large-scale nonlinear optimization. We then present the results of intensitive numberical tests and discuss the relative merits of the options. The experiments described involve both academic and applied problems. Finally, we propose conclusion, both specific to LANCELOT and of more general scope. This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079     

Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints

This paper presents two new trust-region methods for solving nonlinear optimization problems over convex feasible domains. These methods are distinguished by the fact that they do not enforce strict monotonicity of the objective function values at successive iterates. The algorithms are proved to be convergent to critical points of the problem from any starting point. Extensive numerical experiments show that this approach is competitive with the LANCELOT package.     

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for \(p\ge 1\)) and to assume Lipschitz continuity of the p-th derivative, then an \(\epsilon \)-approximate first-order critical point can be computed in at most \(O(\epsilon ^{-(p+1)/p})\) evaluations of the problem’s objective function and its derivatives. This generalizes and subsumes results known for \(p=1\) and \(p=2\).     

Updating the regularization parameter in the adaptive cubic regularization algorithm

The adaptive cubic regularization method (Cartis et al. in Math. Program. Ser. A 127(2):245?C295, 2011; Math. Program. Ser. A. 130(2):295?C319, 2011) has been recently proposed for solving unconstrained minimization problems. At each iteration of this method, the objective function is replaced by a cubic approximation which comprises an adaptive regularization parameter whose role is related to the local Lipschitz constant of the objective??s Hessian. We present new updating strategies for this parameter based on interpolation techniques, which improve the overall numerical performance of the algorithm. Numerical experiments on large nonlinear least-squares problems are provided.     

Recent progress in unconstrained nonlinear optimization without derivatives

We present an introduction to a new class of derivative free methods for unconstrained optimization. We start by discussing the motivation for such methods and why they are in high demand by practitioners. We then review the past developments in this field, before introducing the features that characterize the newer algorithms. In the context of a trust region framework, we focus on techniques that ensure a suitable “geometric quality” of the considered models. We then outline the class of algorithms based on these techniques, as well as their respective merits. We finally conclude the paper with a discussion of open questions and perspectives. Current reports available by anonymous ftp from the directory “pub/reports” on thales.math.fundp.ac.be. WWW: http://www.fundp.ac.be/ phtoint/pht/publications.html.     

Using approximate secant equations in limited memory methods for multilevel unconstrained optimization

The properties of multilevel optimization problems defined on a hierarchy of discretization grids can be used to define approximate secant equations, which describe the second-order behavior of the objective function. Following earlier work by Gratton and Toint (2009) we introduce a quasi-Newton method (with a linesearch) and a nonlinear conjugate gradient method that both take advantage of this new second-order information. We then present numerical experiments with these methods and formulate recommendations for their practical use.