Exact Penalty Function Methods and Their Applications in Search Engine Advertising Problems

In this thesis, primarily inspired by W. Huyer and A. Neumair' work (W. Huyer and A. Neumair. A New Exact Penalty Function. SIAM Journal on Optimization, 13: 1141-1159, 2003), we propose a new class of smooth exact penalty functions for the nonlinear programming prpblems, which includes a unified framework both barrier-type and exterior-type penalty functions as special cases. We develop necessary and sufficient conditions for exact penalty property and local exactness properties, respectively. Furthermore, utilizing these conditions, we characterize the equivalence between the class of penalty functions and the classical simple exact penalty functions in the sense of exactness property. Based on the class of penalty functions, a class of feasible penalty function algorithms are presented. Under certain conditions, we present that the proposed algorithm terminates at the optimal solution to the primal problem after finite iterations and while under mild assumptions, the algorithm possesses globally convergent property. In addition, we design and apply new smooth and exact penalty functions for tackling the semi-infinite programming problems and the min-max programming problems. Here, the merit function is considered as a function of x and epsilon simultaneously which has good smoothness and exactness properties, without involving gradient and Jacobian matrices. We derive another useful property that the minimizer (x☆, epsilon☆) of the penalty problem satisfies epsilon☆ = 0 if and only if x☆ solves the original problem. This property demonstrates that the introduced new variable epsilon can be viewed as an indicator variable of a local (global) minimizer of primal problem. For the semi-infinite programming and min-max programming problems, the local exactness proofs are also shown. Furthermore, the second-order sufficient conditions for the local exactness properties are characterized for the proposed exact and smooth penalty function. As important applications, we solve an increasingly popular search engine advertising problem which stems from the online advertising auction via the new proposed penalty function. In addition, we give numerical simulations to address managerial insights on both operational and theoretical aspects and compare the numerical performances with currently existing algorithms for search engine advertising problems.