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

Optimization;Parameter selection;Mathematical program with complementarity constraints;Global optimization algorithm;Support vector machine regression;Pure characteristics demand model

Lee, Yu-Ching

关键词: Optimization;    Parameter selection;    Mathematical program with complementarity constraints;    Global optimization algorithm;    Support vector machine regression;    Pure characteristics demand model;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/42414/Yu-Ching_Lee.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This thesis contains five chapters. The notations, terminologies, definitions and numbering of equations, theorems and algorithmsare independent in each chapter.Chapter 1 provides a fundamental introduction and contextual discussions to provide a unified theme for the subsequentchapters 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 basictechniques 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 isfollowed 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, inverseoptimization, is defined in this chapter.A linear program with linear complementarity constraints (LPCC) is among the simplest mathematical programs with complementarityconstraints. 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 aspecific type of the LPCC which we term a bi-parametric LPCC. Reformulating the bi-parametric LPCC as a non-convex quadraticallyconstrained program, we develop a domain-partitioning algorithm that solves a series of linear subprograms and/or convex quadraticallyconstrained subprograms obtained by the relaxations of the complementarity constraint. We control the domain on which the partitioningis 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 ParametersSelection Problem. The Support vector machine regression is a robust regression method to minimize the sum of deductedresiduals, 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 validationtechnique to gain better forecasts. The cross-validated parameterselection 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 explicitlyidentifying the edges of the regions on the parameter plane. This algorithm is tested on syntheticand 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 bya 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 superiorto the conventional methods for estimating PCM. The framework of this mathematical program also allows the extension to deal with broader scopesof market level data. In addition to the observed market share considered in the literature, we introduce a Nash-Bertrand game to reflectthe 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 mathematicalprogram belongs to the class of quadratic programs with nonlinear complementarity constraints. Three variations of the PCM estimation models aredeveloped and validated by synthetic numerical experiments.