We build a variety of customer booking choice models for a major airline that operates in a very competitive origin-destination market. Some of the models are aimed at incorporating unobserved heterogeneous customer preferences for different departure times. The estimation results show that including these factors into choice models dramatically affects price sensitivity estimates, and therefore matters. We present a stochastic trust region algorithm for estimating ML-type models that involve high-dimensional integrals. The algorithm embeds two sampling processes: (i) a data sampling process and (ii) a Monte Carlo sampling process, and the algorithm dynamically controls sample sizes based on the magnitude of the errors incurred due to the two sampling processes. The first-order convergence is proved based on generalized uniform law of large numbers theories for both the average log-likelihood function and its gradient. The efficiency of the algorithm is tested with real data and compared with existing algorithms. We also study how a specific behavioral phenomenon, called the decoy effect, affects the decisions of sellers in product assortment competition in a duopoly. We propose a discrete choice model to capture decoy effects, and we provide a complete characterization of the Nash equilibria and their dependence on choice model parameters. For the cases in which there are multiple equilibria, we consider dynamical systems models of the sellers responding to their competitors using Cournot adjustment or fictitious play to study the evolution of the assortment competition and the stability of the equilibria. We provide a simple geometric characterization of the dynamics of fictitious play for 2×2 games that is more complete than previous characterizations.

Kernel methods are a popular choice in solving a number of problems in statistical machine learning. In this thesis, we propose new methods for two important kernel based classification problems: 1) learning from highly unbalanced large-scale datasets and 2) selecting a relevant subset of input features for a given kernel specification. The first problem is known as the rare class problem, which is characterized by a highly skewed or unbalanced class distribution. Unbalanced datasets can introduce significant bias in standard classification methods. In addition, due to the increase of data in recent years, large datasets with millions of observations have become commonplace. We propose an approach to address both the problem of bias and computational complexity in rare class problems by optimizing area under the receiver operating characteristic curve and by using a rare class only kernel representation, respectively. We justify the proposed approach theoretically and computationally. Theoretically, we establish an upper bound on the difference between selecting a hypothesis from a reproducing kernel Hilbert space and a hypothesis space which can be represented using a subset of kernel functions. This bound shows that for a fixed number of kernel functions, it is optimal to first include functions corresponding to rare class samples. We also discuss the connection of a subset kernel representation with the Nystrom method for a general class of regularized loss minimization methods. Computationally, we illustrate that the rare class representation produces statistically equivalent test error results on highly unbalanced datasets compared to using the full kernel representation, but with significantly better time and space complexity. Finally, we extend the method to rare class ordinal ranking, and apply it to a recent public competition problem in health informatics. The second problem studied in the thesis is known as the feature selection problem in literature. Embedding feature selection in kernel classification leads to a non-convex optimization problem. We specify a primal formulation and solve the problem using a second-order trust region algorithm. To improve efficiency, we use the two-block Gauss-Seidel method, breaking the problem into a convex support vector machine subproblem and a non-convex feature selection subproblem. We reduce possibility of saddle point convergence and improve solution quality by sharing an explicit functional margin variable between block iterates. We illustrate how our algorithm improves upon state-of-the-art methods.

Universiẗat, Diss., 2004--Würzburg. / Erscheinungsjahr an der Haupttitelstelle: 2003.

Cardiovascular diseases form one of the most dangerous events that affect human life. They are usually the result of high blood pressure. Thus controlling blood pressure within patient specific healthy limits is a goal that we must target. There are two control loops for blood haemostasis inside the body either long term or short term. Baroreceptors control the short term blood pressure regulation. They are nerve endings that exist in certain locations within the blood vessel walls and they report blood pressure into the brain and the central nervous system. However the basics of their function are not yet known. We propose here that the baroreceptors work by converting circumferential and axial pressure into a stress into their respective direction and they start to send nerve signals based on a threshold of strain energy of the location they are embedded in. Thus baroreceptors A fibre is highly likely to exist in the stiffer adventitia, while the media will contain C fibres. This explains the reason behind having identical fibres with different threshold. We were able to arrive to this solution by getting a relationship between stress–strain relationship for the whole wall and for the arterial vessels. These findings are quiet significant as they allow a method to identify different stress in the arterial wall layers using whole wall experimental data and also as they were able to differentiate between different fibres based on their locations inside the arterial wall. A complete modelling of the baroreceptors function might lead to the formation of biosynthetic material that could interact with the body on the cellular level, so as to give humans the mean to the control of short term blood regulation thus preventing hypertension and its accompanying diseases such as atherosclerosis.

Cette thèse se concentre sur l'étude d'un algorithme multi niveaux de régions de confiance en norme infinie, conçu pour la résolution de problèmes d'optimisation non linéaires de grande taille pouvant être soumis a des contraintes de bornes. L'étude est réalisée tant sur le plan théorique que numérique. L'algorithme RMTR8 que nous étudions ici a été élaboré a partir de l'algorithme présente par Gratton, Sartenaer et Toint (2008b), et modifie d'abord en remplaçant l'usage de la norme Euclidienne par une norme infinie, et ensuite en l'adaptant a la résolution de problèmes de minimisation soumis a des contraintes de bornes. Dans un premier temps, les spécificités du nouvel algorithme sont exposées et discutées. De plus, l'algorithme est démontré globalement convergent au sens de Conn, Gould et Toint (2000), c'est-a-dire convergent vers un minimum local au départ de tout point admissible. D'autre part, il est démontre que la propriété d'identification des contraintes actives des méthodes de régions de confiance basées sur l'utilisation d'un point de Cauchy peut être étendue a tout solveur interne respectant une décroissance suffisante. En conséquence, cette propriété d'identification est aussi respectée par une variante particulière du nouvel algorithme. Par la suite, nous étudions différents critères d'arrêt pour les algorithmes d'optimisation avec contraintes de bornes afin de déterminer le sens et les avantages de chacun, et ce pour pouvoir choisir aisément celui qui convient le mieux a certaines situations. En particulier, les critères d'arrêts sont analyses en termes d'erreur inverse (backward erreur), tant au sens classique du terme (avec l'usage d'une norme produit) que du point de vue de l'optimisation multicritères. Enfin, un algorithme pratique est mis en place, utilisant en particulier une technique similaire au lissage de Gauss-Seidel comme solveur interne. Des expérimentations numériques sont réalisées sur une version FORTRAN 95 de l'algorithme. Elles permettent d'une part de définir un panel de paramètres efficaces par défaut et, d'autre part, de comparer le nouvel algorithme a d'autres algorithmes classiques d'optimisation, comme la technique de raffinement de maillage ou la méthode du gradient conjugue, sur des problèmes avec et sans contraintes de bornes. Ces comparaisons numériques semblent donner l'avantage à l'algorithme multi niveaux, en particulier sur les cas peu non-linéaires, comportement attendu de la part d'un algorithme inspire des techniques multi grilles. En conclusion, l'algorithme de région de confiance multi niveaux présente dans cette thèse est une amélioration du précédent algorithme de cette classe d'une part par l'usage de la norme infinie et d'autre part grâce a son traitement de possibles contraintes de bornes. Il est analyse tant sur le plan de la convergence que de son comportement vis-à-vis des bornes, ou encore de la définition de son critère d'arrêt. Il montre en outre un comportement numérique prometteur. / This thesis concerns the study of a multilevel trust-region algorithm in infinity norm, designed for the solution of nonlinear optimization problems of high size, possibly submitted to bound constraints. The study looks at both theoretical and numerical sides. The multilevel algorithm RMTR8 that we study has been developed on the basis of the algorithm created by Gratton, Sartenaer and Toint (2008b), which was modified first by replacing the use of the Euclidean norm by the infinity norm and also by adapting it to solve bound-constrained problems. In a first part, the main features of the new algorithm are exposed and discussed. The algorithm is then proved globally convergent in the sense of Conn, Gould and Toint (2000), which means that it converges to a local minimum when starting from any feasible point. Moreover, it is shown that the active constraints identification property of the trust-region methods based on the use of a Cauchy step can be extended to any internal solver that satisfies a sufficient decrease property. As a consequence, this identification property also holds for a specific variant of our new algorithm. Later, we study several stopping criteria for nonlinear bound-constrained algorithms, in order to determine their meaning and their advantages from specific points of view, and such that we can choose easily the one that suits best specific situations. In particular, the stopping criteria are examined in terms of backward error analysis, which has to be understood both in the usual meaning (using a product norm) and in a multicriteria optimization framework. In the end, a practical algorithm is set on, that uses a Gauss-Seidel-like smoothing technique as an internal solver. Numerical tests are run on a FORTRAN 95 version of the algorithm in order to define a set of efficient default parameters for our method, as well as to compare the algorithm with other classical algorithms like the mesh refinement technique and the conjugate gradient method, on both unconstrained and bound-constrained problems. These comparisons seem to give the advantage to the designed multilevel algorithm, particularly on nearly quadratic problems, which is the behavior expected from an algorithm inspired by multigrid techniques. In conclusion, the multilevel trust-region algorithm presented in this thesis is an improvement of the previous algorithm of this kind because of the use of the infinity norm as well as because of its handling of bound constraints. Its convergence, its behavior concerning the bounds and the definition of its stopping criteria are studied. Moreover, it shows a promising numerical behavior.

The Trust Region Subproblem (TRS), which minimizes a nonconvex quadratic function over the unit ball, is an important subproblem in trust region methods for nonlinear optimization. Even though TRS is a nonconvex problem, it can be solved in polynomial time using, for example, a semidefinite programming (SDP) relaxation. Different variants of TRS have been considered from both theoretical and practical perspectives. In this thesis, we study three variants of TRS and their SDP/conic relaxations. We first study an extended trust region subproblem (eTRS) in which the trust region equals the intersection of the unit ball with M linear cuts. When m = 0, when m = 1, or when m = 2 and the linear cuts are parallel, it is known that the eTRS optimal value equals the optimal value of a particular conic relaxation, which is solvable in polynomial time. However, it is also known that, when m ≥2 and at least two of the linear cuts intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same conic relaxation may admit a gap with eTRS. We show that the conic relaxation admits no gap for arbitrary M as long as the linear cuts are non-intersecting. We then extend our result to a more general setting. We study an eTRS in which a quadratic function is minimized over a structured nonconvex feasible region: the unit ball with M linear cuts and R hollows. In the special case when m = 0 and r = 1, it is known that the eTRS has a tight polynomial-time solvable conic relaxation. We show that a certain conic relaxation is also tight for general R and M as long as the cuts and hollows satisfy some non-intersecting assumptions that generalize the previous paragraph. Finally, intersecting the feasible region of TRS with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing approaches do not provide a concise conic relaxation. We investigate the use of conic relaxation for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid second-order-cone (SOC) inequalities. For the special case of TTRS in dimension n=2, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the SOC inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when n > 2 to solve TTRS instances that were previously unsolved using techniques of conic relaxation.

The research presented in this dissertation investigates the use of all-at-once methods applied to aerodynamic design. All-at-once schemes are usually based on the assumption of sufficient continuity in the constraints and objectives, and this assumption can be troublesome in the presence of shock discontinuities. Special treatment has to be considered for such problems and we study several approaches. Our all-at-once methods are based on the Sequential Quadratic Programming method, and are designed to exploit the structure inherent in a given problem. The first method is a Reduced Hessian formulation which projects the optimization problem to a lower dimension design space. The second method exploits the sparse structure in a given problem which can yield significant savings in terms of computational effort as well as storage requirements. An underlying theme in all our applications is that careful analysis of the given problem can often lead to an efficient implementation of these all-at-once methods. Chapter 2 describes a nozzle design problem involving one-dimensional transonic flow. An initial formulation as an optimal control problem allows us to solve the problem as as two-point boundary problem which provides useful insight into the nature of the problem. Using the Reduced Hessian formulation for this problem, we find that a conventional CFD method based on shock capturing produces poor performance. The numerical difficulties caused by the presence of the shock can be alleviated by reformulating the constraints so that the shock can be treated explicitly. This amounts to using a shock fitting technique. In Chapter 3, we study variants of a simplified temperature control problem. The control problem is solved using a sparse SQP scheme. We show that for problems where the underlying infinite-dimensional problem is well-posed, the optimizer performs well, whereas it fails to produce good results for problems where the underlying infinite-dimensional problem is ill-posed. A transonic airfoil design problem is studied in Chapter 4, using the Reduced SQP formulation. We propose a scheme for performing the optimization subtasks that is based on an Euler Implicit time integration scheme. The motivation is to preserve the solution-finding structure used in the analysis algorithm. Preliminary results obtained using this method are promising. Numerical results have been presented for all the problems described. / Ph. D.

No description available.

L’optimisation sans dérivées (OSD) a connu un regain d’intérêt ces dernières années, principalement motivée par le besoin croissant de résoudre les problèmes d’optimisation définis par des fonctions dont les valeurs sont calculées par simulation (par exemple, la conception technique, la restauration d’images médicales ou de nappes phréatiques).Ces dernières années, un certain nombre de méthodes d’optimisation sans dérivée ont été développées et en particulier des méthodes fondées sur un modèle de région de confiance se sont avérées obtenir de bons résultats.Dans cette thèse, nous présentons un nouvel algorithme de région de confiance, basé sur l’interpolation, qui se montre efficace et globalement convergent (en ce sens que sa convergence vers un point stationnaire est garantie depuis tout point de départ arbitraire). Le nouvel algorithme repose sur la technique d’auto-correction de la géométrie proposé par Scheinberg and Toint (2010). Dans leur théorie, ils ont fait avancer la compréhension du rôle de la géométrie dans les méthodes d’OSD à base de modèles. Dans notre travail, nous avons pu améliorer considérablement l’efficacité de leur méthode, tout en maintenant ses bonnes propriétés de convergence. De plus, nous examinons l’influence de différents types de modèles d’interpolation sur les performances du nouvel algorithme.Nous avons en outre étendu cette méthode pour prendre en compte les contraintes de borne par l’application d’une stratégie d’activation. Considérer une méthode avec ensemble actif pour l’optimisation basée sur des modèles d’interpolation donne la possibilité d’économiser une quantité importante d’évaluations de fonctions. Il permet de maintenir les ensembles d’interpolation plus petits tout en poursuivant l’optimisation dans des sous-espaces de dimension inférieure. L’algorithme résultant montre un comportement numérique très compétitif. Nous présentons des résultats sur un ensemble de problèmes-tests issu de la collection CUTEr et comparons notre méthode à des algorithmes de référence appartenant à différentes classes de méthodes d’OSD.Pour réaliser des expériences numériques qui intègrent le bruit, nous créons un ensemble de cas-tests bruités en ajoutant des perturbations à l’ensemble des problèmes sans bruit. Le choix des problèmes bruités a été guidé par le désir d’imiter les problèmes d’optimisation basés sur la simulation. Enfin, nous présentons des résultats sur une application réelle d’un problème de conception de forme d’une aile fourni par Airbus. / Derivative-free optimization (DFO) has enjoyed renewed interest over the past years, mostly motivated by the ever growing need to solve optimization problems defined by functions whose values are computed by simulation (e.g. engineering design, medical image restoration or groundwater supply).In the last few years, a number of derivative-free optimization methods have been developed and especially model-based trust-region methods have been shown to perform well.In this thesis, we present a new interpolation-based trust-region algorithm which shows to be efficient and globally convergent (in the sense that its convergence is guaranteed to a stationary point from arbitrary starting points). The new algorithm relies on the technique of self-correcting geometry proposed by Scheinberg and Toint [128] in 2009. In their theory, they advanced the understanding of the role of geometry in model-based DFO methods, in our work, we improve the efficiency of their method while maintaining its good theoretical convergence properties. We further examine the influence of different types of interpolation models on the performance of the new algorithm.Furthermore, we extended this method to handle bound constraints by applying an active-set strategy. Considering an active-set method in bound-constrained model-based optimization creates the opportunity of saving a substantial amount of function evaluations. It allows to maintain smaller interpolation sets while proceeding optimization in lower dimensional subspaces. The resulting algorithm is shown to be numerically highly competitive. We present results on a test set of smooth problems from the CUTEr collection and compare to well-known state-of-the-art packages from different classes of DFO methods.To report numerical experiments incorporating noise, we create a test set of noisy problems by adding perturbations to the set of smooth problems. The choice of noisy problems was guided by a desire to mimic simulation-based optimization problems. Finally, we will present results on a real-life application of a wing-shape design problem provided by Airbus.

In this thesis an algorithm (MLOPT) for mixed logit models is proposed. Mixed logit models are flexible discrete choice models, but their estimation with large datasets involves the solution of a nonlinear optimization problem with a high dimensional integral in the objective function, which is the log-likelihood function. This complex structure is a general problem that occurs in statistics and optimization. MLOPT uses sampling from the dataset of individuals to generate a data sample. In addition to this, Monte Carlo samples are used to generate an integration sample to estimate the choice probabilities. MLOPT estimates the log-likelihood function values for each individual in the dataset by controlling and adaptively changing the data sample and the size of the integration sample at each iteration. Furthermore, MLOPT incorporates statistical testing for the quality of the solution obtained within the optimization problem. MLOPT is tested with a benchmark study from the literature (AMLET) and further applied to real-life applications in the automotive industry by predicting market shares in the Low Segment of the new car market. The automotive industry is particularly interesting in that understanding the behavior of buyers and how rebates affect their preferences is very important for revenue management. Real transaction data is used to generate and test the mixed logit models developed in this study. Another new aspect of this study is that the sales transactions are differentiated with respect to the transaction type of the purchases made. These mixed logit models are used to estimate demand and analyze market share changes under different what-if scenarios. An analysis and discussion of the results obtained are also presented.