Error bounds and singularity degree in semidefinite programming
From MaRDI portal
Abstract: In semidefinite programming a proposed optimal solution may be quite poor in spite of having sufficiently small residual in the optimality conditions. This issue may be framed in terms of the discrepancy between forward error (the unmeasurable `true error') and backward error (the measurable violation of optimality conditions). In his seminal work, Sturm provided an upper bound on forward error in terms of backward error and singularity degree. In this paper we provide a method to bound the maximum rank over all solutions and use this result to obtain a lower bound on forward error for a class of convergent sequences. This lower bound complements the upper bound of Sturm. The results of Sturm imply that semidefinite programs with slow convergence necessarily have large singularity degree. Here we show that large singularity degree is, in some sense, also a sufficient condition for slow convergence for a family of external-type `central' paths. Our results are supported by numerical observations.
Recommendations
Cites work
- scientific article; zbMATH DE number 3728055 (Why is no real title available?)
- scientific article; zbMATH DE number 3737415 (Why is no real title available?)
- scientific article; zbMATH DE number 1182578 (Why is no real title available?)
- scientific article; zbMATH DE number 1534296 (Why is no real title available?)
- scientific article; zbMATH DE number 3061616 (Why is no real title available?)
- A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming
- A note on alternating projections for ill-posed semidefinite feasibility problems
- A robust algorithm for semidefinite programming
- Complementarity and nondegeneracy in semidefinite programming
- Conic convex programming and self-dual embedding
- Convex Analysis
- Cubic regularization of Newton method and its global performance
- Error Bounds for Linear Matrix Inequalities
- Facial reduction algorithms for conic optimization problems
- Generating and measuring instances of hard semidefinite programs
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
- Initialization in semidefinite programming via a self-dual skew-symmetric embedding
- Maximum determinant positive definite Toeplitz completions
- On solving trust-region and other regularised subproblems in optimization
- On the identification of the optimal partition for semidefinite optimization
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Polyhedral and semidefinite programming methods in combinatorial optimization
- Preprocessing and regularization for degenerate semidefinite programs
- Regularizing the abstract convex program
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization
- Strong duality in conic linear programming: facial reduction and extended duals
- The Gauss-Newton direction in semidefinite programming
- The Generic Nature of Optimality Conditions in Nonlinear Programming
- The real positive definite completion problem for a simple cycle
- The variation of the spectrum of a normal matrix
Cited in
(12)- Proximal-stabilized semidefinite programming
- A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
- Condition-measure bounds on the behavior of the central trajectory of a semidefinite program
- Interval Enclosures of Upper Bounds of Roundoff Errors Using Semidefinite Programming
- Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
- On the central path of semidefinite optimization: degree and worst-case convergence rate
- A strengthened Barvinok-Pataki bound on SDP rank
- Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
- Generating linear, semidefinite, and second-order cone optimization problems for numerical experiments
- Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
- Revisiting degeneracy, strict feasibility, stability, in linear programming
- Error Bounds for Linear Matrix Inequalities
This page was built for publication: Error bounds and singularity degree in semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5857289)
