|
Keywords
|
Semidefinite optimization,predictor-corrector interior-point algorithm, new search directions,
wide neighborhood, polynomial complexity
|
|
Abstract
|
This paper presents a new primal-dual interior-point predictor-corrector algorithm based on
the wide neighborhood for semidefinite optimization (SDO). Per the idea of the neighborhood used, we
decompose Newton’s directions into two separate directions corresponding to the positive and negative parts
of the right-hand side of the centrality equation. The predictor step uses the search directions of the negative
part, while the use of a new corrector direction corresponding to the positive part also reduces the duality
gap in the corrector step. We prove that the new algorithm has an iteration bound of O(√n log Tr(X0S0)
ε ),
which matches the currently best-known iteration bound for interior-point methods. Finally, numerical
results are presented that show the effectiveness and competitiveness of the proposed algorithm.
|