Global solution to parametric complementarity constrained programs and applications in optimal parameter selection

This thesis contains five chapters. The notations, terminologies, definitions and numbering of equations, theorems and algorithms are independent in each chapter. Chapter 1 provides a fundamental introduction and contextual discussions to provide a unified theme for the subsequent chapters into a complete work. Chapters 2, 3 and 4 are arranged for ease of reading and understanding separately. Future research directions are proposed in Chapter 5 based on our findings. Chapter 1, Parametric Complementarity Constrained Programs-- a Review of Methodologies, summarizes the basic techniques that are used in the algorithms for solving the mathematical program with complementarity constraints (MPCC), which is also referred to as the mathematical program with equilibrium constraints (MPEC) interchangeably in the chapter. We review the philosophy and main techniques behind the existing algorithms developed for solving MPEC. This background knowledge is followed by a section focusing on the methodologies for solving the specific class of problems that are uni-parametric, bi-parametric, and multi-parametric complementarity constrained. One of the main sources of the parametric complementarity constrained program, inverse optimization, is defined in this chapter. A linear program with linear complementarity constraints (LPCC) is among the simplest mathematical programs with complementarity constraints. Yet the global solution of the LPCC remains difficult to find and/or verify. In Chapter 2, Global Solution of Bi-Parametric Linear Complementarity Constrained Linear Programs, we study a specific type of the LPCC which we term a bi-parametric LPCC. Reformulating the bi-parametric LPCC as a non-convex quadratically constrained program, we develop a domain-partitioning algorithm that solves a series of linear subprograms and/or convex quadratically constrained subprograms obtained by the relaxations of the complementarity constraint. We control the domain on which the partitioning is done via a pair of scalars that define the slope and intercept of a line in the bi-parametric space. Numerical results of the algorithm are presented. An important application of bi-parametric LPCC is the Cross-validated Support Vector Machine Regression Parameters Selection Problem. The Support vector machine regression is a robust regression method to minimize the sum of deducted residuals, and thus is less sensitive to changes of data points near the regression hyperplane than the standard regression method. Two design parameters, the insensitive tube size and the weight assigned to the regression error, are selected by users via a cross validation technique to gain better forecasts. The cross-validated parameter selection procedure can be formulated as a bi-level optimization problem, which then is equivalently reformulated as an LPCC. In Chapter 3, we propose a two-stage global optimization algorithm to solve this LPCC. The algorithm exhausts invariancy regions without explicitly identifying the edges of the regions on the parameter plane. This algorithm is tested on synthetic and real-world support vector machine regression problems with up to hundreds of data points and compared with several other approaches. The resulting global optimal parameter is important and can be serve as a benchmark for any other selection of parameter values. In Chapter 4, we study an inverse optimization problem: Estimation of Pure Characteristics Demand Models. The pure characteristics demand model (PCM) is a discrete-choice model that formulates a consumer's utility of a product by a linear function on a bundle of quantitative and observed product characteristics, the product price, and one unobserved product characteristic. The estimation of PCM calculates consumer specific coefficients of the observed product characteristics so that the observed market level data, such as market shares, are appropriately reflected. This process also requires an estimation of the unobserved product characteristic. Traditional algorithms used in the economics literature include contraction mapping, element-by-element inverse, and homotopy methods. These methods, however, are time-consuming if an exact solution is required, and are limited to solving specific types of numerical examples. In this chapter, we construct a hierarchical mathematical program to formulate the estimation problem, which is a significantly superior to the conventional methods for estimating PCM. The framework of this mathematical program also allows the extension to deal with broader scopes of market level data. In addition to the observed market share considered in the literature, we introduce a Nash-Bertrand game to reflect the mechanism of firms' competition and market optimization. The objective function of this hierarchical mathematical program employs the Generalized Method of Moments (GMM) to identify the values of the unobserved product characteristics, so they are least correlated to the observed ones. The resulting mathematical program belongs to the class of quadratic programs with nonlinear complementarity constraints. Three variations of the PCM estimation models are developed and validated by synthetic numerical experiments