Exact Penalty Methods In Nonlinear Programming

Constrained nonlinear programming problems abound in many important fields such as engineering, national defence, finance etc. One of the main approaches for solving constrained nonlinear programming problems is to transform it into unconstrained nonlinear programming problem. Penalty function methods and Lagrangian duality methods are the two prevailing approaches to implement the transformation. Penalty function methods seek to obtain the solutions of constrained programming problem by solving one or more penalty problems. If each minimum of the penalty problem is a minimum of the primal constrained programming problem, then the corresponding penalty function is called exact penalty function. In this thesis, we discuss global exact penalty property of l1 exact penalty function, smoothing of l1 exact penalty function, local exact penalty property and global exact penalty property of lower order penalty function, smoothing of lower order penalty function, the relationship between k-calm conditions and exact penalty property, exact penalty functions in integer programming.The present thesis is organized as follows. In Chapter 1, we give a brief introduction to the existing research work on exact penalty functions. In Chapter 2, we discuss the global exact penalty property of l1 exact penalty function and its smoothing. Under the following assumptions: 1. the objective function satisfies the coercive conditions; 2. there are only finite global minima of the primal constrained nonlinear programming problem; 3. KKT second order sufficiency condition of the primal constrained nonlinear programming problem holds at its any global minimum, we establish the global exact penalty property, i.e. the set of global minima of the primal constrained nonlinear programming problem is identical to the set of global minima of the l1 exact penalty problem. Since the l1 exact penalty function is not differential, generally speaking, optimization techniques employing gradient can not be used directly to solve the l1 exact penalty problem. To avoid this drawback, we propose a quadratic smoothing approximation to the l1 exact penalty function. It is shown that if there exists at least one global minimum of the primal problem in the quasi-interior of the feasible region of the primal problem, then any global minimum of the smoothed penalty problem is a global minimum of the primal problem when the penalty parameter is sufficiently large. If the feasible region of the primal problem is quasi-robust, then any global minimum of the smoothed penalty problem is a feasible approximate global minimum of the primal problem when the penalty parameter is sufficiently large, and the precision of the approximation can be set in advance. The following numerical examples show that it is applicable to solve the smoothed penalty problem in order to solve the primal problem.In Chapter 3, we firstly introduce lower order penalty function. Under the KKT second order sufficiency condition, we obtain the local exact penalty property, i.e. any local minimum satisfying the KKT second order sufficiency condition is a strict local minimum of the lower order penalty function, and the penalty parameter can be any positive number. Then, under the same three assumptions as in Chapter 2 mentioned above, we obtain the global exact penalty property, i.e. the set ofglobal minima of the primal constrained nonlinear programming problem is identical to the set of global minima of the lower order exact penalty problem. As the l1 exact penalty function, the lower order exact penalty function is not differential. Thus we present a quadratic smoothing approximation to the lower order exact penalty function, and obtain similar results to these obtained in the smoothing approximation in Chapter 2.In Chapter 4, we firstly give the definition of k-calm condition at a point for the primal problem, and then obtain the sufficient and necessary condition for a local minimum of the primal problem to be k-calm. Next we give the definition of k-calm condition at (0,0) æ‹¢ Rm x R...