Research Specifications

Home \A new wide neighbourhood ...
Title
A new wide neighbourhood primal-dual interior-point algorithm for semidefinite optimization
Type of Research Article
Keywords
wide neighbourhood; interior-point method; iteration complexity bound
Abstract
In this paper, we present a wide neighbourhood primaldual 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,werecommend 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 (X0, y0, S0) ∈ 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
Researchers Behrouz Kheirfam (First Researcher)