Marzieh Sayadi Shahraki¹, Nezam Mahdavi-Amiri^2*
1Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran.
²Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran.
DOI: 10.4236/ajor.2026.163006   PDF    HTML   XML   5 Downloads   37 Views   Citations

Abstract

Two Mehrotra-type predictor-corrector interior point algorithms are proposed for solving symmetric cone optimization (SCO) problems, using the Euclidean Jordan algebra. The algorithms produce sequences of iterates in the wide neighborhood of the central path. We establish $\text{O}\left(\sqrt{r}\log {\epsilon }^{?1}\right)$ iteration complexity bound for the Nesterov-Todd (NT) scaling direction. To our knowledge, this is the best complexity result obtained so far for interior-point methods over wide neighborhood. We demonstrate the computational efficiency of the proposed algorithms by numerical test results.

Keywords

Interior-Point Algorithm, Wide Neighborhood, Mehrotra-Type Algorithm, Symmetric Cone Programming, Euclidean Jordan Algebra

Share and Cite:

1. Introduction

Symmetric cone optimization (SCO) problem is a convex optimization problem, minimization of a linear function over the intersection of an affine subspace and a symmetric cone. The SCO problem is considered to be an important class of convex optimization problems, because it includes linear optimization (LO), second-order cone optimization (SOCO), and semidefinite optimization (SDO) as special cases. In recent years, these problems have attracted the attention of many scholars in optimization.

Among various approaches for solving SCO problem, interior-point methods (IPMs) are the most popular algorithms and have been widely used to obtain the best iteration complexity results. The basic idea for solving SCO problems using IPMs was first proposed by Nesterov and Nemirovskii [1]. Faybusovich [2] extended a primal-dual IPM for SDO to SCO using the Euclidean Jordan algebra. Consequently, several efficient IPMs for SCO have been developed; see, e.g., [3]-[10].

Predictor-corrector methods, the most studied variants of interior-point methods, are being used as Mehrotra’s predictor-corrector algorithm [11] in a number of optimization packages. In these methods, by solving linear systems with the same coefficient matrix, three directions are produced: predictor, corrector and centering. The moving direction is determined by a combination of these directions. Zhang and Zhang [12] first established convergence theory and complexity bounds for two Mehrotra-type second-order algorithms. Later, Zhang and Zhang [13] extended the idea of [12] to SCO and showed the complexity bound of $\text{O}\left(r^{3/2}\log {ϵ}^{-1}\right)$ for the Nesterov-Todd search direction. Many primary IPMs are based on the small neighborhood or the negative infinity large neighborhood. Among all existing path-following interior-point algorithms, the theoretical iteration complexity of wide neighborhood algorithms is the worst, but in practice, these algorithms perform better than small neighborhood algorithms. Recently, Ai and Zhang [14] considered an IPM for linear complementarity problem (LCP), which works in a wide neighborhood and has the same complexity as the best known small neighborhood IPMs. Applying an interesting idea, they decomposed the classical Newton search direction into the nonnegative and nonpositive parts corresponding to the nonnegative and the nonpositive parts of the right-hand side. They showed that if these two directions are equipped with different and appropriate step sizes, then the method enjoys the low iteration bound of $\text{O}\left(\sqrt{n}\log {ϵ}^{-1}\right)$ . Liu et al. [15] modified the Ai-Zhang’s primal-dual path-following interior-point method of [14] to gain a class of Mehrotra-type predictor-corrector algorithm for monotone LCPs. Here, we are to modify the Ai-Zhang’s primal-dual interior point method to present two Mehrotra-type predictor-corrector algorithms. First, we present a Mehrotra-type predictor-corrector algorithm generalizing the approach of [15] for LCP to SCO. Then, we propose the second Mehrotra-type predictor-corrector algorithm for SCO, by adding two corrector steps to the Ai-Zhang path-following algorithm [14], to improve the performance. Finally, we show that the use of corrector steps does not impair the worst-case complexity of the algorithm.

2. Preliminaries

Here, we recall briefly the basic concept and useful results of Euclidean Jordan algebra. We refer the reader to [16] for details.

Definition 1. Let $\mathcal{J}$ be an $n$ -dimensional vector space over the field of real numbers with a multiplication “$\circ$ ” where the map $\circ :\left(x,y\right)\mapsto x\circ y$ is bilinear from $\mathcal{J}\times \mathcal{J}$ to $\mathcal{J}$ . The triple $\left(\mathcal{J}, \circ , \langle \cdot , \cdot \rangle \right)$ is a Euclidean Jordan algebra if for all $x,y,z\in \mathcal{J}$ , we have:

1) $x\circ y=y\circ x$ ;

2) $x\circ \left(x^2\circ y\right)=x^2\circ \left(x\circ y\right)$ , where $x^2:=x\circ x$ ;

3) $\langle x\circ y,z\rangle =\langle y,x\circ z\rangle$ .

We assume that there exists an identity element $e\in \mathcal{J}$ such that $e\circ x=x\circ e=x$ , for all $x\in \mathcal{J}$ . The degree of $x\in \mathcal{J}$ , denoted by $\text{deg}\left(x\right)$ , is the smallest integer $k$ such that $\left\{e,x,\cdots ,x^k\right\}$ is linearly dependent. The rank of $\mathcal{J}$ , denoted by $\text{rank}\left(\mathcal{J}\right)$ , is defined as the maximum $\text{deg}\left(x\right)$ over all $x\in \mathcal{J}$ .

An element c is idempotent if $c\ne 0$ and $c^2=c$ . An idempotent $c$ is primitive if it is nonzero and can not be expressed by sum of two other nonzero idempotents. Two idempotents $c_i$ and $c_j$ are said to be pairwise orthogonal if $c_i\circ c_j=0$ . A set of orthogonal primitive idempotents $\left\{c_1,c_2,\cdots ,c_k\right\}$ is called a Jordan frame if $c_i\circ c_j=0$ , $i\ne j$ , and $c_1+\cdots +c_k=e$ . For $x\in \mathcal{J}$ , let $k$ be the smallest positive integer such that $\left\{e,x,\cdots ,x^k\right\}$ is linearly dependent; $k$ is called the degree of $x$ and is denoted by $\text{deg}\left(x\right)$ . The rank of $\mathcal{J}$ , denoted by $\text{rank}\left(\mathcal{J}\right)$ , is defined by $r:=\text{max}\left\{\text{deg}\left(x\right):x\in \mathcal{J}\right\}$ .

A cone is symmetric if and only if it is the cone of squares of a Euclidean Jordan algebra, which is denoted by $\mathcal{K}:=\left\{x^2:x\in \mathcal{J}\right\}$ . For a given $x\in \mathcal{J}$ , the Lyapunov transformation $L:\mathcal{J}\to \mathcal{J}$ is defined by $L\left(x\right)y:=x\circ y$ , for every $y\in \mathcal{J}$ . Furthermore, we define the quadratic representation of $x$ in $\mathcal{J}$ by $Q\left(x\right):=2L{\left(x\right)}^2-L\left(x^2\right)$ , where $L{\left(x\right)}^2=L\left(x\right)L\left(x\right)$ .

The spectral decomposition theorem (Theorem III.1.2 of [16]) of a Euclidean Jordan algebra $\mathcal{J}$ states that for any $x\in \mathcal{J}$ , there exists a Jordan frame $\left\{c_1,c_2,\cdots ,c_r\right\}$ and real numbers $\left\{{\lambda }_1,\cdots ,{\lambda }_r\right\}$ (the eigenvalues of $x$ ) such that $x={\lambda }_1{c}_1+\cdots +{\lambda }_r{c}_r$ . Some generated functions by the eigenvalues of $x$ are: the Frobenius norm on $\mathcal{J}$ is defined by $\Vert x\Vert :=\sqrt{\langle x,x\rangle }={\left({\displaystyle {\sum }_{i=1}^r{\lambda }_i^2}\right)}^{1/2}$ , and $Tr\left(x\right)={\displaystyle {\sum }_{i=1}^r{\lambda }_i}$ . Moreover, since $Tr\left(x\circ y\right)$ is a symmetric positive definite quadratic form, the inner product can be defined as $\langle x,y\rangle :=Tr\left(x\circ y\right)$ . The inverse is $x^{-1}:={\displaystyle {\sum }_{i=1}^r{\lambda }_i^{-1}{c}_i}$ , whenever all ${\lambda }_i\ne 0$ . Accordingly, $x^{+}={\displaystyle {\sum }_{i=1}^r{\lambda }_i^{+}{c}_i}$ , where ${\lambda }_i^{+}=\text{max}\left\{{\lambda }_i,0\right\}$ , for $i=1,2,\cdots ,r$ . We define $x^{-}=x-x^{+}$ . We call $x\in \mathcal{J}$ positive semidefinite (positive definite), denoted by $x\underset{\_}{\succ }0$ $\left(x\succ 0\right)$ , if all eigenvalues of $\mathcal{J}$ are nonnegative (positive). Moreover, $x\underset{\_}{\succ }0$ $\left(x\succ 0\right)$ if and only if $x\in \mathcal{K}$ $\left(x\in \mathrm{int}\mathcal{K}\right)$ .

3. The SCO Problem and Neighborhood of Central Path

Let $\mathcal{J}$ be a Euclidean Jordan algebra of dimension $n$ with rank $r$ , and $\mathcal{K}$ be the cone of squares corresponding to $\mathcal{J}$ . Consider the following primal and dual problems in the standard forms:

(P) $\text{min}\langle c,x\rangle :\mathcal{A}x=b,x\in \mathcal{K},$

and

(D) $\text{max}\langle b,y\rangle :{\mathcal{A}}^{\text{*}}y+s=c,s\in \mathcal{K},y\in {ℝ}^m,$

where $c\in \mathcal{J}$ , $b\in {ℝ}^m$ , $\mathcal{A}$ is a linear operator that maps $\mathcal{J}$ into ${ℝ}^m$ and ${\mathcal{A}}^{\text{*}}$ is its adjoint operator such that $\langle x,{\mathcal{A}}^{\text{*}}y\rangle =\langle \mathcal{A}x,y\rangle$ , for all $x\in \mathcal{J}$ .

The primal-dual feasible set is defined as

$ℱ=\left\{\left(x,y,s\right)\in \mathcal{K}\times {ℝ}^m\times \mathcal{K}:\mathcal{A}x=b,{\mathcal{A}}^{\text{*}}y+s=c\right\},$

and we assume that the interior of the primal-dual feasible set,

${ℱ}^0=\left\{\left(x,y,s\right)\in \mathrm{int}\mathcal{K}\times {ℝ}^m\times \mathrm{int}\mathcal{K}:\mathcal{A}x=b,{\mathcal{A}}^{*}y+s=c\right\},$

is nonempty; that is, the primal-dual pair of the SCO problems satisfies the interior-point condition (IPC). Under the IPC, finding an optimal solution of (P) and (D) is equivalent to solving the following system [17]:

$\begin{array}{l}\mathcal{A}x=b,x\in \mathcal{K},\\ {\mathcal{A}}^{\text{*}}y+s=c,s\in \mathcal{K},y\in {ℝ}^m,\\ x\circ s=0.\end{array}$ (1)

The basic idea of a path-following interior-point algorithm is to replace the third equation in (1), the so-called complementarity condition, by the parameterized equation $x\circ s=\tau \mu e$ , for $\mu =\langle x,s\rangle /r$ , and $\tau \in \left(0,1\right)$ . Thus, we consider the following system:

$\begin{array}{l}\mathcal{A}x=b,x\in \mathcal{K},\\ {\mathcal{A}}^{\text{*}}y+s=c,s\in \mathcal{K},y\in {ℝ}^m,\\ x\circ s=\tau \mu e.\end{array}$ (2)

Due to the IPC, a unique solution $\left(x\left(\mu \right),y\left(\mu \right),s\left(\mu \right)\right)$ of the perturbed system (2) exists for each $\mu >0$ [17]. This solution is called the $\mu$ -center for the SCO problem. The set of $\mu$ -centers provides a path, which is called the central path of the SCO problem. The $\mu$ -center approximates an optimal solution of the given problem pair as $\mu$ goes to zero. Applying the Newton method for the perturbed system of (2), we get the following equations:

$\begin{array}{l}\mathcal{A}\Delta x=0,\\ {\mathcal{A}}^{*}\Delta y+\Delta s=0,\\ x\circ \Delta s+s\circ \Delta x=\tau \mu e-x\circ s.\end{array}$ (3)

It has been shown that the reason for the system (3) not having a unique solution is the fact that $x$ and $s$ do not operator commute, in general; that is, $L\left(x\right)L\left(s\right)\ne L\left(s\right)L\left(x\right)$ .

To overcome this defect, we use the scaling scheme based on the following fact (Lemma 28 of [6]). Let $u$ be invertible. Then, $x\circ s=\mu e$ if and only if $Q\left(u\right)x\circ Q\left(u^{-1}\right)s=\mu e$ .

In our work here, we choose

$u={\left[Q\left(x^{\frac{1}{2}}\right){\left(Q\left(x^{\frac{1}{2}}\right)s\right)}^{-\frac{1}{2}}\right]}^{-1/2}={\left[Q\left(s^{-\frac{1}{2}}\right){\left(Q\left(s^{\frac{1}{2}}\right)x\right)}^{\frac{1}{2}}\right]}^{-1/2},$

which gives the Nesterov-Todd (NT) direction. For the NT direction [18], we have $Q\left(u\right)x=Q\left(u^{-1}\right)s$ . The system (3) can be rewritten as follows:

$\begin{array}{l}\tilde{\mathcal{A}}\Delta \tilde{x}=0,\\ {\tilde{\mathcal{A}}}^{*}\Delta y+\Delta \tilde{s}=0,\\ \tilde{s}\circ \Delta \tilde{x}+\tilde{x}\circ \Delta \tilde{s}=\tau \mu e-\tilde{x}\circ \tilde{s},\end{array}$ (4)

where $\tilde{\mathcal{A}}=\mathcal{A}Q\left(u^{-1}\right)$ , $v:=\tilde{x}=Q\left(u\right)x=\tilde{s}=Q\left(u^{-1}\right)s$ , $\Delta \tilde{x}=Q\left(u\right)\Delta x$ and $\Delta \tilde{s}=Q\left(u^{-1}\right)\Delta s$ .

Most interior point algorithms work in the classical negative infinity large neighborhood, defined by

${\mathcal{N}}_{\infty }^{-}\left(1-\gamma \right)=\left\{\left(x,y,s\right)\in \mathrm{int}\mathcal{K}\times {ℝ}^m\times \mathrm{int}\mathcal{K}:{\lambda }_{\min }\left(w\right)\ge \gamma \mu \right\},$

where $w=Q\left(x^{1/2}\right)s$ and $\gamma \in \left(0,1\right)$ . Our proposed algorithms start from a feasible point in a wide neighborhood of the central path due to [14] [19], as follows:

$\mathcal{N}\left(\tau ,\beta \right)=\left\{\left(x,y,s\right)\in \mathrm{int}\mathcal{K}\times {ℝ}^m\times \mathrm{int}\mathcal{K}:\Vert {\left(\tau \mu e-w\right)}^{+}\Vert \le \beta \tau \mu \right\},$

where $\beta \in \left(0,1\right)$ .

This neighborhood is even larger than the ${\mathcal{N}}_{\infty }^{-}\left(1-\gamma \right)$ neighborhood, since it can be verified that

${\mathcal{N}}_{\infty }^{-}\left(1-\tau \right)\subseteq \mathcal{N}\left(\tau ,\beta \right)\subseteq {\mathcal{N}}_{\infty }^{-}\left(1-\left(1-\beta \right)\tau \right).$ (5)

4. Mehrotra Predictor-Corrector Algorithms

Here, we describe our algorithms in detail. In accordance with the Ai-Zhang’s original idea [14], we decompose the Newton direction into two separate parts corresponding to the positive and negative parts of the right-hand side of the third equality of the system (4); i.e., $\tau \mu e-\tilde{x}\circ \tilde{s}$ . Therefore, in our algorithms, we compute the predictor directions $\left(\Delta {\tilde{x}}_{-},\Delta y_{-},\Delta {\tilde{s}}_{-}\right)$ and $\left(\Delta {\tilde{x}}_{+},\Delta y_{+},\Delta {\tilde{s}}_{+}\right)$ respectively by solving the following two systems:

$\begin{array}{l}\tilde{\mathcal{A}}\Delta {\tilde{x}}_{-}=0,\\ {\tilde{\mathcal{A}}}^{*}\Delta y_{-}+\Delta {\tilde{s}}_{-}=0,\\ \tilde{s}\circ \Delta {\tilde{x}}_{-}+\tilde{x}\circ \Delta {\tilde{s}}_{-}={\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-},\end{array}$ (6)

and

$\begin{array}{l}\tilde{\mathcal{A}}\Delta {\tilde{x}}_{+}=0,\\ {\tilde{\mathcal{A}}}^{*}\Delta y_{+}+\Delta {\tilde{s}}_{+}=0,\\ \tilde{s}\circ \Delta {\tilde{x}}_{+}+\tilde{x}\circ \Delta {\tilde{s}}_{+}={\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}.\end{array}$ (7)

4.1. First Algorithm and Its Convergence Analysis

We present a Mehrotra predictor-corrector path-following algorithm for SCO problems based on Liu et al.’s idea for LCP [15]. For this, we compute the maximum step size $\theta \in \left(0,1\right]$ that ensures

$\left(\tilde{x}+\theta \Delta {\tilde{x}}_{-}\right)\circ \left(\tilde{s}+\theta \Delta {\tilde{s}}_{-}\right)\in \mathcal{K}.$ (8)

Using the predictor step obtained by solving (6), we compute the corrector direction $\left(\Delta {\tilde{x}}_{-}^c,\Delta y_{-},\Delta {\tilde{s}}_{-}^c\right)$ by solving the following system:

$\begin{array}{l}\tilde{\mathcal{A}}\Delta {\tilde{x}}_{-}^c=0,\\ {\tilde{\mathcal{A}}}^{*}\Delta y_{-}^c+\Delta {\tilde{s}}_{-}^c=0,\\ \tilde{s}\circ \Delta {\tilde{x}}_{-}^c+\tilde{x}\circ \Delta {\tilde{s}}_{-}^c=-\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}.\end{array}$ (9)

Let $\alpha =\left({\alpha }_1,{\alpha }_2\right)\in {ℝ}_{+}^2$ give the step lengths. Then, we define a combination of directions as follows:

$\begin{array}{l}\left(\Delta \tilde{x}\left(\alpha \right),\Delta y\left(\alpha \right),\Delta \tilde{s}\left(\alpha \right)\right)\\ :={\alpha }_1\left(\left(\Delta {\tilde{x}}_{-},\Delta y_{-},\Delta {\tilde{s}}_{-}\right)+\left(\Delta {\tilde{x}}_{-}^c,\Delta y_{-}^c,\Delta {\tilde{s}}_{-}^c\right)\right)+{\alpha }_2\left(\Delta {\tilde{x}}_{+},\Delta y_{+},\Delta {\tilde{s}}_{+}\right).\end{array}$

Finally, the new iterate is:

$\left(\tilde{x}\left(\alpha \right),y\left(\alpha \right),\tilde{s}\left(\alpha \right)\right)=\left(\tilde{x},y,\tilde{s}\right)+\left(\Delta \tilde{x}\left(\alpha \right),\Delta y\left(\alpha \right),\Delta \tilde{s}\left(\alpha \right)\right).$ (10)

Since $Tr\left(\Delta \tilde{x}\left(\alpha \right)\circ \Delta \tilde{s}\left(\alpha \right)\right)=0$ , the duality gap corresponding to the new iterate can be written as

$\mu \left(\alpha \right)=\mu +\frac{{\alpha }_1}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)+\frac{{\alpha }_2}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right).$ (11)

We now describe the Mehrotra predictor-corrector method for the SCO problem as Algorithm 1.

Algorithm 1. The Mehrotra predictor-corrector method for solving the SCO problem (first method).

Accuracy parameter $\epsilon >0$ ; neighborhood parameters $0<\beta \le 1/3$ and $0<\tau \le 1/4$ ; the initial point $\left(x^0,y^0,s^0\right)\in \mathcal{N}\left(\tau ,\beta \right)$ with ${\mu }^0=\langle x^0,s^0\rangle /r$ . Step 0: Set $k:=0$ . Step 1: If $\langle x^k,s^k\rangle \le \epsilon$ then stop. Step 2: Choose a Nesterov-Todd scaling element $u$ . Step 3: Compute the directions $\left(\text{Δ}{\tilde{x}}_{-},\text{Δ}{y}_{-},\text{Δ}{\tilde{s}}_{-}\right)$, by solving (6) and $\left(\text{Δ}{\tilde{x}}_{+},\text{Δ}{y}_{+},\text{Δ}{\tilde{s}}_{+}\right)$ by solving (7). Step 4: Find the maximum feasible step length $\theta$ by (8). Step 5: Compute the direction $\left(\text{Δ}{\tilde{x}}_{-}^c,\text{Δ}{y}_{-}^c,\text{Δ}{\tilde{s}}_{-}^c\right)$ by solving (9). Step 6: Find the step lengths $\alpha =\left({\alpha }_1,{\alpha }_2\right)$ giving a sufficient reduction of the duality gap and assuring $\left(\tilde{x}\left(\alpha \right),y\left(\alpha \right),\tilde{s}\left(\alpha \right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ . Step 7: Let ${\alpha }^k:=\alpha$ , $\left({\tilde{x}}^{k+1},y^{k+1},{\tilde{s}}^{k+1}\right):=\left(\tilde{x}\left({\alpha }^k\right),y\left({\alpha }^k\right),\tilde{s}\left({\alpha }^k\right)\right)$ and ${\mu }^{k+1}:=\langle x^{k+1},s^{k+1}\rangle /r$ . Step 8: Set $k:=k+1$ and go to Step 1.

Next, we present an analysis of Algorithm 1. Some of the obtained results will also be useful for the analysis of the second algorithm.

Lemma 1 (Lemma 2.13 of [20]). Let $x,s\in \mathcal{J}$ with $\langle x,s\rangle =0$ . Then, we have:

$\Vert x\circ s\Vert \le 2^{-3/2}{\Vert x+s\Vert }^2.$

Lemma 2 (Lemma 5.12 of [21]). If $x,y\in \mathcal{J}$ , then we have:

$\Vert {\left(x+y\right)}^{+}\Vert \le \Vert x^{+}+y^{+}\Vert \le \Vert x^{+}\Vert +\Vert y^{+}\Vert .$

Lemma 3 (Lemma 5.1 of [7]). Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ . Then,

$\Vert {\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert \le \beta \tau \mu .$

Lemma 4 (Lemma 5.2 of [7]). Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ . Then,

$Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\le \sqrt{r}\beta \tau \mu .$

Lemma 5. Let $\left(\tilde{x},y,\tilde{s}\right)\in {ℱ}^0$ , and $\left(\Delta {\tilde{x}}_{-},\Delta y_{-},\Delta {\tilde{s}}_{-}\right)$ be the solution of (6). Then, we have:

1) $\frac{1}{4}e-{\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\in \mathcal{K}$ ,

2) $\left(1-\theta \right)e+{\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\in \mathcal{K}$ .

Proof. Let $\tilde{x}\circ \tilde{s}={\displaystyle {\sum }_{i=1}^r{\lambda }_i{c}_i}$ for some Jordan frame $\left\{c_1,\cdots ,c_r\right\}$ and let the spectral eigenvalues satisfy

$\tau \mu -{\lambda }_1\le \cdots \le \tau \mu -{\lambda }_k\le 0<\tau \mu -{\lambda }_{k+1}\le \cdots \le \tau \mu -{\lambda }_r.$ (12)

Thus, since $\tilde{x}$ and $\tilde{s}$ are operator commute, we have:

$\begin{array}{c}{\left(L{\left(v\right)}^{-1}{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)}^2={\left(L{\left(v\right)}^{-1}{\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right)c_i\right)}^2\\ ={\left({\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right)L{\left(v\right)}^{-1}{c}_i\right)}^2\\ ={\left({\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right){\lambda }_i^{-1/2}{c}_i\right)}^2\\ ={\displaystyle \sum }_{i=1}^k\frac{{\left(\tau \mu -{\lambda }_i\right)}^2}{{\lambda }_i}{c}_i={\displaystyle \sum }_{i=1}^k\left({\lambda }_i-\tau \mu \right)\frac{\left({\lambda }_i-\tau \mu \right)}{{\lambda }_i}{c}_i\\ \preccurlyeq {\displaystyle \sum }_{i=1}^k\left({\lambda }_i-\tau \mu \right)c_i\preccurlyeq {\displaystyle \sum }_{i=1}^r{\lambda }_i{c}_i=v^2.\end{array}$ (13)

The third equation of (6) can be written as

$\Delta {\tilde{x}}_{-}+\Delta {\tilde{s}}_{-}=L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right).$

Then, using the fact that $\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}=\frac{1}{4}\left({\left(\Delta {\tilde{x}}_{-}+\Delta {\tilde{s}}_{-}\right)}^2-{\left(\Delta {\tilde{x}}_{-}-\Delta {\tilde{s}}_{-}\right)}^2\right)$ , we have:

$\begin{array}{c}\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}=\frac{1}{4}\left[{\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\right)}^2-{\left(\text{Δ}{\tilde{x}}_{-}-\text{Δ}{\tilde{s}}_{-}\right)}^2\right]\\ \preccurlyeq \frac{1}{4}{\left[L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\right]}^2.\end{array}$ (14)

By (13) and (14), we have:

$\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\preccurlyeq \frac{1}{4}{v}^2.$ (15)

This relationship along with ${\left(L{\left(v\right)}^{-1}\right)}^2{v}^2=e$ gives the first part of the lemma.

From (8), we have:

$\tilde{x}\circ \tilde{s}+\theta {\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\theta }^2\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}\in \mathcal{K}.$ (16)

On the other hand, it is trivial to verify

$\tilde{x}\circ \tilde{s}+\theta {\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\succcurlyeq \tilde{x}\circ \tilde{s}+\theta {\left(-\tilde{x}\circ \tilde{s}\right)}^{-}=\left(1-\theta \right)v^2.$

This equality together with (16) implies:

$\left(1-\theta \right)e+{\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\in \mathcal{K},$ (17)

which completes the proof.

Let $\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}$ have the spectral decomposition $\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}={\displaystyle {\sum }_{i=1}^r{\sigma }_i{d}_i}$ , where $\left\{d_1,\cdots ,d_r\right\}$ is a Jordan frame. Moreover, we may write ${\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}={\displaystyle {\sum }_{i=1}^t{\sigma }_i{d}_i}$ and ${\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}={\displaystyle {\sum }_{i=t+1}^r{\sigma }_i{d}_i}$ . Then, by (15), we have:

$\begin{array}{c}Tr{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}={\displaystyle \sum }_{i=t+1}^r{\sigma }_i\\ ={\displaystyle \sum }_{i=t+1}^r\langle \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-},d_i\rangle \\ ={\displaystyle \sum }_{i=t+1}^r\left(\langle \frac{1}{4}{v}^2,d_i\rangle -\langle \frac{1}{4}{v}^2-\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-},d_i\rangle \right)\\ \le \frac{1}{4}{\displaystyle \sum }_{i=t+1}^r\langle v^2,d_i\rangle \le \frac{1}{4}r\mu .\end{array}$ (18)

Lemma 6. Let $\left(\tilde{x},y,\tilde{s}\right)\in {ℱ}^0$ , and $\left(\Delta {\tilde{x}}_{-},\Delta y_{-},\Delta {\tilde{s}}_{-}\right)$ be the solution of (6). Then, we have:

${\Vert L{\left(v\right)}^{-1}\left(\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\Vert }^2\le \frac{1}{4}r\mu .$

Proof. Using Lemma 5, $\langle \Delta {\tilde{x}}_{-},\Delta {\tilde{s}}_{-}\rangle =0$ , and (18), we have:

$\begin{array}{l}\langle {\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}\rangle \\ =\langle \left(1-\theta \right)e,-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}\rangle \\ -\langle \left(1-\theta \right)e+{\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}\rangle \\ \le \left(1-\theta \right)\langle e,-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}\rangle \le \left(1-\theta \right)\frac{1}{4}r\mu .\end{array}$ (19)

Moreover, by Lemma 5 and (18), we have:

$\begin{array}{l}{\theta }^2\langle {\left(L{\left(v\right)}^{-1}\right)}^2\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}\rangle \\ ={\theta }^2\langle \frac{1}{4}e,-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}\rangle \\ -{\theta }^2\langle \frac{1}{4}e+{\left(L{\left(v\right)}^{-1}\right)}^2\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}\rangle \\ \le {\theta }^2\langle \frac{1}{4}e,-{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}\rangle \le \frac{1}{4}{\theta }^2\left(\frac{1}{4}r\mu \right).\end{array}$ (20)

Now, using (19) and (20), we have:

$\begin{array}{l}{\Vert L{\left(v\right)}^{-1}\left(\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\Vert }^2\\ =\langle L{\left(v\right)}^{-1}\left(\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),L{\left(v\right)}^{-1}\left(\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\rangle \\ =\langle {\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\rangle \\ =\langle {\left(L{\left(v\right)}^{-1}\right)}^2\left({\theta }^2\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{-}\rangle \\ +{\theta }^2\langle {\left(L{\left(v\right)}^{-1}\right)}^2\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right),{\left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)}^{+}\rangle \\ \le \left(1-\theta +\frac{1}{4}{\theta }^2\right)\left(\frac{1}{4}r\mu \right)\le \frac{1}{4}r\mu ,\end{array}$

which completes the proof.

Lemma 7. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ and $\beta \le 1/3$ . Then, we have:

1) ${\Vert L{\left(v\right)}^{-1}{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\Vert }^2\le r\mu$ ,

2) ${\Vert L{\left(v\right)}^{-1}{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert }^2\le \frac{1}{2}\beta \tau \mu$ .

Proof. From (13), we obtain:

${\Vert L{\left(v\right)}^{-1}{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\Vert }^2\le r\mu ,$

which implies the first part of the lemma.

Similarly, making use of the proof of (13) and since $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ by Lemma 3, we have:

$\begin{array}{c}{\Vert L{\left(v\right)}^{-1}{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert }^2={\Vert {\displaystyle \sum }_{i=k+1}^r\left(\tau \mu -{\lambda }_i\right)L{\left(v\right)}^{-1}{c}_i\Vert }^2\\ ={\Vert {\displaystyle \sum }_{i=k+1}^r\left(\tau \mu -{\lambda }_i\right){\lambda }_i^{-1/2}{c}_i\Vert }^2={\displaystyle \sum }_{i=k+1}^r\frac{{\left(\tau \mu -{\lambda }_i\right)}^2}{{\lambda }_i}\\ \le \frac{1}{\left(1-\beta \right)\tau \mu }{\displaystyle \sum }_{i=k+1}^r{\left(\tau \mu -{\lambda }_i\right)}^2\\ =\frac{1}{\left(1-\beta \right)\tau \mu }{\Vert {\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert }^2\\ \le \frac{{\left(\beta \tau \mu \right)}^2}{\left(1-\beta \right)\tau \mu }\le \frac{1}{2}\beta \tau \mu ,\end{array}$

where the last inequality follows from $\beta \le 1/3$ . This completes the proof for the second part.

Lemma 8. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ and $\beta \le 1/3$ . If ${\alpha }_1\le \frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ , then we have:

$\Vert \Delta \tilde{x}\left(\alpha \right)\circ \Delta \tilde{s}\left(\alpha \right)\Vert \le \frac{4}{5}{\alpha }_2\beta \tau \mu .$

Proof. Since $Tr\left(\Delta \tilde{x}\left(\alpha \right)\circ \Delta \tilde{s}\left(\alpha \right)\right)=0$ , we have:

$\begin{array}{l}\Vert \Delta \tilde{x}\left(\alpha \right)\circ \Delta \tilde{s}\left(\alpha \right)\Vert \le \frac{1}{2}\left({\Vert \Delta \tilde{x}\left(\alpha \right)\Vert }^2+{\Vert \Delta \tilde{s}\left(\alpha \right)\Vert }^2\right)=\frac{1}{2}\left({\Vert \Delta \tilde{x}\left(\alpha \right)+\Delta \tilde{s}\left(\alpha \right)\Vert }^2\right)\\ =\frac{1}{2}\left[{\Vert L{\left(v\right)}^{-1}\left({\alpha }_1{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\alpha }_2{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}-{\alpha }_1\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\Vert }^2\right]\\ \le \frac{1}{2}[\Vert L{\left(v\right)}^{-1}\left({\alpha }_1{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\alpha }_2{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\Vert \\ +{{\alpha }_1\Vert L{\left(v\right)}^{-1}\left(\theta \Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)\Vert ]}^2\\ \le \frac{1}{2}{\left(\sqrt{{\alpha }_1^{2}r\mu +\frac{{\alpha }_2^2}{2}\beta \tau \mu }+\frac{{\alpha }_1}{2}\sqrt{r\mu }\right)}^2\\ \le \frac{1}{2}{\left(\sqrt{\frac{9{\alpha }_2^2}{25}\beta \tau \mu +\frac{{\alpha }_2^2}{2}\beta \tau \mu }+\frac{3}{10}{\alpha }_2\sqrt{\beta \tau \mu }\right)}^2\le \frac{4}{5}{\alpha }_2\beta \tau \mu ,\end{array}$

where the second inequality follows from Lemmas 6 and 7, the properties of $L\left(v\right)$ and the third inequality uses the fact that ${\alpha }_1\le \frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ . The proof is now complete.

For simplicity of notations, we define:

$\delta :=-\frac{Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)}{Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)},$ (21)

and

$\psi \left(\alpha \right):=\tilde{x}\circ \tilde{s}+{\alpha }_1{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\alpha }_2{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}-{\alpha }_1\theta \left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right).$ (22)

Using the Cauchy-Schwarz inequality and Lemma 3, and the facts that $\beta \le 1/3$ and $\tau \le 1/4$ , we have:

$\begin{array}{c}\delta =-\frac{Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)}{Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)}\le \frac{\beta \tau }{\left(1-\tau \right)\sqrt{r}}\\ =\frac{\sqrt{\beta \tau }}{1-\tau }\sqrt{\frac{\beta \tau }{r}}\le \frac{\sqrt{12}}{9}\sqrt{\frac{\beta \tau }{r}}.\end{array}$ (23)

Next, using the definition of $\delta$ given by (21), we further have the following lemma.

Lemma 9. If we choose ${\alpha }_1\ge \delta$ , then we have $\mu \left(\alpha \right)\le \mu$ .

Proof. From (11) and (21), we obtain:

$\begin{array}{c}\mu \left(\alpha \right)=\mu +\frac{{\alpha }_1}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)+\frac{{\alpha }_2}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\\ \le \mu +\frac{\delta }{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)+\frac{1}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\le \mu ,\end{array}$

which completes the proof.

Lemma 10. Let $\psi \left(\alpha \right)$ be defined as (22). Then, the eigenvalues of $\psi \left(\alpha \right)$ are nonnegative.

Proof. By using (14) and following the proof of (13), we obtain:

$\begin{array}{c}\psi \left(\alpha \right)=\tilde{x}\circ \tilde{s}+{\alpha }_1{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\alpha }_2{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}-{\alpha }_1\theta \left(\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}\right)\\ ={\displaystyle \sum }_{i=1}^r{\lambda }_i{c}_i+{\alpha }_1{\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right)c_i+{\displaystyle \sum }_{i=k+1}^r\left(\tau \mu -{\lambda }_i\right)c_i-{\alpha }_1\theta \left(\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}\right)\\ ={\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1\right){\lambda }_i+{\alpha }_1\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ -{\alpha }_1\theta \left(\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}\right)\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1\right){\lambda }_i+{\alpha }_1\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ -\frac{{\alpha }_1\theta }{4}{\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\right)}^2\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1\right){\lambda }_i+{\alpha }_1\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ -\frac{{\alpha }_1\theta }{4}{\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right)c_i\\ ={\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1-\frac{{\alpha }_1\theta }{4}\right){\lambda }_i+\left({\alpha }_1+\frac{{\alpha }_1\theta }{4}\right)\tau \mu \right)c_i\\ +{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\tau \mu c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i,\end{array}$ (24)

where the second inequality is due to the fact ${\lambda }_i-\tau \mu \ge 0$ , $i=1,\cdots ,k$ , and the last inequality follows from $\tau \mu -{\lambda }_i\ge 0$ , $i=k+1,\cdots ,r$ . Now, it is easy to see that the eigenvalues of $\psi \left(\alpha \right)$ are nonnegative, and the proof is complete.

Lemma 11. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/4$ . If ${\alpha }_1\ge \delta$ , then we have:

$\Vert {\left(\tau \mu \left(\alpha \right)e-\psi \left(\alpha \right)\right)}^{+}\Vert \le \left(1-{\alpha }_2\right)\left(\beta \tau \mu \left(\alpha \right)\right).$

Proof. From Lemma 9, we have $\frac{\mu \left(\alpha \right)}{\mu }\le 1$ . This, together with (24) and Lemma 10, gives

$\begin{array}{c}\tau \mu \left(\alpha \right)e-\psi \left(\alpha \right)=\frac{\mu \left(\alpha \right)}{\mu }{\displaystyle \sum }_{i=1}^r\left[\tau \mu -\frac{\mu }{\mu \left(\alpha \right)}{\lambda }_i\left(\psi \left(\alpha \right)\right)\right]c_i\\ \preccurlyeq \frac{\mu \left(\alpha \right)}{\mu }{\displaystyle \sum }_{i=1}^r\left[\tau \mu -{\lambda }_i\left(\psi \left(\alpha \right)\right)\right]c_i\\ \preccurlyeq \frac{\mu \left(\alpha \right)}{\mu }\left[{\displaystyle \sum }_{i=1}^k\left(\tau \mu -\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left(1-{\alpha }_2\right)\left(\tau \mu -{\lambda }_i\right)c_i\right]\\ =\frac{\mu \left(\alpha \right)}{\mu }{\displaystyle \sum }_{i=k+1}^r\left(1-{\alpha }_2\right)\left(\tau \mu -{\lambda }_i\right)c_i.\end{array}$ (25)

By using (25) and Lemma 3, we have:

$\begin{array}{c}{\Vert {\left(\tau \mu \left(\alpha \right)e-\psi \left(\alpha \right)\right)}^{+}\Vert }^2\le {\left(1-{\alpha }_2\right)}^2{\left(\frac{\mu \left(\alpha \right)}{\mu }\right)}^2{\Vert {\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert }^2\\ \le {\left(1-{\alpha }_2\right)}^2{\left(\beta \tau \mu \left(\alpha \right)\right)}^2,\end{array}$

which completes the proof.

The next lemma shows that $\left(\tilde{x}\left(\alpha \right),y\left(\alpha \right),\tilde{s}\left(\alpha \right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , for

${\alpha }_1\in \left[\delta ,\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\right].$

Lemma 12. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/4$ . If

${\alpha }_1\in \left[\delta ,\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\right],$

then we have $\left(\tilde{x}\left(\alpha \right),y\left(\alpha \right),\tilde{s}\left(\alpha \right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ .

Proof. It is easy to see

$Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)=-\left(1-\tau \right)Tr\left(\tilde{x}\circ \tilde{s}\right)-Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right).$ (26)

Using this fact and Lemma 4, we have:

$Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\ge -\left(1-\tau \right)Tr\left(\tilde{x}\circ \tilde{s}\right)-\sqrt{r}\beta \tau \mu \ge -Tr\left(\tilde{x}\circ \tilde{s}\right).$

Now, together with (11), we have:

$\mu \left(\alpha \right)\ge \left(1-{\alpha }_1\right)\mu \ge \left(1-\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\right)\mu \ge \frac{41}{50}\mu .$ (27)

On the other hand, using Lemmas 8 and 11, we have:

$\begin{array}{l}\Vert {\left(\tau \mu \left(\alpha \right)e-\tilde{x}\left(\alpha \right)\circ \tilde{s}\left(\alpha \right)\right)}^{+}\Vert \\ =\Vert {\left(\tau \mu \left(\alpha \right)e-\psi \left(\alpha \right)-\text{Δ}\tilde{x}\left(\alpha \right)\circ \text{Δ}\tilde{s}\left(\alpha \right)\right)}^{+}\Vert \\ \le \Vert {\left(\tau \mu \left(\alpha \right)e-\psi \left(\alpha \right)\right)}^{+}\Vert +\Vert {\left(-\text{Δ}\tilde{x}\left(\alpha \right)\circ \text{Δ}\tilde{s}\left(\alpha \right)\right)}^{+}\Vert \\ \le \left(1-{\alpha }_2\right)\beta \tau \mu \left(\alpha \right)+\frac{4}{5}{\alpha }_2\beta \tau \mu \\ \le \left(1-{\alpha }_2\right)\beta \tau \mu \left(\alpha \right)+\frac{4}{5}{\alpha }_2\beta \tau \left(\frac{50}{41}\mu \right)\le \beta \tau \mu \left(\alpha \right),\end{array}$

where the third inequality follows from (27). The proof is now complete.

The following lemma gives an upper bound for the duality gap, which plays an important role in the analysis of Algorithm 1.

Lemma 13. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/4$ . If ${\alpha }_1=\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ , then we have:

$\mu \left(\alpha \right)\le \left(1-\frac{2}{25}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\right)\mu .$

Proof. From (26), it is easy to see $Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\le -\left(1-\tau \right)Tr\left(\tilde{x}\circ \tilde{s}\right)$ . Together with (11), we obtain:

$\begin{array}{c}\tilde{\mu }\left(\alpha \right)\le \mu -{\alpha }_1\left(1-\tau \right)\mu +\frac{{\alpha }_2}{\sqrt{r}}\beta \tau \mu \\ \le \mu -\frac{3}{4}{\alpha }_1\mu +\frac{{\alpha }_2}{\sqrt{r}}\beta \tau \mu \\ \le \mu -\left(\frac{3}{4}-\frac{5}{3}\sqrt{\beta \tau }\right)\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\mu \\ \le \left(1-\frac{2}{25}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}\right)\mu ,\end{array}$ (28)

which completes the proof.

Using Lemma 13, the main result of Algorithm 4.1 is obtained as follows.

Theorem 14. If $\beta \le 1/3$ and $\tau \le 1/4$ , then the iteration complexity of Algorithm 1 is:

$\text{O}\left(\sqrt{r}\log {\epsilon }^{-1}\right).$

4.2. Second Algorithm and Its Convergence Analysis

Based on Algorithm 1, a new variant of Mehrotra-type predictor-corrector algorithm for SCO will be described. The predictor step will be the same as in Algorithm 1. The deficiency of Algorithm 1 is that $\text{Δ}{\tilde{x}}_{+}\circ \text{Δ}{\tilde{s}}_{+}$ is ignored in the corrector step. To remedy, we add the following system to the corrector step of Algorithm 1:

$\begin{array}{l}\tilde{\mathcal{A}}\Delta {\tilde{x}}_{+}^c=0,\\ {\tilde{\mathcal{A}}}^{*}\Delta y_{+}^c+\Delta {\tilde{s}}_{+}^c=0,\\ \tilde{s}\circ \Delta {\tilde{x}}_{+}^c+\tilde{x}\circ \Delta {\tilde{s}}_{+}^c=-\Delta {\tilde{x}}_{+}\circ \Delta {\tilde{s}}_{+}.\end{array}$ (29)

After deciding the step lengths $\overline{\alpha }=\left({\alpha }_1,{\alpha }_2,{\alpha }_3\right)\in {ℝ}_{+}^3$ , the iterates are updated as follows:

$\left(\tilde{x}\left(\overline{\alpha }\right),y\left(\overline{\alpha }\right),\tilde{s}\left(\overline{\alpha }\right)\right)=\left(\tilde{x},y,\tilde{s}\right)+\left(\Delta \tilde{x}\left(\overline{\alpha }\right),\Delta y\left(\overline{\alpha }\right),\Delta \tilde{s}\left(\overline{\alpha }\right)\right),$ (30)

where

$\begin{array}{c}\left(\Delta \tilde{x}\left(\overline{\alpha }\right),\Delta y\left(\overline{\alpha }\right),\Delta \tilde{s}\left(\overline{\alpha }\right)\right):={\alpha }_1\left(\left(\Delta {\tilde{x}}_{-},\Delta y_{-},\Delta {\tilde{s}}_{-}\right)+\left(\Delta {\tilde{x}}_{-}^c,\Delta y_{-}^c,\Delta {\tilde{s}}_{-}^c\right)\right)\\ +{\alpha }_2\left(\Delta {\tilde{x}}_{+},\Delta y_{+},\Delta {\tilde{s}}_{+}\right)+{\alpha }_3\left(\Delta {\tilde{x}}_{+}^c,\Delta y_{+}^c,\Delta {\tilde{s}}_{+}^c\right).\end{array}$

Since $Tr\left(\Delta \tilde{x}\left(\overline{\alpha }\right)\circ \Delta \tilde{s}(\overline{\alpha }\right)=0$ , we have:

$\mu \left(\overline{\alpha }\right)=\mu +\frac{{\alpha }_1}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)+\frac{{\alpha }_2}{r}Tr\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)=\mu \left(\alpha \right).$ (31)

In most interior point methods, the factors $\text{Δ}{\tilde{x}}_{-}\circ \text{Δ}{\tilde{s}}_{-}$ and $\text{Δ}{\tilde{x}}_{+}\circ \text{Δ}{\tilde{s}}_{+}$ are ignored; however, here we make use of these factors to reduce the duality gap faster.

Next, we describe the general framework of our second algorithm for the SCO problem.

Algorithm 2. The Mehrotra predictor-corrector method for solving the SCO problem (second method).

Inputs: Accuracy parameter $\epsilon >0$ ; neighborhood parameters $0<\beta \le 1/3$ and $0<\tau \le 1/4$ ; the initial point $\left(x^0,y^0,s^0\right)\in \mathcal{N}\left(\tau ,\beta \right)$ with ${\mu }^0=\langle x^0,s^0\rangle /r$ . Step 0: Set $k:=0$ . Step 1: If $\langle x^k,s^k\rangle \le \epsilon$ then stop. Step 2: Choose a Nesterov-Todd scaling element $u$ . Step 3: Compute the directions $\left(\text{Δ}{\tilde{x}}_{-},\text{Δ}{y}_{-},\text{Δ}{\tilde{s}}_{-}\right)$ by solving (6) and $\left(\text{Δ}{\tilde{x}}_{+},\text{Δ}{y}_{+},\text{Δ}{\tilde{s}}_{+}\right)$ by solving (7). Step 4: Find the maximum feasible step length $\theta$ by (8). Step 5: Compute the directions $\left(\text{Δ}{\tilde{x}}_{-}^c,\text{Δ}{y}_{-}^c,\text{Δ}{\tilde{s}}_{-}^c\right)$ by solving (9) and $\left(\text{Δ}{\tilde{x}}_{+}^c,\text{Δ}{y}_{+}^c,\text{Δ}{\tilde{s}}_{+}^c\right)$ by solving (29). Step 6: Find the step lengths $\overline{\alpha }=\left({\alpha }_1,{\alpha }_2,{\alpha }_3\right)$ giving a sufficient reduction of the duality gap and assuring $\left(\tilde{x}\left(\overline{\alpha }\right),y\left(\overline{\alpha }\right),\tilde{s}\left(\overline{\alpha }\right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ . Step 7: Let ${\overline{\alpha }}^k:=\overline{\alpha }$ , $\left({\tilde{x}}^{k+1},y^{k+1},{\tilde{s}}^{k+1}\right):=\left(\tilde{x}\left({\overline{\alpha }}^k\right),y\left({\overline{\alpha }}^k\right),\tilde{s}\left({\overline{\alpha }}^k\right)\right)$ and ${\mu }^{k+1}:=\langle x^{k+1},s^{k+1}\rangle /r$ . Step 8: Set $k:=k+1$ and go to Step 1.

We now proceed to show the complexity of Algorithm 2. Since the proof techniques are the same as in Algorithm 1, we only give a brief outline of the proofs and omit the details.

Lemma 15. Let $\left(\Delta {\tilde{x}}_{+},\Delta y_{+},\Delta {\tilde{s}}_{+}\right)$ be the solution of (7) and $\beta \le 1/3$ . Then, we have:

$\Vert {\alpha }_{3}L{\left(v\right)}^{-1}\left(\text{Δ}{\tilde{x}}_{+}\circ \text{Δ}{\tilde{s}}_{+}\right)\Vert \le \frac{{\alpha }_3}{8}\sqrt{\beta \tau \mu }.$

Proof. Multiplying the third equation of (7) by $L{\left(v\right)}^{-1}$ , by Lemmas 1 and 7, we have:

$\begin{array}{c}\Vert {\alpha }_3\left(\text{Δ}{\tilde{x}}_{+}\circ \text{Δ}{\tilde{s}}_{+}\right)\Vert \le \frac{{\alpha }_3}{\sqrt{8}}{\Vert L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\Vert }^2\\ \le \frac{1}{2\sqrt{8}}{\alpha }_3\beta \tau \mu .\end{array}$ (32)

Similar to the proof of Lemma 2 of [13] and by (32), we have:

$\Vert {\alpha }_{3}L{\left(v\right)}^{-1}\left(\text{Δ}{\tilde{x}}_{+}\circ \text{Δ}{\tilde{s}}_{+}\right)\Vert \le \frac{{\alpha }_3}{8}\sqrt{\beta \tau \mu },$

which completes the proof.

Similar to Lemma 8 and by Lemma 15, we give the following lemma, which gives a bound on $\Vert \text{Δ}\tilde{x}\left(\overline{\alpha }\right)\circ \text{Δ}\tilde{s}\left(\overline{\alpha }\right)\Vert$.

Lemma 16. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/24$ . If

${\alpha }_3\le {\alpha }_1\le \frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ , then we have:

$\Vert \text{Δ}\tilde{x}\left(\overline{\alpha }\right)\circ \text{Δ}\tilde{s}\left(\overline{\alpha }\right)\Vert \le \frac{4}{5}{\alpha }_2\beta \tau \mu .$

Now, for simplicity, we use the following notation:

$\begin{array}{l}h\left(\overline{\alpha }\right):=\tilde{x}\circ \tilde{s}+{\alpha }_1{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}+{\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\\ -{\alpha }_1\theta \left(\Delta {\tilde{x}}_{-}\circ \Delta {\tilde{s}}_{-}\right)-{\alpha }_3\left(\Delta {\tilde{x}}_{+}\circ \Delta {\tilde{s}}_{+}\right).\end{array}$ (33)

Lemma 17. Let $h\left(\overline{\alpha }\right)$ be defined as (33) and ${\alpha }_3\le \frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ . Then, the eigenvalues of $h\left(\overline{\alpha }\right)$ are nonnegative.

Proof. Since $\Delta {\tilde{x}}_{+}\circ \Delta {\tilde{s}}_{+}=\frac{1}{4}\left({\left(\Delta {\tilde{x}}_{+}+\Delta {\tilde{s}}_{+}\right)}^2-{\left(\Delta {\tilde{x}}_{+}-\Delta {\tilde{s}}_{+}\right)}^2\right)$ , we have:

$\begin{array}{c}\Delta {\tilde{x}}_{+}\circ \Delta {\tilde{s}}_{+}=\frac{1}{4}\left({\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\right)}^2-{\left(\Delta {\tilde{x}}_{+}-\Delta {\tilde{s}}_{+}\right)}^2\right)\\ \preccurlyeq \frac{1}{4}{\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\right)}^2.\end{array}$ (34)

Using (34), Lemma 16 and similar arguments as in the proof of Lemma 10, we obtain:

$\begin{array}{c}h\left(\overline{\alpha }\right)\succcurlyeq {\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1\right){\lambda }_i+{\alpha }_1\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ -\frac{{\alpha }_1\theta }{4}{\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{-}\right)\right)}^2-\frac{{\alpha }_3\theta }{4}{\left(L{\left(v\right)}^{-1}\left({\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\right)\right)}^2\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1\right){\lambda }_i+{\alpha }_1\tau \mu \right)c_i+{\displaystyle \sum }_{i=k+1}^r\left({\lambda }_i+{\alpha }_2\left(\tau \mu -{\lambda }_i\right)\right)c_i\\ -\frac{{\alpha }_1\theta }{4}{\displaystyle \sum }_{i=1}^k\left(\tau \mu -{\lambda }_i\right)c_i-\frac{{\alpha }_3}{4}{\displaystyle \sum }_{i=k+1}^r\frac{{\left(\tau \mu -{\lambda }_i\right)}^2}{{\lambda }_i}{c}_i\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\left(\left(1-{\alpha }_1-\frac{{\alpha }_1\theta }{4}\right){\lambda }_i+\left({\alpha }_1+\frac{{\alpha }_1\theta }{4}\right)\tau \mu \right)c_i\\ +{\displaystyle \sum }_{i=k+1}^r\left(\left(1-{\alpha }_2\right){\lambda }_i+\left({\alpha }_2-\frac{{\alpha }_3}{8}\beta \right)\tau \mu \right)c_i\\ \succcurlyeq {\displaystyle \sum }_{i=1}^k\tau \mu c_i+{\displaystyle \sum }_{i=k+1}^r\left(\left(1-{\alpha }_2\right){\lambda }_i+\left({\alpha }_2-\frac{{\alpha }_3}{8}\beta \right)\tau \mu \right)c_i\succcurlyeq 0,\end{array}$ (35)

where the third inequality follows from Lemma 3, the fourth inequality follows from the fact that ${\lambda }_i-\tau \mu \ge 0$ , $i=1,\cdots ,k$ , and the last inequality follows from $\delta \le {\alpha }_3\le \frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ . Therefore, we conclude that the eigenvalues of $h\left(\alpha \right)$ are nonnegative, and this completes the proof.

Lemma 18. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/4$ . If

$\delta \le {\alpha }_3\le {\alpha }_1=\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ , then we have:

$\Vert {\left(\tau \mu \left(\overline{\alpha }\right)e-h\left(\overline{\alpha }\right)\right)}^{+}\Vert =\left(1-{\alpha }_2\right)\beta \tau \mu .$

Proof. If ${\alpha }_1\ge \delta$ , then from (31) and Lemma 9, we have $\mu \left(\overline{\alpha }\right)\le \mu$ . Therefore, by (35), (28), Lemmas 2 and 17, we obtain:

$\begin{array}{l}\Vert {\left(\tau \mu \left(\overline{\alpha }\right)e-h\left(\overline{\alpha }\right)\right)}^{+}\Vert \\ \le \Vert {\left({\displaystyle \sum }_{i=1}^k\left(\mu \left(\overline{\alpha }\right)-\mu \right)\tau c_i\right)}^{+}\Vert \\ +\Vert {\left({\displaystyle \sum }_{i=k+1}^r\left[\left({\alpha }_2-1\right){\lambda }_i+\left(\mu \left(\overline{\alpha }\right)-{\alpha }_2\mu +\frac{{\alpha }_3}{8}\beta \mu \right)\tau \right]c_i\right)}^{+}\Vert \\ \le \Vert {\left({\displaystyle \sum }_{i=k+1}^r\left[\left({\alpha }_2-1\right){\lambda }_i+\left(\mu -{\alpha }_1\left(1-\tau \right)\mu +\frac{{\alpha }_2}{\sqrt{r}}\beta \tau \mu -{\alpha }_2\mu +\frac{{\alpha }_3}{8}\beta \mu \right)\tau \right]c_i\right)}^{+}\Vert \\ \le \Vert {\left({\displaystyle \sum }_{i=k+1}^r\left[\left(1-{\alpha }_2\right)\left(\tau \mu -{\lambda }_i\right)+\left(-1+\tau +\frac{5}{3}\sqrt{\beta \tau }+\frac{\beta }{8}\right){\alpha }_1\tau \mu \right]c_i\right)}^{+}\Vert \\ \le \Vert {\left({\displaystyle \sum }_{i=k+1}^r\left[\left(1-{\alpha }_2\right)\left(\tau \mu -{\lambda }_i\right)\right]c_i\right)}^{+}\Vert \\ ={\Vert \left(1-{\alpha }_2\right){\left(\tau \mu e-\tilde{x}\circ \tilde{s}\right)}^{+}\Vert }^2\le \left(1-{\alpha }_2\right)\beta \tau \mu ,\end{array}$

where the fourth inequality follows from the fact that ${\alpha }_3\le {\alpha }_1=\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ and the last inequality follows from Lemma 3. The proof of lemma is now complete.

Lemma 19. Let $\left(\tilde{x},y,\tilde{s}\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , $\beta \le 1/3$ and $\tau \le 1/4$ . If

$\delta \le {\alpha }_3\le {\alpha }_1=\frac{3}{5}{\alpha }_2\sqrt{\frac{\beta \tau }{r}}$ , then $\left(\tilde{x}\left(\overline{\alpha }\right),y\left(\overline{\alpha }\right),\tilde{s}\left(\overline{\alpha }\right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ .

Proof. From Lemmas 2, 16 and 18, we have:

$\begin{array}{l}\Vert {\left(\tau \mu \left(\overline{\alpha }\right)e-\tilde{x}\left(\overline{\alpha }\right)\circ \tilde{s}\left(\overline{\alpha }\right)\right)}^{+}\Vert \\ =\Vert {\left(\tau \mu \left(\overline{\alpha }\right)e-h\left(\overline{\alpha }\right)-\Delta \tilde{x}\left(\overline{\alpha }\right)\circ \Delta \tilde{s}\left(\overline{\alpha }\right)\right)}^{+}\Vert \\ \le \Vert {\left(\tau \mu \left(\overline{\alpha }\right)e-h\left(\overline{\alpha }\right)\right)}^{+}+{\left(-\Delta \tilde{x}\left(\overline{\alpha }\right)\circ \Delta \tilde{s}\left(\overline{\alpha }\right)\right)}^{+}\Vert \\ \le \left(1-{\alpha }_2\right)\beta \tau \mu +\frac{4}{5}{\alpha }_2\beta \tau \mu =\left(1-{\alpha }_1\right)\beta \tau \mu +\left({\alpha }_1-{\alpha }_2+\frac{4}{5}{\alpha }_2\right)\beta \tau \mu \\ \le \left(1-{\alpha }_1\right)\beta \tau \mu +\left(\frac{3}{5}\sqrt{\frac{\beta \tau }{r}}-1+\frac{4}{5}\right){\alpha }_2\beta \tau \mu \le \left(1-{\alpha }_1\right)\beta \tau \mu \le \beta \tau \mu \left(\overline{\alpha }\right),\end{array}$

where the last inequality follows from (27). This implies $\left(\tilde{x}\left(\overline{\alpha }\right),y\left(\overline{\alpha }\right),\tilde{s}\left(\overline{\alpha }\right)\right)\in \mathcal{N}\left(\tau ,\beta \right)$ , which completes the proof.

Now, using Lemma 13, since $\mu \left(\overline{\alpha }\right)=\mu \left(\alpha \right)$ , we are led to the following iteration complexity of Algorithm 2.

Theorem 20. If $\beta \le 1/3$ and $\tau \le 1/4$ , then the iteration complexity of Algorithm 2 is:

$\text{O}\left(\sqrt{r}\log {\epsilon }^{-1}\right).$

5. Numerical Testing

Here we compare our two proposed algorithms (Alg. 1 and Alg. 2) with Algorithm 3 (Alg. 3) of [9] and Algorithm 4 (Alg. 4) of [5], using MATLAB R2017b on an Intel Core i7 (2.20 GHz) with 8 GB RAM. We also solve the numerical examples with SeDuMi [22] and display the results. In order to test the algorithms, we use some SDO problems of [23]. These test problems are random semidefinite programming problems (Table 1 and Table 2), educational testing problems (Table 3 and Table 4), norm minimization problems (Table 5 and Table 6) and max-cut problems (Table 7 and Table 8). The parameters were set to be $\epsilon ={10}^{-8}$ , $\beta =1/3$ and $\tau =1/4$ .

In Tables 1-8, we list the number of the constraints (m), the dimension of the blocks (n) and the obtained average number of iterations and the average CPU time in seconds. In each instance, we run the algorithm ten times for the same m and n and the average results are shown in the tables.

Table 1. Average number of iterations on Random problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
30	30	0.11	0.20	0.20	0.85	2.07
40	45	0.19	0.77	0.83	1.26	5.51
50	50	0.16	1.09	0.97	2.83	6.16
70	80	0.57	2.93	3.04	4.07	11.48
100	100	1.16	4.39	4.84	9.82	25.58

Table 2. Average CPU times on Random problems.

m	n	SeDuMi	Alg. 1	Alg.2	Alg. 3	Alg. 4
30	30	13.0	13.4	13.3	14.8	18.4
40	45	12.8	13.5	13.0	15.4	23.0
50	50	13.5	14.8	14.6	16.1	25.1
70	80	13.9	17.1	16.7	22.5	27.8
100	100	14.8	21.3	19.6	28.4	34.2

Table 3. Average number of iterations on educational test problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
5	10	12.7	14.8	14.1	15.9	22.2
20	40	14.6	35.5	34.6	38.1	46.3
25	50	19.0	46.7	46.5	52.4	72.6
40	80	23.8	63.1	60.8	86.2	95.3
50	100	22.6	70.8	68.4	112.5	118.0

Table 4. Average CPU times on educational test problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
5	10	0.03	0.74	0.83	1.72	2.83
20	40	0.15	3.39	3.86	4.75	15.18
25	50	0.30	6.41	6.84	10.63	36.07
40	80	0.50	12.70	11.53	18.24	44.62
50	100	0.64	18.26	18.69	30.73	58.22

Table 5. Average number of iterations on norm minimization problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
30	30	13.5	12.7	12.7	13.1	15.6
30	40	13.7	13.5	12.8	17.1	23.7
50	50	12.6	14.2	13.8	19.5	27.3
80	90	13.6	19.3	18.8	24.6	41.3
100	100	14.2	23.4	23.4	48.3	53.6

Table 6. Average CPU times on norm minimization problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
30	30	0.65	0.11	0.39	1.37	2.34
30	40	0.33	0.19	0.55	2.13	5.19
50	50	0.45	0.26	0.79	4.06	6.22
80	90	0.99	1.62	1.55	4.77	7.19
100	100	1.37	3.52	3.48	6.56	9.62

Table 7. Average number of iterations on Max-Cut problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
30	30	12.4	13.3	12.8	14.1	18.1
45	45	13.5	14.3	13.5	15.8	22.4
50	50	12.7	14.7	14.6	16.1	25.8
80	80	12.6	18.8	18.6	27.5	44.1
100	100	13.4	22.6	20.6	31.7	44.9

Table 8. Average CPU times on Max-Cut problems.

m	n	SeDuMi	Alg. 1	Alg. 2	Alg. 3	Alg. 4
30	30	0.80	0.22	0.31	0.52	1.83
45	45	0.33	0.71	0.90	1.63	5.03
50	50	0.35	0.93	1.36	2.76	6.84
80	80	0.50	1.84	1.86	3.32	8.63
100	100	0.44	3.62	3.47	4.16	8.84

Based on the numerical results, as summarized in the tables, our proposed algorithms show to be more efficient and promise to be encouraging. It can be observed that the average number of iterations needed for Algorithm 2 mostly turns to be less than the ones obtained by the other algorithms, while most often the average CPU time of Algorithm 1 is slightly better than the one obtained by Algorithm 2.

6. Concluding Remarks

We modified the Ai-Zhang primal-dual path-following interior-point method to gain two classes of Mehrotra-type predictor-corrector algorithms for SCO. The Euclidean Jordan algebra was a basic tool in our analysis. We showed that the use of the corrector steps did not cause any loss in the worst-case complexity of the algorithms. Based on the NT direction, our proposed algorithms had an $\text{O}\left(\sqrt{r}\log {\epsilon }^{-1}\right)$ iteration complexity bound, as the best complexity results available for SCO so far. Numerical experiments showed encouraging evidence for practical efficiency of the proposed algorithms.

Acknowledgements

The first author would like to thank Shahrekord University for financial support. The research of the first author was also partially supported by the Center of Excellence for Mathematics, University of Shahrekord, Shahrekord, Iran. The second author thanks Research Council of Sharif University of Technology for financial support.

Funding

The research of the first author was in part supported by a grant from Shahrekord University (No. 404GRD1M2025).