A new perspective on the complexity of interior point methods for linear programming
In a dynamical systems paradigm, many optimization algorithms are equivalent to applying forward Euler method to the system of ordinary differential equations defined by the vector field of the search directions. Thus the stiffness of such vector fields will play an essential role in the complexity...
| Autori principali: | , |
|---|---|
| Natura: | Report |
| Pubblicazione: |
Unspecified
2007
|
| _version_ | 1826280862054875136 |
|---|---|
| author | Cartis, C Hauser, R |
| author_facet | Cartis, C Hauser, R |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | In a dynamical systems paradigm, many optimization algorithms are equivalent to applying forward Euler method to the system of ordinary differential equations defined by the vector field of the search directions. Thus the stiffness of such vector fields will play an essential role in the complexity of these methods. We first exemplify this point with a theoretical result for general linesearch methods for unconstrained optimization, which we further employ to investigating the complexity of a primal short-step path-following interior point method for linear programming. Our analysis involves showing that the Newton vector field associated to the primal logarithmic barrier is nonstiff in a sufficiently small and shrinking neighbourhood of its minimizer. Thus, by confining the iterates to these neighbourhoods of the primal central path, our algorithm has a nonstiff vector field of search directions, and we can give a worst-case bound on its iteration complexity. Furthermore, due to the generality of our vector field setting, we can perform a similar (global) iteration complexity analysis when the Newton direction of the interior point method is computed only approximately, using some direct method for solving linear systems of equations. |
| first_indexed | 2024-03-07T00:20:06Z |
| format | Report |
| id | oxford-uuid:7c3c586c-7c90-467b-b5a3-8a19b7fe8e6d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:20:06Z |
| publishDate | 2007 |
| publisher | Unspecified |
| record_format | dspace |
| spelling | oxford-uuid:7c3c586c-7c90-467b-b5a3-8a19b7fe8e6d2022-03-26T20:55:46ZA new perspective on the complexity of interior point methods for linear programmingReporthttp://purl.org/coar/resource_type/c_93fcuuid:7c3c586c-7c90-467b-b5a3-8a19b7fe8e6dMathematical Institute - ePrintsUnspecified2007Cartis, CHauser, RIn a dynamical systems paradigm, many optimization algorithms are equivalent to applying forward Euler method to the system of ordinary differential equations defined by the vector field of the search directions. Thus the stiffness of such vector fields will play an essential role in the complexity of these methods. We first exemplify this point with a theoretical result for general linesearch methods for unconstrained optimization, which we further employ to investigating the complexity of a primal short-step path-following interior point method for linear programming. Our analysis involves showing that the Newton vector field associated to the primal logarithmic barrier is nonstiff in a sufficiently small and shrinking neighbourhood of its minimizer. Thus, by confining the iterates to these neighbourhoods of the primal central path, our algorithm has a nonstiff vector field of search directions, and we can give a worst-case bound on its iteration complexity. Furthermore, due to the generality of our vector field setting, we can perform a similar (global) iteration complexity analysis when the Newton direction of the interior point method is computed only approximately, using some direct method for solving linear systems of equations. |
| spellingShingle | Cartis, C Hauser, R A new perspective on the complexity of interior point methods for linear programming |
| title | A new perspective on the complexity of interior point methods for linear programming |
| title_full | A new perspective on the complexity of interior point methods for linear programming |
| title_fullStr | A new perspective on the complexity of interior point methods for linear programming |
| title_full_unstemmed | A new perspective on the complexity of interior point methods for linear programming |
| title_short | A new perspective on the complexity of interior point methods for linear programming |
| title_sort | new perspective on the complexity of interior point methods for linear programming |
| work_keys_str_mv | AT cartisc anewperspectiveonthecomplexityofinteriorpointmethodsforlinearprogramming AT hauserr anewperspectiveonthecomplexityofinteriorpointmethodsforlinearprogramming AT cartisc newperspectiveonthecomplexityofinteriorpointmethodsforlinearprogramming AT hauserr newperspectiveonthecomplexityofinteriorpointmethodsforlinearprogramming |