EPSRC Reference: |
GR/S34472/01 |
Title: |
STIFFNESS AND COMPLEXITY IN NUMERICAL OPTIMISATION |
Principal Investigator: |
Hauser, Dr R |
Other Investigators: |
|
Researcher Co-Investigators: |
|
Project Partners: |
|
Department: |
Computer Science |
Organisation: |
University of Oxford |
Scheme: |
First Grant Scheme Pre-FEC |
Starts: |
05 January 2004 |
Ends: |
04 January 2007 |
Value (£): |
124,243
|
EPSRC Research Topic Classifications: |
Mathematical Aspects of OR |
Numerical Analysis |
|
EPSRC Industrial Sector Classifications: |
No relevance to Underpinning Sectors |
|
|
Related Grants: |
|
Panel History: |
|
Summary on Grant Application Form |
We explore the close relationship between search direction methods in optimisation and forward Euler time stepping. In this framework, search directions that lead to low algorithmic complexity are vector fields that are cheap to compute, have the local solutions of the optimisation problem as their stable attractors and are as nonstiff as possible. We analyse various common search directions in this light. We also show that the power of selfconcordant barrier functions - a central concept in the complexity analysis of convex programming - relies on the fact that they lead to merit functions with particularly nonstiff Newton direction fields. Similar ideas extend to general constrained nonlinear optimisation, where the stiffness of search direction fields has an important influence on the rate at which homotopy parameters should be reduced. The superiority of primal-dual versus primal only interior point methods will also be analysed in this light.
|
Key Findings |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
Potential use in non-academic contexts |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
Impacts |
Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
Summary |
|
Date Materialised |
|
|
Sectors submitted by the Researcher |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
Project URL: |
|
Further Information: |
|
Organisation Website: |
http://www.ox.ac.uk |