SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Function minimization by conjugate gradients

1964-02-01
R. Fletcher
A quadratically convergent gradient method for locating an unconstrained local minimum of a function of several variables is described. Particular advantages are its simplicity and its modest demands on storage, … A quadratically convergent gradient method for locating an unconstrained local minimum of a function of several variables is described. Particular advantages are its simplicity and its modest demands on storage, space for only three vectors being required. An ALGOL procedure is presented, and the paper includes a discussion of results obtained by its used on various test functions.
View PDF Chat

A Rapidly Convergent Descent Method for Minimization

1963-08-01
R. Fletcher , M. J. D. Powell
A powerful iterative descent method for finding a local minimum of a function of several variables is described. A number of theorems are proved to show that it always converges … A powerful iterative descent method for finding a local minimum of a function of several variables is described. A number of theorems are proved to show that it always converges and that it converges rapidly. Numerical tests on a variety of functions confirm these theorems. The method has been used to solve a system of one hundred non-linear simultaneous equations.
View PDF Chat

A new approach to variable metric algorithms

1970-03-01
R. Fletcher
An approach to variable metric algorithms has been investigated in which the linear search sub-problem no longer becomes necessary. The property of quadratic termination has been replaced by one of … An approach to variable metric algorithms has been investigated in which the linear search sub-problem no longer becomes necessary. The property of quadratic termination has been replaced by one of monotonic convergence of the eigenvalues of the approximating matrix to the inverse hessian. A convex class of updating formulae which possess this property has been established, and a strategy has been indicated for choosing a member of the class so as to keep the approximation away from both singularity and unboundedness. A FORTRAN program has been tested extensively with encouraging results.
View PDF Chat

Nonlinear programming without a penalty function

2002-01-01
R. Fletcher , Sven Leyffer

Conjugate gradient methods for indefinite systems

1976-01-01
R. Fletcher

Solving mixed integer nonlinear programs by outer approximation

1994-08-01
R. Fletcher , Sven Leyffer

Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming

2005-02-16
Yu‐Hong Dai , R. Fletcher
View PDF Chat

On the Global Convergence of a Filter--SQP Algorithm

2002-01-01
R. Fletcher , Sven Leyffer , Philippe L. Toint
A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of … A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of a penalty parameter whose adjustment can be problematic. The main point of interest is to demonstrate how convergence for NLP can be induced without forcing sufficient descent in a penalty-type merit function. The proof relates to a prototypical algorithm, within which is allowed a range of specific algorithm choices associated with the Hessian matrix representation, updating the trust region radius, and feasibility restoration.

Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming

2002-01-01
R. Fletcher , Nicholas I. M. Gould , Sven Leyffer +2 more
A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for … A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for an approximate solution of the quadratic subproblem and incorporates the safeguarding tests described in Fletcher, Leyffer, and Toint [On the Global Convergence of an SLP-Filter Algorithm, Technical Report 98/13, Department of Mathematics, University of Namur, Namur, Belgium, 1998; On the Global Convergence of a Filter-SQP Algorithm, Technical Report 00/15, Department of Mathematics, University of Namur, Namur, Belgium, 2000] is considered. It is proved that, under reasonable conditions and for every possible choice of the starting point, the sequence of iterates has at least one first-order critical accumulation point.

Local Convergence of SQP Methods for Mathematical Programs with Equilibrium Constraints

2006-01-01
R. Fletcher , Sven Leyffer , D. Ralph +1 more
Recently, nonlinear programming solvers have been used to solve a range of mathematical programs with equilibrium constraints (MPECs). In particular, sequential quadratic programming (SQP) methods have been very successful. This … Recently, nonlinear programming solvers have been used to solve a range of mathematical programs with equilibrium constraints (MPECs). In particular, sequential quadratic programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. SQP is shown to converge superlinearly under reasonable assumptions near a strongly stationary point. A number of examples are presented that show that some of the assumptions are difficult to relax.

On the Barzilai-Borwein Method

2005-07-18
R. Fletcher

Solving mathematical programs with complementarity constraints as nonlinear programs

2004-02-01
R. Fletcher , Sven Leyffer
Abstract We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to … Abstract We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to tackle large instances of MPCCs. Numerical experience on MacMPEC, a large collection of MPCC test problems is presented. Our experience indicates that sequential quadratic programming (SQP) methods are very well suited for solving MPCCs and at present outperform interior-point solvers both in terms of speed and reliability. All NLP solvers also compare very favorably to special MPCC solvers on tests published in the literature. Keywords: MPCCComplementarity constraintsNonlinear programmingSequential quadratic programmingInterior-point methods Acknowledgments This work was supported EPSRC grant GR/M59549. We are also grateful for the opportunity to using Argonne's computing resources in carrying out our comparisons. We are grateful to Stefan Scholtes, Danny Ralph and Michael Ferris for many fruitful discussions on MPCCs. Finally, we gratefully acknowledge the insightful comments of an anonymous referee who greatly improved the article. Many individuals provided help and input for the problem library. We are grateful to David Gay for sharing his AMPL expertise with us. Michal Kocvara provided help with the packaging problems. Francis Tin Loi supplied some challenging structural engineering problems. Finally, we have 'borrowed' test problems from a variety of sources but most notably from MPECLIB of Steven Dirkse. Notes *[email protected] ‡This work was carried out while the second author was at the University of Dundee. Additional informationNotes on contributorsRoger FletcherFootnote* *[email protected] Sven Leyffer,Footnote‡ ‡This work was carried out while the second author was at the University of Dundee.

Function Minimization Without Evaluating Derivatives--a Review

1965-04-01
R. Fletcher
The efficiency of methods for minimizing functions without evaluating derivatives is considered, with particular regard to three methods recently developed. A set of test functions representative of a wide range … The efficiency of methods for minimizing functions without evaluating derivatives is considered, with particular regard to three methods recently developed. A set of test functions representative of a wide range of minimization problems is proposed and is used as a basis for comparison.
View PDF Chat

Numerical Experience with Lower Bounds for MIQP Branch-And-Bound

1998-05-01
R. Fletcher , Sven Leyffer
The solution of convex mixed-integer quadratic programming (MIQP) problems with a general branch-and-bound framework is considered. It is shown how lower bounds can be computed efficiently during the branch-and-bound process. … The solution of convex mixed-integer quadratic programming (MIQP) problems with a general branch-and-bound framework is considered. It is shown how lower bounds can be computed efficiently during the branch-and-bound process. Improved lower bounds such as the ones derived in this paper can reduce the number of quadratic programming (QP) problems that have to be solved. The branch-and-bound approach is also shown to be superior to other approaches in solving MIQP problems. Numerical experience is presented which supports these conclusions.

An Ideal Penalty Function for Constrained Optimization

1975-01-01
R. Fletcher
A well known approach to constrained optimization is via a sequence of unconstrained minimization calculations applied to a penalty function. This paper shown how it is posiible to generalize Powell's … A well known approach to constrained optimization is via a sequence of unconstrained minimization calculations applied to a penalty function. This paper shown how it is posiible to generalize Powell's penelty function to solve constrained problems with both equality and inequality constraints. The resulting methods are equivalent to the Hestenes' method of multipliers, and a generalization of this to inequality constraints suggested by Rockafellar. Local duality results (not all of which have appeared before) for these methods are reviewed, with particular emphasis on those of practical importance. It is shown that various strategies for varying control parameters are possible, all of which can be viewed as Newton or Newton-like iterations applied to the dual problem. Practical strategies for guaranteeing convergence are also discussed. A wide selection of numerical evidence is reported, and the algorithms are compared both amongst themselves and with other penalty function methods. The new penalty function is well conditioned, without singularities, and it is not necessary for the control parameters to tend to infinity in order to force convergence. The rate of convergence is rapid and high accuracy is achieved in few unconstrained minimizations.; furthermore the computational effort for successive minimizations goes down rapidly. The methods are very easy to program efficiently, using an established quasi-Newton subroutine for unconstrained minimization.

New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds

2005-10-12
Yu‐Hong Dai , R. Fletcher

On the global convergence of an SLP-filter algorithm that takes EQP steps

2003-04-01
Choong Ming Chin , R. Fletcher

Semi-Definite Matrix Constraints in Optimization

1985-07-01
R. Fletcher
Positive semi-definite matrix constraints arise in a number of optimization problems in which some or all of the elements of a matrix are variables, such as the educational testing and … Positive semi-definite matrix constraints arise in a number of optimization problems in which some or all of the elements of a matrix are variables, such as the educational testing and matrix modification problems. The structure of such constraints is developed, including expressions for the normal cone, feasible directions and their application to optimality conditions. A computational framework is given within which these concepts can be exploited and which permits the quantification of second order effects. The matrix of Lagrange multipliers in this formulation is shown to have an important relationship to the characterization of the normal cone. Modifications of various iterative schemes in nonlinear programming are considered in order to develop an effective algorithm for the educational testing problem, and comparative numerical experiments are described. It is shown that a particular choice of the penalty parameter for an $l_1 $ exact penalty function is appropriate for this type of problem. The behaviour of the extreme eigenvalues (or sums thereof) of a matrix is related to the ideas of the paper, and the convexity of such functions is proved, together with expressions for subgradients.

A model algorithm for composite nondifferentiable optimization problems

1982-01-01
R. Fletcher

New iterative methods for solution of the eigenproblem

1966-12-01
W. W. Bradbury , R. Fletcher

Nonlinear programming and nonsmooth optimization by successive linear programming

1989-01-01
R. Fletcher , Eduardo Sáinz de la Maza

Hybrid Methods for Nonlinear Least Squares

1987-01-01
R. Fletcher , C. X. Xu
Journal Article Hybrid Methods for Nonlinear Least Squares Get access R. FLETCHER, R. FLETCHER Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this … Journal Article Hybrid Methods for Nonlinear Least Squares Get access R. FLETCHER, R. FLETCHER Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this author on: Oxford Academic Google Scholar C. XU C. XU Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this author on: Oxford Academic Google Scholar IMA Journal of Numerical Analysis, Volume 7, Issue 3, July 1987, Pages 371–389, https://doi.org/10.1093/imanum/7.3.371 Published: 01 July 1987 Article history Received: 20 January 1986 Revision received: 04 August 1986 Published: 01 July 1987

Variational Methods for Non-Linear Least-Squares

1985-05-01
M. Al-Baali , R. Fletcher

On the asymptotic behaviour of some new gradient methods

2005-02-08
Yu‐Hong Dai , R. Fletcher

An algorithm for composite nonsmooth optimization problems

1986-03-01
Robert S. Womersley , R. Fletcher

A limited memory steepest descent method

2011-07-20
R. Fletcher

Generalized inverse methods for the best least squares solution of systems of non-linear equations

1968-04-01
R. Fletcher
It is shown how many previous methods for the exact solution (or best least squares solution) of systems of non-linear equations are all based upon simple cases of the generalized … It is shown how many previous methods for the exact solution (or best least squares solution) of systems of non-linear equations are all based upon simple cases of the generalized inverse of the matrix of first derivatives of the equations. The general case is given and algorithms for its application are suggested, especially in the case where the matrix of first derivatives cannot be calculated. Numerical tests confirm that these algorithms extend the range of practical problems which can be solved.
View PDF Chat

An Overview of Unconstrained Optimization

1994-01-01
R. Fletcher

A New Variational Result for Quasi-Newton Formulae

1991-02-01
R. Fletcher
The recent measure function of Byrd and Nocedal [SIAM J. Numer. Anal., 26 (1989), pp. 727–739] is considered and simple proofs of some of its properties are given. It is … The recent measure function of Byrd and Nocedal [SIAM J. Numer. Anal., 26 (1989), pp. 727–739] is considered and simple proofs of some of its properties are given. It is then shown that the BFGS and DFP formulae satisfy a least change property with respect to this new measure.

A Class of Methods for Nonlinear Programming II Computational Experience

1970-01-01
R. Fletcher , SHIRLEY A. LILL

An efficient line search for nonlinear least squares

1986-03-01
M. Al-Baali , R. Fletcher

A new efficient method for locating saddle points

1981-08-01
Stephen G. Bell , James S. Crighton , R. Fletcher

Minimization of a Quadratic Function of Many Variables Subject only to Lower and Upper Bounds

1974-01-01
R. Fletcher , Marion Jackson
Methods for solving this problem are considered with particular reference to achieving maximum efficiency. A streamlined version of Fletcher's (1971) method for quadratic programming is considered and also a new … Methods for solving this problem are considered with particular reference to achieving maximum efficiency. A streamlined version of Fletcher's (1971) method for quadratic programming is considered and also a new approach based on the use of partial LDLT factorizations. Results on a wide variety of test problems indicate that the LDLT method is superior in both efficiency and error control. This method can often be expected to solve the problem in a time comparable to that required for a Choleski factorization, and always in a small multiple of this time.

Resolving degeneracy in quadratic programming

1993-09-01
R. Fletcher

Fast matrix methods for calculating the relaxation about defects in crystals

1970-11-01
M J Norgett , R. Fletcher
The authors present a method for calculating the relaxation about lattice defects which avoids the very many computations of the energy which are usually required in such calculations. The energy … The authors present a method for calculating the relaxation about lattice defects which avoids the very many computations of the energy which are usually required in such calculations. The energy of the crystal is minimized using a modified Newton-Raphson method in which the matrix of the second derivatives of the energy with respect to the relaxation coordinates is corrected after each iteration so that very rapid convergence is obtained.

An Optimal Positive Definite Update for Sparse Hessian Matrices

1995-02-01
R. Fletcher
A Hessian update is described that preserves sparsity and positive definiteness and satisfies a minimal change property. The update reduces to the BFGS update in the dense case and generalises … A Hessian update is described that preserves sparsity and positive definiteness and satisfies a minimal change property. The update reduces to the BFGS update in the dense case and generalises a recent result in [SIAM J. Nnmer. Anal., 26 (1989), pp. 727–739] relating to the Byrd and Nocedal measure function. A surprising outcome is that a sparsity projection of the inverse Hessian plays a major role. It is shown that the Hessian itself can be recovered from this information under mild assumptions. The update is computed by solving a concave programming problem derived by using the Wolfe dual. The Hessian of the dual is important and plays a similar role to the matrix Q that arises in the sparse PSB update of Toint [Math. Comp., 31 (1977), pp. 954–961]. This matrix is shown to satisfy the same structural and definiteness conditions as Toint's matrix. The update has been implemented for tridiagonal systems and some numerical experiments are described. These experiments indicate that there is potential for a significant reduction in the number of quasi-Newton iterations, but that more development is needed to obtain an efficient implementation. Solution of the variational problem by primal methods is also discussed and provides an interesting application of generalized elimination. The possibility of instability and nonexistence of a positive definite update raised by Sorensen [Math. Programming Study, 18 (1982), pp. 135–159] is still a difficulty and some remedies are discussed.

A modified Newton method for minimization

1977-11-01
R. Fletcher , T. L. Freeman

On the modification of 𝐿𝐷𝐿^{𝑇} factorizations

1974-01-01
R. Fletcher , M. J. D. Powell
A number of methods are compared for modifying an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper D upper L Superscript upper T"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>D</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>L</mml:mi> … A number of methods are compared for modifying an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L upper D upper L Superscript upper T"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mi>D</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>L</mml:mi> <mml:mi>T</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">LD{L^T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> factorization of a positive definite matrix <italic>A</italic> when a matrix of rank one is added to <italic>A</italic>. Both the efficiency and error propagation characteristics are discussed, and it is shown that a suitable method must be chosen with care. An error analysis of some of the algorithms is given which has novel features. A worked example which also illustrates error growth is presented. Extensions to the methods are desribed which enable them to be used advantageously in representing and updating positive semidefinite matrices.
View PDF Chat

Factorizing symmetric indefinite matrices

1976-01-01
R. Fletcher

First and second order conditions for a class of nondifferentiable optimization problems

1980-12-01
R. Fletcher , G. A. Watson

The Sequential Quadratic Programming Method

2010-01-01
R. Fletcher
View PDF Chat

NUMERICAL EXPERIMENTS WITH AN EXACT L1 PENALTY FUNCTION METHOD

1981-01-01
R. Fletcher

Penalty Functions

1983-01-01
R. Fletcher

Filter-type Algorithms for Solving Systems of Algebraic Equations and Inequalities

2003-01-01
R. Fletcher , Sven Leyffer

A Nonlinear Programming Problem in Statistics (Educational Testing)

1981-09-01
R. Fletcher
The educational testing problem is reviewed; it concerns a reliability coefficient which measures how reliable are the student’s total scores in an examination consisting of a number of subtests. A … The educational testing problem is reviewed; it concerns a reliability coefficient which measures how reliable are the student’s total scores in an examination consisting of a number of subtests. A lower bound on this coefficient is obtained by solving a certain nonlinear programming problem. Expressions for both first and second derivatives are given, and a scaling feature is described which enables the search for a solution to take place along feasible arcs on the boundary of the feasible region. The SOLVER method is used to generate the directions of search and numerical results are described. While an improvement over previous methods is obtained, some difficulties over slow convergence are observed in some cases and a possible explanation is given.

Methods for the solution of optimization problems

1972-04-01
R. Fletcher

A nonmonotone filter method for nonlinear optimization

2011-10-28
Chungen Shen , Sven Leyffer , R. Fletcher
View PDF Chat

Flexible retrofit design of multiproduct batch plants

1991-12-01
R. Fletcher , J. A. J. Hall , Willis Robert John

On the Stability of Null-Space Methods for KKT Systems

1997-10-01
R. Fletcher , Tom Johnson
This paper considers the numerical stability of null-space methods for Karush--Kuhn--Tucker (KKT)systems, particularly in the context of quadratic programming. The methods we consider are based on the direct elimination of … This paper considers the numerical stability of null-space methods for Karush--Kuhn--Tucker (KKT)systems, particularly in the context of quadratic programming. The methods we consider are based on the direct elimination of variables, which is attractive for solving large sparse systems. Ill-conditioning in a certain submatrix A in the system is shown to adversely affect the method insofar as it is commonly implemented. In particular, it can cause growth in the residual error of the solution, which would not normally occur if Gaussian elimination or related methods were used. The mechanism of this error growth is studied and is not due to growth in the null-space basis matrix Z, as might have been expected, but to the indeterminacy of this matrix. When LU factors of A are available it is shown that an alternative form of the method is available which avoids this residual error growth. These conclusions are supported by error analysis and Matlab experiments on some extremely ill-conditioned test problems. These indicate that the alternative method is very robust in regard to residual error growth and is unlikely to be significantly inferior to the methods based on an orthogonal basis matrix. The paper concludes with some discussion of what needs to be done when LU factors are not available.

Linear Minimax Approximation as the Limit of Best $L_p $-Approximation

1974-03-01
R. Fletcher , J. A. Grant , M. D. Hebden
Some established results concerning best $L_p $-approximations are introduced, and it is shown that a minimax approximation can generally be found as the limit of a sequence of such approximations. … Some established results concerning best $L_p $-approximations are introduced, and it is shown that a minimax approximation can generally be found as the limit of a sequence of such approximations. The values of p required, however, are too large to be practicable, and the main part of this paper is devoted to the development of an extrapolation scheme which enables minimax approximations to be predicted from best $L_p $-approximations for comparatively small values of p. Numerical evidence is presented to show that the scheme works well in practice.

Augmented Lagrangians, box constrained QP and extensions

2017-01-30
R. Fletcher
A new method is described for the solution of the box constrained convex quadratic programming (QP) problems, based on modifications of Rockafellar’s augmented Lagrangian function. A reduced function is defined … A new method is described for the solution of the box constrained convex quadratic programming (QP) problems, based on modifications of Rockafellar’s augmented Lagrangian function. A reduced function is defined by eliminating the multiplier parameter vector in a novel way. A minimizer of this function is shown to solve box-constrained QP. The function is convex and |$C^1$| piecewise quadratic, and under mild conditions it is strictly convex. Thus a Newton iteration is readily devised and easily implemented. The same Newton iteration is already well known and frequently used as a consequence of semi-smooth Newton theory, but the development here, especially the globalization scheme, is thought to be new. A nonmonotonic line search can be used to guarantee finite convergence, but often this is not required. Some important issues in regard to the line search are discussed. Successful numerical results are presented on a wide selection of large dimension test problems from various areas of application and from the CUTE test set. Some very large problems are solved in a reasonable time. Further, this method is extended to solve box constrained QPs that include a few linear equations. Encouraging numerical evidence is presented on a range of practical problems of up to 10|${}^8$| variables from various sources. Issues relating to guaranteed convergence are discussed.

On Wolfe's Method for Resolving Degeneracy in Linearly Constrained Optimization

2014-01-01
R. Fletcher
Wolfe [J. Soc. Indust. Appl. Math., 11 (1963), pp. 205--211] describes a novel and very useful method for resolving degeneracy in the Simplex method for Linear Programming (LP). The simplicity … Wolfe [J. Soc. Indust. Appl. Math., 11 (1963), pp. 205--211] describes a novel and very useful method for resolving degeneracy in the Simplex method for Linear Programming (LP). The simplicity and reliability of the method makes it an excellent choice in this author's opinion. The method is described here in the context of an active set method (ASM) format for LP. The method solves recursively generated subproblems that are smaller than the original, which contributes to efficiency. Data structures are described that enable the recursive aspect of the method to be implemented very easily with minimal storage overhead. The method is extended to solve a general form of linearly constrained optimization problem that includes quadratic programming (QP) and allows simple bounds on the variables and both equation and inequality general linear constraints. Issues of round-off error are discussed and heuristics are described that have proved to be very reliable in practice. The method is further extended to QP problems in which general linear constraints are handled as $L_1$ terms in the objective function.

A Sequential Linear Constraint Programming Algorithm for NLP

2012-01-01
R. Fletcher
A new method for nonlinear programming (NLP) using sequential linear constraint programming (SLCP) is described. Linear constraint programming (LCP) subproblems are solved by a new code using a recently developed … A new method for nonlinear programming (NLP) using sequential linear constraint programming (SLCP) is described. Linear constraint programming (LCP) subproblems are solved by a new code using a recently developed spectral gradient method for minimization. The method requires only first derivatives and avoids having to store and update approximate Hessian or reduced Hessian matrices. Globalization is provided by a trust region filter scheme. Open source production quality software is available. Results on a large selection of CUTEr test problems are presented and discussed and show that the method is reliable and reasonably efficient.

A nonmonotone filter method for nonlinear optimization

2011-10-28
Chungen Shen , Sven Leyffer , R. Fletcher
View PDF Chat

A limited memory steepest descent method

2011-07-20
R. Fletcher

The Sequential Quadratic Programming Method

2010-01-01
R. Fletcher
View PDF Chat

Local Convergence of SQP Methods for Mathematical Programs with Equilibrium Constraints

2006-01-01
R. Fletcher , Sven Leyffer , D. Ralph +1 more
Recently, nonlinear programming solvers have been used to solve a range of mathematical programs with equilibrium constraints (MPECs). In particular, sequential quadratic programming (SQP) methods have been very successful. This … Recently, nonlinear programming solvers have been used to solve a range of mathematical programs with equilibrium constraints (MPECs). In particular, sequential quadratic programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. SQP is shown to converge superlinearly under reasonable assumptions near a strongly stationary point. A number of examples are presented that show that some of the assumptions are difficult to relax.

New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds

2005-10-12
Yu‐Hong Dai , R. Fletcher

On the Barzilai-Borwein Method

2005-07-18
R. Fletcher

Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming

2005-02-16
Yu‐Hong Dai , R. Fletcher
View PDF Chat

On the asymptotic behaviour of some new gradient methods

2005-02-08
Yu‐Hong Dai , R. Fletcher

Solving mathematical programs with complementarity constraints as nonlinear programs

2004-02-01
R. Fletcher , Sven Leyffer
Abstract We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to … Abstract We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to tackle large instances of MPCCs. Numerical experience on MacMPEC, a large collection of MPCC test problems is presented. Our experience indicates that sequential quadratic programming (SQP) methods are very well suited for solving MPCCs and at present outperform interior-point solvers both in terms of speed and reliability. All NLP solvers also compare very favorably to special MPCC solvers on tests published in the literature. Keywords: MPCCComplementarity constraintsNonlinear programmingSequential quadratic programmingInterior-point methods Acknowledgments This work was supported EPSRC grant GR/M59549. We are also grateful for the opportunity to using Argonne's computing resources in carrying out our comparisons. We are grateful to Stefan Scholtes, Danny Ralph and Michael Ferris for many fruitful discussions on MPCCs. Finally, we gratefully acknowledge the insightful comments of an anonymous referee who greatly improved the article. Many individuals provided help and input for the problem library. We are grateful to David Gay for sharing his AMPL expertise with us. Michal Kocvara provided help with the packaging problems. Francis Tin Loi supplied some challenging structural engineering problems. Finally, we have 'borrowed' test problems from a variety of sources but most notably from MPECLIB of Steven Dirkse. Notes *[email protected] ‡This work was carried out while the second author was at the University of Dundee. Additional informationNotes on contributorsRoger FletcherFootnote* *[email protected] Sven Leyffer,Footnote‡ ‡This work was carried out while the second author was at the University of Dundee.

On the global convergence of an SLP-filter algorithm that takes EQP steps

2003-04-01
Choong Ming Chin , R. Fletcher

Filter-type Algorithms for Solving Systems of Algebraic Equations and Inequalities

2003-01-01
R. Fletcher , Sven Leyffer

On the Global Convergence of a Filter--SQP Algorithm

2002-01-01
R. Fletcher , Sven Leyffer , Philippe L. Toint
A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of … A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of a penalty parameter whose adjustment can be problematic. The main point of interest is to demonstrate how convergence for NLP can be induced without forcing sufficient descent in a penalty-type merit function. The proof relates to a prototypical algorithm, within which is allowed a range of specific algorithm choices associated with the Hessian matrix representation, updating the trust region radius, and feasibility restoration.

Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming

2002-01-01
R. Fletcher , Nicholas I. M. Gould , Sven Leyffer +2 more
A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for … A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for an approximate solution of the quadratic subproblem and incorporates the safeguarding tests described in Fletcher, Leyffer, and Toint [On the Global Convergence of an SLP-Filter Algorithm, Technical Report 98/13, Department of Mathematics, University of Namur, Namur, Belgium, 1998; On the Global Convergence of a Filter-SQP Algorithm, Technical Report 00/15, Department of Mathematics, University of Namur, Namur, Belgium, 2000] is considered. It is proved that, under reasonable conditions and for every possible choice of the starting point, the sequence of iterates has at least one first-order critical accumulation point.

Nonlinear programming without a penalty function

2002-01-01
R. Fletcher , Sven Leyffer

References

2000-05-23
R. Fletcher
View PDF Chat

Initialising distillation column models

2000-01-01
R. Fletcher , William A. Morton

A New Degeneracy Method and Steepest-Edge--Based Conditioning for LP

1998-11-01
R. Fletcher
A new recursive method for resolving degeneracy in simplex-like methods for linear programming (LP) is described. The method provides a guarantee of termination, even in the presence of round-off errors, … A new recursive method for resolving degeneracy in simplex-like methods for linear programming (LP) is described. The method provides a guarantee of termination, even in the presence of round-off errors, and is readily implemented. In contrast to a previous method of the author, this method works throughout in the primal space. One consequence is that the steepest-edge criterion can be used on all iterations and at all levels of recursion. It is also shown that the associated steepest-edge coefficients provide information from which the expected condition of the current LP basis can be calculated cheaply. This provides a more accurate indication of the actual condition of a system than is obtained from norm-based condition numbers. This idea also enables the condition of null space matrices to be estimated.

Numerical Experience with Lower Bounds for MIQP Branch-And-Bound

1998-05-01
R. Fletcher , Sven Leyffer
The solution of convex mixed-integer quadratic programming (MIQP) problems with a general branch-and-bound framework is considered. It is shown how lower bounds can be computed efficiently during the branch-and-bound process. … The solution of convex mixed-integer quadratic programming (MIQP) problems with a general branch-and-bound framework is considered. It is shown how lower bounds can be computed efficiently during the branch-and-bound process. Improved lower bounds such as the ones derived in this paper can reduce the number of quadratic programming (QP) problems that have to be solved. The branch-and-bound approach is also shown to be superior to other approaches in solving MIQP problems. Numerical experience is presented which supports these conclusions.

On the Stability of Null-Space Methods for KKT Systems

1997-10-01
R. Fletcher , Tom Johnson
This paper considers the numerical stability of null-space methods for Karush--Kuhn--Tucker (KKT)systems, particularly in the context of quadratic programming. The methods we consider are based on the direct elimination of … This paper considers the numerical stability of null-space methods for Karush--Kuhn--Tucker (KKT)systems, particularly in the context of quadratic programming. The methods we consider are based on the direct elimination of variables, which is attractive for solving large sparse systems. Ill-conditioning in a certain submatrix A in the system is shown to adversely affect the method insofar as it is commonly implemented. In particular, it can cause growth in the residual error of the solution, which would not normally occur if Gaussian elimination or related methods were used. The mechanism of this error growth is studied and is not due to growth in the null-space basis matrix Z, as might have been expected, but to the indeterminacy of this matrix. When LU factors of A are available it is shown that an alternative form of the method is available which avoids this residual error growth. These conclusions are supported by error analysis and Matlab experiments on some extremely ill-conditioned test problems. These indicate that the alternative method is very robust in regard to residual error growth and is unlikely to be significantly inferior to the methods based on an orthogonal basis matrix. The paper concludes with some discussion of what needs to be done when LU factors are not available.

Computing Sparse Hessian and Jacobian Approximations with Optimal Hereditary Properties

1997-01-01
R. Fletcher , Andreas Grothey , Sven Leyffer
In nonlinear optimization it is often important to estimate large sparse Hessian or Jacobian matrices, to be used for example in a trust region method. We propose an algorithm for … In nonlinear optimization it is often important to estimate large sparse Hessian or Jacobian matrices, to be used for example in a trust region method. We propose an algorithm for computing a matrix B with a given sparsity pattern from a bundle of the m most recent difference vectors $$\Delta = \left[ {{{\delta }^{{k - m + 1}}} \ldots {{\delta }^{k}}} \right],\Gamma = \left[ {{{\gamma }^{{k - m + 1}}} \ldots {{\gamma }^{k}}} \right] $$ where B should approximately map △ into Г. In this paper B is chosen such that it satisfies m quasi—Newton conditions B△ = Г in the least squares sense. We show that B can always be computed by solving a positive semi—definite system of equations in the nonzero components of B. We give necessary and sufficient conditions under which this system is positive definite and indicate how B can be computed efficiently using a conjugate gradient method. In the case of unconstrained optimization we use the technique to determine a Hessian approximation which is used in a trust region method. Some numerical results are presented for a range of unconstrained test problems.

On the Order of Convergence of Preconditioned Nonlinear Conjugate Gradient Methods

1996-05-01
M. Al-Baali , R. Fletcher
An analysis is given of preconditioned nonlinear conjugate gradient methods in which the preconditioning matrix is the exact Hessian matrix at each iteration (or a nearby matrix). It is shown … An analysis is given of preconditioned nonlinear conjugate gradient methods in which the preconditioning matrix is the exact Hessian matrix at each iteration (or a nearby matrix). It is shown that the order of convergence of certain preconditioned methods is less than that of Newton’s method when exact line searches are used, and an example is given.

An Optimal Positive Definite Update for Sparse Hessian Matrices

1995-02-01
R. Fletcher
A Hessian update is described that preserves sparsity and positive definiteness and satisfies a minimal change property. The update reduces to the BFGS update in the dense case and generalises … A Hessian update is described that preserves sparsity and positive definiteness and satisfies a minimal change property. The update reduces to the BFGS update in the dense case and generalises a recent result in [SIAM J. Nnmer. Anal., 26 (1989), pp. 727–739] relating to the Byrd and Nocedal measure function. A surprising outcome is that a sparsity projection of the inverse Hessian plays a major role. It is shown that the Hessian itself can be recovered from this information under mild assumptions. The update is computed by solving a concave programming problem derived by using the Wolfe dual. The Hessian of the dual is important and plays a similar role to the matrix Q that arises in the sparse PSB update of Toint [Math. Comp., 31 (1977), pp. 954–961]. This matrix is shown to satisfy the same structural and definiteness conditions as Toint's matrix. The update has been implemented for tridiagonal systems and some numerical experiments are described. These experiments indicate that there is potential for a significant reduction in the number of quasi-Newton iterations, but that more development is needed to obtain an efficient implementation. Solution of the variational problem by primal methods is also discussed and provides an interesting application of generalized elimination. The possibility of instability and nonexistence of a positive definite update raised by Sorensen [Math. Programming Study, 18 (1982), pp. 135–159] is still a difficulty and some remedies are discussed.

Solving mixed integer nonlinear programs by outer approximation

1994-08-01
R. Fletcher , Sven Leyffer

An Overview of Unconstrained Optimization

1994-01-01
R. Fletcher

Resolving degeneracy in quadratic programming

1993-09-01
R. Fletcher

Ordering algorithms for irreducible sparse linear systems

1993-01-01
R. Fletcher , J. A. J. Hall

Flexible retrofit design of multiproduct batch plants

1991-12-01
R. Fletcher , J. A. J. Hall , Willis Robert John

A New Variational Result for Quasi-Newton Formulae

1991-02-01
R. Fletcher
The recent measure function of Byrd and Nocedal [SIAM J. Numer. Anal., 26 (1989), pp. 727–739] is considered and simple proofs of some of its properties are given. It is … The recent measure function of Byrd and Nocedal [SIAM J. Numer. Anal., 26 (1989), pp. 727–739] is considered and simple proofs of some of its properties are given. It is then shown that the BFGS and DFP formulae satisfy a least change property with respect to this new measure.

Nonlinear programming and nonsmooth optimization by successive linear programming

1989-01-01
R. Fletcher , Eduardo Sáinz de la Maza

Degeneracy in the presence of roundoff errors

1988-08-01
R. Fletcher

Hybrid Methods for Nonlinear Least Squares

1987-01-01
R. Fletcher , C. X. Xu
Journal Article Hybrid Methods for Nonlinear Least Squares Get access R. FLETCHER, R. FLETCHER Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this … Journal Article Hybrid Methods for Nonlinear Least Squares Get access R. FLETCHER, R. FLETCHER Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this author on: Oxford Academic Google Scholar C. XU C. XU Department of Mathematical Sciences, University of DundeeDundee DD1 4HN, Scotland Search for other works by this author on: Oxford Academic Google Scholar IMA Journal of Numerical Analysis, Volume 7, Issue 3, July 1987, Pages 371–389, https://doi.org/10.1093/imanum/7.3.371 Published: 01 July 1987 Article history Received: 20 January 1986 Revision received: 04 August 1986 Published: 01 July 1987

Cancellation Errors in Quasi-Newton Methods

1986-10-01
R. Fletcher
It is shown that the effect of cancellation errors in a quasi-Newton method can be predicted with reasonable accuracy on the basis of simple formulae derived by using probabilistic arguments. … It is shown that the effect of cancellation errors in a quasi-Newton method can be predicted with reasonable accuracy on the basis of simple formulae derived by using probabilistic arguments. Errors induced by cancellation are shown to have the potential to increase without bound as the method converges. They are shown to be one of the dominant factors affecting attainable accuracy in the variables of a problem.

An algorithm for composite nonsmooth optimization problems

1986-03-01
Robert S. Womersley , R. Fletcher

An efficient line search for nonlinear least squares

1986-03-01
M. Al-Baali , R. Fletcher

Semi-Definite Matrix Constraints in Optimization

1985-07-01
R. Fletcher
Positive semi-definite matrix constraints arise in a number of optimization problems in which some or all of the elements of a matrix are variables, such as the educational testing and … Positive semi-definite matrix constraints arise in a number of optimization problems in which some or all of the elements of a matrix are variables, such as the educational testing and matrix modification problems. The structure of such constraints is developed, including expressions for the normal cone, feasible directions and their application to optimality conditions. A computational framework is given within which these concepts can be exploited and which permits the quantification of second order effects. The matrix of Lagrange multipliers in this formulation is shown to have an important relationship to the characterization of the normal cone. Modifications of various iterative schemes in nonlinear programming are considered in order to develop an effective algorithm for the educational testing problem, and comparative numerical experiments are described. It is shown that a particular choice of the penalty parameter for an $l_1 $ exact penalty function is appropriate for this type of problem. The behaviour of the extreme eigenvalues (or sums thereof) of a matrix is related to the ideas of the paper, and the convexity of such functions is proved, together with expressions for subgradients.

Variational Methods for Non-Linear Least-Squares

1985-05-01
M. Al-Baali , R. Fletcher

A stable algorithm for updating triangular factors under a rank one change

1985-01-01
R. Fletcher , S. Matthews
An algorithm is presented for updating the <italic>LU</italic> factors of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> … An algorithm is presented for updating the <italic>LU</italic> factors of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrix <italic>A</italic>, when <italic>A</italic> is changed by a matrix of rank one. The algorithm is based on the repeated use of triangular operations, and stability is obtained by allowing both row and column pivoting. The cost of the algorithm is approximately proportional to the maximum permitted depth for the pivot search. For well-conditioned matrices a maximum depth of 3 is sufficient to ensure stability. For substantially rank deficient matrices it is theoretically possible that pivots of any depth may be required, but in practice we find that a value of 5 is adequate. We suggest a pivot strategy, based on minimizing a growth bound, which penalizes deep pivots and imposes a maximum depth of pivot through a default value. On well-behaved problems the asymptotic cost of the update is observed to be approximately <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2.6 n squared"> <mml:semantics> <mml:mrow> <mml:mn>2.6</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">2.6{n^2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> compared with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="8 n squared"> <mml:semantics> <mml:mrow> <mml:mn>8</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">8{n^2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (or worse) for updating orthogonal factors. Given the accuracy obtained by the new algorithm, we feel that there are many applications in which the lower cost of triangular factors can be exploited. Comparison with <italic>ab initio</italic> factorization indicates that for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than-or-slanted-equals 10"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>⩾<!-- ⩾ --></mml:mo> <mml:mn>10</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n \geqslant 10</mml:annotation> </mml:semantics> </mml:math> </inline-formula> updating triangular factors is advantageous.
View PDF Chat

Stable modification of explicitLU factors for simplex updates

1984-10-01
R. Fletcher , S. Matthews

An Algorithmic Derivation of the Jordan Canonical Form

1983-01-01
R. Fletcher , D. C. Sorensen
In this note the authors give a derivation of the Jordan Canonical form which is very algorithmic in nature. It requires no preparation other than the Schur decomposition and the … In this note the authors give a derivation of the Jordan Canonical form which is very algorithmic in nature. It requires no preparation other than the Schur decomposition and the solution of linear systems.

Penalty Functions

1983-01-01
R. Fletcher

An Algorithmic Derivation of the Jordan Canonical Form

1983-01-01
R. Fletcher , D. C. Sorensen

A model algorithm for composite nondifferentiable optimization problems

1982-01-01
R. Fletcher

Basis Functions for the Exact Control of the Heat Equation

1982-01-01
R. Fletcher , P. J. Harley
The problem of using boundary control to drive the one-dimensional heat equation exactly to a given terminal condition in a finite time T is considered. The control function is described … The problem of using boundary control to drive the one-dimensional heat equation exactly to a given terminal condition in a finite time T is considered. The control function is described in terms of a set of finite dimensional basis functions which have certain optimality properties. An efficient algorithm for the evaluation of these basis functions and the control is presented and the use of the control is demonstrated using numerical examples. The controls resulting from this algorithm are likely to be most useful as initial approximations to the control in, for example, quadratic cost control problems.

A Nonlinear Programming Problem in Statistics (Educational Testing)

1981-09-01
R. Fletcher
The educational testing problem is reviewed; it concerns a reliability coefficient which measures how reliable are the student’s total scores in an examination consisting of a number of subtests. A … The educational testing problem is reviewed; it concerns a reliability coefficient which measures how reliable are the student’s total scores in an examination consisting of a number of subtests. A lower bound on this coefficient is obtained by solving a certain nonlinear programming problem. Expressions for both first and second derivatives are given, and a scaling feature is described which enables the search for a solution to take place along feasible arcs on the boundary of the feasible region. The SOLVER method is used to generate the directions of search and numerical results are described. While an improvement over previous methods is obtained, some difficulties over slow convergence are observed in some cases and a possible explanation is given.

A new efficient method for locating saddle points

1981-08-01
Stephen G. Bell , James S. Crighton , R. Fletcher

Degenerate values for broyden methods

1981-03-01
R. Fletcher , James W. Sinclair

NUMERICAL EXPERIMENTS WITH AN EXACT L1 PENALTY FUNCTION METHOD

1981-01-01
R. Fletcher
Coauthor Papers Together
Sven Leyffer 10
Yu‐Hong Dai 3
M. Al-Baali 3
D. C. Sorensen 2
M. J. D. Powell 2
S. Matthews 2
J. A. J. Hall 2
J. A. Grant 2
M. D. Hebden 2
Philippe L. Toint 2
M J Norgett 1
James W. Sinclair 1
Chungen Shen 1
P. J. Harley 1
Choong Ming Chin 1
Eduardo Sáinz de la Maza 1
Marion Jackson 1
Tom Johnson 1
W. W. Bradbury 1
David F. Griffiths 1
C. X. Xu 1
G. A. Watson 1
William A. Morton 1
J. N. Holt 1
Andreas Wächter 1
T. L. Freeman 1
I. D. Coope 1
Nicholas I. M. Gould 1
SHIRLEY A. LILL 1
James S. Crighton 1
Stefan Scholtes 1
Stephen G. Bell 1
Willis Robert John 1
Andreas Grothey 1
Robert S. Womersley 1
D. Ralph 1

A Rapidly Convergent Descent Method for Minimization

1963-08-01
R. Fletcher , M. J. D. Powell
A powerful iterative descent method for finding a local minimum of a function of several variables is described. A number of theorems are proved to show that it always converges … A powerful iterative descent method for finding a local minimum of a function of several variables is described. A number of theorems are proved to show that it always converges and that it converges rapidly. Numerical tests on a variety of functions confirm these theorems. The method has been used to solve a system of one hundred non-linear simultaneous equations.
View PDF Chat

Nonlinear programming without a penalty function

2002-01-01
R. Fletcher , Sven Leyffer

A globally convergent method for nonlinear programming

1977-07-01
S.-P. Han
View PDF Chat

Function minimization by conjugate gradients

1964-02-01
R. Fletcher
A quadratically convergent gradient method for locating an unconstrained local minimum of a function of several variables is described. Particular advantages are its simplicity and its modest demands on storage, … A quadratically convergent gradient method for locating an unconstrained local minimum of a function of several variables is described. Particular advantages are its simplicity and its modest demands on storage, space for only three vectors being required. An ALGOL procedure is presented, and the paper includes a discussion of results obtained by its used on various test functions.
View PDF Chat

On the Global Convergence of a Filter--SQP Algorithm

2002-01-01
R. Fletcher , Sven Leyffer , Philippe L. Toint
A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of … A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described. Such methods are characterized by their use of thedominance concept of multiobjective optimization, instead of a penalty parameter whose adjustment can be problematic. The main point of interest is to demonstrate how convergence for NLP can be induced without forcing sufficient descent in a penalty-type merit function. The proof relates to a prototypical algorithm, within which is allowed a range of specific algorithm choices associated with the Hessian matrix representation, updating the trust region radius, and feasibility restoration.

A fast algorithm for nonlinearly constrained optimization calculations

1978-01-01
M. J. D. Powell

The watchdog technique for forcing convergence in algorithms for constrained optimization

1982-01-01
Richard Chamberlain , M. J. D. Powell , Claude Lemaréchal +1 more

A Nonmonotone Line Search Technique for Newton’s Method

1986-08-01
Luigi Grippo , F. Lampariello , Stefano Lucidi
In this paper a nonmonotone steplength selection rule for Newton’s method is proposed, which can be viewed as a generalization of Armijo’s rule. Numerical results are reported which indicate that … In this paper a nonmonotone steplength selection rule for Newton’s method is proposed, which can be viewed as a generalization of Armijo’s rule. Numerical results are reported which indicate that the proposed technique may allow a considerable saving both in the number of line searches and in the number of function evaluations.

Updating quasi-Newton matrices with limited storage

1980-01-01
Jorge Nocedal
We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information … We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information from the last <italic>m</italic> iterations, where <italic>m</italic> is any number supplied by the user. The quasi-Newton matrix is updated at every iteration by dropping the oldest information and replacing it by the newest information. It is shown that the matrices generated have some desirable properties. The resulting algorithms are tested numerically and compared with several well-known methods.
View PDF Chat

Two-Point Step Size Gradient Methods

1988-01-01
Jonathan Barzilai , Jonathan M. Borwein
We derive two-point step sizes for the steepest-descent method by approximating the secant equation. At the cost of storage of an extra iterate and gradient, these algorithms achieve better performance … We derive two-point step sizes for the steepest-descent method by approximating the secant equation. At the cost of storage of an extra iterate and gradient, these algorithms achieve better performance and cheaper computation than the classical steepest-descent method. We indicate a convergence analysis of the method in the two-dimensional quadratic case. The behaviour is highly remarkable and the analysis entirely nonstandard.

A Technique for Resolving Degeneracy in Linear Programming

1963-06-01
Philip Wolfe

A new approach to variable metric algorithms

1970-03-01
R. Fletcher
An approach to variable metric algorithms has been investigated in which the linear search sub-problem no longer becomes necessary. The property of quadratic termination has been replaced by one of … An approach to variable metric algorithms has been investigated in which the linear search sub-problem no longer becomes necessary. The property of quadratic termination has been replaced by one of monotonic convergence of the eigenvalues of the approximating matrix to the inverse hessian. A convex class of updating formulae which possess this property has been established, and a strategy has been indicated for choosing a member of the class so as to keep the approximation away from both singularity and unboundedness. A FORTRAN program has been tested extensively with encouraging results.
View PDF Chat

An efficient method for finding the minimum of a function of several variables without calculating derivatives

1964-02-01
M. J. D. Powell
A simple variation of the well-known method of minimizing a function of several variables by changing one parameter at a time is described. This variation is such that when the … A simple variation of the well-known method of minimizing a function of several variables by changing one parameter at a time is described. This variation is such that when the procedure is applied to a quadratic form, it causes conjugate directions to be chosen, so the ultimate rate of convergence is fast when the method is used to minimize a general function. A further variation completes the method, and its ensures that the convergence rate from a bad approximation to a minimum is always efficient. Practical applications of the procedure have proved to be very satisfactory, and numerical examples are given in which functions of up to twenty variables are minimized.

On sparse and symmetric matrix updating subject to a linear equation

1977-01-01
Philippe L. Toint
A procedure for symmetric matrix updating subject to a linear equation and retaining any sparsity present in the original matrix is derived. The main feature of this procedure is the … A procedure for symmetric matrix updating subject to a linear equation and retaining any sparsity present in the original matrix is derived. The main feature of this procedure is the reduction of the problem to the solution of an <italic>n</italic> dimensional sparse system of linear equations. The matrix of this system is shown to be symmetric and positive definite. The method depends on the Frobenius matrix norm. Comments are made on the difficulties of extending the technique so that it uses more general norms, the main points being shown by a numerical example.
View PDF Chat

Gradient Method with Retards and Generalizations

1998-01-01
Ana Friedlander , J. M. Martı́nez , Brígida Molina +1 more
A generalization of the steepest descent and other methods for solving a large scale symmetric positive definitive system Ax = b is presented. Given a positive integer m, the new … A generalization of the steepest descent and other methods for solving a large scale symmetric positive definitive system Ax = b is presented. Given a positive integer m, the new iteration is given by $x_{k+1} = x_k - \lambda (x_{\nu(k)}) (A x_k - b)$, where $\lambda (x_{\nu(k)})$ is the steepest descent step at a previous iteration $\nu(k) \in \{k, k-1, \ldots,$ max$\{0,k-m\}\}$. The global convergence to the solution of the problem is established under a more general framework, and numerical experiments are performed that suggest that some strategies for the choice of $\nu(k)$ give rise to efficient methods for obtaining approximate solutions of the system.

Degeneracy in the presence of roundoff errors

1988-08-01
R. Fletcher

The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem

1997-02-01
Marcos Raydan
The Barzilai and Borwein gradient method for the solution of large scale unconstrained minimization problems is considered. This method requires few storage locations and very inexpensive computations. Furthermore, it does … The Barzilai and Borwein gradient method for the solution of large scale unconstrained minimization problems is considered. This method requires few storage locations and very inexpensive computations. Furthermore, it does not guarantee descent in the objective function and no line search is required. Recently, the global convergence for the convex quadratic case has been established. However, for the nonquadratic case, the method needs to be incorporated in a globalization scheme. In this work, a nonmonotone line search strategy that guarantees global convergence is combined with the Barzilai and Borwein method. This strategy is based on the nonmonotone line search technique proposed by Grippo, Lampariello, and Lucidi [SIAM J. Numer. Anal., 23 (1986), pp. 707--716]. Numerical results to compare the behavior of this method with recent implementations of the conjugate gradient method are presented. These results indicate that the global Barzilai and Borwein method may allow some significant reduction in the number of line searches and also in the number of gradient evaluations.

On the Barzilai and Borwein choice of steplength for the gradient method

1993-01-01
Marcos Raydan
In a recent paper, Barzilai and Borwein presented a new choice of steplength for the gradient method. Their choice does not guarantee descent in the objective function and greatly speeds … In a recent paper, Barzilai and Borwein presented a new choice of steplength for the gradient method. Their choice does not guarantee descent in the objective function and greatly speeds up the convergence of the method. They presented a convergence analysis of their method only in the two-dimensional quadratic case. We establish the convergence of the Barzilai and Borwein gradient method when applied to the minimization of a strictly convex quadratic function of any number of variables.
View PDF Chat

Nonlinear programming and nonsmooth optimization by successive linear programming

1989-01-01
R. Fletcher , Eduardo Sáinz de la Maza

Multiplier and gradient methods

1969-11-01
Magnus R. Hestenes

Numerical Solution of Systems of Nonlinear Equations

1963-10-01
Ferdinand Freudenstein , Bernhard Roth
article Free AccessNumerical Solution of Systems of Nonlinear Equations Authors: Ferdinand Freudenstein Department of Mechanical Engineering, Columbia University and Stanford University Department of Mechanical Engineering, Columbia University and Stanford UniversityView … article Free AccessNumerical Solution of Systems of Nonlinear Equations Authors: Ferdinand Freudenstein Department of Mechanical Engineering, Columbia University and Stanford University Department of Mechanical Engineering, Columbia University and Stanford UniversityView Profile , Bernhard Roth Department of Mechanical Engineering, Columbia University and Stanford University Department of Mechanical Engineering, Columbia University and Stanford UniversityView Profile Authors Info & Claims Journal of the ACMVolume 10Issue 4pp 550–556https://doi.org/10.1145/321186.321200Published:01 October 1963Publication History 92citation2,067DownloadsMetricsTotal Citations92Total Downloads2,067Last 12 Months395Last 6 weeks105 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
View PDF Chat

On the global convergence of an SLP-filter algorithm that takes EQP steps

2003-04-01
Choong Ming Chin , R. Fletcher

Generalized gradients and applications

1975-01-01
Frank H. Clarke
A theory of generalized gradients for a general class of functions is developed, as well as a corresponding theory of normals to arbitrary closed sets.It is shown how these concepts … A theory of generalized gradients for a general class of functions is developed, as well as a corresponding theory of normals to arbitrary closed sets.It is shown how these concepts subsume the usual gradients and normals of smooth functions and manifolds, and the subdifferentials and normals of convex analysis.A theorem is proved concerning the differentiability properties of a function of the form max{g(x, u):u e if}.This result unifies and extends some theorems of Danskin and others.The results are then applied to obtain a characterization of flow-invariant sets which yields theorems of Bony and Brezis as corollaries.

An Ideal Penalty Function for Constrained Optimization

1975-01-01
R. Fletcher
A well known approach to constrained optimization is via a sequence of unconstrained minimization calculations applied to a penalty function. This paper shown how it is posiible to generalize Powell's … A well known approach to constrained optimization is via a sequence of unconstrained minimization calculations applied to a penalty function. This paper shown how it is posiible to generalize Powell's penelty function to solve constrained problems with both equality and inequality constraints. The resulting methods are equivalent to the Hestenes' method of multipliers, and a generalization of this to inequality constraints suggested by Rockafellar. Local duality results (not all of which have appeared before) for these methods are reviewed, with particular emphasis on those of practical importance. It is shown that various strategies for varying control parameters are possible, all of which can be viewed as Newton or Newton-like iterations applied to the dual problem. Practical strategies for guaranteeing convergence are also discussed. A wide selection of numerical evidence is reported, and the algorithms are compared both amongst themselves and with other penalty function methods. The new penalty function is well conditioned, without singularities, and it is not necessary for the control parameters to tend to infinity in order to force convergence. The rate of convergence is rapid and high accuracy is achieved in few unconstrained minimizations.; furthermore the computational effort for successive minimizations goes down rapidly. The methods are very easy to program efficiently, using an established quasi-Newton subroutine for unconstrained minimization.

Global Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming

2002-01-01
R. Fletcher , Nicholas I. M. Gould , Sven Leyffer +2 more
A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for … A trust-region SQP-filter algorithm of the type introduced by Fletcher and Leyffer [Math. Program., 91 (2002), pp. 239--269] that decomposes the step into its normal and tangential components allows for an approximate solution of the quadratic subproblem and incorporates the safeguarding tests described in Fletcher, Leyffer, and Toint [On the Global Convergence of an SLP-Filter Algorithm, Technical Report 98/13, Department of Mathematics, University of Namur, Namur, Belgium, 1998; On the Global Convergence of a Filter-SQP Algorithm, Technical Report 00/15, Department of Mathematics, University of Namur, Namur, Belgium, 2000] is considered. It is proved that, under reasonable conditions and for every possible choice of the starting point, the sequence of iterates has at least one first-order critical accumulation point.

A family of variable-metric methods derived by variational means

1970-01-01
Donald Goldfarb
A new rank-two variable-metric method is derived using Greenstadt’s variational approach [<italic>Math. Comp.</italic>, this issue]. Like the Davidon-Fletcher-Powell (DFP) variable-metric method, the new method preserves the positive-definiteness of the approximating … A new rank-two variable-metric method is derived using Greenstadt’s variational approach [<italic>Math. Comp.</italic>, this issue]. Like the Davidon-Fletcher-Powell (DFP) variable-metric method, the new method preserves the positive-definiteness of the approximating matrix. Together with Greenstadt’s method, the new method gives rise to a one-parameter family of variable-metric methods that includes the DFP and rank-one methods as special cases. It is equivalent to Broyden’s one-parameter family [<italic>Math. Comp.</italic>, v. 21, 1967, pp. 368–381]. Choices for the inverse of the weighting matrix in the variational approach are given that lead to the derivation of the DFP and rank-one methods directly.
View PDF Chat

On the Barzilai-Borwein Method

2005-07-18
R. Fletcher

Methods of conjugate gradients for solving linear systems

1952-12-01
Magnus R. Hestenes , Eduard Stiefel
An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method … An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case of a very general method which also includes Gaussian elimination. These general algorithms are essentially algorithms for finding an n dimensional ellipsoid. Connections are made with the theory of orthogonal polynomials and continued fractions.

Resolving degeneracy in quadratic programming

1993-09-01
R. Fletcher

Nonlinear Programming

1969-01-01
John C. G. Boot , H. P. Kunzi , W. Krelle

Nonmonotone Spectral Projected Gradient Methods on Convex Sets

2000-01-01
E. G. Birgin , J. M. Martı́nez , Marcos Raydan
Nonmonotone projected gradient techniques are considered for the minimization of differentiable functions on closed convex sets. The classical projected gradient schemes are extended to include a nonmonotone steplength strategy that … Nonmonotone projected gradient techniques are considered for the minimization of differentiable functions on closed convex sets. The classical projected gradient schemes are extended to include a nonmonotone steplength strategy that is based on the Grippo--Lampariello--Lucidi nonmonotone line search. In particular, the nonmonotone strategy is combined with the spectral gradient choice of steplength to accelerate the convergence process. In addition to the classical projected gradient nonlinear path, the feasible spectral projected gradient is used as a search direction to avoid additional trial projections during the one-dimensional search process. Convergence properties and extensive numerical results are presented.
View PDF Chat

Minimization of a Quadratic Function of Many Variables Subject only to Lower and Upper Bounds

1974-01-01
R. Fletcher , Marion Jackson
Methods for solving this problem are considered with particular reference to achieving maximum efficiency. A streamlined version of Fletcher's (1971) method for quadratic programming is considered and also a new … Methods for solving this problem are considered with particular reference to achieving maximum efficiency. A streamlined version of Fletcher's (1971) method for quadratic programming is considered and also a new approach based on the use of partial LDLT factorizations. Results on a wide variety of test problems indicate that the LDLT method is superior in both efficiency and error control. This method can often be expected to solve the problem in a time comparable to that required for a Choleski factorization, and always in a small multiple of this time.

Numerical methods for nonlinear algebraic equations

1970-01-01
Philip Rabinowitz

Numerical methods for constrained optimization

1974-01-01
Philip E. Gill , William Allan Murray

Variable Metric Method for Minimization

1991-02-01
William C. Davidon
This is a method for determining numerically local minima of differentiable functions of several variables. In the process of locating each minimum, a matrix which characterizes the behavior of the … This is a method for determining numerically local minima of differentiable functions of several variables. In the process of locating each minimum, a matrix which characterizes the behavior of the function about the minimum is determined. For a region in which the function depends quadratically on the variables, no more than N iterations are required, where N is the number of variables. By suitable choice of starting values, and without modification of the procedure, linear constraints can be imposed upon the variables.
View PDF Chat

Stable modification of explicitLU factors for simplex updates

1984-10-01
R. Fletcher , S. Matthews

Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming

1974-05-01
R. T. Rockafellar
If a nonlinear programming problem is analyzed in terms of its ordinary Lagrangian function, there is usually a duality gap, unless the objective and constraint functions are convex. It is … If a nonlinear programming problem is analyzed in terms of its ordinary Lagrangian function, there is usually a duality gap, unless the objective and constraint functions are convex. It is shown here that the gap can be removed by passing to an augmented Lagrangian which involves quadratic penalty-like terms. The modified dual problem then consists of maximizing a concave function of the Lagrange multipliers and an additional variable, which is a penalty parameter. In contrast to the classical case, the multipliers corresponding to inequality constraints in the primal are not constrained a priori to be nonnegative in the dual. If the maximum in the dual problem is attained (and conditions implying this are given), optimal solutions to the primal can be represented in terms of global saddle points of the augmented Lagrangian. This suggests possible improvements of existing penalty methods for computing solutions.

An Interior Point Algorithm for Large-Scale Nonlinear Programming

1999-01-01
Richard H. Byrd , Mary E. Hribar , Jorge Nocedal
The design and implementation of a new algorithm for solving large nonlinear programming problems is described. It follows a barrier approach that employs sequential quadratic programming and trust regions to … The design and implementation of a new algorithm for solving large nonlinear programming problems is described. It follows a barrier approach that employs sequential quadratic programming and trust regions to solve the subproblems occurring in the iteration. Both primal and primal-dual versions of the algorithm are developed, and their performance is illustrated in a set of numerical tests.
View PDF Chat

A Modification of Davidon's Minimization Method to Accept Difference Approximations of Derivatives

1967-01-01
G. W. Stewart
A modification of Davidon's method for the unconstrained minimization of a function of several variables is proposed in which the gradient vector is approximated by differences. The step sizes for … A modification of Davidon's method for the unconstrained minimization of a function of several variables is proposed in which the gradient vector is approximated by differences. The step sizes for the differencing are calculated from information available in the course of the minimization and are chosen to approximately balance off the effects of truncation error and cancellation error. Numerical results and comparisons with other methods are given.
View PDF Chat

Quasi-Newton methods and their application to function minimisation

1967-01-01
C. G. Broyden
Introduction.The solution of a set of n nonlinear simultaneous equations, which may be writtencan in general only be found by an iterative process in which successively better, in some sense, … Introduction.The solution of a set of n nonlinear simultaneous equations, which may be writtencan in general only be found by an iterative process in which successively better, in some sense, approximations to the solution are computed.Of the methods available most rely on evaluating at each stage of the calculation a set of residuals and from these obtaining a correction to each element of the approximate solution.The most common way of doing this is to take each correction to be a suitable linear combination of the residuals.There is, of course, no reason in principle why more elaborate schemes should not be used but they are difficult both to analyse theoretically and to implement in practice.The minimisation of a function of n variables, for which it is possible to obtain analytic expressions for the n first partial derivatives, is a particular example of this type of problem.Any technique used to solve nonlinear equations may be applied to the expressions for the partial derivatives but, because it is known in this case that the residuals form the gradient of some function, it is possible to introduce refinements into the method of solution to take account of this extra information.Since, in addition, the value of the function itself is known, further refinements are possible.
View PDF Chat

On the Solution of Large Quadratic Programming Problems with Bound Constraints

1991-02-01
Jorge J. Morè , Gerardo Toraldo
An algorithm is proposed that uses the conjugate gradient method to explore the face of the feasible region defined by the current iterate, and the gradient projection method to move … An algorithm is proposed that uses the conjugate gradient method to explore the face of the feasible region defined by the current iterate, and the gradient projection method to move to a different face. It is proved that for strictly convex problems the algorithm converges to the solution, and that if the solution is nondegenerate, then the algorithm terminates at the solution in a finite number of steps. Numerical results are presented for the obstacle problem, the elastic-plastic torsion problem, and the journal bearing problems. On a selection of these problems with dimensions ranging from 5000 to 15,000, the algorithm determines the solution in fewer than 15 iterations, and with a small number of function-gradient evaluations and Hessian-vector products per iteration.

R-linear convergence of the Barzilai and Borwein gradient method

2002-01-01
Y. H. Dai
Journal Article R‐linear convergence of the Barzilai and Borwein gradient method Get access Yu‐Hong Dai, Yu‐Hong Dai Search for other works by this author on: Oxford Academic Google Scholar Li‐Zhi … Journal Article R‐linear convergence of the Barzilai and Borwein gradient method Get access Yu‐Hong Dai, Yu‐Hong Dai Search for other works by this author on: Oxford Academic Google Scholar Li‐Zhi Liao Li‐Zhi Liao Search for other works by this author on: Oxford Academic Google Scholar IMA Journal of Numerical Analysis, Volume 22, Issue 1, 1 January 2002, Pages 1–10, https://doi.org/10.1093/imanum/22.1.1 Published: 01 January 2002

A New Algorithm for Unconstrained Optimization

1970-01-01
M. J. D. Powell

Function Minimization Without Evaluating Derivatives--a Review

1965-04-01
R. Fletcher
The efficiency of methods for minimizing functions without evaluating derivatives is considered, with particular regard to three methods recently developed. A set of test functions representative of a wide range … The efficiency of methods for minimizing functions without evaluating derivatives is considered, with particular regard to three methods recently developed. A set of test functions representative of a wide range of minimization problems is proposed and is used as a basis for comparison.
View PDF Chat

An Algorithm for Minimax Solution of Overdetermined Systems of Non-linear Equations

1975-01-01
Kristoffer H. Madsen
The problem of minimizing the maximum residual of a system of non-linear equations is studied in the case where the number of equations is larger than the number of unknowns. … The problem of minimizing the maximum residual of a system of non-linear equations is studied in the case where the number of equations is larger than the number of unknowns. It is supposed that the functions defining the problem have continuous first derivatives, and the algorithm is based on successive linear approximations to these functions. The resulting linear systems are solved in the minimax sense, subject to bounds on the solutions, the bounds being adjusted automatically, depending on the goodness of the linear approximations. It is proved that the method always has sure convergence properties. Some numerical examples are given.

The generalized simplex method for minimizing a linear form under linear inequality restraints

1955-06-01
George B. Dantzig , Alexander Orden , Philip Wolfe
Background and summary.The determination of "optimum" solutions of systems of linear inequalities is assuming increasing importance as a tool for mathematical analysis of certain problems in economics, logistics, and the … Background and summary.The determination of "optimum" solutions of systems of linear inequalities is assuming increasing importance as a tool for mathematical analysis of certain problems in economics, logistics, and the theory of games [l;5] The solution of large systems is becoming more feasible with the advent of high-speed digital computers; however, as in the related problem of inversion of large matrices, there are difficulties which remain to be resolved connected with rank.This paper develops a theory for avoiding assumptions regarding rank of underlying matrices which has import in applications where little or nothing is known about the rank of the linear inequality system under consideration.The simplex procedure is a finite iterative method which deals with problems involving linear inequalities in a manner closely analogous to the solution of linear equations or matrix inversion by Gaussian elimination.Like the latter it is useful in proving fundamental theorems on linear algebraic systems.For example, one form of the fundamental duality theorem associated with linear inequalities is easily shown as a direct consequence of solving the main problem.Other forms can be obtained by trivial manipulations (for a fuller discussion of these interrelations, see [13]); in particular, the duality theorem [8; 10; 11; 12] leads directly to the Minmax theorem for zero-sum two-person games [id] and to a computational method (pointed out informally by Herman Rubin and demonstrated by Robert Dorfman [la]) which simultaneously yields optimal strategies for both players and also the value of the game.The term "simplex" evolved from an early geometrical version in which (like in game theory) the variables were nonnegative and summed to unity.In that formulation a class of "solutions" was considered which lay in a simplex.The generalized method given here was outlined earlier by the first of the authors (Dantzig) in a short footnote [lb] and then discussed somewhat more fully at the Symposium of Linear Inequalities in 1951.Its purpose, as we have
View PDF Chat

On the use of exact penalty functions to determine step length in optimization algorithms

1980-01-01
D.Q. Mayne

THE CONVERGENCE OF VARIABLE METRIC METHODS FOR NONLINEARLY CONSTRAINED OPTIMIZATION CALCULATIONS

1978-01-01
M. J. D. Powell

Gradient projection methods for quadratic programs and applications in training support vector machines

2005-01-18
Thomas Serafini , Gaetano Zanghirati , Luca Zanni
Abstract Gradient projection methods based on the Barzilai–Borwein spectral steplength choices are considered for quadratic programming (QP) problems with simple constraints. Well-known nonmonotone spectral projected gradient methods and variable projection … Abstract Gradient projection methods based on the Barzilai–Borwein spectral steplength choices are considered for quadratic programming (QP) problems with simple constraints. Well-known nonmonotone spectral projected gradient methods and variable projection methods are discussed. For both approaches, the behavior of different combinations of the two spectral steplengths is investigated. A new adaptive steplength alternating rule is proposed, which becomes the basis for a generalized version of the variable projection method (GVPM). Convergence results are given for the proposed approach and its effectiveness is shown by means of an extensive computational study on several test problems, including the special quadratic programs arising in training support vector machines (SVMs). Finally, the GVPM behavior as inner QP solver in decomposition techniques for large-scale SVMs is also evaluated. Keywords: Quadratic programsGradient projection methodsSupport vector machinesDecom-position techniquesLarge-scale problems Acknowledgement The authors are most grateful to Prof. Roger Fletcher for the valuable discussions and suggestions on the Barzilai–Borwein method, as well as to the referees for their constructive comments. This work was supported by the Italian Education, University and Research Ministry (grants FIRB2001/RBAU01JYPN and FIRB2001/RBAU01877P).

CUTE

1995-03-01
Ingrid Bongartz , Andrew R. Conn , Nicholas I. M. Gould +1 more
The purpose of this article is to discuss the scope and functionality of a versatile environment for testing small- and large-scale nonlinear optimization algorithms. Although many of these facilities were … The purpose of this article is to discuss the scope and functionality of a versatile environment for testing small- and large-scale nonlinear optimization algorithms. Although many of these facilities were originally produced by the authors in conjunction with the software package LANCELOT, we believe that they will be useful in their own right and should be available to researchers for their development of optimization software. The tools can be obtained by anonymous ftp from a number of sources and may, in many cases, be installed automatically. The scope of a major collection of test problems written in the standard input format (SIF) used by the LANCELOT software package is described. Recognizing that most software was not written with the SIF in mind, we provide tools to assist in building an interface between this input format and other optimization packages. These tools provide a link between the SIF and a number of existing packages, including MINOS and OSL. Additionally, as each problem includes a specific classification that is designed to be useful in identifying particular classes of problems, facilities are provided to build and manage a database of this information. There is a Unix and C shell bias to many of the descriptions in the article, since, for the sake of simplicity, we do not illustrate everything in its fullest generality. We trust that the majority of potential users are sufficiently familiar with Unix that these examples will not lead to undue confusion.
View PDF Chat