A predictor–corrector algorithm for quadratic semi-definite programming combining Dikin-type and Newton centering steps

Recently, we have extended Semi-Definite Programming by adding a quadratic term in the objective function and give a potential reduction algorithm using NT directions. This paper presents a predictor–corrector algorithm using both Dikin-type and Newton centering steps and studies properties of Dikin-type step. In this algorithm, when the condition K(X S) is less than a given number K0, we use Dikin-type step. Otherwise, Newton centering step is taken. In both cases, step-length is determined by line search. We show that at least a constant reduction in the potential function is guaranteed. Moreover the algorithm is proved to terminate in O(√(n) log(1/ϵ)) steps. In the end of this paper, we discuss how to compute search direction (ΔX, ΔS) using the conjugate gradient method.