Exact penalty function methods and their applications in search engine advertising problems

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.