A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization

A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization

0.00 Avg rating0 Votes
Article ID: iaor200971367
Country: United States
Volume: 52
Issue: 2
Start Page Number: 225
End Page Number: 255
Publication Date: Oct 2009
Journal: Numerical Algorithms
Authors: ,
Keywords: interior point methods, programming (semidefinite)
Abstract:

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ϵ-solution or by detecting that the primal-dual problem pair has no optimal solution (X *,y *,S *) with vanishing duality gap such that the eigenvalues of X * and S * do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.

Reviews

Required fields are marked *. Your email address will not be published.