A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function

Abstract

As indicated in the recent studies about primal-dual interior-point methods (IPMs) based on kernel functions, a kernel function not only serves to determine the search direction and measure the distance of the current iteration point to the $\mu$-center, but also affects the iteration complexity and the practical computational efficiency of the algorithm. In this paper, we propose a new IPM for semidefinite optimization (SDO) based on a parameterized kernel function which is a generalization of the one presented by Bai et al. (Optim Methods Softw 17(6):985–1008, 2002). By using the good properties of the parameterized kernel function, we deduce that the iteration bound for large-update method is $O(\sqrt{n}\log {n}\log {\frac{n}{\epsilon }})$ for $q=O(n)$, which is the best known complexity results for such methods. In our knowledge, this result is the first instance of primal-dual interior point method for SDO which involving the kernel function. Some numerical results have been provided.

1 Introduction

Semidefinite optimization problems (SDO) are convex optimization problems over the intersection of an affine set and the cone of positive semidefinite matrices. It is not only widely used in the field of mathematical programming, but also widely used in other fields, such as control theory, combinatorial optimization, statistics, etc. Interested reader can refer to Wolkowicz et al. (2000), Alizadeh (1991), Boyd et al. (1994) for more concrete description. The first paper dealing with SDO problems dates back to the early 1960s. However, SDO was out of interest for a long time afterwards, because of lacking of powerful and effective algorithm to solve. The situation changed dramatically around the beginning of the 1990s when it became clear that the algorithm for linear optimization (LO) can often be extended to the more general SDO case.

Since the groundbreaking paper of Karmarkar (1984), some scholars are committed to the study of IPMs and numerous results have been proposed (see Roos et al. 1997; Wright 1997; Ye 1997). IPMs have led to increasing interest both in the theoretical research and application of SDO. As far as we know, Nesterov and Nemirovskii first extended IPMs from LO to SDO, at least in a theoretical sense (Nesterov and Nemirovskii 1994). Subsequently, many IPMs designed for LO have been successfully extended to SDO. Among the different variants of IPMs, it is generally agreed that the most efficient methods are the so-called primal-dual IPMs from a computational point of view (Andersen et al. 1996).

Most of IPMs for LO are based on the logarithmic barrier function. Recently, there is an active research on the primal-dual IPMs proposed by Peng et al. (2001a) based on the a new nonlogarithmic kernel function for LO and SDO, which called self-regular kernel function, the prototype of the self-regular kernel function is given by

$$\begin{aligned} \Upsilon _{p,q}(t)=\frac{t^{p+1}-1}{p(p+1)}+\frac{t^{1-q}-1}{q(q-1)}+\frac{p-q}{pq}(t-1),\quad t>0,\quad p\ge 1,\quad q>1. \end{aligned}$$

Such a function is strongly convex and smooth coercive on its domain: the positive real axis. The self-regular kernel function is used to determine the search direction and measure the distance of the current iteration point to the $\mu$-center of the algorithm. Based on the self-regular kernel function, the complexity bound of the large-update primal-dual IPM for LO has been significantly improved from $O(n\log {\frac{n}{\epsilon }})$ to $O(\sqrt{n}\log {n}\log {\frac{n}{\epsilon }})$ (Peng et al. 2001b). Furthermore, Bai et al. introduced a class of eligible kernel functions, and gave a scheme to analyze the primal-dual IPMs for LO that the iteration bounds for both large-update and small-update methods can be obtained based on the eligible kernel functions (Bai et al. 2004). El Ghami et al. (2012) first introduced a trigonometric kernel function and derived the worst case complexity bound for large-update IPMs is $O(n^{\frac{3}{4}}\log {\frac{n}{\epsilon }})$. Recently, a lot of (trigonometric) kernel functions have been proposed. For example, Bouafia et al. (2016b) proposed a new trigonometric kernel function, with the various values of its parameter, generalizes the complexity algorithm found by various researchers (to see Bai et al. 2002a, 2004; El Ghami et al. 2012; Peyghami et al. 2014; Peyghami and Hafshejani 2014; Cai et al. 2014; Kheirfam and Moslem 2015). They also proposed a new kernel function with logarithmic barrier term which is the first function of this type giving the best complexity algorithmics (Bouafia et al. 2018). For more studies with primal-dual IPMs based on a kernel function, we refer to Li and Zhang (2015), Bouafia et al. (2016a).

Moreover, the methods of solving LO based on a kernel function were extended to SDO. For example, Lee et al. (2013) proposed a primal-dual interior-point algorithm for SDO based on a class of kernel functions which are both eligible and self-regular, and obtained the best known complexity results for both small- and large-update methods. Wang et al. (2015) presented a class of large- and small-update primal-dual interior-point methods for SDO based on a parameterized kernel function with a trigonometric barrier term, and derived the worst case iteration bounds, namely, $O(n^{\frac{2}{3}}\log {\frac{n}{\epsilon }})$ and $O(\sqrt{n}\log {\frac{n}{\epsilon }})$, respectively. Recently, Fathi-Hafshejani et al. (2018) presented a new generic trigonometric kernel function, which is constructed by introducing some new conditions on the kernel function. They proved that the large-update primal-dual interior-point method for solving SDO problems with this new kernel function enjoys as worst case iteration complexity bound which matches the currently best known complexity bound for large-update methods. For more studies with primal-dual IPMs based on a kernel function please refer to El Ghami et al. (2009, 2010), Choi and Lee (2009), Qian et al. (2008), Peyghami et al. (2016), Kheirfam (2012). It is worth noting that although most IPMs for SDO can be viewed as natural extensions of IPMs for LO and have similar polynomial complexity results, in fact, obtaining a valid search direction in SDO case is much more difficult than in the LO case.

Motivated by the previous research, very recently, Li et al. (2019) introduced a parameterized version of a kernel function that was previously presented by Bai et al. (2002b). Although almost all the early proposed kernel functions have been parameterized, as we can see, no one has put forward its parameterized version so far. The new parameterized kernel function is not self-regular, but it is eligible. They gave the iteration bound and numerical results of the primal-dual IPMs based on the kernel function for LO. In this paper we present a new primal-dual interior-point algorithm for SDO based on this kernel function. We adopt the basic analysis used in Li et al. (2019) and revise them to be suited for the SDO case. we also develop some new analytic tools that are used in the complexity analysis of the algorithm. Finally. we derive the currently best known iteration bounds for the algorithm with large-update methods. The iteration bounds are as good as the bounds for the LO case. To our knowledge, this is the first primal-dual interior-point algorithm for SDO based on the kernel function. We also give some numerical results.

The paper is organized as follows. In Sect. 2, we recall the notions of the central path and search direction, which are the basic concepts of the primal-dual IPMs for SDO. We also give a generic primal-dual IPM for SDO in Fig. 1. The kernel function and its properties are recalled in Sect. 3. Section 4 is devoted to analyzing the convergence of the algorithm and deriving the iteration bound for large-update method. Moveover, we give few numerical results in Sect. 5. Finally, concluding remarks are given in Sect. 6.

Some notations used throughout the paper are as follows: The $R^{n}$ denotes the set of n-dimensional vectors, the set of n-dimensional nonnegative vectors and positive vectors are denoted as $R^{n}_{+}$ and $R^{n}_{++}$, respectively. $S^{n}$, $S^{n}_{+}$ and $S^{n}_{++}$ denote the cone of symmetric, symmetric positive semidefinite and symmetric positive definite $n\times n$ matrices, respectively. Furthermore, $\parallel \cdot \parallel$ denotes the Frobenius norm for matrices, and the 2-norm of a vector. Given A and B in $S^{n}_{++}$, the Löwner partial order “$\succeq$” (or “$\succ$”) on positive semidefinite (or positive) matrices means $A\succeq B$ (or $A\succ B$) if $A-B$ is positive semidefinite (or positive). The matrix inner product is defined as $A\cdot B=tr(A^{T}B)$. For any $Q, V\in S^{n}_{++}$, $Q^{\frac{1}{2}}$ denotes its symmetric square root. We assume that the eigenvalues of V are arranged in non-increasing order, that is, $\lambda _{1}(V)\ge \lambda _{2}(V)\ge \cdots \lambda _{n}(V)$.

2 Preliminaries

2.1 Kernel function and its barrier function

It is well known that the barrier function $\Psi (\upsilon )$ is determined by the univariate kernel function $\psi (t)$. A twice differentiable function $\psi (t):R_{++}\rightarrow R_+$ is called a kernel function if $\psi (t)$ satisfies the following conditions:

$$\begin{aligned} \psi (1)=\psi ^{\prime }(1)=0;\quad \psi ^{\prime \prime }(t)>0,\quad \forall t>0; \quad \lim _{t\downarrow 0}\psi (t)=\lim _{t\rightarrow \infty }\psi (t)=\infty . \end{aligned}$$

Obviously, the kernel function $\psi (t)$ attains its minimal value at $t=1$ and goes to infinity if either $t\downarrow 0$ or $t\rightarrow \infty$, hence $\psi (t)$ can be completely determined by its second derivative as follows:

$$\begin{aligned} \begin{array}{ll} \psi (t)= \int ^{t}_{1}\int ^{\xi }_{1}\psi ^{\prime \prime }(\zeta ) d\zeta d\xi . \end{array} \end{aligned}$$

(2.1)

The barrier function $\Psi (\upsilon )$ determined by its kernel function $\psi (t)$ is

$$\begin{aligned} \Psi (\upsilon ):=\sum _{i=1}^n\psi (\upsilon _i). \end{aligned}$$

(2.2)

Using the concept of a matrix function (Horn and Johnson 1985), we are ready to show how a matrix function can be obtained from a kernel function $\psi (t)$.

Definition 2.1

Suppose the matrix V is a diagonalizable with eigen-decomposition

$$\begin{aligned} V=Q_{V}^{-1}diag(\lambda_{1}(V),\lambda_{2}(V), \ldots ,\lambda_{n}(V))Q_{V}, \end{aligned}$$

(2.3)

where $Q_{V}$ is nonsingular. The matrix function $\psi (V)$ is defined by

$$\begin{aligned} \psi (V)=Q_{V}^{-1}diag(\psi (\lambda_{1}(V)), \psi (\lambda_{2}(V)),\ldots ,\psi (\lambda_{n}(V)))Q_{V}. \end{aligned}$$

(2.4)

In particular, if V is symmetric then $Q_{V}$ can be chosen to be orthogonal, i.e., $Q_{V}^{-1}=Q_{V}^{T}$.

Since $\psi (t)$ is a twice differentiable function, the derivatives $\psi ^{\prime }(t)$ and $\psi ^{\prime \prime }(t)$ are well-defined for $t>0$. Replacing $\psi (\lambda _{i}(V))$ in (2.4) by $\psi ^{\prime }(\lambda _{i}(V))$ and $\psi ^{\prime \prime }(\lambda _{i}(V))$, respectively. Then for each i, the matrix functions $\psi ^{\prime }(V)$ and $\psi ^{\prime \prime }(V)$ are defined. Similarly to the case LO, we denote by $\Psi (V)$ the trace of the matrix function $\psi (V)$, i.e.,

$$\begin{aligned} \Psi (V)=tr(\Psi (V))=\sum ^{n}_{i=1}\psi (\lambda_{i}(V)). \end{aligned}$$

(2.5)

The usual concepts of differentiability can be naturally extended to matrices of functions, by interpreting them entry-wise. Let M(t) and N(t) be two matrices of functions, then we have

$$\begin{aligned}&\frac{d}{dt}M(t)=M^{\prime }(t); \end{aligned}$$

(2.6a)

$$\begin{aligned}&\frac{d}{dt}tr(M(t))=tr(M^{\prime }(t)); \end{aligned}$$

(2.6b)

$$\begin{aligned}&\frac{d}{dt}tr(\psi (M(t)))=tr(\psi (M^{\prime }(t))M^{\prime }(t)); \end{aligned}$$

(2.6c)

$$\begin{aligned}&\frac{d}{dt}(M(t)N(t))=M^{\prime }(t)N(t)+M(t)N^{\prime }(t). \end{aligned}$$

(2.6d)

Remark 2.1

In the rest of this paper, when we use the function $\psi (\cdot )$ and its derivatives $\psi ^{\prime }(\cdot )$ and $\psi ^{\prime \prime }(\cdot )$, it always denotes a matrix function if the argument is a matrix and it means a general function from R to R if the argument is also in R.

2.2 The central path

Consider the standard form of SDO

$$\begin{aligned} (P)\quad min\{C\cdot X: A_{i}\cdot X=b_{i},\ i=1,2,\ldots ,m,\ X\succeq 0\} \end{aligned}$$

and its dual problem

$$\begin{aligned} (D)\quad max\left\{ b^{T}y: \sum ^{m}_{i=1}y_{i}A_{i}+S=C,\ S\succeq 0\right\} , \end{aligned}$$

where each $A_{i}\in S^{n}$, $b,y\in R^{m}$ and $C \in S^{n}$. The matrices $A_{i}$ are linearly independent.

It is well known that solving an optimal solution of (P) and (D) is equivalent to solving the following system:

$$\begin{aligned} \left\{ \begin{array}{ll} A_{i}\cdot X=b_{i},\quad i=1,2,\ldots ,m,&{}\quad X\succeq 0,\\ \sum ^{m}_{i=1}y_{i}A_{i}+S=C, &{}\quad S\succeq 0,\\ XS=0. \end{array} \right. \end{aligned}$$

(2.7)

The third equation in (2.7) is so-called complementarity condition for (P) and (D), and the basic idea of primal-dual IPMs is to replace the complementarity condition in (2.7) by the parameterized equation $XS=\mu E(u>0)$. Therefore, we consider the system as below:

$$\begin{aligned} \left\{ \begin{array}{ll} A_{i}\cdot X=b_{i},\quad i=1,2,\ldots ,m,&{}\quad X\succeq 0,\\ \sum ^{m}_{i=1}y_{i}A_{i}+S=C, &{}\quad S\succeq 0,\\ XS=\mu E. \end{array} \right. \end{aligned}$$

(2.8)

A solution exists in (2.8) if and only if (P) and (D) satisfy the interior-point condition (IPC) from Roos et al. (1997), i.e., there exists $(X^0,y^0,S^0)$ such that

$$\begin{aligned} A_{i}\cdot X^{0}=b_{i},\quad i=1,2,\ldots ,m,\ \quad \sum ^{m}_{i=1}y_{i}^{0}A_{i}+S^{0}=C, \quad X^{0}\succeq 0,\quad S^{0}>0. \end{aligned}$$

Without loss of generality, we can assume that the IPC is satisfied. In fact we may, and will, even assume that $X^0=S^0=E,\ \mu =1$. Then for each $\mu >0$, a unique solution of (P) and (D) exists. The solution of (2.8) is denoted as $(X(\mu ),y(\mu ),S(\mu ))$, where $X(\mu )$ is called the $\mu$-center of (P) and $(y(\mu ),S(\mu ))$ is called the $\mu$-center of (D). The set of $\mu$-center gives a homotopy path, which is called the central path of (P) and (D). If $\mu \rightarrow 0$, then the limit of the central path yields optimal solutions for (P) and (D) (Wolkowicz et al. 2000; Nesterov and Nemirovskii 1994).

2.3 The search direction

The search direction of the primal-dual IPMs is determined by Newton’s method, and this yields the following equations:

$$\begin{aligned} \left\{ \begin{array}{ll} A_{i}\cdot \Delta X=0, \quad i=1,2,\ldots ,m,\\ \sum ^{m}_{i=1}\Delta y_{i}A_{i}+\Delta S=0,\\ X\Delta S+\Delta X S=\mu E-XS. \end{array} \right. \end{aligned}$$

(2.9)

A crucial observation for SDO is that the $\Delta X$ in the above system is not necessarily symmetric. Several ways have been proposed for symmetrizing the third equation in the Newton system such that the resulting new system has a unique symmetric solution. In this paper, we consider the symmetrization scheme from which the NT direction (Nesterov and Nemirovskii 1994; Nesterov and Todd 1998) is derived.

Define

$$\begin{aligned} P:=X^{\frac{1}{2}}(X^{\frac{1}{2}}SX^{\frac{1}{2}}) ^{-\frac{1}{2}}X^{\frac{1}{2}}= S^{-\frac{1}{2}}(S^{\frac{1}{2}} XS^{\frac{1}{2}})^{\frac{1}{2}}S^{-\frac{1}{2}}\quad and\quad D:=P^{\frac{1}{2}}. \end{aligned}$$

(2.10)

The matrix D can be used to scale X and S to the same matrix V defined by Peng et al. (2002) as below:

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

(2.11)

Note that the matrices D and V are symmetric and positive definite. Let us further define

$$\begin{aligned} \begin{aligned}&\overline{A}_{i}=\frac{1}{\sqrt{\mu }}DA_{i}D,\quad i=1,2,\ldots ,m;\\&D_{X}:=\frac{1}{\sqrt{\mu }}D^{-1}\Delta X D^{-1};\\&D_{S}:=\frac{1}{\sqrt{\mu }}D\Delta S D. \end{aligned} \end{aligned}$$

(2.12)

After some elementary reductions, then (2.9) is equivalent to the following system:

$$\begin{aligned} \left\{ \begin{array}{ll} \overline{A}_{i} D_{X}=0,\quad i=1,2,\ldots ,m,\\ \sum ^{m}_{i=1}\Delta y_{i}\overline{A}_{i}+D_{S}=0,\\ D_{X}+D_{S}=V^{-1}-V. \end{array} \right. \end{aligned}$$

(2.13)

The third equation in (2.13) is called the scaled centering equation. Define the so-called classical logarithmic barrier function and its kernel function as follows:

$$\begin{aligned} \Psi _c(\upsilon ):=\sum _{i=1}^n\Bigg ({\frac{\upsilon _i^2-1}{2} -log~\upsilon _i}\Bigg ),\quad \psi _c(t)=\frac{t^{2}-1}{2}-\log t. \end{aligned}$$

(2.14)

Then the right-hand of the third equation in (2.13) is exactly equal to $\psi _{c}(V)$. In this paper, we use a new kernel function $\psi (t)$ instead of the classical logarithmic kernel function $\psi _c(t)$ (Peng et al. 2002). Thus $V^{-1}-V$ in (2.13) is replaced by $-\psi ^{\prime }(V)$, the system (2.13) can be rewritten as

$$\begin{aligned} \left\{ \begin{array}{ll} \overline{A}_{i} D_{X}=0,\quad i=1,2,\ldots ,m,\\ \sum ^{m}_{i=1}\Delta y_{i}\overline{A}_{i}+D_{S}=0,\\ D_{X}+D_{S}=-\psi ^{\prime }(V). \end{array} \right. \end{aligned}$$

(2.15)

Now one easily obtains the scale search direction $D_{X}$ and $D_{S}$ by solving (2.15), and after some elementary reductions by (2.12), we can derive the centering search direction $(\Delta X, \Delta y, \Delta S)$. From the orthogonality of $\Delta X$ and $\Delta S$, it is trivial to see that

$$\begin{aligned} tr(D_{X}D_{S})=tr(D_{S}D_{X})=0. \end{aligned}$$

Thus we have

$$\begin{aligned} D_{X}=D_{S}=0_{n\times n}\Leftrightarrow \psi ^{\prime }(V)=0_{n\times n}\Leftrightarrow V=E \Leftrightarrow \Psi (V)=0. \end{aligned}$$

From what has been discussed above, we may safely draw a conclusion that if $(X,y,S)\ne (X(\mu ),y(\mu ),S(\mu ))$, then $(\Delta X, \Delta y, \Delta S)$ is nonzero. By taking a step along the search direction, with the step size $\alpha$ defined by some line search rules. The new point is then computed by

$$\begin{aligned} X_+=X+\alpha \Delta X;\quad y_+=y+\alpha \Delta y; \quad S_+=S+\alpha \Delta S. \end{aligned}$$

(2.16)

A generic primal-dual algorithm for SDO is given in Fig. 1 as follows:

Fig. 1

Algorithm 1

The parameters $\theta ,\tau$ and the step-size $\alpha$ described in the algorithm are chosen to ensure that the number of iterations is as small as possible. Moreover, if the parameter $\theta$ which we choose is a constant independent of the dimension n of the problem, such as $\theta =\frac{1}{2}$, then the algorithm is called a large-update method. If the parameter $\theta$ which we choose depends on the dimension n of the problem, for instance $\theta =\frac{1}{\sqrt{n}}$, then we call the algorithm a small-update method.

In the theoretical analysis, small-update methods are much more efficient than large-update methods, however, in practice, large-update methods perform better (Roos et al. 1997; Wright 1997; Ye 1997). This implies that there is a gap between the theoretical behavior and practical computational efficiency of the algorithm (Renegar 2001). In this paper, we mainly analyze large-update methods.

3 The kernel function and its properties

Bai et al. introduced the following kernel function in Bai et al. (2002b):

$$\begin{aligned} \psi _A(t)=\frac{t^2-1}{2}+\frac{(e-1)^2}{e(e^t-1)}-\frac{e-1}{e},\quad t>0. \end{aligned}$$

(3.1)

Li et al parameterized it and obtained a new kernel functions as follows (Li et al. 2019):

$$\begin{aligned} \psi (t)=\frac{t^2-1}{2}+\frac{(e-1)^{q+1}}{qe(e^t-1)^q}-\frac{e-1}{qe},\quad t>0,\quad q\ge 1. \end{aligned}$$

(3.2)

In the following convergence analysis of the method we also use the norm-based proximity measure $\delta (V)$ defined by

$$\begin{aligned} \begin{aligned} \delta (V):&=\frac{1}{2}\Vert \psi ^{\prime }(V)\Vert =\frac{1}{2}\sqrt{\sum ^{n}_{i=1}\psi ^{\prime }(\lambda _{i}(V))^{2}} =\frac{1}{2}\Vert D_{x}+D_{s}\Vert . \end{aligned} \end{aligned}$$

(3.3)

Bai et al. gave five more conditions on the kernel function in the literature (Bai et al. 2004), namely,

$$\begin{aligned}&t\psi ^{\prime \prime }(t)+\psi ^{\prime }(t)>0,\quad t<1; \end{aligned}$$

(3.4a)

$$\begin{aligned}&t\psi ^{\prime \prime }(t)-\psi ^{\prime }(t)>0,\quad t>1; \end{aligned}$$

(3.4b)

$$\begin{aligned}&\psi ^{\prime \prime \prime }(t)<0,\quad t>0; \end{aligned}$$

(3.4c)

$$\begin{aligned}&2\psi ^{\prime \prime }(t)^{2}-\psi ^{\prime }(t)\psi ^{\prime \prime \prime }(t)>0,\quad t<1; \end{aligned}$$

(3.4d)

$$\begin{aligned}&\psi ^{\prime \prime }(t) \psi ^{\prime }(\beta t)-\beta \psi ^{\prime }(t) \psi ^{\prime \prime }(\beta t)>0,\quad t>1,\quad \beta >1. \end{aligned}$$

(3.4e)

For simplicity of presentation, let $M=\frac{(e-1)^{q+1}}{e}$. Some straightforward computations yield the first three derivatives of the kernel function $\psi (t)$ as follows:

$$\begin{aligned}&\psi ^{\prime }(t)=t-\frac{Me^{t}}{(e^{t}-1)^{q+1}}, \end{aligned}$$

(3.5a)

$$\begin{aligned}&\psi ^{\prime \prime }(t)=1+\frac{M(qe^{2t}+e^{t})}{(e^{t}-1)^{q+2}}, \end{aligned}$$

(3.5b)

$$\begin{aligned}&\psi ^{\prime \prime \prime }(t)=-\frac{M[q^{2}e^{3t}+(3q+1)e^{2t}+e^{t}]}{(e^{t}-1)^{q+3}}. \end{aligned}$$

(3.5c)

Following (Bai et al. 2004), a kernel function $\psi (t)$ is called an eligible kernel function if $\psi (t)$ satisfies conditions (3.4a), (3.4c), (3.4d) and (3.4e). Moreover, If $\psi (t)$ satisfies (3.4b) and (3.4c), then $\psi (t)$ satisfies (3.4e). Now one easily checks that $\psi (t)$ is eligible.

Theorem 3.1

(Li et al. 2019, Theorem 4.1) $\psi (t)$ is an eligible kernel function.

In the following lemma we list some formulas that are equivalent to (3.4a).

Lemma 3.1

(Peng et al. 2001a, Lemma 2.1.2) The following three formulas are equivalent if $\psi (t)$ is a twice differentiable function for $t>0$:

• (1) $\psi (\sqrt{t_{1}t_{2}}) \le \frac{1}{2}(\psi (t_{1}) +\psi (t_{2}))$, $\ t_{1}, \ t_{2}>0;$

• (2) $\psi ^{\prime }(t)+t\psi ^{\prime \prime }(t) \ge 0,\ t>0;$

• (3) $\psi (e^{\xi })$ is convex.

In fact, a twice differentiable function is called exponential convex or e-convex if it satisfies the property described in Lemma 3.1, and this property has been proved to be essential in analyzing the convergence of the primal-dual IPMs based on kernel functions. It is clear that that our kernel function $\psi (t)$ is e-convex by Lemma 3.1.

Define $\psi _{b}(t):=\frac{(e-1)^{q+1}}{qe(e^{t}-1)^{q}}-\frac{e-1}{qe},\ t>0,\ q \ge 1$. One may easily verify that $\psi _{b}(t)$ is monotonically decreasing and $\psi ^{\prime }_{b}(t)$ is monotonically increasing for $t\in (0,\infty )$. We also have $\psi _{b}(1)=0$ and $\psi _{b}^{\prime }(1)=1$.

The following lemmas give several crucial properties which are important in the analysis of the algorithm.

Lemma 3.2

(Li et al. 2019, Lemma 4.3) $\frac{1}{2}(t-1)^2 \le \psi (t) \le \frac{1}{2} \psi ^{\prime }(t)^{2}$, if $t>0,\ q\ge 1$.

Lemma 3.3

(Li et al. 2019, Lemma 4.4) Let $\rho :[0,\infty ) \rightarrow (0,1]$ denote the inverse function of the restriction of $-\frac{1}{2}\psi ^{\prime }(t)$ to the interval (0, 1]. Then

$$\begin{aligned} \frac{1}{e^{\rho (s)}-1} \le \bigg (\frac{2s+1}{M}\bigg )^{\frac{1}{q+1}},\ q \ge 1. \end{aligned}$$

Lemma 3.4

(Li et al. 2019, Lemma 4.5) Let $\varrho :[0,\infty ) \rightarrow [1,\infty )$ be the inverse function of $\psi (t)$ for $t\in [1,\infty )$. Then

$$\begin{aligned} \sqrt{1+2s}\le \varrho \le 1+\sqrt{2s}. \end{aligned}$$

Lemma 3.5

$\delta (V)\ge \sqrt{\frac{\Psi }{2}}$.

Proof

By using Lemma 3.2, we obtain

$$\begin{aligned} \psi (t)\le \frac{1}{2}\psi ^{\prime }(t)^2, \end{aligned}$$

which means

$$\begin{aligned} \Psi (V)=\sum _{i=1}^n\psi (\lambda _i(V)) \le \frac{1}{2}\sum _{i=1}^n\psi ^{\prime }(\lambda _i(V))^2 =\frac{1}{2} \Vert \Psi ^{\prime }(\lambda _i(V)) \Vert ^2=2\delta (V)^2. \end{aligned}$$

Thus we have

$$\begin{aligned} \delta (V) \ge \sqrt{\frac{\Psi }{2}}. \end{aligned}$$

It completes the proof. $\square$

The following Theorem 3.2 gives the influence of the parameter q on the kernel function.

Theorem 3.2

(Li et al. 2019, Theorem 4.2) $\psi (t,q)$ decreases as parameter q increases for $t\in (0,1)$, and increases as parameter q increases for $t\in [1,\infty )$.

The effects of different values of the parameter q on $\psi (t)$ are illustrated in Fig. 2.

Fig. 2

Comparisons of the effects with different q on the kernel function

4 Complexity analysis of the algorithm

Note that our algorithm consists of two parts: inner iteration and outer iteration. Every time before the outer iteration of the algorithm begins, just before the $\mu -$update with the factor $1-\theta$, $0<\theta <1$, we have $\Psi (V)\le \tau$. The vector V is divided by the factor $\sqrt{1-\theta }$ in the outer iteration, which in general leads to an increase in the value of $\Psi (V)$. Then the algorithm starts executing the inner iterations if $\Psi (V)>\tau$, and the inner iterations will decrease the value of $\Psi (V)$. The algorithm returns to the outer iteration again when $\Psi (V)\le \tau$. Repeat the above iteration process until $\mu$ is small enough, say, until $n\mu \le \epsilon$, at this stage we have found an $\epsilon -$solution of (P) and (D).

In order to investigate the convergence of the algorithm, we first briefly analyze the growth behavior of the barrier function in the outer iteration, then discuss the decrease behavior of the barrier function and the choice of step size $\alpha$ in the inner iteration. Finally, we deduce the iteration bound of the algorithm.

4.1 Growth behavior

From the above analysis we conclude that the largest value of $\Psi (V)$ occur after the $\mu$-update, just before the inner iteration begins. What we want is to find an upper bound of $\Psi (V)$ to research the amount of decrease of the barrier function during an inner iteration. Due to the fact that $\psi (t)$ is eligible, and also El Ghami et al. (2009), we have the following lemma.

Lemma 4.1

Let $\varrho$ be as defined in Lemma 3.4, and $\upsilon \succ 0,\ \beta \ge 1$, then

$$\begin{aligned} \Psi (\beta V) \le n\psi \Bigg (\beta \varrho \bigg (\frac{\Psi (V)}{n}\bigg )\Bigg ). \end{aligned}$$

Defining

$$\begin{aligned} L_{\psi }(n,\theta ,\tau ):=n\psi \Bigg (\frac{1}{\sqrt{1-\theta }} \varrho \bigg (\frac{\tau }{n}\bigg )\Bigg ). \end{aligned}$$

(4.1)

Obviously, if $\Psi (V)\le \tau$ and $\beta =\frac{1}{\sqrt{1-\theta }}$, then $L_{\psi }(n,\theta ,\tau )$ is an upper bound for $\Psi \Big (\frac{V}{\sqrt{1-\theta }}\Big )$ by using Lemma 4.1.

Lemma 4.2

Using the notations of (4.1), we have

$$\begin{aligned} L_{\psi }(n,\theta ,\tau )\le \frac{n\theta +2\sqrt{2n\tau }+2\tau }{2(1-\theta )}. \end{aligned}$$

Proof

Since $\psi _{b}(t)$ is monotonically decreasing for $t\ge 1$, and $\psi _{b}(1)=0$, we get

$$\begin{aligned} \psi (t)=\frac{t^{2}-1}{2}+\psi _{b}(t) \le \frac{t^{2}-1}{2},\quad t\ge 1,\quad q\ge 1. \end{aligned}$$

Using above results, Lemma 3.4 and $\psi (t)$ is monotonically increasing for $t \in [1,\infty )$, we have

$$\begin{aligned} \begin{aligned} L_{\psi }(n,\theta ,\tau )&=n\psi \Bigg (\frac{\varrho (\frac{\tau }{n})}{\sqrt{1-\theta }}\Bigg ) \le n\psi \Bigg (\frac{1+\sqrt{\frac{2\tau }{n}}}{\sqrt{1-\theta }}\Bigg )\\&\le n\frac{\Big (\frac{1+\sqrt{\frac{2\tau }{n}}}{\sqrt{1-\theta }}\Big )^{2}-1}{2}= \frac{n\theta +2\sqrt{2n\tau }+2\tau }{2(1-\theta )}. \end{aligned} \end{aligned}$$

Hence the lemma is proved. $\square$

4.2 Decrease behavior and the choice of step size

This section serves to analyze the decrease behavior of the barrier function and the choice of step size during an inner iteration. After a damped step we have

$$\begin{aligned} X_{+}=X+\alpha \Delta X=X+\alpha \sqrt{\mu } DD_{X}D=\sqrt{\mu } D(V+\alpha D_{X})D, \end{aligned}$$

and

$$\begin{aligned} S_{+}=S+\alpha \Delta S=S+\alpha \sqrt{\mu }D^{-1}D_{S}D^{-1}=\sqrt{\mu }D^{-1}(V+\alpha D_{S})D^{-1}. \end{aligned}$$

Thus we obtain

$$\begin{aligned} V_{+}=\frac{1}{\sqrt{\mu }}(D^{-1}X_{+}S_{+})^{\frac{1}{2}}. \end{aligned}$$

(4.2)

One can easily verify that $V_{+}^{2}$ is similar to the matrix $\frac{1}{\mu }X_{+}^{\frac{1}{2}}S_{+}X_{+}^{\frac{1}{2}}$. Then the eigenvalues of the matrix $V_{+}$ are the same as those of the matrix $\left( (V+\alpha D_{X})^{\frac{1}{2}}(V+\alpha D_{S})(V+\alpha D_{X})^{\frac{1}{2}}\right) ^{\frac{1}{2}}$. Since the proximity after one step is defined by $\Psi (V_{+})$, from (2.5), we have

$$\begin{aligned} \Psi (V_{+})=\Psi \left( \left( (V+\alpha D_{X})^{\frac{1}{2}}(V+\alpha D_{S})(V+\alpha D_{X})^{\frac{1}{2}}\right) ^{\frac{1}{2}}\right) \end{aligned}$$

Using the Lemma 3.1, one can get

$$\begin{aligned} \Psi (V_{+})\le \frac{1}{2}(\Psi (V+\alpha D_{X})+\Psi (V+\alpha D_{S})). \end{aligned}$$

(4.3)

Defining

$$\begin{aligned} f(\alpha ):=\Psi (V_{+})-\Psi (V), \end{aligned}$$

which denotes the decrease of the barrier function on each inner iteration. An immediate consequence follows from (4.3) is

$$\begin{aligned} f(\alpha )\le f_{1}(\alpha ):=\frac{1}{2}(\Psi (V+\alpha D_{X})+\Psi (V+\alpha D_{S}))-\Psi (V). \end{aligned}$$

The first second derivatives of $f_{1}(\alpha )$ are given as follows:

$$\begin{aligned} f_{1}^{\prime }(\alpha )= & {} \frac{1}{2}tr(\Psi^{\prime }(V+\alpha D_{X})D_{X}+\Psi^{\prime }(V+\alpha D_{S})D_{S}), \end{aligned}$$

(4.4)

$$\begin{aligned} f_{1}^{\prime \prime }(\alpha )= & {} \frac{1}{2}tr(\Psi^{\prime \prime }(V+\alpha D_{X})D_{X}^{2} +\Psi^{\prime \prime }(V+\alpha D_{S})D_{S}^{2}). \end{aligned}$$

(4.5)

We thus have

$$\begin{aligned} f(0)=f_{1}(0)=0 \end{aligned}$$

and

$$\begin{aligned} \begin{aligned} f_{1}^{\prime }(0)&=\frac{1}{2}tr\big (\psi ^{\prime }(V)D_{X}+\psi ^{\prime }(V)D_{S}\big ) =\frac{1}{2}tr\big (\psi ^{\prime }(V)(D_{X}+D_{S})\big )\\&=\frac{1}{2}tr\big (\psi ^{\prime }(V)(-\psi ^{\prime }(V))\big )=\frac{1}{2} tr\big (-\psi ^{\prime }(V)^{2}\big )=-2\delta (V)^{2}. \end{aligned} \end{aligned}$$

(4.6)

With $\delta (V)$ as defined in (3.3), then we use the following notations:

$$\begin{aligned} \lambda _{1}(V):=\lambda _{\min }(V),\quad \delta :=\delta (V). \end{aligned}$$

Now we cite following lemmas which will be used in analyzing the convergence of the algorithm.

Lemma 4.3

(El Ghami et al. 2009, Lemma 3.3) $f_{1}^{\prime \prime }(\alpha )\le 2\delta ^{2}\psi ^{\prime \prime }(\lambda _{1}(V)-2\alpha \delta ).$

Putting $v_{i}=\lambda _{i}(V)$, we have $f_{1}^{\prime \prime }(\alpha )\le 2\delta ^{2}\psi ^{\prime \prime }(\lambda _{1}(v_{1})-2\alpha \delta )$ from 4.3, which is equivalent to the results of Lemma 4.1 in Bai et al. (2004). From this stage one can apply word-by-word the same arguments as in Bai et al. (2004) for the LO case to obtain the following results.

Lemma 4.4

(Bai et al. 2004, Lemma 4.2) If $\alpha$ satisfies the inequality

$$\begin{aligned} -\psi ^{\prime }(\lambda _{1}(V)-2\alpha \delta )+\psi ^{\prime }(\lambda _{1}(V))\le 2\delta , \end{aligned}$$

(4.7)

then $f_{1}^{\prime }(\alpha )\le 0$.

Lemma 4.5

(Bai et al. 2004, Lemma 4.3) Using the notions of Lemma 3.3, if step size $\alpha$ satisfies (4.6), then the largest step size $\alpha$ is given by

$$\begin{aligned} \bar{\alpha }:=\frac{1}{2\delta }(\rho (\delta )-\rho (2\delta )). \end{aligned}$$

(4.8)

Lemma 4.6

(Bai et al. 2004, Lemma 4.4) Let $\rho$ and $\bar{\alpha }$ be as defined in Lemma 4.5, then

$$\begin{aligned} \bar{\alpha }\ge \tilde{\alpha }:=\frac{1}{\psi ^{\prime \prime }(\rho (2\delta ))}, \end{aligned}$$

(4.9)

and we will use $\tilde{\alpha }$ as the default step size.

Lemma 4.7

If $\tilde{\alpha }$ is defined as Lemma 4.6, then

$$\begin{aligned} \tilde{\alpha } \ge \frac{1}{2(9q+4)(4\delta +1)^{\frac{q+2}{q+1}}}, \end{aligned}$$

Proof

By using $\rho$ defined in Lemma 3.3, we may assume that $t=\rho (2\delta )$ for $t\in (0,1]$. Thus we have

$$\begin{aligned} \begin{aligned} \psi ^{\prime \prime }(\rho (2\delta ))&=\psi ^{\prime \prime }(t)=1+\frac{M(qe^{2t}+e^{t})}{(e^{t}-1)^{q+2}}\\&\le 1+(4\delta +1)^{\frac{q+2}{q+1}}M^{-\frac{1}{q+1}}(qe^{2t}+e^{t})\\&\le 4(2q+1)(4\delta +1)^{\frac{q+2}{q+1}},\ t\in (0,1]. \end{aligned} \end{aligned}$$

Combining the above results and Lemma 4.6, through the simple calculation, we derive that

$$\begin{aligned} \tilde{\alpha }=\frac{1}{\psi ^{\prime \prime }(\rho (2\delta ))}\ge \frac{1}{4(2q+1)(4\delta +1)^{\frac{q+2}{q+1}}}. \end{aligned}$$

This proves the lemma. $\square$

Lemma 4.8

(Bai et al. 2004, Lemma 4.5) If the step size $\alpha$ is such that $\alpha \le \bar{\alpha }$, then

$$\begin{aligned} f(\alpha )\le -\alpha \delta ^{2}. \end{aligned}$$

(4.10)

Lemma 4.9

One has

$$\begin{aligned} f(\tilde{\alpha })\le -\frac{\delta ^{2}}{\psi ^{\prime \prime } (\rho (2\delta ))}\le -\frac{\delta ^{\frac{q}{q+1}}}{4\big (2q+1\big ) \Big (4+\frac{1}{\delta }\Big )^{\frac{q+2}{q+1}}}. \end{aligned}$$

(4.11)

Proof

According to Lemmas 4.6, 4.7 and 4.8, we have

$$\begin{aligned} f(\tilde{\alpha })\le -\frac{\delta ^{2}}{\psi ^{\prime \prime }(\rho (2\delta ))}\le -\frac{\delta ^{2}}{4(2q+1)(4\delta +1)^{\frac{q+2}{q+1}}}\le -\frac{\delta ^{\frac{q}{q+1}}}{4(2q+1)\Big (4+\frac{1}{\delta }\Big )^{\frac{q+2}{q+1}}}. \end{aligned}$$

Hence, the results of this lemma holds. $\square$

4.3 Iteration complexity

Our aim in this section is to analyze the convergence of the algorithm. The question now is to count how many inner iterations are required to return to the situation where $\Psi (V)\le \tau$. To investigate this, we define the value of $\Psi (\upsilon )$ after each $\mu -$update as $\Psi _{0}$, and the subsequent values during inner iterations as $\Psi _{\kappa },\kappa =1,2,\ldots ,K$. Thus K is the number of iterations in the inner iteration after once $\mu -$update.

By using Lemmas 4.1, 4.2 and the definition of $\Psi _{0}$, we have $L_{\Psi }\ge \Psi _{0}\ge \Psi \ge \tau$. In what follows we assume $L_{\psi }\ge \Psi _{0}\ge \Psi \ge \tau \ge 2$. From Lemma 3.5, we deduce that $\delta \ge \sqrt{\frac{\Psi }{2}}\ge 1$. Substitution into (4.10) gives

$$\begin{aligned} f(\tilde{\alpha })\le -\frac{\delta ^{\frac{q}{q+1}}}{4(2q+1)\Big (4+\frac{1}{\delta }\Big )^{\frac{q+2}{q+1}}}\le -\frac{\Psi ^{\frac{q}{2(q+1)}}}{64(2q+1)}, \end{aligned}$$

(4.12)

which implies

$$\begin{aligned} \Psi _{\kappa +1}\le \Psi _{\kappa }-\frac{\Psi _{\kappa }^{\frac{q}{2(q+1)}}}{64(2q+1)},\quad \kappa =0,1,2,\ldots ,K-1. \end{aligned}$$

(4.13)

To derive an upper bound for the total number of inner iterations in an outer iteration, we give the following technical lemma, and its elementary proof please refer to Peng et al. (2001a).

Lemma 4.10

Let $t_{0},t_{1},\ldots ,t_{K}$ be a sequence of positive numbers such that

$$\begin{aligned} t_{\kappa +1}\le t_{\kappa }-\beta t_{\kappa }^{1-\gamma },\quad \kappa =0,1,2,\ldots ,K-1, \end{aligned}$$

where $\beta >0$ and $0<\gamma \le 1$. Then $K\le \left\lfloor \frac{t_{0}^{\gamma }}{\beta \gamma }\right\rfloor$.

Lemma 4.11

The following inequality holds:

$$\begin{aligned} K \le 128(2q+1)\Psi _{0}^{\frac{q+2}{2(q+1)}},\quad q\ge 1. \end{aligned}$$

Proof

Let $t_{\kappa }=\Psi _{\kappa },\ \beta =\frac{1}{64(2q+1)},\ \gamma =\frac{q+2}{2(q+1)}$. Using Lemma 4.10 and substitution gives, we have

$$\begin{aligned} \begin{aligned} K \le \frac{\Psi _{0}^{\gamma }}{\beta \gamma }&= \frac{128(2q+1)(q+1)\Psi _{0}^{\frac{q+2}{2(q+1)}}}{q+2}\\&\le 128(2q+1)\Psi _{0}^{\frac{q+2}{2(q+1)}}, \quad q\ge 1. \end{aligned} \end{aligned}$$

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

The Lemma 4.11 gives an upper bound for the number of iterations in the inner iteration after once $\mu -$update. Multiplication the number K by the number of barrier parameter updates yields an upper bound for the total number of iterations (Roos et al. 1997), where the number of barrier parameter updates is bounded by

$$\begin{aligned} \frac{1}{\theta }\log \frac{n}{\epsilon }. \end{aligned}$$

Thus we obtain that an upper bound for the total number of iterations as follows:

$$\begin{aligned} K\frac{1}{\theta }\log \frac{n}{\epsilon } \le \frac{\Psi _{0}^{\gamma }}{\theta \kappa \gamma }\log \frac{n}{\epsilon }. \end{aligned}$$

Recall that $L_{\psi }\ge \Psi _{0}$, and $L_{\psi }$ is bounded by Lemma 4.2, combining the above results and Lemma 4.11, we immediately obtain following theorem:

Theorem 4.1

The total number of iterations required by the algorithm is at most

$$\begin{aligned} 128\frac{(n\theta +2\sqrt{2n\tau }+2\tau )^{\frac{q+2}{2(q+1)}}(2q+1)}{\theta [2(1-\theta )]^{\frac{q+2}{2(q+1)}}} \log \frac{n}{\epsilon },\quad q\ge 1. \end{aligned}$$

Set $\tau =O(n)$ and $\theta =\Theta (1)$, as a consequence, we conclude that the iteration bound of the large-update method is

$$\begin{aligned} O\left(qn^{\frac{q+2}{2(q+1)}}\log \frac{n}{\epsilon }\right). \end{aligned}$$

Note that $\psi (t)$ is precisely the kernel function proposed by Bai et al. (2002b) if $q=1$, and the iteration bound for large-update method is $O(n^{\frac{3}{4}}\log \frac{n}{\epsilon })$. By choosing $q=O(\log n)$, the iteration bound becomes $O(\sqrt{n}\log n\log \frac{n}{\epsilon })$, which is the best known bound for such methods.

5 Numerical results

In this section, some numerical results of the large-update primal-dual IPMs for SDO are given. Consider the SDO problems with the following setting:

Problem 5.1

For the SDO problem with

$$\begin{aligned} A_{1}= & {} \left[ \begin{array}{cccccc} 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 2 &{}\quad 0 &{}\quad 0 &{}\quad -1 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad -2 &{}\quad -1 \\ 0 &{}\quad -1 &{}\quad 1 &{}\quad -1 &{}\quad -2 \\ \end{array} \right] ,\quad A_{2}=\left[ \begin{array}{cccccc} 0 &{}\quad 0 &{}\quad -2 &{}\quad 2 &{}\quad 0 \\ 0 &{}\quad 2 &{}\quad 1 &{}\quad 0 &{}\quad 2 \\ -2 &{}\quad 1 &{}\quad -2 &{}\quad 0 &{}\quad 1 \\ 2 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 2 &{}\quad 1 &{}\quad 0 &{}\quad 2 \\ \end{array} \right] ,\quad \\ A_{3}= & {} \left[ \begin{array}{cccccc} 2 &{}\quad 2 &{}\quad -1 &{}\quad -1 &{}\quad 1 \\ 2 &{}\quad 0 &{}\quad 2 &{}\quad 1 &{}\quad 1 \\ -1 &{}\quad 2 &{}\quad 0 &{}\quad 1 &{}\quad 0 \\ -1 &{}\quad 1 &{}\quad 1 &{}\quad -2 &{}\quad 0 \\ 1 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad -2 \\ \end{array} \right] ,\quad b=\left[ \begin{array}{ccc} -2 \\ 2 \\ -2 \\ \end{array} \right] ,\quad C=\left[ \begin{array}{cccccc} 3 &{}\quad 3 &{}\quad -3 &{}\quad 1 &{}\quad 1 \\ 3 &{}\quad 5 &{}\quad 3 &{}\quad 1 &{}\quad 2 \\ -3 &{}\quad 3 &{}\quad -1 &{}\quad 1 &{}\quad 2 \\ 1 &{}\quad 1 &{}\quad 1 &{}\quad -3 &{}\quad -1 \\ 1 &{}\quad 2 &{}\quad 2 &{}\quad -1 &{}\quad -1 \\ \end{array} \right] . \end{aligned}$$

Starting with the initial feasible solution of the test problem is $(X^{0},y^{0},S^{0})$, where $X^{0}=S^{0}=E$ and $y^{0}=(1,1,1)^{T}$.

Problem 5.2

For the SDO problem with

$$\begin{aligned} A_{1}=\left[ \begin{array}{ccc} 1 &{}\quad -1 \\ -1 &{}\quad 1 \\ \end{array} \right] ,\quad A_{2}=E,\quad b=\left[ \begin{array}{ccc} 1 \\ 1 \\ \end{array} \right] ,\quad C=\left[ \begin{array}{ccc} -2 &{}\quad 0 \\ 0 &{}\quad -2 \\ \end{array} \right] . \end{aligned}$$

Starting with the following initial feasible solution:

$$\begin{aligned} X^{0}=\left[ \begin{array}{ccc} 0.5 &{}\quad 0 \\ 0 &{}\quad 0.5 \\ \end{array} \right] ,\quad y^{0}=\left[ \begin{array}{ccc} 0 \\ -3 \\ \end{array} \right] ,\quad S^{0}=E. \end{aligned}$$

Problem 5.3

For the SDO problem with

$$\begin{aligned} A_{k}(i,j)=\left\{ \begin{array}{ll} 1 &{}\quad if\; i=j=k \;or \; i=j=k+1; \\ -1 &{}\quad if\; i=k,j=k+1 \;or \; i=k+1,\,\,j=k; \\ 0 &{}\quad otherwise, \end{array} \right. \end{aligned}$$

where $k=1,2,3$, and

$$\begin{aligned} A_{4}=E,\quad b=(2,2,2,4)^{T},\quad C=\left[ \begin{array}{cccccc} 2 &{}\quad -1 &{}\quad 0 &{}\quad 0 \\ -1 &{}\quad 2 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 2 &{}\quad -1 \\ -1 &{}\quad 1 &{}\quad 1 &{}\quad -2 \\ 0 &{}\quad 0 &{}\quad -1 &{}\quad 2 \\ \end{array} \right] . \end{aligned}$$

Starting with the following initial feasible solution:

$$\begin{aligned} X^{0}=S^{0}=E,\quad y^{0}= (1,0,1,0)^{T}. \end{aligned}$$

Problem 5.4

For the SDO problem with

$$\begin{aligned} A_{k}(i,j)=\left\{ \begin{array}{ll} 1 &{}\quad if \; i=j=k; \\ 1 &{}\quad if\; i=j \;and \; i=k+m; \\ 0 &{}\quad otherwise, \end{array} \right. \end{aligned}$$

where $k=1,2,3,\ldots ,m$, and

$$\begin{aligned} m\in \{5,15,25\},~~n=2m,~~b=(2,2,\ldots ,2)^{T},~~C=-E. \end{aligned}$$

Starting with the following initial feasible solution:

$$\begin{aligned} X^{0}=S^{0}=E,\quad y^{0}= (-2,-2,\ldots -2)^{T}. \end{aligned}$$

In all experiments, we set threshold parameter $\tau =2.5$, the accuracy parameter $\epsilon =10^{-6}$,the barrier update parameter $\theta \in \{0.5,0.6,0.7,0.8,0.9,0.99\}$. By using MATLAB2012 we obtain the iteration numbers of the algorithms based on different kernel functions that are stated in Tables 1, 2, 3, 4, 5, and 6. Some kernel functions we used in our experiments are as follows:

$$\begin{aligned} \begin{aligned}&\psi _{new}(t)=\frac{t^2-1}{2}+\frac{(e-1)^{q+1}}{qe(e^t-1)^q}-\frac{e-1}{qe},\quad q=1,2,3,\\&\psi _{1}(t)=\frac{t^{2}-1}{2}-\log t,\quad \psi _{2}(t)=\frac{t^{2}-1}{2}+\frac{t^{-1}-t}{2},\\&\psi _{3}(t)=\frac{t^{2}-1}{2}+\frac{6}{\pi }\tan (h(t)),\quad h(t)=\frac{\pi (1-t)}{4t+2},\\&\psi _{4}(t)=\frac{t^{2}-1}{2}+\frac{1}{q^{2}}\big (\frac{q}{t}-1\big )e^{q(\frac{1}{t}-1)}-\frac{q-1}{q^{2}},\quad q=1,2,3,\\&\psi _{5}(t)=\frac{t^{2}-1}{2}-\int ^{t}_{1}\Big (\frac{e-1}{e^{x}-1}\Big )^{p}dx,\quad p\ge 1, \end{aligned} \end{aligned}$$

The first kernel function $\psi _{new}(t)$ is proposed in this paper, and it is exactly the kernel function presented by Bai et al. (2002b) for $q=1$. $\psi _1(t)$ is the classical logarithmic kernel function. $\psi _2(t)$ is a self-regular kernel function presented by Peng et al. (2000). $\psi _3(t)$ is a trigonometric kernel function (El Ghami et al. 2012). $\psi _{4}(t)$ (Bai et al. 2012) and $\psi _{5}(t)$ (Fathi-Hafshejani and Fakharzadeh 2018) are parameterized kernel function, which obtain the best iteration complexity for $q=O(\log n)$.

Table 1 Numerical results for Problem 5.1

Table 2 Numerical results for Problem 5.2

Table 3 Numerical results for Problem 5.3

Table 4 Numerical results with $m=5$ for Problem 5.4

Table 5 Numerical results $m=15$ for Problem 5.4

Table 6 Numerical results $m=25$ for Problem 5.4

From the numerical results in Tables 1, 2, 3, 4, 5, and 6, we can get the following conclusions:

• The results in Tables 1, 2, 3, 4, 5, and 6 show that the larger $\theta$ is, the less or the same iteration numbers will be.

• For Problems 5.1–5.4 the best numerical results are obtained by performing algorithms 1 based on the new proposed kernel function $\psi (t)$ with $q=3$.

• Compared with the original kernel function, that is, when the parameter $q=1$, the numerical result are significantly improved.

• In most cases, our kernel function $\psi (t)$ have better numerical results than several other kernel functions $\psi _{1-5}(t)$.

These results imply that our kernel function is quite efficient and promising.

6 Concluding remarks

We have extended a pimal-dual interior-point algorithm for LO to SDO and derived the currently best known bound for the algorithm with large-update method, namely, $O(\sqrt{n}\log {n}\log {\frac{n}{\epsilon }})$, which is the same iteration bounds as the LO case. Finally, we present some numerical results, and the practical performance seems quite promising and significant based on our kernel function for SDO.

Some interesting topics for further research remain. Firstly, the search directions used in this paper are all based on the NT-symmetrization scheme. It may be possible to design similar algorithms using other symmetrization schemes and to obtain polynomial time iteration bounds. Secondly, the extension to symmetric cone optimization (SCO) deserves to be investigated.