Files in this item
Files  Description  Format 

application/pdf YuChing_Lee.pdf (7MB)  (no description provided) 
Description
Title:  Global solution to parametric complementarity constrained programs and applications in optimal parameter selection 
Author(s):  Lee, YuChing 
Director of Research:  Pang, JongShi 
Doctoral Committee Chair(s):  Pang, JongShi 
Doctoral Committee Member(s):  Nedich, Angelia; Sreenivas, Ramavarapu S.; Su, CheLin 
Department / Program:  Industrial&Enterprise Sys Eng 
Discipline:  Industrial Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Optimization
Parameter selection Mathematical program with complementarity constraints Global optimization algorithm Support vector machine regression Pure characteristics demand model 
Abstract:  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 uniparametric, biparametric, and multiparametric 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 BiParametric Linear Complementarity Constrained Linear Programs, we study a specific type of the LPCC which we term a biparametric LPCC. Reformulating the biparametric LPCC as a nonconvex quadratically constrained program, we develop a domainpartitioning 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 biparametric space. Numerical results of the algorithm are presented. An important application of biparametric LPCC is the Crossvalidated 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 crossvalidated parameter selection procedure can be formulated as a bilevel optimization problem, which then is equivalently reformulated as an LPCC. In Chapter 3, we propose a twostage 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 realworld 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 discretechoice 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, elementbyelement inverse, and homotopy methods. These methods, however, are timeconsuming 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 NashBertrand 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. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42414 
Rights Information:  Copyright 2012 YuChing Lee 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Industrial and Enterprise Systems Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois