Improved Complexity Analysis of Full Nesterov–Todd Step Interior-Point Methods for Semidefinite Optimization

Abstract

In this paper, we present an improved convergence analysis of full Nesterov–Todd step feasible interior-point method for semidefinite optimization, and extend it to the infeasible case. This improvement due to a sharper quadratic convergence result, which generalizes a known result in linear optimization and leads to a slightly wider neighborhood for the iterates in the feasible algorithm and for the feasibility steps in the infeasible algorithm. For both versions of the full Nesterov–Todd step interior-point methods, we derive the same order of the iteration bounds as the ones obtained in linear optimization case.

1 Introduction

Semidefinite optimization (SDO) problems are convex optimization problems over the intersection of an affine set and the cone of positive semidefinite matrices. For years, SDO has been one of the most active research areas in mathematical programming. Particularly, many interior-point methods (IPMs) for linear optimization (LO) are successfully extended to SDO [1–6], due to their polynomial complexity and practical efficiency. Some popular software packages for SDO are developed based on IPMs, such as SDPHA [7], SeDuMi [8], and SDPT3 [9]. For an overview of these results we refer to [10] and within references.

One may distinguish different IPMs, according to whether they are feasible IPMs or infeasible IPMs. Feasible IPMs start with a strictly feasible symmetric positive definite matrix and maintain feasibility during the solution process. However, obtaining such a point is usually as difficult as solving the underlying problem itself. The general method to overcome this problem is to use the homogeneous embedding model for SDO by De Klerk [10], and independently also by Luo et al. [2]. The homogeneous embedding method has been implemented in the well-known solvers SDPHA [7] and SeDuMi [8]. Infeasible IPMs for SDO start with an arbitrary positive definite matrix, and feasibility is researched as optimality is approached. Kojima et al. [1] and Potra and Sheng [4] independently analyzed infeasible IPMs for SDO and derived the best known iteration bound under some mild assumptions. The performance of the existing infeasible IPMs highly depends on the choice of the starting point. The well-known solver SDPT3 [9] employs an infeasible primal-dual predictor-corrector path-following method.

The primal-dual full Newton-step feasible IPM for LO was first analyzed by Roos et al. in [11] and was later extended to infeasible version by Roos [12]. The obtained iteration bounds for both feasible and infeasible versions of the algorithm match the best known ones for these types of algorithms. Both versions of the IPMs were extended by De Klerk [10] and Mansouri and Roos [13] to SDO by using full Nesterov–Todd (NT) direction as a search direction, respectively. Darvay [14] proposed a new full Newton-step feasible IPM for LO. The search direction of his algorithm is introduced by an algebraic equivalent transformation (form) of the nonlinear equations, which define the central path. He also derived the same iteration bound as the one in [11]. Later on, Wang and Bai [15, 16] extended Darvay’s algorithm for LO to second-order cone optimization (SOCO) and SDO. However, the above-mentioned full step IPMs are essentially small-update methods, which enjoy the best known worst-case iteration bound, but they may not be efficient from a practical point of view. The motivation for the use of full steps is that, though such methods are less greedy, the best complexity results for IPMs are obtained for such methods.

In [11], Roos et al. also presented an improved convergence analysis of full Newton-step feasible IPM with a sharper quadratic convergence result for LO. Later on, Gu et al. [17] proposed an improved version of full Newton-step infeasible IPM for LO, where the convergence analysis of the algorithm was simplified. They derived a slightly better iteration bound than the one obtained for such method in [12]. An interesting question here is whether or not we can directly extend both versions of the improved full Newton-step IPMs for LO to SDO. As we will see later, this extension is by no means obvious or expected. Some other related full step IPMs can be refer to [18–25].

The purpose of the paper is to propose an improved convergence analysis of full NT-step IPMs for SDO, which is the generalization of full Newton-step feasible IPM and infeasible IPM for LO analyzed in [11, 17], and full NT-step feasible IPM and infeasible IPM for SDO analyzed in [10, 13], respectively. Our convergence analysis is slightly different from the ones considered in [10, 13]. Here, we establish a sharper quadratic convergence result, which leads to a slightly wider neighborhood for the iterates in the feasible algorithm and for the feasibility steps in the infeasible algorithm. Both versions of the full NT-step IPMs are established the currently best known iteration bounds.

This paper is organized as follows. In Sect. 2, we recall and develop some important results on matrices from linear algebra that relate to SDO. The full NT-step feasible IPM and the full NT-step infeasible IPM for SDO are presented in Sects.  3 and 4, respectively. Finally, some conclusions and topics for further research are made in Sect. 5.

2 Preliminaries

Some notations are used throughout the paper. ${\mathrm{I}\hbox \mathrm{R}}^{m\times n}$ and $\mathbf {C}^{m\times n}$ denote the space of all real and complex $m\times n$ matrices, respectively. $\Vert \cdot \Vert$ and $\Vert \cdot \Vert _\infty$ denote the Frobenius norm and the infinity norm for matrices, respectively. $\mathbf {S}^n$, $\mathbf {S}^n_+$, and $\mathbf {S}^n_{++}$ denote the cone of symmetric, symmetric positive semidefinite and symmetric positive definite real $n\times n$ matrices, respectively. $E$ denotes $n\times n$ identity matrix. $A\succeq B$ ($A\succ B$) means that $A-B$ is positive semidefinite (positive definite). The matrix inner product is defined by $\langle A,B\rangle :=A\cdot B={\mathbf {Tr}} (A^\mathrm{{T}}B)$. For any $V\in \mathbf {S}^n,$ we denote by $\lambda (V)$ the vector of eigenvalues of $V$ arranged in non-increasing order, that is, $\lambda _1(V)\ge \lambda _2(V)\ge \cdots \ge \lambda _n(V)$. $\lambda _\mathrm{max}(V)$ and $\lambda _\mathrm{min}(V)$ denote the largest and the smallest eigenvalue of the matrix $V$, respectively. For any matrix $M$, we denote by $\sigma _1(M)\ge \sigma _2(M)\ge \cdots \ge \sigma _n(M)$ the singular values of $M$. Especially if $M$ is symmetric, then one has $\sigma _ i(M):=|\lambda _i(M)|,~i=1,\,2,\,\ldots ,\,n$.

First, we recall three well-known inequalities on the singular values of the matrices from [26].

Lemma 2.1

( Theorem 3.3.13 in [26]) Let $A\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$. Then

$$\begin{aligned} \sum _{i=1}^n|\lambda _i(A)|\le \sum _{i=1}^n\sigma _i(A). \end{aligned}$$

Lemma 2.2

(Theorem 3.3.14 in [26]) Let $A, B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$. Then

$$\begin{aligned} \sum _{i=1}^n\sigma _i(AB)\le \sum _{i=1}^n\sigma _i(A)\sigma _i(B). \end{aligned}$$

Lemma 2.3

(Corollary 3.4.3 in [26]) Let $A, B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$. Then

$$\begin{aligned} \sum _{i=1}^n\sigma _i(A+B)\le \sum _{i=1}^n\sigma _i(A)+\sum _{i=1}^n\sigma _i(B). \end{aligned}$$

Lemma 2.4

Let $A, B\in \mathbf {S}^n$. Then

$$\begin{aligned} -\frac{1}{2}\Vert A-B\Vert ^2 E\preceq AB+BA\preceq \frac{1}{2}\Vert A+B\Vert ^2 E. \end{aligned}$$

Proof

We have

$$\begin{aligned} AB+BA=\frac{1}{2}\left( (A+B)^2-(A-B)^2\right) . \end{aligned}$$

Note that $(A+B)^2$ and $(A-B)^2$ are positive semidefinite matrices. This implies

$$\begin{aligned} -\frac{1}{2}(A-B)^2 \preceq AB+BA\preceq \frac{1}{2}(A+B)^2. \end{aligned}$$

Since $A+B$ and $A-B$ are symmetric matrices, and

$$\begin{aligned} X\preceq |\lambda _\mathrm{max}(X)|E=\sigma _\mathrm{max}(X)E\preceq \Vert X\Vert E, \end{aligned}$$

for any symmetric matrix $X\in \mathbf {S}^n$, and $\Vert X^2\Vert \le \Vert X\Vert ^2$, we obtain

$$\begin{aligned} -\frac{1}{2}\Vert A-B\Vert ^2 E\preceq AB+BA\preceq \frac{1}{2}\Vert A+B\Vert ^2 E. \end{aligned}$$

This completes the proof of the lemma. $\square$

Lemma 2.5

Let $A,B\in \mathbf {S}^n$. Then

$$\begin{aligned} \sum _{i=1}^n \left| \lambda _i\left( \frac{AB+BA}{2}\right) \right| \le \frac{1}{2}(\Vert A\Vert ^2+\Vert B\Vert ^2). \end{aligned}$$

Proof

We have

$$\begin{aligned} \sum _{i=1}^n \left| \lambda _i\left( \frac{AB+BA}{2}\right) \right|&\le \frac{1}{2}\sum _{i=1}^n\sigma _i(AB+BA)\le \frac{1}{2}\sum _{i=1}^n(\sigma _i(AB)+\sigma _i(BA))\\&\le \sum _{i=1}^n\sigma _i(A)\sigma _i(B)\le \frac{1}{2}\sum _{i=1}^n(\sigma _i^2(A)+\sigma _i^2(B))\\&= \frac{1}{2}(\Vert A\Vert ^2+\Vert B\Vert ^2). \end{aligned}$$

The first inequality follows from Lemma 2.1, the second inequality follows from Lemma 2.3, the third line follows from Lemma 2.2, while the last line follows from the fact that $2ab\le a^2+b^2$ for any $a,b\in {\mathrm{I}\hbox \mathrm{R}}$. This completes the proof of the lemma. $\square$

Lemma 2.6

(Lemma C.6 in [11]) Let $\gamma$ be a vector in ${\mathrm{I}\hbox \mathrm{R}}^p$ such that $\gamma >-e$ and $e^\mathrm{{T}}\gamma =\sigma$. Then, if either $\gamma \ge 0$ or $\gamma \le 0$,

$$\begin{aligned} \sum _{i=1}^p\frac{-\gamma _i}{1+\gamma _i}\le \frac{-\sigma }{1+\sigma }, \end{aligned}$$

equality holds if and only if at most one of the coordinates of $\gamma$ is nonzero.

Lemma 2.7

Let $A,B\in \mathbf {S}^n$ such that $\langle A,B\rangle =0$ and $\Vert A+B\Vert =2a$ with $a<1$. Then

$$\begin{aligned} \left\langle E, \left( E+\frac{AB+BA}{2}\right) ^{-1}-E\right\rangle \le \frac{2a^4}{1-a^4}. \end{aligned}$$

Proof

Since $\langle A,B\rangle =0$, it follows that

$$\begin{aligned} \Vert A+B\Vert =\Vert A-B\Vert =2a<2. \end{aligned}$$

From Lemma 2.4, we have

$$\begin{aligned} -E\preceq -\frac{1}{4}\Vert A-B\Vert ^2 E\preceq \frac{AB+BA}{2}\preceq \frac{1}{4}\Vert A+B\Vert ^2 E\preceq E. \end{aligned}$$

Hence, putting $M: =\frac{AB+BA}{2}$, we have $\langle E,M\rangle = 0$ and $-E\prec M \prec E$. Now let

$$\begin{aligned} I_+(M):=\{i: \lambda _i(M)>0\}\,\mathrm{and}\, I_-(M):=\{i: \lambda _i(M)<0\} \end{aligned}$$

be two index sets. Then

$$\begin{aligned} \sum _{i\in I_+(M)}\lambda _i(M)=-\sum _{i\in I_-(M)}\lambda _i(M). \end{aligned}$$

Let $\sigma$ denote this common value. Using Lemma 2.6 twice, with respectively $\gamma _i=\lambda _i(M)$ for $i\in I_+(M)$ and $\gamma _i=\lambda _i(M)$ for $i\in I_-(M)$, we have

$$\begin{aligned} \left\langle E, \left( E+\frac{AB+BA}{2}\right) ^{-1}-E\right\rangle&= \langle E, (E+M)^{-1}-E\rangle =\mathbf {Tr}((E+M)^{-1}-E)\\&= \sum _{i=1}^n\left( \frac{1}{1+\lambda _i(M)}-1\right) =\sum _{i=1}^n \frac{-\lambda _i(M)}{1+\lambda _i(M)} \\&= \sum _{i\in I_+(M)}\frac{-\lambda _i(M)}{1+\lambda _i(M)}+\sum _{i\in I_-(M)} \frac{-\lambda _i(M)}{1+\lambda _i(M)}\\&\le \frac{-\sigma }{1+\sigma }+\frac{\sigma }{1-\sigma }=\frac{2\sigma ^2}{1-\sigma ^2}. \end{aligned}$$

Note that the last expression is monotonically increasing in $\sigma$. Hence, we may replace it by an upper bound, which can be obtained, by Lemma 2.5, as follows:

$$\begin{aligned} \sigma&= \frac{1}{2}\sum _{i=1}^n |\lambda _i(M)|=\frac{1}{2}\sum _{i=1}^n \left| \lambda _i\left( \frac{AB+BA}{2}\right) \right| \le \frac{1}{4}(\Vert A\Vert ^2+\Vert B\Vert ^2)\\&= \frac{1}{4}\Vert A+B\Vert ^2=a^2. \end{aligned}$$

Substitution of this bound for $\sigma$ yields

$$\begin{aligned} \left\langle E, \left( E+\frac{AB+BA}{2}\right) ^{-1}-E\right\rangle \le \frac{2a^4}{1-a^4}. \end{aligned}$$

This completes the proof of the lemma. $\square$

Recall that, if $A\in {\mathrm{I}\hbox \mathrm{R}}^{m\times n}$ and $B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times m}$, then

$$\begin{aligned} \mathbf{Tr}(AB)&= \sum _{i=1}^m(AB)_{ii}=\sum _{i=1}^m\sum _{j=1}^nA_{ij}B_{ji} =\sum _{j=1}^n\sum _{i=1}^mB_{ji}A_{ij}\nonumber \\&= \sum _{j=1}^n(BA)_{jj}=\mathbf{Tr}(BA). \end{aligned}$$

(1)

Furthermore, we know that

$$\begin{aligned} \mathbf {Tr}(B^TB)=\sum _{i=1}^m\sum _{j=1}^nB_{ji}^2\ge 0. \end{aligned}$$

(2)

Particularly, if $B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$ is skew-symmetric, then

$$\begin{aligned} \mathbf {Tr}(B^2)=-\mathbf {Tr}(B^TB)\le 0. \end{aligned}$$

(3)

Lemma 2.8

Let $A\in \mathbf {S}^{n}$, and let $B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$ be skew-symmetric. Then

$$\begin{aligned} \Vert A+B\Vert ^2 \ge \Vert A\Vert ^2. \end{aligned}$$

Proof

It follows from (1), (2) and (3) that

$$\begin{aligned} \Vert A+B\Vert ^2&= \mathbf {Tr}\left( (A+B)^T(A+B)\right) =\mathbf {Tr}\left( (A-B)(A+B)\right) \\&= \mathbf {Tr}\left( A^2+AB-BA+B^2\right) \\&= \mathbf {Tr}\left( A^2-B^2\right) = \mathbf {Tr}(A^2)-\mathbf {Tr}(B^2)\ge \mathbf {Tr}(A^2)=\Vert A\Vert ^2. \end{aligned}$$

This completes the proof of the lemma. $\square$

Lemma 2.9

(Lemma A.1 in [10]) Let $A\in \mathbf {S}^{n}_{++}$, and let $B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$ be skew-symmetric. If $\lambda _i(A+B)\in {\mathrm{I}\hbox \mathrm{R}}$ ($i=1,\ldots ,n$), then

$$\begin{aligned} 0<\lambda _\mathrm{min}(A)\le \lambda _\mathrm{min}(A+B)\le \lambda _\mathrm{max}(A+B)\le \lambda _\mathrm{max}(A). \end{aligned}$$

In what follows, we directly cite the following result without its proof, which enables us to prove Lemma 2.11.

Lemma 2.10

(Corollary 3.1 in [28]) Let $M, N\in \mathbf {C}^{n\times n}$ be a Hermitian matrix and a skew-Hermitian matrix (i.e., $N^*=-N$, where $N^*$ denotes the conjugate transpose of $N$), respectively. If $M+N\succ 0$, then

$$\begin{aligned} \mathbf {Tr}(((M+N)^{*}(M+N))^{-r} )\le \mathbf {Tr}(M^{-2r} ),\,\forall r>0. \end{aligned}$$

As a consequence of Lemma 2.10 with $r=1/{2}$, we can easily verify the following result.

Lemma 2.11

Let $A\in \mathbf {S}^n_{++}$, and let $B\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}$ be skew-symmetric. Then

$$\begin{aligned} \Vert (A+B)^{-\frac{1}{2}} \Vert ^2 \le \Vert (A)^{-\frac{1}{2}} \Vert ^2. \end{aligned}$$

3 Full NT-step Feasible IPM

3.1 The SDO Problems

In this paper, we consider the primal problem of SDO in the standard form

$$\begin{aligned} \mathrm{(SDOP)}\qquad \qquad \text{ min } \left\{ C\cdot X: A_i\cdot X = b_i,\,i=1,\,2,\,\ldots ,\,m,\,X \succeq 0\right\} , \end{aligned}$$

and its dual problem

$$\begin{aligned} \mathrm{(SDOD)}\qquad \qquad \text{ max } \left\{ b^\mathrm{{T}} y: \sum \limits _{i=1}^m y_iA_i + S = C,\,S \succeq 0\right\} . \end{aligned}$$

Here, each $A_i \in \mathbf {S}^n$, $b\in {\mathrm{I}\hbox \mathrm{R}}^m$, and $C\in \mathbf {S}^n$. Throughout the paper, we assume that the matrices $A_i$ are linearly independent. Many researchers have studied SDO and achieved plentiful and beautiful results. For an overview of these results, we refer to the subject monograph [10] and references within.

3.2 The Central Path

In this section, we assume that both (SDOP) and (SDOD) satisfy the interior-point condition (IPC), i.e., there exists $(X^0,y^0,S^0)$ such that

$$\begin{aligned} A_i\cdot X^0 = b_i,\,\, i=1,\,\ldots ,\,m,\,X^0 \succ 0,\quad \sum _{i=1}^m y_i^0A_i + S^0 = C^0 ,\,\, S^0 \succ 0. \end{aligned}$$

The Karush–Kuhn–Tucker (KKT) conditions for (SDOP) and (SDOD) are equivalent to the following system

$$\begin{aligned} A_i\cdot X= b_i,\, i=1,\,\ldots ,\,m,\,X\succeq 0,\,\quad \sum _{i=1}^{m} y_i A_i +S = C,\,S\succeq 0,\,\,XS=0. \end{aligned}$$

(4)

The standard approach is to replace the third equation in (4), i.e., the so-called complementarity condition for (SDOP) and (SDOD), by the parameterized equation $XS=\mu E$ with $\mu >0$. This yields

$$\begin{aligned} A_i\cdot X\!=\! b_i,\,i=1,\,\ldots ,\,m,\,X\succeq 0,\,\quad \sum _{i=1}^{m} y_i A_i +S \!=\! C,\,S\succeq 0,\,\, XS=\mu E. \end{aligned}$$

(5)

Under the assumption that (SDOP) and (SDOD) satisfy the IPC (this can be achieved via the so-called self-dual embedding technique, which was first introduced for LO in [27, 29] and later on generalized for SDO by Klerk in [10]), the system (5) has a unique solution, denoted by $(X(\mu ),y(\mu ), S(\mu ))$. We call $X(\mu )$ the $\mu$-center of (SDOP) and $(y(\mu ),S(\mu ))$ the $\mu$-center of (SDOD). The set of $\mu$-centers (with $\mu$ running through positive real numbers) gives a homotopy path, which is called the central path of (SDOP) and (SDOD). If $\mu \rightarrow 0$, then the limit of the central path exists, and since the limit points satisfy the complementarity condition, i.e., $XS=0$, it naturally yields an optimal solution for (SDOP) and (SDOD) [10].

3.3 The Classic NT Search Direction

Now, we consider the symmetrization operator

$$\begin{aligned} H_P(M):=\frac{1}{2}(PMP^{-1}+(PMP^{-1})^\mathrm{{T}}),\quad \forall M\in {\mathrm{I}\hbox \mathrm{R}}^{n\times n}, \end{aligned}$$

introduced by Zhang [5]. It is well known that

$$\begin{aligned} H_P(M)=\mu E\Leftrightarrow M=\mu E, \end{aligned}$$

for any nonsingular matrix $P$, any matrix $M$ with real spectrum and any $\mu \in {\mathrm{I}\hbox \mathrm{R}}$. For any given nonsingular matrix $P$, the system (5) is equivalent to

$$\begin{aligned} A_i\cdot X=b_i,\,i=1,\,\ldots ,\,m,\,X\succeq 0, \sum _{i=1}^{m} y_i A_i +S = C,\,S\succeq 0,\,H_P(XS)=\mu E.\nonumber \\ \end{aligned}$$

(6)

Applying Newton method to the system (6), this yields

$$\begin{aligned} A_i\cdot \Delta X&= b_i-A_i\cdot X,\,i=1,\ldots ,m, \nonumber \\ \sum _{i=1}^m \Delta y_i A_i + \Delta S&= C-\sum _{i=1}^{n} y_i A_i -S, \\ H_P(X \Delta S + \Delta X S)&= \mu E -H_P(X S). \nonumber \end{aligned}$$

(7)

The search direction obtained through the system (7) is called the Monteiro–Zhang (MZ) unified direction. Different choices of the matrix $P$ result in different search directions (see, e.g., [5, 10]). In this paper, we consider the so-called NT-symmetrization scheme, from which the NT search direction [30, 31] is derived. Let

$$\begin{aligned} P:=X^{\frac{1}{2}}(X^{\frac{1}{2}} S X^{\frac{1}{2}})^{-\frac{1}{2}}X^{\frac{1}{2}} =S^{-\frac{1}{2}} (S^{\frac{1}{2}}X S^{\frac{1}{2}})^{\frac{1}{2}}S^{-\frac{1}{2}}, \end{aligned}$$

and $D=P^{\frac{1}{2}}$. The matrix $D$ can be used to rescale $X$ and $S$ to the same matrix $V$, defined by

$$\begin{aligned} V:=\frac{1}{\sqrt{\mu }}D^{-1}X D^{-1}=\frac{1}{\sqrt{\mu }}D S D. \end{aligned}$$

(8)

Let us further define

$$\begin{aligned} \bar{A}_i\!:=\!\frac{1}{\sqrt{\mu }}DA_iD,~i\!=\!1,\ldots ,m,~ D_X\! :=\! \frac{1}{\sqrt{\mu }}D^{-1}\Delta XD^{-1},~\mathrm{and}~D_S \!:=\!\frac{1}{\sqrt{\mu }}D\Delta SD.\nonumber \\ \end{aligned}$$

(9)

From (8) and (9), after some elementary reductions, we have

$$\begin{aligned} \bar{A_i}\cdot D_X&= \frac{1}{\sqrt{\mu }}(b_i-A_i\cdot X),\,i=1,\ldots ,m, \nonumber \\ \sum _{i=1}^m\Delta y_i \bar{A_i} + D_S&= \frac{1}{\sqrt{\mu }}D(C-\sum _{i=1}^{m} y_i A_i -S)D, \\ D_X + D_S&= V^{-1} -V. \nonumber \end{aligned}$$

(10)

The scaled NT search direction ($D_X,\Delta y, D_S)$ is computed by solving (10) so that $\Delta X$ and $\Delta S$ are obtained through (9).

If $X$ is primal feasible and $(y,S)$ are dual feasible, then $b_i-A_i\cdot X=0$ with $i=1,\ldots ,m$ and $C-\sum _{i=1}^{m} y_i A_i -S=0$, whence the system (10) reduces to

$$\begin{aligned} \bar{A_i}\cdot D_X=0,\,i=1,\ldots ,m,\, \sum _{i=1}^m\Delta y_i \bar{A_i} + D_S = 0,\,D_X + D_S= V^{-1} -V, \end{aligned}$$

(11)

which gives the usual scaled NT search direction for feasible primal-dual IPMs.

If $(X,y, S)\ne (X(\mu ), y(\mu ), S(\mu ))$, then $(\Delta X, \Delta y, \Delta S)$ is nonzero. The new iterate is obtained by taking a full NT-step as follows:

$$\begin{aligned} X^+:=X+\Delta X,\quad y^+:=y+\Delta y,\quad \mathrm{and}~ S^+:=S+\Delta S. \end{aligned}$$

(12)

3.4 The Generic Full NT-step Feasible IPM

The generic full NT-step feasible IPM for SDO is now presented in Fig. 1.

Fig. 1

Full NT-step feasible IPM

3.5 Analysis of the Full NT-step Feasible IPM

3.5.1 Feasibility of the Full NT-step

For the analysis of the algorithm, we define a norm-based proximity measure as follows:

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

(13)

Furthermore, we can conclude that

$$\begin{aligned} \delta (V)=0\Leftrightarrow D_X=D_S=0\Leftrightarrow V=E \Leftrightarrow XS=\mu E. \end{aligned}$$

Hence, the value of $\delta (V)$ can be considered as a measure for the distance between the given tripe $(X,y,S)$ and the corresponding $\mu$-center $(X(\mu ),y(\mu ),S(\mu ))$.

The following lemma shows the strict feasibility of the full NT-step under the condition $\delta (X,S;\mu )<1$.

Lemma 3.1

(Lemma 7.1 in [10]) Let $\delta :=\delta (X,S;\mu )<1$. Then, the full NT-step is strictly feasible.

The following lemma shows that, after a full NT-step, the duality gap assumes the same value as at the $\mu$-centers, namely $n\mu$.

Lemma 3.2

(Corollary 7.1 in [10]) After a full NT-step, the duality gap is given by

$$\begin{aligned} \mathbf {Tr}(X^+S^+)= n\mu . \end{aligned}$$

3.5.2 Local Quadratic Convergence to the Central Path

It follows from (12) and (9) that

$$\begin{aligned} X^+=\sqrt{\mu }D(V+D_X)D,\,\mathrm{and}~S^+=\sqrt{\mu }D^{-1}(V+D_S)D^{-1}. \end{aligned}$$

(14)

Therefore

$$\begin{aligned} X^+S^+=\mu D(V+D_X)(V+D_S)D^{-1}. \end{aligned}$$

(15)

From (15), (14) and Lemma 3.1, after some elementary reductions, we can conclude that

$$\begin{aligned} X^+S^+ \sim \mu (V+D_X)(V+D_S)=\mu (E+D_{XS}+M)\succ 0, \end{aligned}$$

(16)

where

$$\begin{aligned} D_{XS}:=\frac{1}{2}\left( D_XD_S+D_SD_X\right) \end{aligned}$$

and

$$\begin{aligned} M:= \frac{1}{2}(D_XD_S-D_SD_X)+\frac{1}{2}(D_XV+VD_S-VD_X-D_SV). \end{aligned}$$

are symmetric and skew-symmetric, respectively.

It is important to investigate the effect on $\delta (X,S;\mu )$ of a full NT-step to the target point $(X(\mu ),y(\mu ),S(\mu ))$. For this purpose, De Klerk [10] extended Theorem II.50 of [11] for LO to the SDO case. This result plays an important role in the analysis of full NT-step infeasible IPM for SDO in [13].

Lemma 3.3

(Lemma 7.4, Corollary 7.2 in [10]) Let $\delta :=\delta (X,S;\mu )<1$. Then

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

Furthermore, if $\delta \le 1/{\sqrt{2}}$, then the full NT-step is strictly feasible and $\delta (X^+,S^+;\mu )\le \delta ^2$, which shows the quadratical convergence of the full NT-step.

In what follows, we give a sharper quadratic convergence result than the above one used in [13], which provides a slightly wider neighborhood for the feasibility step of our algorithm.

Theorem 3.1

Let $\delta :=\delta (X,S;\mu )<1$. Then

$$\begin{aligned} \delta (X^+,S^+;\mu )\le \frac{\delta ^2}{\sqrt{2(1-\delta ^4)}}. \end{aligned}$$

Proof

Let $U:=(E+D_{XS}+M)$. It follows from (16) and (8) that

$$\begin{aligned} \Vert U^{\frac{1}{2}}\Vert ^2=\Vert V^+\Vert ^2=\frac{1}{\mu }\mathbf {Tr}( X_+S_+)=n. \end{aligned}$$

Furthermore, since $M$ is a skew-symmetric matrix, we can conclude that, by Lemma 2.11,

$$\begin{aligned} \Vert U^{-\frac{1}{2}}\Vert ^2= \Vert (E+D_{XS}+M)^{-\frac{1}{2}}\Vert ^2\le \Vert (E+D_{XS})^{-\frac{1}{2}}\Vert ^2. \end{aligned}$$

Now we may write

$$\begin{aligned} 4\delta (X^+,S^+;\mu )^2&= \Vert (V^+)^{-1}-V^+\Vert ^2=\Vert U^{-\frac{1}{2}}-U^{\frac{1}{2}}\Vert ^2\\&= \Vert U^{-\frac{1}{2}}\Vert ^2-n \le \langle E, (E+D_{XS})^{-1}-E \rangle . \end{aligned}$$

Application of Lemma 2.7 to the last expression (with $A=D_X$ and $B=D_S$) yields

$$\begin{aligned} 4\delta (X^+,S^+;\mu )^2\le \left\langle E, \left( E+\frac{D_XD_S+D_SD_X}{2} \right) ^{-1}-E \right\rangle \le \frac{2\delta ^4}{1-\delta ^4}, \end{aligned}$$

since $\Vert D_X+D_S\Vert =2\delta$, with $\delta <1$. This completes the proof of the theorem. $\square$

The following corollary shows the quadratic convergence of the full NT-step to the target $\mu$-center in the wider neighborhood, determined by $1/{\root 4 \of {2}}$ as opposed to $1/{\sqrt{2}}$ in [10].

Corollary 3.1

Let $\delta :=\delta (X,S;\mu )\le 1/{\root 4 \of {2}}$. Then the full NT-step is strictly feasible and $\delta (X^+,S^+;\mu )\le \delta ^2$.

3.5.3 Updating the Barrier Parameter $\mu$

In the following theorem, we investigate the effect on the proximity measure of a full NT-step followed by an update of the barrier parameter $\mu$.

Theorem 3.2

(Lemma 7.5 in [10]) Let $\delta :=\delta (X,S;\mu )<1$ and $\mu ^+=(1-\theta )\mu$ with $0<\theta <1$. Then

$$\begin{aligned} \delta (X,S;\mu ^+)^2= (1-\theta )\delta ^2+\frac{n\theta ^2}{4(1-\theta )}. \end{aligned}$$

Corollary 3.2

Let $\delta :=\delta (X,S;\mu ) \le 1/{\root 4 \of {2}}$ and $\theta = 1/{\sqrt{2n}}$ with $n\ge 2$. Then

$$\begin{aligned} \delta (X^+,S^+;\mu ^+)\le 1/{\root 4 \of {2}}. \end{aligned}$$

Proof

From Corollary 3.1 and the fact that $\delta \le 1/{\root 4 \of {2}}$, we have

$$\begin{aligned} \delta (X^+,S^+;\mu )\le \delta ^2\le 1/{\sqrt{2}}. \end{aligned}$$

Then, after the barrier parameter is updated to $\mu ^+=(1-\theta )\mu$, with $\theta = 1/{\sqrt{2n}}$, Theorem 3.2 yields the following upper bound for $\delta (X^+,S^+;\mu ^+)^2$:

$$\begin{aligned} \delta (X^+,S^+;\mu ^+)^2&\le (1-\theta )\delta (X^+,S^+;\mu )^2+\frac{n\theta ^2}{4(1-\theta )}\\&\le \frac{1-\theta }{2}\nonumber +\frac{1}{8(1-\theta )} \le \mathrm{max}\left\{ \frac{5}{8},\frac{1}{2}\right\} =\frac{5}{8}. \end{aligned}$$

The last inequality holds due to its left hand-side is a convex function of $\theta$, whose values are $5/8$ and $1/2$ in $\theta = 0$ and $\theta = 1/2$. Since $\theta \in [0,1/2]$, the left hand-side does not exceed $5/8$. Note that ${5}/{8}< 1/{\sqrt{2}}$. Hence, we have

$$\begin{aligned} \delta (X^+,S^+;\mu ^+)< 1/{\root 4 \of {2}}. \end{aligned}$$

The conclusion of the corollary follows. $\square$

3.5.4 Iteration Bound

Similar to the proof of Lemma 4.7 in [15], we can easily verify the validity of the following lemma.

Lemma 3.4

Let $X^0$ and $S^0$ be strictly feasible and such that $\mathbf {Tr}(X^0S^0)=n\mu _0$ and $\delta (X^0,S^0;\mu ^0)\le 1/{\root 4 \of {2}}$. Moreover, let $X^k$ and $S^k$ be the matrices obtained after $k$ iterations. Then, the inequality $\mathbf {Tr}(X^k S^k)\le \varepsilon$ is satisfied for

$$\begin{aligned} k\ge \frac{1}{\theta }\log {\frac{n\mu _0}{\varepsilon }}. \end{aligned}$$

As a consequence of Lemma 3.4, we have the main result for the full NT-step feasible IPM.

Theorem 3.3

Let $\tau = 1/{\root 4 \of {2}}$ and $\theta = 1/{\sqrt{2n}}$. Then, the algorithm in Fig. 1 requires at most

$$\begin{aligned} \sqrt{2n}\log {\frac{n\mu _0}{\varepsilon }} \end{aligned}$$

iterations to generate a primal-dual pair $(X,S)$ satisfying $\mathbf {Tr}(XS)\le \varepsilon$.

4 Full NT-step Infeasible IPM

4.1 The Perturbed Problems

We assumed that (SDOP) and (SDOD) have an optimal solution $(X^*,y^*,S^*)$ with vanishing duality gap, i.e., $\mathbf {Tr}(X^*S^*)=0$. As it is common for feasible IPMs, we start the algorithm with choosing arbitrarily $X^0,S^0\in \mathbf {S}_{++}^n$ and $\mu ^0>0$ such that

$$\begin{aligned} X^0=\zeta E,\,y^0=0,\,S^0=\zeta E,\,\mathrm{and}~\mu ^0=\zeta ^2, \end{aligned}$$

(17)

where $\zeta$ is a (positive) number such that $X^*+S^*\preceq \zeta E.$ The initial values of the primal and dual residuals are denoted as $r^0_p$ and $R^0_d$, respectively. So, we have

$$\begin{aligned} \Big (r_p^0\Big )_i:=b_i-\zeta A_i\cdot E,\,i=1,\ldots ,m, \,\mathrm{and}~R_d^0:=C-\sum _{i=1}^m y_i A_i-\zeta E. \end{aligned}$$

For any $\nu$ with $0 < \nu \le 1$, we consider the perturbed problem

$$\begin{aligned} \mathrm{(SDOP_\nu )}\qquad \text{ min }\left\{ \left( C\!-\!\nu R_d^0\right) \cdot X: b_i\!-\!A_i\cdot X \!=\! \nu \Big (r_p^0\Big )_i,\,i\!=\!1,\,2,\,\ldots ,\,m,\,X \succeq 0\right\} , \end{aligned}$$

and its dual problem

$$\begin{aligned} \mathrm{(SDOD_\nu )}\qquad \text{ max } \left\{ \sum _{i=1}^{m}y_i\Big (b_i-\nu \Big (r_p^0\Big )_i\Big ): C-\sum _{i=1}^m y_iA_i - S = \nu R_d^0,\,S \succeq 0\right\} . \end{aligned}$$

Theorem 4.1

(Lemma 4.11 in [13]) The original problems (SDOP) and (SDOD) are feasible, iff for each $\nu$ satisfying $0 < \nu \le 1$, the perturbed problems (SDOP$_\nu$) and (SDOD$_\nu$) satisfy the IPC.

Let (SDOP) and (SDOD) be feasible and $0 < \nu \le 1$. Then, Theorem 4.1 implies that the central path of the perturbed problems exists. This means that the system

$$\begin{aligned} b_i-A_i\cdot X \!= \!\nu (r_p^0)_i,\,i=1,\ldots ,m, \, C-\sum _{i=1}^m y_i A_i -S =\nu R_d^0,\, XS=\mu E \end{aligned}$$

(18)

has a unique solution, for every $\mu >0$, denoted by $(X(\mu , \nu ), y(\mu , \nu ), S(\mu , \nu ))$, which are the $\mu$-centers of the perturbed problems (SDOP$_\nu$) and (SDOD$_\nu$). In the sequel, we will always have $\mu =v\zeta ^2$.

4.2 An Iteration of Infeasible IPM

As we established above, if $\nu = 1$ and $\mu = \mu ^0$, then $X = X^0$ is the $\mu$-center of the perturbed problem (SDOP$_1$) and $(y,S)=(y^0, S^0 )$ the $\mu ^0$-center of (SDOD$_1$). These are our initial iterates.

Suppose that, for some $\nu \in ]0, 1]$ we have $X$ and $(y,S)$ are feasible for the perturbed problems (SDOP$_\nu$) and (SDOD$_\nu$)., and such that $\mathbf {Tr}(XS)=n\mu$ and $\delta (X,S;\mu ) \le \tau$, where $\tau > 0$ is a small threshold parameter. Obviously, this condition is certainly satisfied at the start of the first iteration due to, the fact that $\mathbf {Tr}(X^0S^0)=n\mu$ and $\delta (X^0,S^0;\mu ^0) =0$.

Every (main) iteration consists of a feasibility step and a few centering steps. The feasibility step serves to get iterates $(X^f,y^f,S^f)$ that are strictly feasible for (SDOP$_{\nu ^+})$ and (SDOD$_{\nu ^+})$, and such that $\delta (X^f,S^f;\mu ^+)\le 1/\root 4 \of {2}$. In other words, $(X^f,y^f,S^f)$ belongs to the quadratic convergence neighborhood with respect to the $\mu ^+$-center of (SDOP$_{\nu ^+})$ and (SDOD$_{\nu ^+})$. Hence, because the full NT-step is quadratically convergent in that region, a few centering steps, starting from $(X^f,y^f,S^f)$ and targeting at the $\mu ^+$-center of (SDOP$_{\nu ^+})$ and (SDOD$_{\nu ^+})$ will generate the iterate $(X^+,y^+,S^+)$, that is feasible for (SDOP$_{\nu ^+})$ and (SDOD$_{\nu ^+})$ and satisfies $\mathbf {Tr}(X^+,S^+) = n\mu ^+$ with $\mu ^+=\nu ^+\zeta ^2$ and $\delta (X^+,S^+;\mu ^+) \le \tau$. This process is repeated until the duality gap and the norms of residual vectors are less than some prescribed accuracy parameter $\varepsilon$.

4.3 The Generic Full NT-step Infeasible IPM

The generic full NT-step infeasible IPM for SDO is presented in Fig.  2.

Fig. 2

Full NT-step infeasible IPM

4.4 Analysis of Full NT-step Infeasible IPM

In the feasibility step, we scale the search direction $(\Delta ^f X, \Delta ^f S)$, just as we did in the feasible case (9), by defining

$$\begin{aligned} D^f_X := \frac{1}{\sqrt{\mu }}D^{-1}\Delta ^f XD^{-1},\,\mathrm{and}~D^f_S :=\frac{1}{\sqrt{\mu }}D\Delta ^f SD. \end{aligned}$$

(19)

For finding iterates that are feasible for (SDOP$_\nu$) and (SDOD$_\nu$), we need displacements $(\Delta ^f X,\Delta ^f y,\Delta ^f S)$ such that

$$\begin{aligned} X^f:= X+\Delta ^f X,\,y^f:=y +\Delta ^f y,\,\mathrm{and}~S^f:= S+\Delta ^f S \end{aligned}$$

(20)

are feasible for (SDOP$_\nu$) and (SDOD$_\nu$). This hold only if the scale search directions $D^f_X$ and $\Delta ^f_y, D^f_S$ satisfy

$$\begin{aligned} \bar{A_i}\cdot D^fX&= \frac{1}{\sqrt{\mu }}\theta \nu \Big (r_b^0\Big )_i,\quad i=1,\ldots ,m,\nonumber \\ \sum _{i=1}^m \Delta ^fy_i \bar{A_i} +D^fS&= \frac{1}{\sqrt{\mu }}\theta \nu DR_d^0D,\\ D^f_X+D^f_S&= (1-\theta )V^{-1}-V. \nonumber \end{aligned}$$

(21)

We can easily verify that, after the feasibility step, the iterates $(X^f,y^f,S^f)$ satisfy the first two equations of the system (18), with $\nu$ replaced by $\nu ^+$. The hard part in the analysis will be to guarantee that $X^f,S^f\in \mathbf {S}^n_{++}$ and to guarantee that the new iterates satisfy $\delta (X^f,S^f;\mu ^+)\le \tau$.

It follows from (20) and (19) that

$$\begin{aligned} X^f=\sqrt{\mu }D\Big (V+D_X^f\Big )D,\,\mathrm{and}~S^f=\sqrt{\mu }D^{-1}\Big (V+D_S^f\Big )D^{-1}. \end{aligned}$$

As the discussion in the feasible IPM, we can conclude that

$$\begin{aligned} X^fS^f\sim \mu \Big ((1-\theta )E+D_{XS}^f+M^f\Big ), \end{aligned}$$

where

$$\begin{aligned} D_{XS}^f:=\frac{1}{2}\Big (D_X^fD_S^f+D_S^fD_X^f\Big ) \end{aligned}$$

and

$$\begin{aligned} M^f:= \frac{1}{2}\Big (D_X^fD_S^f-D_S^fD_X^f\Big )+\frac{1}{2}\Big (D_X^fV+VD_S^f-VD_X^f-D_S^fV\Big ) \end{aligned}$$

are symmetric and skew-symmetric, respectively.

The following lemma provides the sufficient condition of the strict feasibility of the new iterate $(X^f,y^f,S^f)$.

Lemma 4.1

(Corollary 5.5 in [13]) The iterates $\big (X^f,y^f,S^f\big )$ are strictly feasible if

$$\begin{aligned} \Big \Vert D_{XS}^f\Big \Vert _\infty < 1-\theta . \end{aligned}$$

Recall from the definition (13) that

$$\begin{aligned} \delta \Big (X^f,S^f;\mu ^+\Big ):=\delta \Big (V^f\Big ):=\frac{1}{2}\Big \Vert \Big (V^f\Big )^{-1}-V^f\Big \Vert , \end{aligned}$$

(22)

where

$$\begin{aligned} V^f:=\frac{1}{\sqrt{\mu }}D^{-1}X^fD^{-1}=\frac{1}{\sqrt{\mu }}DS^fD. \end{aligned}$$

Assuming $\big \Vert D_{XS}^f\big \Vert _\infty < 1-\theta$, which guarantees strict feasibility of the iterates $\big (X^f,y^f,S^f\big )$, we can derive an upper bound for $\delta \big (V^f\big )$ as follows (see Lemma 4.8 in [21]):

$$\begin{aligned} 4\delta \Big (V^f\Big )^2\le \frac{\Big \Vert \frac{D_{XS}^f}{1-\theta }\Big \Vert ^2}{1-\Big \Vert \frac{\lambda (D_{XS}^f)}{1-\theta }\Big \Vert _\infty }\le \frac{\frac{1}{4} \Big (\frac{\Vert D_{X}^f\Vert ^2+\Vert D_{S}^f\Vert ^2}{1-\theta }\Big )^2}{1-\frac{1}{2}\frac{\Vert D_{X}^f\Vert ^2+\Vert D_{S}^f\Vert ^2}{1-\theta }}. \end{aligned}$$

(23)

We want to choose $\theta$, $0 <\theta < 1$, as large as possible, and such that $(X^f,y^f,S^f)$ lies in the quadratic convergence neighborhood with respect to the $\mu ^+$-center of the perturbed problems, i.e., $\delta (V^f)\le 1/{\root 4 \of {2}}$. From (23), after some elementary calculations, we can conclude that this hold only if

$$\begin{aligned} \frac{\Vert D_X^f\Vert ^2+\Vert D_S^f\Vert ^2}{1-\theta }\le 2\sqrt{2}\Big (\sqrt{1+\sqrt{2}}-1\Big )\le 1.5664. \end{aligned}$$

(24)

Let $\mathcal {L}:=\{\xi \in \mathbf {S}^n: DA_iD\cdot \xi =0,\,i=1,\ldots ,m\}$ and $\mathcal {L}^\bot$ be the orthogonal complement of $\mathcal {L}$. The following lemma provides an upper bound for $\Vert D_X^f\Vert ^2+\Vert D_S^f\Vert ^2$.

Lemma 4.2

(Lemma 4.9 [21]) Let $Q$ be the (unique) matrix in the intersection of the affine spaces $D_X^f+\mathcal {L}$ and $D_S^f+\mathcal {L}^\bot$. Then

$$\begin{aligned} \big \Vert D_X^f\big \Vert ^2+\big \Vert D_S^f\big \Vert ^2\le \big \Vert Q\big \Vert ^2+\Big (\Vert Q\Vert +\sqrt{4(1-\theta )^2\delta ^2+n\theta ^2}\Big )^2. \end{aligned}$$

Combining the results of Lemmas 5.12–5.14 and 5.16 in [13] and Lemma II.60 in [11], we have the following lemma, which provides an upper bound for $\Vert Q\Vert$.

Lemma 4.3

Let $\rho (\delta )=\delta +\sqrt{1+\delta ^2}$. Then

$$\begin{aligned} \Vert Q\Vert \le n\theta \rho (\delta ) (1+\rho ^2(\delta )). \end{aligned}$$

At this stage we choose

$$\begin{aligned} \tau =1/16. \end{aligned}$$

(25)

Since $\delta \le \tau =1/16$ and $\rho (\delta )$ is monotonically increasing in $\delta$, we have, by Lemma 4.3,

$$\begin{aligned} \Vert Q\Vert \le n\theta \rho (\delta ) (1+\rho ^2(\delta ))\le n\theta \rho (1/16)(1+\rho ^2(1/16))\le 2.2706 n\theta . \end{aligned}$$

(26)

It follows from Lemma 4.2 that

$$\begin{aligned} \big \Vert D_X^f\big \Vert ^2+\big \Vert D_S^f\big \Vert ^2\le (2.2706 n\theta )^2+\Big (2.2706 n\theta +\sqrt{4(1-\theta )^2\delta ^2+n\theta ^2}\Big )^2. \end{aligned}$$

(27)

We have proved that $\delta \big (V^f\big )\le 1/{\root 4 \of {2}}$ certainly holds if the inequality (24) is satisfied. Then by (27), inequality (24) holds if

$$\begin{aligned} (2.2706 n\theta )^2+\Big (2.2706 n\theta +\sqrt{4(1-\theta )^2\delta ^2+n\theta ^2}\Big )^2\le 1.5664(1-\theta ). \end{aligned}$$

(28)

One may easily verify that, if

$$\begin{aligned} \theta =1/(4n), \end{aligned}$$

(29)

then the above inequality (28) is satisfied.

By Corollary 3.1, the required number of centering steps can easily be obtained. Indeed, assuming $\delta =\delta (X^f, S^f;\mu ^+)\le 1/\root 4 \of {2}$, after $k$ centering steps we will have iterates $(X^+, y^+, S^+)$, that are still strictly feasible for $(SDOP_{\nu ^+})$ and $(SDOD_{\nu ^+})$ and that satisfy

$$\begin{aligned} \delta (X^+, S^+; \mu ^+)\le \big (1/{\root 4 \of {2}}\big )^{2^k}\le \tau . \end{aligned}$$

From this, we can easily verify that $\delta (X^+, S^+; \mu ^+)\le \tau$ with $\tau =1/16$ holds after at most

$$\begin{aligned} 2+\lceil \log _2(\log _2 (1/{\tau }))\rceil =2+\lceil \log _2(\log _2 16)\rceil =4 \end{aligned}$$

centering steps; then suffice to get iterate $(X^+,y^+,S^+)$ that satisfies $\delta (X^+,S^+;\mu ^+) \le \tau$ again. So, each main iteration consists of at most five the so-called inner iterations. In each main iteration, both the duality gap and the norms of the residual vectors are reduced by the factor $(1-\theta )$. Hence, using $\mathbf {Tr}(X^0S^0) = n\zeta ^2$, the total number of main iterations is bounded above by

$$\begin{aligned} \frac{1}{\theta }\log {\frac{\mathrm{max}\{n\zeta ^2, \Vert r^0_p\Vert , \Vert R^0_d\Vert \}}{\varepsilon }}. \end{aligned}$$

It follows from (29) and the fact that at most five inner iterations per main iteration are needed. The main result of this paper is stated in the following theorem.

Theorem 4.2

Let (SDOP) and (SDOD) have an optimal solution $(X^*,y^*,S^*)$ such that $\mathbf {Tr}(X^*S^*) = 0$ and $X^*+S^*\preceq \zeta E$ for some $\zeta >0$. The algorithm in Fig. 2 requires at most

$$\begin{aligned} 20n\log {\frac{\mathrm{max}\{n\zeta ^2, \Vert r^0_p\Vert , \Vert R^0_d\Vert \}}{\varepsilon }} \end{aligned}$$

inner iterations to generate an $\varepsilon$-solution of (SDOP) and (SDOD).

Remark 4.1

During the course of the algorithm, if at some main iteration, the proximity measure $\delta$ after the feasibility step exceeds $1/\root 4 \of {2}$, then it tells us that the above assumption does not hold. It may happen that the value of $\zeta$ has been chosen too small. In this case, one might run the algorithm once more with a larger value of $\zeta$. If this does not help, then eventually one should realize that (SDOP) and/or (SDOD) do not have optimal solutions at all, or they have optimal solutions with positive duality gap.

5 Conclusions

In this paper, we established a sharper quadratic convergence result for full NT-step feasible IPM for SDO, which leads to a slightly wider neighborhood for the iterates in the feasible algorithm and for the feasibility steps in the infeasible algorithm. This result enables us to propose an improved complexity analysis of full NT-step feasible and infeasible IPMs for SDO.

The paper generalizes results obtained in two papers, [17] where Gu et al. consider full Newton-step infeasible IPMs for LO, which is a generalization of full Newton-step feasible IPM for LO by Roos et al. in [11], and [13] where Mansouri et al. consider the same type of IPMs for SDO. It turns out that the iterations bounds are the same as for the LO cases [11, 17]. Although expected, these results were not obvious and, at certain steps of the analysis, they were not trivial and/or straightforward generalization of the LO case. In order to overcome the difficulty some new results had to be used including Lemmas 2.5 and 2.7. Nevertheless, both versions of the full NT step IPMs are derived the currently best known iteration bounds.

Future research could be done on the generalization of infeasible IPM for SO [18, 24]. Another topic for further research is the use of adaptive steps, as described in [11]. This will not improve the theoretical complexity, but it will enhance significantly the practical performance of the algorithm.