非线性规划问题的精确增广Lagrange函数

对于一般的非线性规划给出一种精确增广Lagrange函数,并讨论其性质.无需假设严格互补条件成立,给出了原问题的局部极小点与增广Lagrange函数在原问题的变量空间上的局部极小的关系.进一步,在适当的假设条件下,建立了两者的全局最优解之间的关系.     

对等式约束非线性规划问题的Hestenes-Powell增广拉格朗日函数的进一步研究

本文对用无约束极小化方法求解等式约束非线性规划问题的Hestenes-Powell 增广拉格朗日函数作了进一步研究．在适当的条件下,我们建立了Hestenes-Powell增广拉格朗日函数在原问题变量空间上的无约束极小与原约束问题的解之间的关系,并且也给出了Hestenes-Powell增广拉格朗日函数在原问题变量和乘子变量的积空间上的无约束极小与原约束问题的解之间的一个关系．因此,从理论的观点来看,原约束问题的解和对应的拉格朗日乘子值不仅可以用众所周知的乘子法求得,而且可以通过对Hestenes-Powell 增广拉格朗日函数在原问题变量和乘子变量的积空间上执行一个单一的无约束极小化来获得．     

一个修正的罚函数方法

本文通过给出的一个修正的罚函数,把约束非线性规划问题转化为无约束非线性规划问题.我们讨论了原问题与相应的罚问题局部最优解和全局最优解之间的关系,并给出了乘子参数和罚参数与迭代点之间的关系,最后给出了一个简单算法,数值试验表明算法是有效的.     

一族精确罚函数的存在性及控制参数的下界

本文讨论了非线性等式与不等式约束的优化问题的一族比较广的精确罚函数的存在性,不需凸性及任何约束规格的假设,证明了当罚参数充分大后,惩罚问题的(严格)局部极小点是原问题的(严格)局部极小点,惩罚问题的全局极小点是原问题的最优解,并给出控制参数的一个下界。     

带新NCP函数的Lagrangian乘子方法

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

一类新的Lagrangian乘子法

本文提出了求解光滑不等式约束最优化问题新的乘子法,在增广Lagrangian函数中,使用了新的NCP函数的乘子法．该方法在增广Lagrangian函数和原问题之间存在很好的等价性;同时该方法具有全局收敛性,且在适当假设下,具有超线性收敛率．本文给出了一个有效选择参数C的方法．     

从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性

增广Lagrange方法是求解非线性规划的一种有效方法.从一新的角度证明不等式约束非线性非光滑凸优化问题的增广Lagrange方法的收敛性.用常步长梯度法的收敛性定理证明基于增广Lagrange函数的对偶问题的常步长梯度方法的收敛性,由此得到增广Lagrange方法乘子迭代的全局收敛性.     

求解线性规划的极大熵方法

极大熵方法是求解多约束非线性规划和极大极小问题的一种有效的方法.用它来求解多约束优化问题,一种途径是将多约束用单约束近似,再用增广Lagrange乘子法求解近似问题;另一种途径是用极大熵方法构造精确罚函数的近似.无论是哪一种途径都需要估计乘子的上界.能否构造不引入乘子估计的算法是很有意义的.Karmarkar算法是求解线性规划的一种有效的多项式内点方法.这种方法在每一次迭代时都要作变换,在像空间用内切球近似单纯形的近似问题得到像空间的新的近似解,再作逆变换求得原空间的新的近似解.可见一次性地构造近似问题并求解之而得     

一个解不等式约束非线性规划问题的有效方法

本文提出了一个解不等式约束非线性规划问题有效方法．在这个方法中,考虑解一个等价Ｋｕｈｎ－Ｔｕｃｋｅｒ条件的非线性方程组．这个方程组中ＮＣＰ函数的使用消去了对应于不等式约束的Ｌａｇｒａｎｇｅ乘子的非负性．截断牛顿方法被用来解这个非线性方程组．为了保证全局收敛性,一个强健的损失函数被选为寻查函数,同时方法中插入修正最速下降方向．本文证明了方法的分Ｑ－二阶收敛性,同时指出新方法可以有效地解稀疏大规模非线性规划问题。     

关于约束极小化问题的一个新的简单精确罚函数

针对等式及不等式约束极小化问题,通过对原问题添加一个变量,给出一个新的简单精确罚函数,即在该精确罚函数表达式中,不含有目标函数及约束函数的梯度．在满足某些约束品性的条件下,可以证明:当罚参数充分大时,所给出的罚问题的局部极小点是原问题的局部极小点．     

An Exact Augmented Lagrangian Function for Nonlinear Programming with Two-Sided Constraints

This paper is aimed toward the definition of a new exact augmented Lagrangian function for two-sided inequality constrained problems. The distinguishing feature of this augmented Lagrangian function is that it employs only one multiplier for each two-sided constraint. We prove that stationary points, local minimizers and global minimizers of the exact augmented Lagrangian function correspond exactly to KKT pairs, local solutions and global solutions of the constrained 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.     

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.     

New results on a class of exact augmented Lagrangians

In this paper, a new continuously differentiable exact augmented Lagrangian is introduced for the solution of nonlinear programming problems with compact feasible set. The distinguishing features of this augmented Lagrangian are that it is radially unbounded with respect to the multiplier and that it goes to infinity on the boundary of a compact set containing the feasible region. This allows one to establish a complete equivalence between the unconstrained minimization of the augmented Lagrangian on the product space of problem variables and multipliers and the solution of the constrained problem.The author wishes to thank Dr. L. Grippo for having suggested the topic of this paper and for helpful discussions.     

Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).