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

Semidefinite optimization (SDO) problems are convex optimization problems over the intersection of an affine set and the cone of positive semidefinite matrices. SDO has recently attracted active research from the interior-point methods (IPMs) community. Interior-point methods for SDO have been studied intensively, due to ther 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 (LO) problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper the algorithm is extended to SDO. 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, strictly feasible iterates close enough to the central path of the new perturbed pair are obtained. The starting point depends on a positive number \(\zeta \). The algorithm terminates either by finding an \(\varepsilon\)-solution or by detecting that the primal-dual problem pair has no optimal solution. The iteration bound coincides with the currently best iteration bound for SDO problems and it is of the same order as in the linear optimization (LO) case. Concerning the practical performance of the algorithm, one should realize that it is a common feature of IPMs for LO and SDO with the best known iteration bounds that their practical performance is close to their theoretical performance. Numerical experiments show that when maximizing the barrier parameter with respect to the property given in the paper, the number of iterations reduces drastically and the algorithm becomes really competitive. This goes without worsening the theoretical iteration bound.