Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/5672
Title: Exact penalty function methods and their applications in search engine advertising problems
Authors: Ma, Cheng
Keywords: Hong Kong Polytechnic University -- Dissertations
Nonlinear programming.
Mathematical optimization.
Issue Date: 2012
Publisher: The Hong Kong Polytechnic University
Abstract: The penalty function method is one of the most fundamental and useful tools in the modern optimization and has developed into a major research field since 1950s. The study of penalty functions has proliferated in many interesting areas within mathematical optimization society. Nowadays, researchers in optimization fields still pursue unremittingly new breakthroughs in theoretical and algorithmic aspects of penalty function methods. However, it should be mentioned that the currently existing exact penalty functions have a disadvantage that the evaluation of the merit function either needs Jacobian (e.g., augumented Lagrangian penalty functions) or is no longer smooth (l1 or l∞ penalty functions). "It would be a major theoretic breakthrough in nonlinear programming if a simple continuously differentiable function could be exhibited with the property that any unconstrained minimum is a solution of the constrained problem."Evans, Gould and Tolle [21]. So far, to some extent, the breakthrough of the above quotation has been achieved. Recently, Huyer and Neumair in [38] proposed a new exact and smooth penalty function through adding an auxiliary variable ε to deal with equality constrained minimization problem. The proposed new penalty function enjoys several good properties: (1) good smoothness and exactness properties; (2) bounded below under reasonable conditions; (3) combination of regularization with penalty techniques, which are not possessed by the classical simple and exact penalty functions. Moreover, the new penalty function only involves the information of objective function and constraints function rather than the one of gradient and Hessian matrix. Nevertheless, the new exact penalty function is different from the definition of traditional penalty function, namely, the values of penalty terms are zero on the feasible set and positive outside the feasible set. In spite of significant differences between the new penalty function and the classical simple and exact penalty functions, naturally, a question arises: What's on earth the relationship between them? In this thesis, motivated by Huyer and Neumair's work [38], we extend the norm function term of the exact penalty function in [38] to a class of convex functions with a unified framework for some barrier-types and exterior-type penalty functions. We characterize necessary and sufficient conditions for the exact penalty property. Interestingly, we also explore the equivalence between this class of penalty functions and the traditional simple exact penalty functions in the sense of exactness property. These results clarify that this class of penalty functions not only have exactness property as the classical simple penalty function, but also possess the smoothness property, which is not shared by the latter. Furthermore, since the class of penalty functions are bounded below, a revised penalty function method is established. In addition, we verify that, under certain conditions, the proposed algorithm terminates at the optimal solution of the primal problem after finitely many iterations; while in the absence of these conditions, a perturbation theorem for this algorithm can be derived. As a corollary, the global convergence property is presented-namely, every accumulation point of the sequence generated by the algorithm is an optimal solution of the primal problem. The numerical outputs verify the correctness of our developed theory as desired.
We propose a new exact and smooth penalty function for semi-infinite programming problems. The main feature of our penalty function is that we only need to add one variable ε to handle infinitely many constraints. The merit function is considered as a function of x and ε simultaneously which has good smoothness and exactness properties, without involving gradient and Jacobian matrices. We derive another useful property that the minimizer (x*,ε*) of the penalty problem satisfies ε* = 0 if and only if x* solves semi-infinite programming problem. This property demonstrates that the introduced new variable ε can be viewed as an indicator variable of a local (global) minimizer of semi-infinite programming problem. Alternatively, under some mild conditions, the local exactness proof is shown. The numerical results demonstrate that it is an effective and promising approach for solving constrained semi-infinite programming problems. Similarly, we also apply a new exact penalty function to tackle the min-max programming problem and establish necessary and sufficient conditions for the exactness property. In addition, we characterize the second-order sufficient conditions for the local exactness property. We model and explore the search-based advertising auction as a large scale integer programming problem with more realistic situations, e.g., multiple slots, advertisers with choice behavior and the popular generalized second price mechanism etc.. And then, we apply the new penalty function to this proposed integer programming. 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.
Description: xv, 129 p. : ill. ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577P AMA 2012 Ma
URI: http://hdl.handle.net/10397/5672
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b2551281x_link.htmFor PolyU Users 162 BHTMLView/Open
b2551281x_ir.pdfFor All Users (Non-printable) 1.52 MBAdobe PDFView/Open
Show full item record

Page view(s)

538
Last Week
2
Last month
Checked on Jul 16, 2017

Download(s)

305
Checked on Jul 16, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.