Hessian distances and their applications in the complexity analysis of interior-point methods
(2012) Optimization Methods and Software — Vol. Online first, p. 1-21 (2012)
Files
YN_Hessian.pdf
Restricted Access - Adobe PDF
- 248.8 KB
Details
- Authors
- Abstract
- For interior points in convex cones, we introduce the Hessian distance function, and show that it is convenient for complexity analysis of polynomial-time interior-point methods (IPMs). As an example of its application, we develop new infeasible-start IPM for the linear conic optimization problem. In our setting, the primal and dual cones need not to be self-dual. We can start from any primal–dual point in the interior of the cones. Then, the damped Newton's method can be used for obtaining an approximate solution for the strictly feasible case, or for detecting primal/dual infeasibility. The complexity of these cases depends on the Hessian distance between the starting point and the feasibility/infeasibility certificates. We also present some numerical results.
- Affiliations
Citations
Nesterov, Y., & Xia, Y. (2012). Hessian distances and their applications in the complexity analysis of interior-point methods. Optimization Methods and Software, Online first, 1-21. https://doi.org/10.1080/10556788.2012.737327 (Original work published 2012)