On the identification of the optimal partition for semidefinite optimization
- 5 March 2019
- journal article
- research article
- Published by Taylor & Francis in INFOR: Information Systems and Operational Research
- Vol. 58 (2) , 225-263
Abstract
The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial time. In this paper, we consider the identification of the optimal partition of semidefinite optimization, for which we provide an approximation from a bounded sequence of solutions on, or in a neighbourhood of the central path. Using bounds on the magnitude of the eigenvalues, we identify the subsets of eigenvectors of the interior solutions whose accumulation points are orthonormal bases for the subspaces of the optimal partition. The magnitude of the eigenvalues of an interior solution is quantified using a condition number and an upper bound on the distance of an interior solution to the optimal set. We provide a measure of proximity of the approximation obtained from the central solutions to the true optimal partition of the problem.Keywords
Funding Information
- Air Force Office of Scientific Research (FA9550-15-1-0222)
This publication has 31 references indexed in Scilit:
- Extension of Rotfel’d TheoremLinear Algebra and its Applications, 2011
- Perturbation analysis of second-order cone programming problemsMathematical Programming, 2005
- Analyticity of the central path at the boundary point in semidefinite programmingEuropean Journal of Operational Research, 2002
- On the Convergence of the Central Path in Semidefinite OptimizationSIAM Journal on Optimization, 2002
- A Strongly Polynomial Rounding Procedure Yielding a Maximally Complementary Solution for $P_*(\kappa)$ Linear Complementarity ProblemsSIAM Journal on Optimization, 2000
- Error Bounds for Linear Matrix InequalitiesSIAM Journal on Optimization, 2000
- On parametric semidefinite programmingApplied Numerical Mathematics, 1999
- Initialization in semidefinite programming via a self-dual skew-symmetric embeddingOperations Research Letters, 1997
- Extension of Hoffman’s Error Bound to Polynomial SystemsSIAM Journal on Optimization, 1994
- Degeneracy in interior point methods for linear programming: a surveyAnnals of Operations Research, 1993