Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems

In this paper, some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences {x _k } convergingq-superlinearly to the solution. Furthermore, under mild assumptions, aq-quadratic convergence rate inx is also attained. Other features of these algorithms are that only the solution of linear systems of equations is required at each iteration and that the strict complementarity assumption is never invoked. First, the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied, and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle, and Wang is given.This research was supported by the National Research Program Metodi di Ottimizzazione per la Decisioni, MURST, Roma, Italy.     

Two-step and three-step Q-superlinear convergence of SQP methods

This paper investigates the convergence rates of the variable-multiplier pair (x, ) in sequential quadratic programming methods for equality constrained optimization. The two main results of the paper are that the Q-superlinear convergence of {x _k } implies two-step Q-superlinear convergence for {(x _k , _k )} and that the two-step Q-superlinear convergence of {x _k } implies three-step Q-superlinear convergence for {(x _k , _k )}.The author is indebted to Professor Richard Tapia for many helpful comments and suggestions on the paper. The comments by Professors A. R. Conn and N. I. M. Gould on an earlier version are also acknowledged. This research was funded by SERC and ESRC research contracts.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Some Convergence Properties of Descent Methods

In this paper, we discuss the convergence properties of a class of descent algorithms for minimizing a continuously differentiable function f on R ⁿ without assuming that the sequence { x _k } of iterates is bounded. Under mild conditions, we prove that the limit infimum of is zero and that false convergence does not occur when f is convex. Furthermore, we discuss the convergence rate of { } and { f(x _k )} when { x _k } is unbounded and { f(x _k )} is bounded.     

An interior point method, based on rank-1 updates, for linear programming

We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd ^k andv ^k rather than a primal—dual interior point (x ^k ,s ^k ), where and fori = 1, 2,,n. Only one element ofd ^k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx ^k ands ^k are not needed explicitly in the algorithm, whereasd ^k andv ^k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x ^k, s^k) and (d ^k, v^k) with improving primal—dual potential function values. Moreover, no approximation ofd ^k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Convergence properties of local solutions of sequences of mathematical programming problems in general spaces

This paper gives several sets of sufficient conditions that alocal solutionx ^k exists of the problem \(\min _{R^k } f^k (x)\) ,k=1, 2,..., such that {x ^k } has cluster points that arelocal solutions of a problem of the form min _R f(x). The results are based on a well-known concept of topological, orpoint-wise convergence of the sets {R ^k } toR. Such results have been used to construct and validate large classes of mathematical programming methods based on successive approximations of the problem functions. They are also directly applicable to parametric and sensitivity analysis and provide additional characterizations of optimality for large classes of nonlinear programming problems.     

On Minimizing and Stationary Sequences of a New Class of Merit Functions for Nonlinear Complementarity Problems

Motivated by the work of Fukushima and Pang (Ref. 1), we study the equivalent relationship between minimizing and stationary sequences of a new class of merit functions for nonlinear complementarity problems (NCP). These merit functions generalize that obtained via the squared Fischer–Burmeister NCP function, which was used in Ref. 1. We show that a stationary sequence {x^k} /Reⁿ is a minimizing sequence under the condition that the function value sequence {F(x ^k)} is bounded above or the Jacobian matrix sequence {F(x ^k)} is bounded, where F is the function involved in NCP. The latter condition is also assumed by Fukushima and Pang. The converse is true under the assumption of {F(x ^k)} bounded. As an example shows, even for a bounded function F, the boundedness of the sequence {F(x ^k)} is necessary for a minimizing sequence to be a stationary sequence.     

Proximity control in bundle methods for convex nondifferentiable minimization

Proximal bundle methods for minimizing a convex functionf generate a sequence {x ^k } by takingx ^k+1 to be the minimizer of , where is a sufficiently accurate polyhedral approximation tof andu ^k > 0. The usual choice ofu ^k = 1 may yield very slow convergence. A technique is given for choosing {u ^k } adaptively that eliminates sensitivity to objective scaling. Some encouraging numerical experience is reported.This research was supported by Project CPBP.02.15.     

Disguised and new quasi-Newton methods for nonlinear eigenvalue problems

In this paper, we take a quasi-Newton approach to nonlinear eigenvalue problems (NEPs) of the type M(λ)v =?0, where \(M:\mathbb {C}\rightarrow \mathbb {C}^{n\times n}\) is a holomorphic function. We investigate which types of approximations of the Jacobian matrix lead to competitive algorithms, and provide convergence theory. The convergence analysis is based on theory for quasi-Newton methods and Keldysh’s theorem for NEPs. We derive new algorithms and also show that several well-established methods for NEPs can be interpreted as quasi-Newton methods, and thereby, we provide insight to their convergence behavior. In particular, we establish quasi-Newton interpretations of Neumaier’s residual inverse iteration and Ruhe’s method of successive linear problems.     

On the Superlinear Convergence Order of the Logarithmic Barrier Algorithm

Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter r_k +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if r_k+1=r _k with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods.     

The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization

The BFGS method is the most effective of the quasi-Newton methods for solving unconstrained optimization problems. Wei, Li, and Qi [16] have proposed some modified BFGS methods based on the new quasi-Newton equation B _k+1 s _k = y* _k , where y* _k is the sum of y _k and A _k s _k, and A _k is some matrix. The average performance of Algorithm 4.3 in [16] is better than that of the BFGS method, but its superlinear convergence is still open. This article proves the superlinear convergence of Algorithm 4.3 under some suitable conditions.     

Sparse quasi-Newton updates with positive definite matrix completion

Quasi-Newton methods are powerful techniques for solving unconstrained minimization problems. Variable metric methods, which include the BFGS and DFP methods, generate dense positive definite approximations and, therefore, are not applicable to large-scale problems. To overcome this difficulty, a sparse quasi-Newton update with positive definite matrix completion that exploits the sparsity pattern of the Hessian is proposed. The proposed method first calculates a partial approximate Hessian , where , using an existing quasi-Newton update formula such as the BFGS or DFP methods. Next, a full matrix H _k+1, which is a maximum-determinant positive definite matrix completion of , is obtained. If the sparsity pattern E (or its extension F) has a property related to a chordal graph, then the matrix H _k+1 can be expressed as products of some sparse matrices. The time and space requirements of the proposed method are lower than those of the BFGS or the DFP methods. In particular, when the Hessian matrix is tridiagonal, the complexities become O(n). The proposed method is shown to have superlinear convergence under the usual assumptions.      

New Quasi-Newton Equation and Related Methods for Unconstrained Optimization

In unconstrained optimization, the usual quasi-Newton equation is B _k+1 s _k=y _k, where y _k is the difference of the gradients at the last two iterates. In this paper, we propose a new quasi-Newton equation, , in which is based on both the function values and gradients at the last two iterates. The new equation is superior to the old equation in the sense that better approximates ² f(x _k+1)s _k than y _k. Modified quasi-Newton methods based on the new quasi-Newton equation are locally and superlinearly convergent. Extensive numerical experiments have been conducted which show that the new quasi-Newton methods are encouraging.     

Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions

This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say _k and _k , for which the choice _k =1 gives the Broyden family of unscaled methods, where _k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with _k 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.     

On the Posets ( \user1Wk2 , < ){\left( {{\user1{\mathcal{W}}}^{k}_{2} , < } \right)} and their Connections with Some Homogeneous Inequalities of Degree 2

A class of ranked posets {(D _h ^k , ≪)} has been recently defined in order to analyse, from a combinatorial viewpoint, particular systems of real homogeneous inequalities between monomials. In the present paper we focus on the posets D ₂ ^k , which are related to systems of the form {x _a x _b * _abcd x _c x _d : 0 ≤ a, b, c, d ≤ k, * _abcd ∈ {<, >}, 0 < x ₀ < x ₁ < ...< x _k}. As a consequence of the general theory, the logical dependency among inequalities is adequately captured by the so-defined posets . These structures, whose elements are all the D ₂ ^k 's incomparable pairs, are thoroughly surveyed in the following pages. In particular, their order ideals – crucially significant in connection with logical consequence – are characterised in a rather simple way. In the second part of the paper, a class of antichains is shown to enjoy some arithmetical properties which make it an efficient tool for detecting incompatible systems, as well as for posing some compatibility questions in a purely combinatorial fashion.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Nonlinear programming and an optimization problem on infinitely differentiable functions

A nonnegative, infinitely differentiable function ø defined on the real line is called a Friedrichs mollifier function if it has support in [0, 1] and ₀ ¹ ø(t)dt=1. In this article the following problem is considered. Determine _k =inf ₀ ¹ vø^(k)(t)dt, k=1,..., where ø^(k) denotes thekth derivative of ø and the infimum is taken over the set of all mollifier functions. This problem has applications to monotone polynomial approximation as shown by this author elsewhere. In this article, the structure of the problem of determining _k is analyzed, and it is shown that the problem is reducible to a nonlinear programming problem involving the minimization of a strictly convex function of [(k–1)/2] variables, subject to a simple ordering restriction on the variables. An optimization problem on the functions of bounded variation, which is equivalent to the nonlinear programming problem, is also developed. The results of this article and those from approximation of functions theory are applied elsewhere to derive numerical values of various mathematical quantities involved in this article, e.g., _k =k~2^2k–1 for allk=1, 2, ..., and to establish certain inequalities of independent interest. This article concentrates on problem reduction and equivalence, and not numerical value.This research was supported in part by the National Science Foundation under Grant No. GK-32712.     

Using duality to solve generalized fractional programming problems

In this paper we explore the relations between the standard dual problem of a convex generalized fractional programming problem and the partial dual problem proposed by Barros et al. (1994). Taking into account the similarities between these dual problems and using basic duality results we propose a new algorithm to directly solve the standard dual of a convex generalized fractional programming problem, and hence the original primal problem, if strong duality holds. This new algorithm works in a similar way as the algorithm proposed in Barros et al. (1994) to solve the partial dual problem. Although the convergence rates of both algorithms are similar, the new algorithm requires slightly more restrictive assumptions to ensure a superlinear convergence rate. An important characteristic of the new algorithm is that it extends to the nonlinear case the Dinkelbach-type algorithm of Crouzeix et al. (1985) applied to the standard dual problem of a generalized linear fractional program. Moreover, the general duality results derived for the nonlinear case, yield an alternative way to derive the standard dual of a generalized linear fractional program. The numerical results, in case of quadratic-linear ratios and linear constraints, show that solving the standard dual via the new algorithm is in most cases more efficient than applying directly the Dinkelbach-type algorithm to the original generalized fractional programming problem. However, the numerical results also indicate that solving the alternative dual (Barros et al., 1994) is in general more efficient than solving the standard dual.This research was carried out at the Econometric Institute, Erasmus University Rotterdam, the Netherlands and was supported by the Tinbergen Institute Rotterdam     

Convergence of the BFGS-SQP Method for Degenerate Problems

In this paper, we propose a BFGS (Broyden–Fletcher–Goldfarb–Shanno)-SQP (sequential quadratic programming) method for nonlinear inequality constrained optimization. At each step, the method generates a direction by solving a quadratic programming subproblem. A good feature of this subproblem is that it is always consistent. Moreover, we propose a practical update formula for the quasi-Newton matrix. Under mild conditions, we prove the global and superlinear convergence of the method. We also present some numerical results.