A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization. (2nd December 2019)

• Record Type: Journal Article
• Authors: Kheirfam, B.
• Is Part Of: Optimization. Volume 68:Number 12(2019)
• Page Start: 2247
• Page End: 2267
• Publication Date: 2019-12-02
• Subjects: Semidefinite optimization -- wide neighbourhood -- interior-point method -- iteration complexity bound; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2019.1591405
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: In this paper, we present a wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization. We define a new wide neighbourhood W ( β, τ ), which is an extension of the Darvay-Takács's wide neighbourhood for linear optimization to semidefinite optimization. We use an algebraic reformulation of the centering equation along with Zhang's symmetrization operator to create symmetric search directions. After applying Newton's method to the resulting system, we recommend using the square root function for simplicity. We consider the Newton direction as the sum of two other directions, corresponding to the negative and positive parts of the right-hand side of the centring equation. Starting with a feasible point ( X 0, y 0, S 0 ) ∈ W ( β, τ ), we prove that our algorithm has complexity the same as small neighbourhood path-following algorithms for semidefinite optimization that use the Nesterov-Todd directions. To the best of our knowledge, this is the first large neighbourhood path-following interior-point algorithm that uses a different neighbourhood from those available for semidefinite optimization.