Convergence Analysis of a Class of Nonlinear Penalization Methods for Constrained Optimization via First-Order Necessary Optimality Conditions

We propose a scheme to solve constrained optimization problems by combining a nonlinear penalty method and a descent method. A sequence of nonlinear penalty optimization problems is solved to generate a sequence of stationary points, i.e., each point satisfies a first-order necessary optimality condition of a nonlinear penalty problem. Under some conditions, we show that any limit point of the sequence satisfies the first-order necessary condition of the original constrained optimization problem.     

A New Trust-Region Algorithm for Equality Constrained Optimization

We present a new trust-region algorithm for solving nonlinear equality constrained optimization problems. Quadratic penalty functions are employed to obtain global convergence. At each iteration a local change of variables is performed to improve the ability of the algorithm to follow the constraint level set. Under certain assumptions we prove that this algorithm globally converges to a point satisfying the second-order necessary optimality conditions. Results of preliminary numerical experiments are reported.     

Lower-Order Penalization Approach to Nonlinear Semidefinite Programming

In this paper, we reformulate a nonlinear semidefinite programming problem into an optimization problem with a matrix equality constraint. We apply a lower-order penalization approach to the reformulated problem. Necessary and sufficient conditions that guarantee the global (local) exactness of the lower-order penalty functions are derived. Convergence results of the optimal values and optimal solutions of the penalty problems to those of the original semidefinite program are established. Since the penalty functions may not be smooth or even locally Lipschitz, we invoke the Ekeland variational principle to derive necessary optimality conditions for the penalty problems. Under certain conditions, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original semidefinite program. Communicated by Y. Zhang This work was supported by a Postdoctoral Fellowship of Hong Kong Polytechnic University and by the Research Grants Council of Hong Kong.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

A Sequential Smooth Penalization Approach to Mathematical Programs with Complementarity Constraints

In this paper, a mathematical program with complementarity constraints (MPCC) is reformulated as a nonsmooth constrained mathematical program via the Fischer–Burmeister function. Smooth penalty functions are used to treat this nonsmooth constrained program. Under linear independence constraint qualification, and upper level strict complementarity condition, together with some other mild conditions, we prove that the limit point of stationary points satisfying second-order necessary conditions of unconstrained penalized problems is a strongly stationary point, hence a B-stationary point of the original MPCC. Furthermore, this limit point also satisfies a second-order necessary condition of the original MPCC. Numerical results are presented to test the performance of this method.     

Convergence Analysis of a Class of Penalty Methods for Vector Optimization Problems with Cone Constraints

In this paper, we consider convergence properties of a class of penalization methods for a general vector optimization problem with cone constraints in infinite dimensional spaces. Under certain assumptions, we show that any efficient point of the cone constrained vector optimization problem can be approached by a sequence of efficient points of the penalty problems. We also show, on the other hand, that any limit point of a sequence of approximate efficient solutions to the penalty problems is a weekly efficient solution of the original cone constrained vector optimization problem. Finally, when the constrained space is of finite dimension, we show that any limit point of a sequence of stationary points of the penalty problems is a KKT stationary point of the original cone constrained vector optimization problem if Mangasarian–Fromovitz constraint qualification holds at the limit point.This work is supported by the Postdoctoral Fellowship of Hong Kong Polytechnic University.     

Using negative curvature in solving nonlinear programs

Minimization methods that search along a curvilinear path composed of a non-ascent negative curvature direction in addition to the direction of steepest descent, dating back to the late 1970s, have been an effective approach to finding a stationary point of a function at which its Hessian is positive semidefinite. For constrained nonlinear programs arising from recent applications, the primary goal is to find a stationary point that satisfies the second-order necessary optimality conditions. Motivated by this, we generalize the approach of using negative curvature directions from unconstrained optimization to equality constrained problems and prove that our proposed negative curvature method is guaranteed to converge to a stationary point satisfying second-order necessary conditions.     

A Unified Approach to the Global Exactness of Penalty and Augmented Lagrangian Functions I: Parametric Exactness

In this two-part study, we develop a unified approach to the analysis of the global exactness of various penalty and augmented Lagrangian functions for constrained optimization problems in finite-dimensional spaces. This approach allows one to verify in a simple and straightforward manner whether a given penalty/augmented Lagrangian function is exact, i.e., whether the problem of unconstrained minimization of this function is equivalent (in some sense) to the original constrained problem, provided the penalty parameter is sufficiently large. Our approach is based on the so-called localization principle that reduces the study of global exactness to a local analysis of a chosen merit function near globally optimal solutions. In turn, such local analysis can be performed with the use of optimality conditions and constraint qualifications. In the first paper, we introduce the concept of global parametric exactness and derive the localization principle in the parametric form. With the use of this version of the localization principle, we recover existing simple, necessary, and sufficient conditions for the global exactness of linear penalty functions and for the existence of augmented Lagrange multipliers of Rockafellar–Wets’ augmented Lagrangian. We also present completely new necessary and sufficient conditions for the global exactness of general nonlinear penalty functions and for the global exactness of a continuously differentiable penalty function for nonlinear second-order cone programming problems. We briefly discuss how one can construct a continuously differentiable exact penalty function for nonlinear semidefinite programming problems as well.     

非线性约束优化的光滑化平方根罚函数

介绍一种非线性约束优化的不可微平方根罚函数,为这种非光滑罚函数提出了一个新的光滑化函数和对应的罚优化问题,获得了原问题与光滑化罚优化问题目标之间的误差估计. 基于这种罚函数,提出了一个算法和收敛性证明,数值例子表明算法对解决非线性约束优化具有有效性.     

A unifying theory of exactness of linear penalty functions II: parametric penalty functions

In this article, we develop a general theory of exact parametric penalty functions for constrained optimization problems. The main advantage of the method of parametric penalty functions is the fact that a parametric penalty function can be both smooth and exact unlike the standard (i.e. non-parametric) exact penalty functions that are always nonsmooth. We obtain several necessary and/or sufficient conditions for the exactness of parametric penalty functions, and for the zero duality gap property to hold true for these functions. We also prove some convergence results for the method of parametric penalty functions, and derive necessary and sufficient conditions for a parametric penalty function to not have any stationary points outside the set of feasible points of the constrained optimization problem under consideration. In the second part of the paper, we apply the general theory of exact parametric penalty functions to a class of parametric penalty functions introduced by Huyer and Neumaier, and to smoothing approximations of nonsmooth exact penalty functions. The general approach adopted in this article allowed us to unify and significantly sharpen many existing results on parametric penalty functions.     

无罚函数和滤子的QP-free非可行域方法

提出了求解光滑不等式约束最优化问题的无罚函数和无滤子QP-free非可行域方法. 通过乘子和非线性互补函数, 构造一个等价于原约束问题一阶KKT条件的非光滑方程组. 在此基础上, 通过牛顿-拟牛顿迭代得到满足KKT最优性条件的解, 在迭代中采用了无罚函数和无滤子线搜索方法, 并证明该算法是可实现,具有全局收敛性. 另外, 在较弱条件下可以证明该方法具有超线性收敛性.     

Second-Order Smoothing Objective Penalty Function for Constrained Optimization Problems

In this article, a novel objective penalty function as well as its second-order smoothing is introduced for constrained optimization problems (COP). It is shown that an optimal solution to the second-order smoothing objective penalty optimization problem is an optimal solution to the original optimization problem under some mild conditions. Based on the second-order smoothing objective penalty function, an algorithm that has better convergence is introduced. Numerical examples illustrate that this algorithm is efficient in solving COP.     

Second-order invex functions in nonlinear programming

We introduce a notion of a second-order invex function. A Fréchet differentiable invex function without any further assumptions is second-order invex. It is shown that the inverse claim does not hold. A Fréchet differentiable function is second-order invex if and only if each second-order stationary point is a global minimizer. Two complete characterizations of these functions are derived. It is proved that a quasiconvex function is second-order invex if and only if it is second-order pseudoconvex. Further, we study the nonlinear programming problem with inequality constraints whose objective function is second-order invex. We introduce a notion of second-order type I objective and constraint functions. This class of problems strictly includes the type I invex ones. Then we extend a lot of sufficient optimality conditions with generalized convex functions to problems with second-order type I invex objective function and constraints. Additional optimality results, which concern type I and second-order type I invex data are obtained. An answer to the question when a kernel, which is not identically equal to zero, exists is given.     

A Unified Approach for Constrained Extremum Problems: Image Space Analysis

In this paper, by exploiting the image space analysis we investigate a class of constrained extremum problems, the constraining function of which is set-valued. We show that a (regular) linear separation in the image space is equivalent to the existence of saddle points of Lagrangian and generalized Lagrangian functions and we also give Lagrangian type optimality conditions for the class of constrained extremum problems under suitable generalized convexity and compactness assumptions. Moreover, we consider an exact penalty problem for the class of constrained extremum problems and prove that it is equivalent to the existence of a regular linear separation under suitable generalized convexity and compactness assumptions.     

A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties

We present a null-space primal-dual interior-point algorithm for solving nonlinear optimization problems with general inequality and equality constraints. The algorithm approximately solves a sequence of equality constrained barrier subproblems by computing a range-space step and a null-space step in every iteration. The ℓ₂ penalty function is taken as the merit function. Under very mild conditions on range-space steps and approximate Hessians, without assuming any regularity, it is proved that either every limit point of the iterate sequence is a Karush-Kuhn-Tucker point of the barrier subproblem and the penalty parameter remains bounded, or there exists a limit point that is either an infeasible stationary point of minimizing the ℓ ₂ norm of violations of constraints of the original problem, or a Fritz-John point of the original problem. In addition, we analyze the local convergence properties of the algorithm, and prove that by suitably controlling the exactness of range-space steps and selecting the barrier parameter and Hessian approximation, the algorithm generates a superlinearly or quadratically convergent step. The conditions on guaranteeing that all slack variables are still positive for a full step are presented.     

Proximal Point Methods for Lipschitz Functions on Hadamard Manifolds: Scalar and Vectorial Cases

In the second part of our study, we introduce the concept of global extended exactness of penalty and augmented Lagrangian functions, and derive the localization principle in the extended form. The main idea behind the extended exactness consists in an extension of the original constrained optimization problem by adding some extra variables, and then construction of a penalty/augmented Lagrangian function for the extended problem. This approach allows one to design extended penalty/augmented Lagrangian functions having some useful properties (such as smoothness), which their counterparts for the original problem might not possess. In turn, the global exactness of such extended merit functions can be easily proved with the use of the localization principle presented in this paper, which reduces the study of global exactness to a local analysis of a merit function based on sufficient optimality conditions and constraint qualifications. We utilize the localization principle in order to obtain simple necessary and sufficient conditions for the global exactness of the extended penalty function introduced by Huyer and Neumaier, and in order to construct a globally exact continuously differentiable augmented Lagrangian function for nonlinear semidefinite programming problems.     

Nonlinear Lagrange Duality Theorems and Penalty Function Methods In Continuous Optimization

We propose a general dual program for a constrained optimization problem via generalized nonlinear Lagrangian functions. Our dual program includes a class of general dual programs with explicit structures as special cases. Duality theorems with the zero duality gap are proved under very general assumptions and several important corollaries which include some known results are given. Using dual functions as penalty functions, we also establish that a sequence of approximate optimal solutions of the penalty function converges to the optimal solution of the original optimization problem.     

Augmented Lagrangian Objective Penalty Function

Augmented Lagrangian function is one of the most important tools used in solving some constrained optimization problems. In this article, we study an augmented Lagrangian objective penalty function and a modified augmented Lagrangian objective penalty function for inequality constrained optimization problems. First, we prove the dual properties of the augmented Lagrangian objective penalty function, which are at least as good as the traditional Lagrangian function's. Under some conditions, the saddle point of the augmented Lagrangian objective penalty function satisfies the first-order Karush-Kuhn-Tucker condition. This is especially so when the Karush-Kuhn-Tucker condition holds for convex programming of its saddle point existence. Second, we prove the dual properties of the modified augmented Lagrangian objective penalty function. For a global optimal solution, when the exactness of the modified augmented Lagrangian objective penalty function holds, its saddle point exists. The sufficient and necessary stability conditions used to determine whether the modified augmented Lagrangian objective penalty function is exact for a global solution is proved. Based on the modified augmented Lagrangian objective penalty function, an algorithm is developed to find a global solution to an inequality constrained optimization problem, and its global convergence is also proved under some conditions. Furthermore, the sufficient and necessary calmness condition on the exactness of the modified augmented Lagrangian objective penalty function is proved for a local solution. An algorithm is presented in finding a local solution, with its convergence proved under some conditions.     

带新NCP函数的Lagrangian乘子方法

在经营管理、工程设计、科学研究、军事指挥等方面普遍存在着最优化问题,而实际问题中出现的绝大多数问题都被归纳为非线性规划问题之中。作为带等式、不等式约束的复杂事例,最优化问题的求解向来较为繁琐、困难。适当条件下,非线性互补函数(NCP)可以与约束优化问题相结合,其中NCP函数的无约束极小解对应原约束问题的解及其乘子。本文提出了一类新的NCP函数用于解决等式和不等式约束非线性规划问题,结合新的NCP函数构造了增广Lagrangian函数。在适当假设条件下,证明了增广Lagrangian函数与原问题的解之间的一一对应关系。同时构造了相应算法,并证明了该算法的收敛性和有效性。     

A sequential quadratic penalty method for nonlinear semidefinite programming

In this article, a nonlinear semidefinite program is reformulated into a mathematical program with a matrix equality constraint and a sequential quadratic penalty method is proposed to solve the latter problem. We discuss the differentiability and convexity of the penalty function. Necessary and sufficient conditions for the convergence of optimal values of penalty problems to that of the original semidefinite program are obtained. The convergence of optimal solutions of penalty problems to that of the original semidefinite program is also investigated. We show that any limit point of a sequence of stationary points of penalty problems satisfies the KKT optimality condition of the semidefinite program. Smoothed penalty problems that have the same order of smothness as the original semidefinite program are adopted. Corresponding results such as the convexity of the smoothed penalty function, the convergence of optimal values, optimal solutions and the stationary points of the smoothed penalty problems are obtained.