Title | ||
---|---|---|
Hessian distances and their applications in the complexity analysis of interior-point methods |
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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1080/10556788.2012.737327 | Optimization Methods and Software |
Keywords | Field | DocType |
interior point,infeasibility certificate,convex cone,approximate solution,complexity analysis,interior-point method,hessian distance,dual infeasibility,hessian distance function,dual cone,dual point | Mathematical optimization,Metric (mathematics),Hessian matrix,Regular polygon,Conic optimization,Approximate solution,Interior point method,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 3 | 1055-6788 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yurii Nesterov | 1 | 1800 | 168.77 |
Yu Xia | 2 | 116 | 20.65 |