Professor Roger Fletcher

Name:

Roger Fletcher

Position:

Professor

Department of Mathematics

University of Dundee

Dundee DD1 4HN

Room:

21/1/3

E-mail:

fletchermaths.dundee.ac.uk

Phone:

01382 384490

Fax:

01382 385516

Research Interests:

Optimization Methods, Theory and Applications

Numerical Linear Algebra

Summary

I have been involved over many years in the development of the subject of Optimization and related topics. A focus of recent work has been a a sequence of papers on how to guarantee termination in Linear and Quadratic Programming in the presence of degeneracy and round-off error. A production code for LP and QP, known as bqpd, was made avaiable in 1995. This code has recently been revised to make use of steepest edge pricing and also to use recently developed stable techniques in linear algebra, and a production code is now available. Much of my recent work has been in conjunction with a research fellow Sven Leyffer. We have made new developments in Mixed Integer LP and QP, including a new proof of global convergence of Outer Approximation, and the demonstration of its worst-case behaviour. This research has led to a Mixed Integer LP/QP production code which has also been distributed widely. Together with Andreas Grothey we also have some interesting results on sparse Hessian updates.

More recent ideas have been researched in regard to Sequential QP methods for Non-Linear Programming, including contributions on global convergence through the new idea of an NLP filter. A production code using the filter method is now available. The method is also made available as part of a Mixed Integer Nonlinear Programming package. Licences to use any or all of these codes are available at very modest cost, particularly for academic and non-commercial users. Global convergence proofs of filter--type algorithms have recently been developed. These include a very recent (2001) proof for a filter algorithm for nonlinear systems that is relevant to feasibility restoration. Extensions of the filter idea to sequential Linear Programming have been researched along with a research student Choong Ming Chin (who has now successfully completed) and there are some joint papers.

Other recent work (with Sven Leyffer) has been to apply our SQP filter solvers to solve Mathematical Programs with Equilibrium Constraints (MPECs). This work is supported by an EPSRC research grant. We find that MPECs can be solved very effectively in this way, contrary to what has been reported elsewhere. Together with Stefan Scholtes and Danny Ralph at Cambridge we are trying to make useful statements about the asymptotic properties of the SQP algorithms in this context. This work has also led to consider solving other problems that might be described by variational inequalities. In particular, some interesting results for Stefan moving boundary problems are now emerging. Some informal collaborations with John Mackenzie and others at Strathclyde have been established.

Most recently I have become interested (again!) in the Barziliai-Borwein method, having been impressed by the recent numerical work of Marcos Raydan and others, and having benefitted from discussions with Yu-Hong Dai. A summary of my recent thoughts on this topic are presented in a review paper given at Erice in 2001, and I am following up these ideas in conjunction with Dai and others.

The optimization group at Dundee has been associated with researchers in Mathematics and Chemical Engineering at Edinburgh University as part of the ECOSSE project since about 1989. To follow up this work, the EPSRC has funded (from 1996-99) a reseach project jointly with myself and researchers Ken McKinnon (Maths) and Bill Morton (Chem. Eng.) at Edinburgh. The project has studied the use of decomposition in the optimization of plant-wide flowsheets with application to the chemical industry. This presents significant challenges asoociated with the large dimension involved, and the solution of non-smooth optimization problems. More recently a new technique for solving distillation column problems has been developed which allows accurate initial estimates of the solution to be derived in an efficient way.

Recent Reports

• Fletcher R., An Overview of Unconstrained Optimization, Dundee Numerical Analysis Report NA/149, 1993.
• Fletcher R. and Leyffer S., Computing lower Bounds for MIQP Branch-and-Bound, Dundee Numerical Analysis Report NA/151, 1994.
• Fletcher R., Steepest Edge, Degeneracy and Conditioning in LP, Dundee Numerical Analysis Report NA/154, 1994.
• Fletcher R., Grothey A. and Leyffer S., Computing sparse Hessian and Jacobian approximations with optimal hereditary properties, Dundee Numerical Analysis Report NA/164, 1995.
• Fletcher R. and Johnson T., On the Stability of Null-Space Methods for KKT Systems, Dundee Numerical Analysis Report NA/167, 1995.
• Fletcher R., Dense Factors of Sparse Matrices, Dundee Numerical Analysis Report NA/170, 1996.
• Fletcher R. and Leyffer S.L., Nonlinear Programming without a Penalty Function, Dundee Numerical Analysis Report NA/171, 1996.
• Fletcher R., Block Triangular Orderings and Factors for Sparse Matrices in LP, Dundee Numerical Analysis Report NA/177, 1997.
• Fletcher R., Leyffer S. and Toint Ph. L., On the Global Convergence of an SLP-Filter Algorithm, Dundee Numerical Analysis Report NA/183, 1998.
• Fletcher R., Stable Reduced Hessian Updates for Indefinite Quadratic Programming , Dundee Numerical Analysis Report NA/187, 1999.
• Fletcher R. and Morton W., Initializing Distillation Column Models , Dundee Numerical Analysis Report NA/191, 1999.
• Fletcher R., Leyffer S. and Toint Ph. L., On the Global Convergence of a Filter-SQP Algorithm, Dundee Numerical Analysis Report NA/197, 2000.
• Chin C.M. and Fletcher R., On the Global Convergence of an SLP-Filter Algorithm that takes EQP steps, Dundee Numerical Analysis Report NA/199, 2001.
• Chin C.M. and Fletcher R., Numerical performance of an SLP--filter algorithm that takes EQP steps, Dundee Numerical Analysis Report NA/202, 2001.
• Chin C.M., Numerical results of SLPSQP, filterSQP and LANCELOT on selected CUTE test problems, Dundee Numerical Analysis Report NA/203, 2001.
• Fletcher R. and Leyffer S., Filter-type Algorithms for Solving Systems of Algebraic Equations and Inequalities, Dundee Numerical Analysis Report NA/204, 2001.
• Fletcher R., On the Barzilai-Borwein method, Dundee Numerical Analysis Report NA/207, 2001.
• Fletcher R., Leyffer S., Scholtes S. and Ralph D., Local convergence of SQP methods For Mathematical Programming Problems with Equilibrium Constraints, Dundee Numerical Analysis Report NA/209, 2002.
• Fletcher R. and Leyffer S., Numerical experience with solving MPECs as NLPs, University of Dundee Report NA/210, 2002.
• Dai Y-H. and Fletcher R., On the Asymptotic Behaviour of some New Gradient Methods, University of Dundee Report NA/212, 2003.
• Dai Y-H. and Fletcher R., Projected Barzilai-Borwein Methods for Large-Scale Box-Constrained Quadratic Programming, University of Dundee Report NA/215, 2003.
• Dai Y-H. and Fletcher R., New Algorithms for Singly Linearly Constrained Quadratic Programs Subject to Lower and Upper Bounds, University of Dundee Report NA/216, 2003.
• Fletcher R., A New Low Rank Quasi-Newton Update Scheme for Nonlinear Programming, University of Dundee Report NA/223, 2005.