Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

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     

An exact penalty function for semi-infinite programming

This paper introduces a global approach to the semi-infinite programming problem that is based upon a generalisation of the ℓ₁ exact penalty function. The advantages are that the ensuing penalty function is exact and the penalties include all violations. The merit function requires integrals for the penalties, which provides a consistent model for the algorithm. The discretization is a result of the approximate quadrature rather than an a priori aspect of the model. This research was partially supported by Natural Sciences and Engineering Research Council of Canada grants A-8639 and A-8442. This paper was typeset using software developed at Bell Laboratories and the University of California at Berkeley.     

Stability in the presence of degeneracy and error estimation

Received February 10, 1997 / Revised version received June 6, 1998 Published online October 9, 1998     

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.     

On the exactness of a class of nondifferentiable penalty functions

In this paper, we consider a class of nondifferentiable penalty functions for the solution of nonlinear programming problems without convexity assumptions. Preliminarily, we introduce a notion of exactness which appears to be of relevance in connection with the solution of the constrained problem by means of unconstrained minimization methods. Then, we show that the class of penalty functions considered is exact, according to this notion. This research was partially supported by the National Research Program on “Modelli e Algoritmi per l'Ottimizzazione,” Ministero della Pubblica, Istruzione, Roma, Italy.     

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

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

Discretization in semi-infinite programming: the rate of convergence

The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary and for generalized semi-infinite problems. Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

An exact lower order penalty function and its smoothing in nonlinear programming

In this article, we consider a lower order penalty function and its ε-smoothing for an inequality constrained nonlinear programming problem. It is shown that any strict local minimum satisfying the second-order sufficiency condition for the original problem is a strict local minimum of the lower order penalty function with any positive penalty parameter. By using an ε-smoothing approximation to the lower order penalty function, we get a modified smooth global exact penalty function under mild assumptions.     

Nonlinear programming algorithms using trust regions and augmented Lagrangians with nonmonotone penalty parameters

The strategy for obtaining global convergence is based on the trust region approach. The merit function is a type of augmented Lagrangian. A new updating scheme is introduced for the penalty parameter, by means of which monotone increase is not necessary. Global convergence results are proved and numerical experiments are presented. Received May 31, 1995 / Revised version received December 12, 1997 Published online October 21, 1998     

Failure of global convergence for a class of interior point methods for nonlinear programming

Using a simple analytical example, we demonstrate that a class of interior point methods for general nonlinear programming, including some current methods, is not globally convergent. It is shown that those algorithms produce limit points that are neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed problem. Received: December 1999 / Accepted: May 2000?Published online August 18, 2000     

On the convexity of the multiplicative potential and penalty functions and related topics

It is well known that a function f of the real variable x is convex if and only if (x,y)→yf(y ^-1 x),y>0 is convex. This is used to derive a recursive proof of the convexity of the multiplicative potential function. In this paper, we obtain a conjugacy formula which gives rise, as a corollary, to a new rule for generating new convex functions from old ones. In particular, it allows to extend the aforementioned property to functions of the form (x,y)→g(y)f(g(y)^-1 x) and provides a new tool for the study of the multiplicative potential and penalty functions. Received: June 3, 1999 / Accepted: September 29, 2000?Published online January 17, 2001     

On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms

In this paper, the author studies a Broyden-like method for solving nonlinear equations with nondifferentiable terms, which uses as updating matrices, approximations for Jacobian matrices of differentiable terms. Local and semilocal convergence theorems are proved. The results generalize those of Broyden, Dennis and Moré.     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

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 convergence of the Gauss-Newton method for convex composite optimization

The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h. Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001     

Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

The asymptotic convergence of parameterized variants of Newton’s method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable path leading to a solution of the original system, the scalar parameter determining the progress along the path. A path-following algorithm, which involves an inner iteration in which the perturbed systems are approximately solved, is outlined. It is shown that asymptotically, a single linear system is solved per update of the scalar parameter. It turns out that a componentwise Q-superlinear rate may be attained, both in the direct error and in the residuals, under standard assumptions, and that this rate may be made arbitrarily close to quadratic. Numerical experiments illustrate the results and we discuss the relationships that this method shares with interior methods in constrained optimization. Received: September 8, 2000 / Accepted: September 17, 2001?Published online February 14, 2002     

Superlinear and quadratic convergence of affine-scaling interior-point Newton methods for problems with simple bounds without strict complementarity assumption

A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally q–superlinear or q–quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67, 189–224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence analysis is given. A simple example is presented to illustrate the pitfalls of the original approach by Coleman and Li in the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper. Received October 2, 1998 / Revised version received April 7, 1999?Published online July 19, 1999     

Continuity properties of the Karush-Kuhn-Tucker point set in quadratic programming problems

Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998