Michaël Clément Louis Ghislain Thémans
In this thesis, we focus on standard classes of problems in numerical optimization: unconstrained nonlinear optimization as well as systems of nonlinear equations. More precisely, we consider two types of unconstrained nonlinear optimization problems. On the one hand, we are interested in solving problems whose second derivatives matrix is singular at a local minimum. On the other hand, we focus on the identification of a global minimum of problems which present several local minima. The increasing use of simulation tools in real applications requires solving more and more complicated problems of these classes. The main goal of this thesis is the development of efficient numerical methods, based on trust-region and filter frameworks, able to find the solution of such problems in a limited number of function evaluations. Indeed, the algorithmic developments we present have been motivated by real transportation applications in which the objective function is usually cumbersome to evaluate. The specific nonlinear optimization problems mentioned above are encountered in the estimation of discrete choice models while systems of nonlinear equations have to be solved in the context of Dynamic Traffic Management Systems (DTMS). We also dedicate a part of this dissertation to the challenging task of human behavior modeling in the context of DTMS. First we propose a new trust-region algorithm and a new filter algorithm to solve singular unconstrained nonlinear problems. A characterization of the singularity at a local minimum is described and we present an iterative procedure which allows to identify a singularity in the objective function during the execution of the optimization algorithm. Our trust-region based algorithms make use of information on the singularity by adopting a penalty approach. Numerical results provide evidence that our approaches require less function evaluations to solve singular problems compared to classical trust-region algorithms from the literature. The CPU time to find a solution is also significantly decreased when the problem is singular. Second we present a new heuristic designed for nonlinear global optimization, based on the variable neighborhood search from discrete optimization within which we use a trust-region algorithm from nonlinear optimization as local search procedure. The algorithm we propose is able to prematurely stop the local search as soon as it does not look promising. The neighborhoods and the neighbors selection are based on information about the curvature of the objective function. Intensive numerical tests illustrate that our method is able to significantly reduce the average number of function evaluations compared to existing heuristics in the literature of nonlinear global optimization. Important improvements are also obtained in terms of success rate as well as CPU time. Third we design a new secant method for systems of nonlinear equations. The proposed algorithm uses a population of previous iterates and the linear model of the system is calibrated using a least squares approach. We also propose two globalization techniques for quasi-Newton methods in this context, namely a linesearch framework and a linesearch-filter approach. Our algorithm exhibits a faster convergence as well as a better robustness compared to secant methods from the literature. Globalization strategies are shown to highly increase the robustness of considered secant methods. Moreover, the combination of our algorithm with these strategies gives rise to an algorithmic method which is competitive with Newton-Krylov methods both in terms of robustness and efficiency. Fourth we present a real application of discrete choice models in the context of DTMS. The models are designed to capture the response of Swiss drivers to real-time traffic information. We are interested in drivers' decisions in terms of both route and mode choices when traffic information is available before the trip starts while we focus on route choice when traffic information is available during the trip. The "en-route" model is a mixture of binary logit model with panel data while "pre-trip" models are nested logit models. These models are estimated with the BIOGEME software developed by Bierlaire (2003). Estimation results are deeply analyzed and discussed, and models are implemented in a simulator which predicts drivers' behavior in specific scenarii. We conclude this thesis by a review of the main results and we make some comments about promising tracks for future research.
EPFL2007
