Abstract:

In this paper, a corrector-predictor interior-point algorithm is proposed for symmetric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iterates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algorithm is shown and it is proved that the algorithm has the complexity bound O(√rL) for the well-known Nesterov-Todd search direction and O(rL) for the xs and sx search directions.

Key words: symmetric optimization, ellipsoidal approximation, wide neighborhood, interior-point methods, polynomial complexity