Optimization Online


A New Full-Newton step $O(n)$ Infeasible Interior-Point Algorithm for Semidefinite Optimization

Hossein Mansouri (H.Mansouri***at***tudelft.nl)
Cornelis Roos (C.Roos***at***tudelft.nl)

Abstract: Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed an efficient primal-dual infeasible interior-point algorithm with full Newton steps for linear optimization problems. 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 $\zeta$. The algorithm terminates in at most $O(n\log{\frac{n}{\varepsilon}})$ steps either by finding an $\varepsilon$-solution or by determining that the primal-dual problem pair has no optimal solution with vanishing duality gap satisfying a condition in terms of $\zeta$.

Keywords: Semidefinite optimization, infeasible interior-point method, primal-dual method, polynomial complexity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Manuscript. Delft University of Technology. P.O. Box 5031, 2600 GA Delft, The Netherlands. February 2007.

Download: [Postscript][PDF]

Entry Submitted: 07/09/2008
Entry Accepted: 07/09/2008
Entry Last Modified: 07/16/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society