|
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
|