On a class of hybrid methods for smooth constrained optimization

With reference to smooth nonlinearly constrained optimization problems, we consider combinations of locally superlinearly convergent methods with globally convergent ones. The aim of this paper is threefold: to give a survey on well-known as well as possible unknown hybrid optimization methods, based on a special construction principle; to present a general convergence result for the class of hybrid algorithms; and to derive further methods for this class with new convergence properties.The authors thank the anonymous referees for their useful suggestions.     

Quadratic multiplier method convergence

In a recent paper (Ref. 1), the author briefly mentioned a variant of Hestenes' method of multipliers which would converge quadratically. This note examines that method in detail and provides some examples. In the quadratic-linear case, this algorithm converges in one iteration.     

On the accelerating property of an algorithm for function minimization without calculating derivatives

It is shown that the alogrithm of Ref. E1, when converging on a uniformly convex function and when technical condition (13) of Ref. E1 is satisfied, has ann-iterationQ-superlinear rate of convergence and a behaviour which is a precursor of every-iterationQ-superlinearity. This result overrides and corrects main result Theorem 3.1 of Ref. E1.     

On the accelerating property of an algorithm for function minimization without calculating derivatives

This paper studies the speed of convergence of a general algorithm for function minimization without calculating derivatives. This algorithm contains Powell's 1964 algorithm as well as Zangwill's second modification of this procedure. The main results are Theorems 3.1 and 4.1 which show that, if the algorithm behaves well, then asymptotically almost conjugate directions are built; therefore, the algorithm has an every-iteration superlinear speed of convergence. The paper hinges on ideas of McCormick and Ritter and Powell.The authors wish to thank the Namur Department of Mathematics, especially its optimization group, for many discussions and encouragements. The authors also thank the reviewer for many helpful suggestions.     

A combined penalty function and gradient projection method for nonlinear programming

A new programming algorithm for nonlinear constrained optimization problems is proposed. The method is based on the penalty function approach and thereby circumyents the necessity to maintain feasibility at each iteration, but it also behaves much like the gradient projection method. Although only first-order information is used, the algorithm converges asymptotically at a rate which is independent of the magnitude of the penalty term; hence, unlike the simple gradient method, the asymptotic rate of the proposed method is not affected by the ill-conditioning associated with the introduction of the penalty term. It is shown that the asymptotic rate of convergence of the proposed method is identical with that of the gradient projection method.Dedicated to Professor M. R. HestenesThis research was supported by the National Science Foundation, Grant No. GK-16125.     

On the entropic perturbation and exponential penalty methods for linear programming

This note points out that the recently proposed exponential penalty approach to linear programming is identical to the well-known entropic perturbation approach. The primal and dual trajectories provided by these two approaches are shown to be equivalent.The work of the first author was supported partially by the North Carolina Supercomputing Center and 1995 Cray Research Grant.     

On the convergence of the exponential multiplier method for convex programming

In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy proximal term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive the convergence rate of these methods when applied to linear programs.Research supported by the National Science Foundation under Grant DDM-8903385, and the Army Research Office under Grant DAAL03-86-K-0171.     

Primal and dual convergence of a proximal point exponential penalty method for linear programming

We consider the diagonal inexact proximal point iteration where f(x,r)=c ^T x+r∑exp[(A _i x-b _i )/r] is the exponential penalty approximation of the linear program min{c ^T x:Ax≤b}. We prove that under an appropriate choice of the sequences λ _k , ε _k and with some control on the residual ν ^k , for every r _k →0⁺ the sequence u ^k converges towards an optimal point u ^∞ of the linear program. We also study the convergence of the associated dual sequence μ _i ^k =exp[(A _i u ^k -b _i )/r _k ] towards a dual optimal solution. Received: May 2000 / Accepted: November 2001?Published online June 25, 2002     

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).     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

An accelerated multiplier method for nonlinear programming

This paper describes an accelerated multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems. The unconstrained problems are solved using a rank-one recursive algorithm described in an earlier paper. Multiplier estimates are obtained by minimizing the error in the Kuhn-Tucker conditions using a quadratic programming algorithm. The convergence of the sequence of unconstrained problems is accelerated by using a Newton-Raphson extrapolation process. The numerical effectiveness of the algorithm is demonstrated on a relatively large set of test problems.This work was supported by the US Air Force under Contract No. F04701-74-C-0075.     

An economic interpretation of exact penalty functions using sensitivity analysis

It has already been demonstrated that under some assumptions, a local minimum of a constrained problem is also a local unconstrained minimum of a function which is called an exact penalty function. Here, we present the same result with a new demonstration. By using sensitivity analysis, we give an economic interpretation for exact penalty functions.     

不等式约束优化问题的低阶精确罚函数的光滑化算法

对不等式约束优化问题提出了一个低阶精确罚函数的光滑化算法. 首先给出了光滑罚问题、非光滑罚问题及原问题的目标函数值之间的误差估计,进而在弱的假
设之下证明了光滑罚问题的全局最优解是原问题的近似全局最优解. 最后给出了一个基于光滑罚函数的求解原问题的算法,证明了算法的收敛性,并给出数值算例说明算法的可行性.     

The role of the multipliers in the multiplier method

The paper studies the role of the multipliers when the multiplier method is applied as a computational technique for minimizing penalized cost functionals for optimal control problems characterized by linear systems and integral quadratic costs.Theauthor would like to gratefully thank two anonymous referees for many helpful suggestions which led to a major improvement in both the quality and clarity of the paper, and to Professor Angelo Miele for his encouragement.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.     

A convergence theory for a class of anti-jamming strategies

A convergence theory for a class of anti-jamming strategies for nonlinear programming algorithms is presented. This theory generalizes previous results in this area by Zoutendijk, Topkis and Veinott, Mangasarian, and others; it is applicable to algorithms in which the anti-jamming parameter is fixed at some positive value as well as to algorithms in which it tends to zero. In addition, under relatively weak hypotheses, convergence of the entire sequence of iterates is proved.This research was sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

Exact penalty function algorithm with simple updating of the penalty parameter

A new globally convergent algorithm for minimizing an objective function subject to equality and inequality constraints is presented. The algorithm determines a search direction by solving a quadratic programming subproblem, which always has an optimal solution, and uses an exact penalty function to compute the steplength along this direction through an Armijo-type scheme. The special structure of the quadratic subproblem is exploited to construct a new and simple method for updating the penalty parameter. This method may increase or reduce the value of the penalty parameter depending on some easily performed tests. A new method for updating the Hessian of the Lagrangian is presented, and a Q-superlinear rate of convergence is established.This work was supported in part by the British Council and the Conselho Nacional de Desenvolvimento Cientifico & Tecnologico/CNPq, Rio de Janeiro, Brazil.The authors are very grateful to Mr. Lam Yeung for his invaluable assistance in computing the results and to a reviewer for constructive advice.     

On a characterization of convergence for the Hestenes method of multipliers

The connection between the convergence of the Hestenes method of multipliers and the existence of augmented Lagrange multipliers for the constrained minimum problem (P): minimizef(x), subject tog(x)=0, is investigated under very general assumptions onX,f, andg.In the first part, we use the existence of augmented Lagrange multipliers as a sufficient condition for the convergence of the algorithm. In the second part, we prove that this is also a necessary condition for the convergence of the method and the boundedness of the sequence of the multiplier estimates.Further, we give very simple examples to show that the existence of augmented Lagrange multipliers is independent of smoothness condition onf andg. Finally, an application to the linear-convex problem is given.     

A penalty function approach for solving bi-level linear programs

The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.     

Properties of updating methods for the multipliers in augmented Lagrangians

The convergence properties of different updating methods for the multipliers in augmented Lagrangians are considered. It is assumed that the updating of the multipliers takes place after each line search of a quasi-Newton method. Two of the updating methods are shown to be linearly convergent locally, while a third method has superlinear convergence locally. Modifications of the algorithms to ensure global convergence are considered. The results of a computational comparison with other methods are presented.This work was supported by the Swedish Institute of Applied Mathematics.