Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2001
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915559989313536 |
|---|---|
| author | Wright, Stephen J. |
| author_facet | Wright, Stephen J. |
| contents | We show that the effects of finite-precision arithmetic in forming and solving the linear system that arises at each iteration of primal-dual interior-point algorithms for nonlinear programming are benign, provided that the iterates satisfy centrality and feasibility conditions of the type usually associated with path-following methods. When we replace the standard assumption that the active constraint gradients are independent by the weaker Mangasarian-Fromovitz constraint qualification, rapid convergence usually is attainable, even when cancellation and roundoff errors occur during the calculations. In deriving our main results, we prove a key technical result about the size of the exact primal-dual step. This result can be used to modify existing analysis of primal-dual interior-point methods for convex programming, making it possible to extend the superlinear local convergence results to the nonconvex case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0103102 |
| institution | arXiv |
| publishDate | 2001 |
| record_format | arxiv |
| spellingShingle | Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming Wright, Stephen J. Optimization and Control Numerical Analysis 90C33; 90C30 We show that the effects of finite-precision arithmetic in forming and solving the linear system that arises at each iteration of primal-dual interior-point algorithms for nonlinear programming are benign, provided that the iterates satisfy centrality and feasibility conditions of the type usually associated with path-following methods. When we replace the standard assumption that the active constraint gradients are independent by the weaker Mangasarian-Fromovitz constraint qualification, rapid convergence usually is attainable, even when cancellation and roundoff errors occur during the calculations. In deriving our main results, we prove a key technical result about the size of the exact primal-dual step. This result can be used to modify existing analysis of primal-dual interior-point methods for convex programming, making it possible to extend the superlinear local convergence results to the nonconvex case. |
| title | Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming |
| topic | Optimization and Control Numerical Analysis 90C33; 90C30 |
| url | https://arxiv.org/abs/math/0103102 |