A preconditioned iterative interior point approach to the conic bundle subproblem
From MaRDI portal
Abstract: The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by an iterative approach that exploits structural low rank properties. Two preconditioning approaches are proposed and analyzed. Both might be of interest for rank structured positive definite systems in general. The first employs projections onto random subspaces, the second projects onto a subspace that is chosen deterministically based on structural interior point properties. For both approaches theoretic bounds are derived for the associated condition number. In the instances tested the deterministic preconditioner provides surprisingly efficient control on the actual condition number. The results suggest that for large scale instances the iterative solver is usually the better choice if precision requirements are moderate or if the size of the Schur complemented system clearly exceeds the active dimension within the subspace giving rise to the cutting model of the bundle method.
Recommendations
- Solving Large Scale Semidefinite Programs via an Iterative Solver on the Augmented Systems
- Solving semidefinite programs using preconditioned conjugate gradients
- Preconditioning indefinite systems in interior point methods for optimization
- Efficient Preconditioners for Interior Point Methods via a New Schur Complement-Based Strategy
- Solving some large scale semidefinite programs via the conjugate residual method
Cites work
- scientific article; zbMATH DE number 439380 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 2196287 (Why is no real title available?)
- scientific article; zbMATH DE number 2221749 (Why is no real title available?)
- A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error
- A Spectral Bundle Method for Semidefinite Programming
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
- A spectral approach to bandwidth and separator problems in graphs
- A spectral bundle method with bounds
- An elementary proof of a theorem of Johnson and Lindenstrauss
- An inexact primal-dual path following algorithm for convex quadratic SDP
- Benchmarking optimization software with performance profiles.
- Convex Analysis
- Dynamic graph generation for the shortest path problem in time expanded networks
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Handbook on semidefinite, conic and polynomial optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Latent semantic indexing: A probabilistic analysis
- Matrix Analysis
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- On the Nesterov--Todd Direction in Semidefinite Programming
- On the solution of large-scale SDP problems by the modified barrier method using iterative solvers
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Proximal-ACCPM: a versatile oracle based optimisation method
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- The Analytic Center Cutting Plane Method with Semidefinite Cuts
- The spectral bundle method with second-order information
Cited in
(1)
This page was built for publication: A preconditioned iterative interior point approach to the conic bundle subproblem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126660)
