Corrector-Predictor Interior-Point Method With New Search Direction for Semidefinite Optimization

Abstract

In this paper, we present a new corrector-predictor interior-point method for solving semidefinite optimization. We use an algebraic equivalent transformation of the centering equation of the system which defines the central path. The algebraic transformation plays an essential role in the calculation of the new search directions. We prove that the iteration complexity of the algorithm coincides with the best known ones for interior-point methods (IPMs). To the best of our knowledge, this is the first corrector-predictor interior-point algorithm that uses the search directions obtained from the desired algebraic transformation for semidefinite optimization. Finally, some numerical experiments are provided to demonstrate the efficiency of our new algorithm.

1 Introduction

Semidefinite optimization (SDO) optimizes a linear objective function over the intersection of the cone positive semidefinite matrices with an affine space. Many practical problems in combinatorial optimization can be modeled or approximated as SDOs [1]. SDOs are also used in control theory [4] and eigenvalue optimization problems [23]. SDOs can be efficiently solved by IPMs. Independently of Nesterov and Nemirovskii [27] and Alizadeh [2] generalized IPMs from linear optimization (LO) to SDO. Some articles on IPMs for SDO are published by Helmberg et al. [14], de Klerk [12], Halicka et al. [13], Kheirfam [19, 20] and Wang et al. [32].

The full-Newton step feasible IPM was first introduced for LO by Roos et al. [30]. They provided a novel convergence analysis of the method and obtained the best known iteration complexity for such methods. The extension of this method to SDO based on Nesterov-Todd (NT) directions is discussed by de Klerk [12]. In 2003, an algebraic equivalent transformation (AET) of the system that defines the central path is proposed by Darvay [5]. He used the Newton method for resulting system to obtain search directions based on the square root function, and provided a full-Newton step IPM for LO. The method later generalized to SDO [32], second-order cone optimization (SOCO) [31], symmetric cone optimization (SCO) [33] and convex quadratic symmetric cone optimization (CQSCO) [3]. Subsequently, Wang et al. [34, 35] have tried to improve complexity analysis of IPMs for SDO and SCO, respectively.

An important class of interior-point algorithms which have proven to be efficient in practice are called predictor-corrector (PC) IPMs (see [25, 26]). The first PC interior-point algorithm that uses the AET method for defining the search directions has been proposed by Darvay [6] for LO. Later on, Kheirfam [16,17,18] developed corrector-predictor (CP) IPMs for $P_*(\kappa )$ linear complementarity problem, convex quadratic symmetric optimization (CQSO) and second-order cone optimization (SOCO), which use the search directions based on the square root function. Darvay et al. [11] introduced an CP interior-point algorithm for LO. The authors used the AET method that is based on the difference of the identity map and the square root function, which the first proposed by Darvay et al. in [10] for a full-Newton step IPM. Later on, Darvay et al. [7] and Kheirfam et al. [21] generalized this method to $P_*(\kappa )$-LCP and SCO, respectively.

The aim of this paper is to give a new CP IPM for SDO. The method uses the AET technique that is based on the transformation $\psi (t)=\psi (\sqrt{t})$ with $\psi (t)=t^2$, which was first introduced in [9]. To the best of our knowledge, this is the first CP interior-point algorithm that uses the aforementioned AET for SDO, and therefore the analysis of the algorithm differs from the existing ones. We prove that the complexity of the algorithm coincides with the best known ones of IPMs.

The paper is organized as follows. In Sect. 2 the primal-dual pair of SDO problem, the notation of the central path and the main idea of the AET of the system defining the central path are given. In Sect. 3 we present the new CP interior-point algorithm. Section 4 is devoted to the convergence analysis of the proposed algorithm. In Sect. 5 we present some numerical results. Concluding remarks are given in Sect. 6.

2 The SDO Problem

Let us consider the following primal-dual pair of SDO problems

$$\begin{aligned} (P)~~~~~~~~~\min \{\textrm{tr}(CX): ~\textrm{tr}(A_{i}X)=b_{i},~~i=1, \ldots ,m, ~X\succeq 0\}, \end{aligned}$$

and

$$\begin{aligned} (D)~~~~~~~~~\max \{b^Ty: ~\sum ^m_{i=1}y_{i}A_{i}+S=C, ~S\succeq 0\}, \end{aligned}$$

where $C, X, S\in \mathbb {S}^n$, $b_i\in {\mathbb R}$ and $A_i\in {\mathbb S}^n, i=1, \ldots , m$ are linearly independent. Here, $\mathbb {S}^n$ denotes the set of real symmetric $n\times n$ matrices and $X\succeq 0$ means that X is a symmetric positive semidefinite matrix. For convenience, we denote the feasible set of the primal-dual pair of (P) and (D) as

$$\begin{aligned} \mathcal {F}= & {} \Bigg \{(X, y, S)\in \mathbb {S}^n\times \mathbb {R}^m\times \mathbb {S}^n: \textrm{tr}(A_{i}X)\\= & {} b_{i},\quad i=1, \ldots ,m, ~X\succeq 0 \sum ^m_{i=1}y_{i}A_{i}+S=C, ~S\succeq 0\Bigg \}, \end{aligned}$$

and its relative interior by

$$\begin{aligned} \mathcal {F}^0=\big \{(X, y, S)\in \mathcal {F}: X\succ 0, S\succ 0\big \}, \end{aligned}$$

where $X\succ 0$ is to mean that X is a symmetric positive definite matrix. Throughout this paper, we assume that $\mathcal {F}^0\ne \emptyset$. Under this last assumption, it is well known that the problem pair (P) and (D) have optimal solutions and their optimal values coincide. Hence, the set of optimal solutions contain of all solutions $(X, y, S)\in {\mathbb S^n}\times \mathbb {R}^m\times \mathbb {S}^n$ to the following system is [12]:

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}X)=b_{i},\quad X\succeq 0,\quad i=1, \ldots , m, \nonumber \\{} & {} \displaystyle \sum ^m_{i=1} y_{i}A_{i}+S=C, \quad S\succeq 0, \nonumber \\{} & {} XS=0, \end{aligned}$$

(1)

where the last equality so-called the complementarity condition. The primal-dual path-following IPMs usually replace the complementarity condition with $XS=\mu I$ where $\mu \in \mathbb {R}, \mu >0$. Under this, we have

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}X)=b_{i},\quad X\succ 0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1} y_{i}A_{i}+S=C, \quad S\succ 0,\nonumber \\{} & {} XS=\mu I. \end{aligned}$$

(2)

It is also well known that the system (2) has a unique solution; $(X(\mu ), y(\mu ), S(\mu ))$, for each $\mu >0$ [22, 27]. The set of all solutions $(X(\mu ), y(\mu ), S(\mu ))$ is called the central path. The limit of the central path exists as $\mu \downarrow 0$ and is a solution of (1) [13].

Let

$$\begin{aligned} V:=\frac{1}{\sqrt{\mu }}D^{-1}XD^{-1}=\frac{1}{\sqrt{\mu }}DSD \end{aligned}$$

(3)

where

$$\begin{aligned} D=\big (X^{\frac{1}{2}}(X^{\frac{1}{2}}SX^{\frac{1}{2}})^{\frac{-1}{2}}X^{\frac{1}{2}}\big )^{\frac{1}{2}} \big [=\big (S^{\frac{-1}{2}}(S^{\frac{1}{2}}XS^{\frac{1}{2}})^{\frac{1}{2}}S^{\frac{-1}{2}}\big )^{\frac{1}{2}}\big ]. \end{aligned}$$

Note that the matrices D and V are symmetric and positive definite. Thus, we have

$$\begin{aligned}{} & {} V^2=\Big (\frac{1}{\sqrt{\mu }}D^{-1}XD^{-1}\Big )\Big (\frac{1}{\sqrt{\mu }}DSD\Big )=\frac{1}{\mu }D^{-1}XSD=I\\{} & {} \Leftrightarrow V=I\Leftrightarrow V^2=V \Leftrightarrow \frac{XS}{\mu }=\frac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}. \end{aligned}$$

Now the central path problem (2) can be equivalently stated as

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}X)=b_{i},\quad X\succ 0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1} y_{i}A_{i}+S=C, \quad S\succ 0,\nonumber \\{} & {} \dfrac{XS}{\mu }=\dfrac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}. \end{aligned}$$

(4)

Let $\bar{\psi }: (\xi ^2, \infty )\rightarrow \mathbb {R}$, with $0 \le \xi < 1$, be a continuously differentiable, invertible and monotone increasing function. Now, by applying the AET to the central path problem in the form (2), we have

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}X)=b_{i},\quad X\succ 0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1} y_{i}A_{i}+S=C, \quad S\succ 0,\nonumber \\{} & {} \bar{\psi }\Big (\dfrac{XS}{\mu }\Big )=\bar{\psi }\Big (I\Big ). \end{aligned}$$

(5)

However, if the AET is applied to (4), using the continuously differentiable, invertible function $\psi : (\xi ^2, \infty )\rightarrow \mathbb {R}$ such that $2t\psi ^{'}(t^2)-\psi ^{'}(t)>0$ for all $t>\xi$ with $0 \le \xi < 1$ [8], then we have

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}X)=b_{i},\quad X\succ 0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1} y_{i}A_{i}+S=C, \quad S\succ 0,\nonumber \\{} & {} \psi \Big (\dfrac{XS}{\mu }\Big )=\psi \Big (\dfrac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}\Big ). \end{aligned}$$

(6)

Assuming that we are given a feasible solution (X, y, S) with $X\succ 0$ and $S\succ 0$ and applying Newton’s method to system (6) leads to the following system, which defines the search directions $\Delta X, \Delta y$ and $\Delta S$

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}\Delta X)=0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1}{\Delta y}_{i}A_{i}+\Delta S=0, \nonumber \\{} & {} \psi \Bigg (\frac{XS}{\mu }+\frac{X\Delta S+\Delta X S+\Delta X\Delta S}{\mu }\Bigg )=\psi \Bigg (\Bigg (\frac{XS}{\mu }+\frac{X\Delta S+\Delta X S+\Delta X\Delta S}{\mu }\Bigg )^{\frac{1}{2}}\Bigg ).\nonumber \\ \end{aligned}$$

(7)

Applying Lemma 2.5 in [32], the third equation of system (7) can be written as

$$\begin{aligned}{} & {} \psi \Big (\frac{XS}{\mu }\Big )+\psi ^{'}\Big (\frac{XS}{\mu }\Big )\Big (\frac{X\Delta S+\Delta X S}{\mu }\Big )-\psi \Big (\big (\frac{XS}{\mu }\big )^{\frac{1}{2}}\Big )\\{} & {} \quad -\frac{1}{2}\Big (\frac{XS}{\mu }\Big )^{-\frac{1}{2}}\psi ^{'}\Big (\big (\frac{XS}{\mu }\big )^{\frac{1}{2}}\Big ) \Big (\frac{X\Delta S+\Delta X S}{\mu }\Big )=0. \end{aligned}$$

Therefore, we obtain the following system

$$\begin{aligned}{} & {} \textrm{tr}(A_{i}\Delta X)=0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1}{\Delta y}_{i}A_{i}+\Delta S=0,\nonumber \\{} & {} \Delta X+X\Delta S S^{-1}\nonumber \\{} & {} \quad =\mu \Big (\psi ^{'}\Big (\frac{XS}{\mu }\Big )-\frac{1}{2}\Big (\frac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}\Big )^{-1}\psi ^{'}\Big (\frac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}\Big )\Big )^{-1}\nonumber \\{} & {} \qquad \times \Big (\psi \Big (\frac{(XS)^{\frac{1}{2}}}{\sqrt{\mu }}\Big )-\psi \Big (\frac{XS}{\mu }\Big )\Big )S^{-1}. \end{aligned}$$

(8)

Clearly, from the second equation of (8) we have $\Delta S\in \mathbb {S}^n$. However, in generally $\Delta X$ does not belong to $\mathbb {S}^n$, because $X\Delta S S^{-1}$ may be non-symmetric. To remedy this situation, many researchers have proposed methods for symmetrizing the third equation in the system (8) such that the resulting new system has a unique symmetric solution. Here, we consider the symmetrization scheme that yields the Nesterov–Todd (NT) direction [28, 29]. In the NT-scheme, the term $X\Delta S S^{-1}$ is replaced by $D^2\Delta S (D^2)^T$, where D is defined as in (3). Moreover, let us define

$$\begin{aligned} {\bar{A}}_i:=\frac{1}{\sqrt{\mu }}DA_iD,\quad D_X:=\frac{1}{\sqrt{\mu }}D^{-1}\Delta X D^{-1},\quad D_S:=\frac{1}{\sqrt{\mu }}D\Delta S D. \end{aligned}$$

(9)

Using these notations, the Newton system (8) can be written as

$$\begin{aligned}{} & {} \textrm{tr}({\bar{A}}_{i}D_X)=0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1}{\Delta y}_{i}{\bar{A}}_{i}+D_S=0, \nonumber \\ D_X+D_S=P_V, \end{aligned}$$

(10)

where

$$\begin{aligned} P_V= & {} \sqrt{\mu }D^{-1}\big (D\psi ^{'}(V^2)D^{-1}-\frac{1}{2}D^{-1}V^{-1}DD\psi ^{'}(V)D^{-1}\big )^{-1}\\{} & {} \times \big (D\psi (V)D^{-1}-D\psi (V^2)D^{-1}\big )S^{-1}D^{-1}. \end{aligned}$$

3 Corrector-Predictor Algorithm

In this section, we present a corrector-predictor interior-point algorithm based on the search directions obtained by using the function $\psi (t)=t^2, t>\frac{1}{\sqrt{2}}$ introduced in [9]. In this way, we have

$$\begin{aligned} P_V=(2V^2-I)^{-1}(V-V^3), \end{aligned}$$

and the third equation of (8) becomes

$$\begin{aligned} \Delta X+D^2\Delta S (D^2)^T=\frac{1}{2}\Big (\mu (2XS-\mu I)^{-1}XS-XS\Big )S^{-1}. \end{aligned}$$

(11)

For analysis of our algorithm, we define a norm-based proximity measure $\delta (X, S; \mu )$ as follows:

$$\begin{aligned} \delta (V):=\delta (X, S; \mu ):=\frac{\Vert P_V\Vert _F}{2}=\frac{1}{2}\big \Vert (V-V^3)(2V^2-I)^{-1}\big \Vert _F. \end{aligned}$$

(12)

Using this, we give the $\tau$-neighborhood of the central path as follows:

$$\begin{aligned} \mathcal {N}(\tau ):=\big \{(X, y, S)\in \mathcal {F}^0:~\delta (X, S; \mu )\le \tau \big \}, \end{aligned}$$

where $\tau \in (0, 1)$. Our algorithm starts with a given point $(X, y, S)\in \mathcal {N}(\tau )$ and performs corrector and predictor steps.

In a corrector step, the search direction $(D_X^c, \Delta ^cy, D^c_S)$ is obtained by solving the following scaled system:

$$\begin{aligned}{} & {} \textrm{tr}({\bar{A}}_{i}D^c_X)=0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1}{\Delta ^c y}_{i}{\bar{A}}_{i}+D^c_S=0, \nonumber \\{} & {} D^c_X+D^c_S=(2V^2-I)^{-1}(V-V^3). \end{aligned}$$

(13)

Using the first two equations of the system (13), it follows that

$$\begin{aligned} \textrm{tr}(D^c_XD^c_S)=0. \end{aligned}$$

(14)

Now, using (9), we have $\Delta ^c X=\sqrt{\mu }DD^c_XD$ and $\Delta ^cS=\sqrt{\mu }D^{-1}D^c_SD^{-1}$. In this way, the corrector iterate is calculated by considering a full-NT step as follows:

$$\begin{aligned} (X_+, y_+, S_+)=(X, y, S)+(\Delta ^cX, \Delta ^cy, \Delta ^cS). \end{aligned}$$

In general, the goal of the predictor step is to reach the optimal solution of the underlying problem in a greedy way. This corresponds to the case when we set $\mu =0$ in (11), which leads to

$$\begin{aligned} \Delta X+D^2\Delta S (D^2)^T=-\frac{1}{2}X, \end{aligned}$$

or equivalently, in terms of scaled directions, we have

$$\begin{aligned} D_X+D_S=-\frac{1}{2}V. \end{aligned}$$

Therefore after updating

$$\begin{aligned} P_+= & {} X_+^{\frac{1}{2}}(X_+^{\frac{1}{2}}S_+X_+^{\frac{1}{2}})^{\frac{-1}{2}}X_+^{\frac{1}{2}},\quad D_+=P_+^{\frac{1}{2}},\\ {\bar{A}{_i}}_+= & {} \frac{1}{\sqrt{\mu }}D_+A_iD_+,~V_+=\frac{1}{\sqrt{\mu }}D_+S_+D_+, \end{aligned}$$

where $\mu =\frac{\textrm{tr }(XS)}{n}$, in the predictor we follow the search direction $(D^p_X, \Delta ^py, D^p_S)$ by solving the following scaled Newton system

$$\begin{aligned}{} & {} \textrm{tr}({\bar{A}}{_{i}}_+D^p_X)=0,\quad i=1, \ldots , m,\nonumber \\{} & {} \displaystyle \sum ^m_{i=1}\Delta ^p y_{i}{\bar{A}}{_{i}}_++D^p_S=0,\nonumber \\{} & {} D^p_X+D^p_S=-\frac{1}{2}V_+. \end{aligned}$$

(15)

Then, we compute the predictor directions in the original space as

$$\begin{aligned} \Delta ^pX=\sqrt{\mu }D_+D^p_XD_+,\quad \Delta ^pS=\sqrt{\mu }D_+^{-1}D^p_SD_+^{-1}, \end{aligned}$$

(16)

and the new predictor iterate is given by

$$\begin{aligned} (X^p, y^p, S^p)=(X_+, y_+, S_+)+\theta (\Delta ^pX, \Delta ^py, \Delta ^pS), \end{aligned}$$

where $\theta \in (0, 1)$ is the update parameter and also $\mu ^p=(1-\frac{1}{2}\theta )\mu$. We expect to obtain a new iterate which belongs to the same neighborhood, thus $(X^p, y^p, S^p)\in \mathcal {N}(\tau ).$ The algorithm repeats corrector and predictor steps alternatively until $\textrm{tr}(XS)\le \varepsilon$ is satisfied.

4 Analysis of the Algorithm

In this section, we will analyze the corrector and the predictor steps in detail, respectively. We first recall some results from [12] which are required in the rest of this paper.

Lemma 1

Suppose that $X\succ 0$ and $S\succ 0$. Moreover, let $X(\alpha )=X+\alpha \Delta X$ and $S(\alpha )=S+\alpha \Delta S$ for $0\le \alpha \le 1$. If one has

$$\begin{aligned} \det \big (X(\alpha )S(\alpha )\big )>0,\quad \forall ~ 0\le \alpha \le \bar{\alpha }, \end{aligned}$$

then $X(\bar{\alpha })\succ 0$ and $S(\bar{\alpha })\succ 0.$

Lemma 2

Suppose that $Q\in \mathbb {S}^n_{++}$, and let $M\in R^{n\times n}$ be skew-symmetric. One has $\det (Q+M)>0$. Moreover, if $\lambda _i(Q+M)\in \mathbb {R}, i=1, \ldots , n$, then

$$\begin{aligned} 0<\lambda _{\min }(Q)\le \lambda _{\min }(Q+M)\le \lambda _{\max }(Q+M)\le \lambda _{\max }(Q), \end{aligned}$$

which implies $Q+M\succ 0$.

Lemma 3

Let $D_X, D_S\in \mathbb {S}^n$ be such that $\textrm{tr }(D_XD_S)=0$. Then

$$\begin{aligned} \Vert D_{XS}\Vert _{\infty }\le \frac{1}{4}\Vert D_X+D_S\Vert _F^2,\quad \Vert D_{XS}\Vert _F\le \frac{\sqrt{2}}{4}\Vert D_X+D_S\Vert _F^2, \end{aligned}$$

where $D_{XS}:=\frac{1}{2}(D_XD_S+D_SD_X).$

Let $Q_V=D^c_X-D^c_S$. In this way, by using (14), we have

$$\begin{aligned} \Vert P_V\Vert _F^2=\Vert D^c_X+D^c_S\Vert _F^2=\Vert D^c_X\Vert _F^2+\Vert D^c_S\Vert _F^2=\Vert Q_V\Vert _F^2. \end{aligned}$$

Thus, we can define

$$\begin{aligned} \delta (X, S; \mu )=\frac{\Vert Q_V\Vert _F}{2}. \end{aligned}$$

Furthermore, we have

$$\begin{aligned} D^c_X=\frac{P_V+Q_V}{2},~~~ D^c_S=\frac{P_V-Q_V}{2}, \end{aligned}$$

hence

$$\begin{aligned} D^c_{XS}=\frac{P_V^2-Q_V^2}{4}. \end{aligned}$$

(17)

4.1 The Corrector Step

The next lemma gives a condition which guarantees the strict feasibility of the corrector step.

Lemma 4

Let $\delta :=\delta (X, S; \mu )<1$ and $\lambda _{\min }(V)>\frac{1}{\sqrt{2}}$. Then $X_+\succ 0$ and $S_+\succ 0$.

Proof

Let us consider $0\le \alpha \le 1$ and denote $X(\alpha )=X+\alpha \Delta ^cX$ and $S(\alpha )=S+\alpha \Delta ^cS$. In this way, using (3) and (9), we have

$$\begin{aligned} X(\alpha )=\sqrt{\mu } D(V+\alpha D^c_X)D,~S(\alpha )=\sqrt{\mu } D^{-1}(V+\alpha D^c_S)D^{-1}. \end{aligned}$$

We have

$$\begin{aligned} \frac{X(\alpha )S(\alpha )}{\mu }\sim & {} (V+\alpha D^c_X)(V+\alpha D^c_S)\nonumber \\= & {} V^2+\alpha (VD^c_S+D^c_XV)+\alpha ^2 D^c_XD^c_S\nonumber \\= & {} V^2+\alpha (VD^c_S+VD^c_X)+\alpha (D^c_XV-VD^c_X)\nonumber \\{} & {} +\,\alpha ^2D^c_{XS}+\frac{1}{2}\alpha ^2(D^c_XD^c_S-D^c_SD^c_X) \nonumber \\= & {} (1-\alpha )V^2+\alpha (V^2+VP_V)+\alpha ^2D^c_{XS}\nonumber \\{} & {} +\,\alpha (D^c_XV-VD^c_X)+\frac{1}{2}\alpha ^2(D^c_XD^c_S-D^c_SD^c_X) \nonumber \\= & {} :Q(\alpha )+M(\alpha ). \end{aligned}$$

(18)

It is clear that $M(\alpha )$ is skew-symmetric and also we have

$$\begin{aligned} V^2+VP_V= & {} V^2+(2V^2-I)^{-1}(V^2-V^4)\\= & {} (2V^2-I)^{-1}V^4-I+I\\= & {} (2V^2-I)^{-1}(V^2-I)^2+I\\\succeq & {} I. \end{aligned}$$

From this last inequality and (17) we deduce that

$$\begin{aligned} Q(\alpha )\succeq & {} (1-\alpha )V^2+\alpha \Big (I+\alpha \frac{P_V^2-Q_V^2}{4}\Big )\\\succeq & {} (1-\alpha )V^2+\alpha \Big (I-(1-\alpha )\frac{P_V^2}{4}-\alpha \frac{Q_V^2}{4}\Big ). \end{aligned}$$

In view of the above inequality, $Q(\alpha )$ is positive definite if $\alpha \le 1$ and

$$\begin{aligned} I-(1-\alpha )\frac{P_V^2}{4}-\alpha \frac{Q_V^2}{4}\succ 0. \end{aligned}$$

The last condition follows from

$$\begin{aligned} \Big \Vert (1-\alpha )\frac{P_V^2}{4}+\alpha \frac{Q_V^2}{4}\Big \Vert _2\le & {} \Big \Vert (1-\alpha )\frac{P_V^2}{4}+\alpha \frac{Q_V^2}{4}\Big \Vert _F~~~~~\\\le & {} (1-\alpha )\frac{\Vert P_V\Vert _F^2}{4}+\alpha \frac{\Vert Q_V\Vert _F^2}{4}\\= & {} (1-\alpha )\delta ^2+\alpha \delta ^2=\delta ^2<1.~ \end{aligned}$$

Thus, by Lemma 2, $\det (X(\alpha )S(\alpha ))>0, \forall \alpha \in [0, 1]$, in addition since $X(0)=X\succ 0, S(0)=S\succ 0$, Lemma 1 implies that $X(1)=X_+\succ 0$ and $S(1)=S_+\succ 0$. Thus we have completed the proof. $\square$

Lemma 5

Let $\delta :=\delta (X, S; \mu )<\frac{1}{\sqrt{2}}$ and $\lambda _{\min }(V)>\frac{1}{\sqrt{2}}$. Then, $\lambda _{\min }(V_+)>\frac{1}{\sqrt{2}}$ and

$$\begin{aligned} \delta (X_+, S_+; \mu )\le \frac{5\delta ^2\sqrt{1-\delta ^2}}{1-2\delta ^2}. \end{aligned}$$

Proof

From (18), with $\alpha =1$, we obtain

$$\begin{aligned} V^2_+\sim Q(1)+M(1)= & {} V^2+VP_V+\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\nonumber \\= & {} I+(2V^2-I)^{-1}(V^2-I)^2+\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\nonumber \\= & {} I+\big (4(2V^2-I)V^{-2}+I\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\nonumber \\= & {} I+\big ((9V^2-4I)V^{-2}\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1). \end{aligned}$$

(19)

Therefore, we have

$$\begin{aligned} \Big \Vert I-V^2_+\Big \Vert _F^2= & {} \sum _{i=1}^n\Big (\lambda _i\Big (I+\big ((9V^2-4I)V^{-2}\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\Big )-1\Big )^2 \nonumber \\= & {} \sum _{i=1}^n\lambda _i\Big (\big ((9V^2-4I)V^{-2}\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\Big )^2\nonumber \\= & {} \textrm{tr}\Big (\big ((9V^2-4I)V^{-2}\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\Big )^2\nonumber \\\le & {} \Big \Vert \big ((9V^2-4I)V^{-2}\big )\frac{P_V^2}{4}-\frac{Q_V^2}{4}\Big \Vert _F^2\nonumber \\\le & {} \Big (\big \Vert (9V^2-4I)V^{-2}\big \Vert \frac{\Vert P_V\Vert _F^2}{4}+\frac{\Vert Q_V\Vert _F^2}{4}\Big )^2\nonumber \\\le & {} (9\delta ^2+\delta ^2)^2=100\delta ^4, \end{aligned}$$

(20)

where the first inequality is due to M(1) is skew-symmetric. Beside these, since $\frac{P_V^2}{4}\succeq 0$ and $V^2+VP_V\succeq I$, we have

$$\begin{aligned} V^2_+\sim V^2+VP_V+\frac{P_V^2}{4}-\frac{Q_V^2}{4}+M(1)\succeq I-\frac{Q_V^2}{4}+M(1). \end{aligned}$$

Therefore,

$$\begin{aligned} \lambda _{\min }\big (V^2_+\big )\ge 1-\Big \Vert \frac{Q_V^2}{4}\Big \Vert _F=1-\delta ^2. \end{aligned}$$

(21)

Using $\delta <\frac{1}{\sqrt{2}}$, we have $\lambda _{\min }\big (V_+\big )\ge \sqrt{1-\delta ^2}>\frac{1}{\sqrt{2}}$. This proves the first part of the lemma. Moreover, we have

$$\begin{aligned} \delta (V_+):=\delta (X_+, S_+; \mu )=\frac{1}{2}\big \Vert (I-V_+^2)V_+(2V_+^2-I)^{-1}\big \Vert _F. \end{aligned}$$

(22)

Let us consider the function $f(t)=\frac{t}{2t^2-1}, \forall t>\frac{1}{\sqrt{2}}$. We get $f^{'}(t)<0$, this means that f(t) is decreasing on $t>\frac{1}{\sqrt{2}}$. Using this, (22), (21) and (20), we obtain

$$\begin{aligned} \delta (V_+):=\delta (X_+, S_+; \mu )\le \frac{1}{2}\frac{\sqrt{1-\delta ^2}}{2(1-\delta ^2)-1}\big \Vert I-V_+^2\big \Vert _F\le \frac{5\delta ^2\sqrt{1-\delta ^2}}{1-2\delta ^2}. \end{aligned}$$

This completes the proof. $\square$

Lemma 6

Suppose that $\delta :=\delta (X, S; \mu )<\frac{1}{\sqrt{2}}$ and $\lambda _{\min }(V)>\frac{1}{2}$. Then

$$\begin{aligned} \textrm{tr}(X_+S_+)\le \mu \big (n+{4}\big ). \end{aligned}$$

Proof

Since $V^2_+\sim \frac{X_+S_+}{\mu }$, we have $\textrm{tr}(X_+S_+)=\mu \textrm{tr}(V^2_+)$. Therefore, from (19) it follows that

$$\begin{aligned} \textrm{tr}(X_+S_+)= & {} \mu \Big (n+\textrm{tr}\big ((9V^2-4I)V^{-2}\frac{P_V^2}{4}-\frac{Q^2_V}{4}+M(1)\big )\Big )~~~~~~~~~~\\\le & {} \mu \Big (n+\lambda _{\max }\big ((9V^2-4I)V^{-2}\big )\textrm{tr}\big (\frac{P_V^2}{4}\big )-\textrm{tr}\big (\frac{Q^2_V}{4}\big )\Big )~~~~~~~\\\le & {} \mu \Big (n+9\frac{\Vert P_V\Vert _F^2}{4}-\frac{\Vert Q_V\Vert _F^2}{4}\Big )=\mu (n+8\delta ^2)\le \mu (n+4),~ \end{aligned}$$

where the first inequality is due to M(1) is skew-symmetric. $\square$

4.2 The Predictor Step

The next lemma gives a sufficient condition for the strict feasibility of the predictor step.

Lemma 7

Let $(X_+, y_+, S_+)\in \mathcal {F}^0$ and $\mu >0$. Let

$$\begin{aligned} X^p=X_++\theta \Delta ^pX,\quad S^p=S_++\theta \Delta ^pS \end{aligned}$$

denote the iterates after a predictor step, where $\theta \in [0, 1]$. Then $(X^p, y^p, S^p)\in \mathcal {F}^0$ if

$$\begin{aligned} h(\delta _+, \theta , n)=\frac{1}{\rho ^2(2\delta _+)}-\frac{n\sqrt{2}\theta ^2}{16(1-\theta /2)}\rho ^2(2\delta _+)>0, \end{aligned}$$

where $\delta _+=\delta (X_+, S_+; \mu )$ and $\rho (\delta _+)=\delta _++\sqrt{1+\delta _+^2}$.

Proof

Let $0\le \alpha \le 1$. We set $X^p(\alpha )=X_++\alpha \theta \Delta ^pX$ and $S^p(\alpha )=S_++\alpha \theta \Delta ^pS.$ In this way, we have

$$\begin{aligned} X^p(\alpha )S^p(\alpha )= & {} \big (X_++\alpha \theta \Delta ^pX\big )\big (S_++\alpha \theta \Delta ^pS\big )\nonumber \\\sim & {} \mu (V_++\alpha \theta D^p_X)(V_++\alpha \theta D^p_S) \nonumber \\= & {} \mu \Big (V_+^2+\alpha \theta \big (D^p_X V_++V_+ D^p_S\big )+\alpha ^2\theta ^2D^p_XD^p_S\Big )\nonumber \\= & {} \mu \Big (\big (1-\frac{\alpha \theta }{2}\big )V_+^2+\alpha \theta \big (D^p_XV_+-V_+D^p_X\big )+\alpha ^2\theta ^2D^p_XD^p_S\Big )\nonumber \\= & {} \mu \Big (\big (1-\frac{\alpha \theta }{2}\big )V_+^2+\frac{1}{2}\alpha ^2\theta ^2\big (D^p_XD^p_S+D^p_SD^p_X\big )\Big )\nonumber \\{} & {} +\mu \alpha \theta \Big (\big (D^p_XV_+-V_+D^p_X\big )+\frac{1}{2}\alpha \theta \big (D^p_XD^p_S-D^p_SD^p_X\big )\Big ). \end{aligned}$$

(23)

Note that

$$\begin{aligned} Q(\alpha ):=\big (1-\frac{\alpha \theta }{2}\big )V_+^2+\frac{1}{2}\alpha ^2\theta ^2\big (D^p_XD^p_S+D^p_SD^p_X\big )\in \mathbb {S}^n_{++}, \end{aligned}$$

and

$$\begin{aligned} M(\alpha ):=\big (D^p_XV_+-V_+D^p_X\big )+\frac{1}{2}\alpha \theta \big (D^p_XD^p_S-D^p_SD^p_X\big ) \end{aligned}$$

is skew-symmetric. Invoking Lemmas 2 and 3, and using (23) it follows that

$$\begin{aligned} \lambda _{\min }\Big (\frac{X^p(\alpha )S^p(\alpha )}{(1-\alpha \theta /2)\mu }\Big )\ge & {} \lambda _{\min }\Big (V_+^2+\frac{\alpha ^2\theta ^2}{2(1-\alpha \theta /2)}\big (D^p_XD^p_S+D^p_SD^p_X\big )\Big )~~\nonumber \\\ge & {} \lambda _{\min }\big (V^2_+\big )-\frac{\alpha ^2\theta ^2}{2(1-\alpha \theta /2)}\big \Vert D^p_XD^p_S+D^p_SD^p_X\big \Vert _{F} \nonumber \\\ge & {} \lambda ^2_{\min }\big (V_+\big )-\frac{\sqrt{2}\alpha ^2\theta ^2}{4(1-\alpha \theta /2)}\big \Vert D^p_X+D^p_S\big \Vert ^2_F~~~~~~~~~\nonumber \\\ge & {} \lambda ^2_{\min }\big (V_+\big )-\frac{\sqrt{2}\theta ^2}{16(1-\theta /2)}\big \Vert V_+\big \Vert ^2_F,~~~~~~~~~~~~~~~~~ \end{aligned}$$

(24)

where the third inequality follows from Lemma 3 and the last inequality is due to the fact that the $g(\alpha )=\frac{\alpha ^2\theta ^2}{1-\alpha \theta /2}$ function is increasing with respect to $0\le \alpha \le 1$ and each fixed $0<\theta <1$; that is $g(\alpha )\le g(1)$, and the third equation of (15).

Now, we define $\sigma _+=\frac{1}{2}\big \Vert V_+^{-1}-V_+\big \Vert _F$ that was first introduced by Jiang [15] (without the constant $\frac{1}{2}$) and with the coefficient $\frac{1}{2}$ in [12]. In this case, for each $1\le i\le n$ we have

$$\begin{aligned} \frac{1}{\rho (\sigma _+)}\le \lambda _i(V_+)\le \rho (\sigma _+). \end{aligned}$$

(25)

On the other hand, we have

$$\begin{aligned} \delta _+=\frac{1}{2}\Big \Vert V^2_+(V_+^{-1}-V_+)(2V^2_+-I)^{-1}\Big \Vert _F \ge \frac{1}{2}\sigma _+, \end{aligned}$$

where the inequality follows from the inequality of $V_+\succ \frac{1}{\sqrt{2}}I$ and the fact that the function $f(t)=\frac{t^2}{2t^2-1}\ge \frac{1}{2}$ for $t>\frac{1}{\sqrt{2}}$. The above inequality implies that $\sigma _+\le 2\delta _+$. Since $\rho (\sigma _+)$ is increasing with respect to $\sigma _+$, we obtain $\rho (\sigma _+)\le \rho (2\delta _+)$. Hence, $\lambda _{\min }(V_+)\ge \frac{1}{\rho (2\delta _+)}$. Therefore,

$$\begin{aligned} \lambda _{\min }\left( \frac{X^p(\alpha )S^p(\alpha )}{(1-\alpha \theta /2)\mu }\right)\ge & {} \frac{1}{\rho ^2(2\delta _+)}-\frac{\sqrt{2} \theta ^2}{16(1-\theta /2)}\sum _{i=1}^n\lambda ^2_i(V_+)\nonumber \\\ge & {} \frac{1}{\rho ^2(2\delta _+)}-\frac{n\sqrt{2} \theta ^2}{16(1-\theta /2)}\rho ^2(2\delta _+)\nonumber \\= & {} h(\delta _+, \theta , n)>0. \end{aligned}$$

(26)

The above inequality implies that $\det (X^p(\alpha )S^p(\alpha ))>0$ for each $0\le \alpha \le 1$. Therefore, in view of Lemma 1 it follows that $X^p(1)=X^p\succ 0$ and $S^p(1)=S^p\succ 0$. The proof is completed. $\square$

Let $V^p=\frac{1}{\sqrt{\mu ^p}}{(D^p)}^{-1}X^p{(D^p)}^{-1}=\frac{1}{\sqrt{\mu ^p}}D^pS^pD^p,$ where

$$\begin{aligned} D^p=\big [(X^p){^{\frac{1}{2}}}((X^p){^{\frac{1}{2}}}S^p(X^p){^{\frac{1}{2}}})^{\frac{-1}{2}}(X^p){^{\frac{1}{2}}}\big ]^{\frac{1}{2}},~ \mu ^p=\Big (1-\frac{\theta }{2}\Big )\mu . \end{aligned}$$

In this way, we have

$$\begin{aligned} (V^p)^2=\frac{1}{\mu ^p}(D^{p}){^{-1}}X^pS^pD^{p}\sim \frac{1}{\mu ^p}X^pS^p. \end{aligned}$$

(27)

Invoking (26) with $\alpha =1$, together with (27), we obtain

$$\begin{aligned} \lambda _{\min }\big ((V^p)^2\big )\ge h(\delta _+, \theta , n)>0. \end{aligned}$$

(28)

Lemma 8

Let $X_+\succ 0$ and $S_+\succ 0$ be a primal-dual feasible solution and $\mu ^p=(1-\frac{\theta }{2})\mu$, where $0<\theta <1$. Moreover, let $h(\delta _+, \theta , n)>\frac{1}{2}$ and let $(X^p, y^p, S^p)$ denotes the iterate after a predictor step. Then, $\lambda _{\min }(V^p)>\frac{1}{\sqrt{2}}$ and

$$\begin{aligned} \delta ^p:=\delta (X^p, S^p; \mu ^p)\le \frac{\sqrt{h(\delta _+, \theta , n)}}{2(2h(\delta _+, \theta , n)-1)}\left( 10\delta ^2+\frac{n\theta ^2\rho ^2(2\delta _+)}{8\sqrt{2}(1-\frac{\theta }{2})}\right) . \end{aligned}$$

Proof

From the assumption $h(\delta _+, \theta , n)>\frac{1}{2}$ and (28) it follows that $\lambda _{\min }(V^p)>\frac{1}{\sqrt{2}}$. From Lemma 7, together with $h(\delta _+, \theta , n)>\frac{1}{2}>0$, we deduce that the predictor step is strictly feasible; i.e, $(X^p, y^p, S^p)\in \mathcal {F}^0$.

By the definition of proximity measure at $(X^p, y^p, S^p)$ one finds that

$$\begin{aligned} \delta ^p=\delta (X^p, S^p; \mu ^p)= & {} \frac{1}{2}\big \Vert \big (V^p-(V^p)^3\big )(2(V^p)^2-I)^{-1}\big \Vert _F \nonumber \\= & {} \frac{1}{2}\big \Vert \big (I-(V^p)^2\big )V^p(2(V^p)^2-I)^{-1}\big \Vert _F\nonumber \\= & {} \frac{1}{2}\sqrt{\sum _{i=1}^n \left( \frac{\lambda _i(V^p)}{(2\lambda ^2_i(V^p)-1)}\big (1-\lambda ^2_i(V^p)\big )\right) ^2}. \end{aligned}$$

(29)

Let us consider the function

$$\begin{aligned} g(t)=\frac{t}{2(2t^2-1)},\quad t>\frac{1}{\sqrt{2}}. \end{aligned}$$

Since $g'(t)<0$, g(t) is decreasing, from (29) and $\lambda _i(V^p)\ge \lambda _{\min }(V^p)$ it follows that

$$\begin{aligned} \delta ^p\le & {} g\left( \lambda _{\min }(V^p)\right) \sqrt{\sum _{i=1}^n\big (1-\lambda ^2_i(V^p)\big )^2}\nonumber \\\le & {} g\left( \sqrt{h(\delta _+, \theta , n)} \right) \big \Vert I-(V^p)^2\big \Vert _F\nonumber \\= & {} g\left( \sqrt{h(\delta _+, \theta , n)}\right) \big \Vert I-V^2_+-\frac{\theta ^2}{2(1-\theta /2)} (D_X^pD_S^p+D_S^pD_X^p)-\frac{\theta }{1-\theta /2}M(1))\big \Vert _F\nonumber \\\le & {} g\left( \sqrt{h(\delta _+, \theta , n)}\right) \Big (\big \Vert I-V^2_+\big \Vert _F +\frac{\theta ^2}{2(1-\theta /2)}\big \Vert D_X^pD_S^p+D_S^pD_X^p\big \Vert _F\Big )\nonumber \\\le & {} g\left( \sqrt{h(\delta _+, \theta , n)}\right) \Big (\big \Vert I-V^2_+\big \Vert _F +\frac{\theta ^2}{2\sqrt{2}(1-\theta /2)}\big \Vert D^p_X+D^p_S\big \Vert ^2_F\Big )\nonumber \\\le & {} g\left( \sqrt{h(\delta _+, \theta , n)}\right) \Big (\big \Vert I-V^2_+\big \Vert _F +\frac{\theta ^2}{8\sqrt{2}(1-\theta /2)}\big \Vert V_+\big \Vert ^2_F\Big )\nonumber \\\le & {} \frac{\sqrt{h(\delta _+, \theta , n)}}{2(2h(\delta _+, \theta , n)-1)} \Big (10\delta ^2+\frac{n\theta ^2\rho ^2(2\delta _+)}{8\sqrt{2}(1-\theta /2)}\Big ), \end{aligned}$$

where the second inequality follows from that g is decreasing and (28), the equality is due to (23) with $\alpha =1$ and (27). Since M(1) is skew-symmetric, the third inequality is obtained in a similar fashion to the proof of Lemma 4.8 in [24] and the triangle inequality, the fourth inequality concludes from Lemma 3, the fifth inequality is obtained from the third equation of the system (15) and the last inequality is due to (20), (25) and $\rho (\sigma _+)\le \rho (2\delta _+)$. Thus we have completed the proof. $\square$

In the next lemma, we give an upper bound for the duality gap after a main iteration.

Lemma 9

Suppose that $\delta :=\delta (X, S; \mu )<\frac{1}{\sqrt{2}}$ and $\lambda _{\min }(V)>\frac{1}{\sqrt{2}}$. Moreover, let $0<\theta <1$. Then

$$\begin{aligned} \textrm{tr}(X^pS^p)\le \big (n+{4}\big )\mu ^p. \end{aligned}$$

Proof

Using (27) and (23) with $\alpha =1$, we have

$$\begin{aligned} \textrm{tr}(X^pS^p)= & {} \mu ^p\textrm{tr}\big ((V^p){^2}\big )\\= & {} \mu ^p\textrm{tr}\Big (V^2_++\frac{\theta ^2}{2(1-\theta /2)}(D^p_XD^p_S+D^p_SD^p_X)+\frac{\theta }{1-\theta /2}M(1)\Big )\\= & {} \mu ^p\textrm{tr}\Big (V^2_+\Big )=\mu ^p\textrm{tr}\Big (\frac{X_+S_+}{\mu }\Big )\le \mu ^p\big (n+4\big ), \end{aligned}$$

where the third equality is due to the fact that M(1) is skew-symmetric and $\textrm{tr}(D^p_XD^p_S)=\textrm{tr}(D^p_SD^p_X)=0$ and the last inequality follows from Lemma 6. The proof is completed. $\square$

4.3 Fixing Parameters

In this subsection, we fix the parameters $\theta$ and $\tau$ to guarantee that after a main iteration, the proximity measure will not exceed the proximity parameter $\tau$.

Let $(X, y, S)\in \mathcal {N}(\tau )$ be the iterate at the start of a main iteration with $X\succ 0$ and $S\succ 0$ such that $\delta :=\delta (X, S; \mu )\le \tau <\frac{1}{\sqrt{2}}$. Then, after a corrector step, by Lemma 5, we have

$$\begin{aligned} \delta _+\le \frac{5\delta ^2}{1-2\delta ^2}\sqrt{1-\delta ^2}. \end{aligned}$$

One can easily verify that the right-hand side of the inequality above is increasing with respect to $\delta$, thus we have

$$\begin{aligned} \delta _+\le \frac{5\tau ^2\sqrt{1-\tau ^2}}{1-2\tau ^2} =:\omega (\tau ). \end{aligned}$$

(30)

Following the predictor step and the $\mu$-update, by Lemma 8, we obtain

$$\begin{aligned} \delta ^p\le \frac{\sqrt{h(\delta _+, \theta , n)}}{2(2h(\delta _+, \theta , n)-1)}\left( 10\delta ^2+\frac{n\theta ^2\rho ^2(2\delta _+)}{8\sqrt{2}(1-\frac{\theta }{2})}\right) . \end{aligned}$$

(31)

The function $h(\delta _+, \theta , n)$ is decreasing with respect to $\delta _+$, hence $h(\delta _+, \theta , n)\ge h(\omega (\tau ), \theta , n)$. We have seen earlier that the function $g(t)=\frac{t}{2(2t^2-1)}$ for $t>\frac{1}{\sqrt{2}}$ is decreasing, thus we get

$$\begin{aligned} g\big (\sqrt{h(\delta _+, \theta , n)}\big )\le g\big (\sqrt{h(\omega (\tau ), \theta , n)}\big ). \end{aligned}$$

(32)

By invoking (31) and using (32) and the fact that $\rho (\delta _+)$ is increasing with respect to $\delta _+$, we deduce that

$$\begin{aligned} \delta ^p\le \frac{\sqrt{h(\omega (\tau ), \theta , n)}}{2(2h(\omega (\tau ), \theta , n)-1)}\left( 10\tau ^2+\frac{n\theta ^2\rho ^2(2\omega (\tau ))}{8\sqrt{2}(1-\frac{\theta }{2})}\right) . \end{aligned}$$

To keep $\delta ^p\le \tau$, it suffices that

$$\begin{aligned} \frac{\sqrt{h(\omega (\tau ), \theta , n)}}{2(2h(\omega (\tau ), \theta , n)-1)}\left( 10\tau ^2+\frac{n\theta ^2\rho ^2(2\omega (\tau ))}{8\sqrt{2}(1-\frac{\theta }{2})}\right) \le \tau . \end{aligned}$$

If we take $\tau =\frac{1}{10}$ and $\theta =\frac{1}{3\sqrt{n}}, n\ge 2$, then the above inequality holds and $h(\delta _+, \theta , n)>\frac{1}{2}$. This means that $X, S\succ 0$ and $\delta (X, S; \mu )<\frac{1}{\sqrt{2}}$ are maintained during the algorithm. Therefore, the algorithm is well-defined.

Table 1 The number of iterations and CPU time

4.4 Polynomial Complexity

The next lemma gives an upper bound for the total number of iterations produced by the algorithm.

Lemma 10

Let $X^0\succ 0$ and $S^0\succ 0$ be strictly feasible primal-dual solutions, $\mu ^0=\frac{\textrm{tr}(X^0S^0)}{n}$ and $\delta (X^0, S^0; \mu ^0)<\frac{1}{\sqrt{2}}$. Moreover, let $X^k$ and $S^k$ be the iterates obtained after k iterations. Then, $\textrm{tr}\big (X^kS^k\big )\le \varepsilon$ if

$$\begin{aligned} k\ge 1+\Big \lceil \frac{2}{\theta }\log \frac{5\textrm{tr}(X^0S^0)}{\varepsilon }\Big \rceil . \end{aligned}$$

Proof

Let $\mu ^k$ denote the barrier parameter after the k main iteration. From Lemma 9 we deduce that

$$\begin{aligned} \textrm{tr}\big (X^kS^k\big )\le \mu ^k\big (n+4\big )<5\Big (1-\frac{\theta }{2}\Big )^{k-1}\mu ^0n=5\Big (1-\frac{\theta }{2}\Big )^{k-1}\textrm{tr}(X^0S^0). \end{aligned}$$

This means that $\textrm{tr}\big (X^kS^k\big )\le \varepsilon$ holds if

$$\begin{aligned} 5\Big (1-\frac{\theta }{2}\Big )^{k-1}\textrm{tr}(X^0S^0)\le \varepsilon . \end{aligned}$$

Taking logarithms, we obtain

$$\begin{aligned} (k-1)\log \Big (1-\frac{\theta }{2}\Big )+\log {5\textrm{tr}(X^0S^0)}\le \log \varepsilon . \end{aligned}$$

Since $\log (1+\beta )\le \beta$ for $\beta >-1$, we obtain that the above inequality holds if

$$\begin{aligned} -\frac{\theta }{2}(k-1)+\log {5\textrm{tr}(X^0S^0)}\le \log \varepsilon . \end{aligned}$$

From this, we conclude that

$$\begin{aligned} k\ge 1+\frac{2}{\theta }\log \frac{5\textrm{tr}(X^0S^0)}{\varepsilon }. \end{aligned}$$

This proves the lemma. $\square$

Using Lemma 10, we can easily conclude the main result of the paper.

Theorem 1

Let $\theta =\frac{1}{3\sqrt{n}}$ and $\tau =\frac{1}{10}$. Then, the proposed corrector-predictor interior-point algorithm is well-defined and requires at most

$$\begin{aligned} \mathcal {O}\left( \sqrt{n}\log \frac{5\textrm{tr}(X^0S^0)}{\varepsilon }\right) \end{aligned}$$

iterations. The output is a strictly feasible primal-dual pair (X, S) satisfying $\textrm{tr}(XS)\le \varepsilon .$

5 Numerical Results

In this section, we compare our new algorithm (new Algor.) with the presented algorithms in [17, 18]. Numerical results were obtained by using MATLAB R2014b on an Intel Core i7 PC with 8GB RAM under Windows 10 to test some SDO problems: Max-cut problem(Mc); Norm-min problem(Nm); Control problem(C) and Graph partitioning problem (Gp). The algorithms are stopped when $\mu \le \varepsilon \mu _0$ with $\varepsilon =10^{-5}$. In Table 1, we present the names of the test problems, the dimension of the blocks and the number of the constraint equations (denoted by (n, m)), the number of iterations (iter) and CPU time. Numerical results show that our presented algorithm is reliable and promising.

6 Concluding Remarks

We have presented a new CP interior-point algorithm for SDO. We used the AET method based on the function $\psi (t)=\psi (\sqrt{t})$ with $\psi (t)=t^2$ for the system which defines the central path. We then used the symmetrization scheme that yields the NT directions and applied Newton’s approach to the transformed system in order to get the new search directions. Furthermore, we presented the convergence analysis of the proposed algorithm and obtained the iteration complexity bound $\mathcal {O}\Big (\sqrt{n}\log \frac{5\textrm{tr}(X^0S^0)}{\varepsilon }\Big )$. We had to assure that the smallest eigenvalue of V-matrices of the scaled space is greater than $\frac{1}{\sqrt{2}}$. To our best knowledge, this is the first CP IPM for solving SDO where the AET method based on the function $\psi (t)=\psi (\sqrt{t})$ is used to derive the new search directions. According to our preliminary numerical results, the new algorithm performs efficiently.