Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems
From MaRDI portal
Publication:3465241
Abstract: In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only in the dual space. It is based on an easily computable gradient proximity measure, which ensures an automatic transformation of the global linear rate of convergence to the local superlinear one under some mild assumptions. Our step-size procedure for the predictor step is related to the maximum step size maintaining feasibility. As the optimal solution set is approached, our algorithm automatically tightens the neighborhood of the central path proportionally to the current duality gap.
Recommendations
- On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems
- On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP
- Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming
- Superlinear convergence of interior-point algorithms for semidefinite programming
- On superlinear convergence of infeasible interior-point algorithms for linearly constrained convex programs
- Superlinear convergence of infeasible-interior-point methods for linear programming
- Superlinear convergence of primal-dual interior point algorithms for nonlinear programming
- On a general class of interior-point algorithms for semidefinite programming with polynomial complexity and superlinear convergence
- Superlinear and quadratic convergence of some primal - dual interior point methods for constrained optimization
- Superlinear convergence of an interior-point method despite dependent constraints
Cites work
- A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
- Error Bounds and Limiting Behavior of Weighted Paths Associated with the SDP Map X1/2SX1/2
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 3307153 (Why is no real title available?)
- Hyperbolic polynomials and convex analysis
- Hyperbolic Polynomials and Interior Point Methods for Convex Programming
- Hyperbolic programs, and their derivative relaxations
- Introductory lectures on convex optimization. A basic course.
- Limiting behavior of the Alizadeh–Haeberly–Overton weighted paths in semidefinite programming
- Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs
- On the Local Convergence of a Predictor-Corrector Method for Semidefinite Programming
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- Optimization Problems over Positive Pseudopolynomial Matrices
- Quadratic Convergence in a Primal-Dual Method
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood
- Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
- Superlinear convergence of interior-point algorithms for semidefinite programming
Cited in
(10)- Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence
- A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization
- Imaginary projections: complex versus real coefficients
- Hyperbolicity cones and imaginary projections
- Primal-dual interior-point methods for domain-driven formulations
- Strict complementarity in semidefinite optimization with elliptopes including the maxcut SDP
- Linear optimization over homogeneous matrix cones
- Set-limited functions and polynomial-time interior-point methods
- Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems
- Improved global performance guarantees of second-order methods in convex minimization
This page was built for publication: Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3465241)
