A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

Abstract

In this paper, we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems. Using the Nesterov–Todd direction as the search direction, we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm. Although the algorithm belongs to the class of large-step interior-point algorithms, its complexity coincides with the best iteration bound for short-step interior-point algorithms. The algorithm is also implemented to demonstrate that it is efficient.

1 Introduction

Let ${{\mathcal {S}}}^n$ be the vector space of all $n\times n$ real symmetric matrices endowed with the inner product $M \cdot N=\text {Tr}(MN)$ and ${{\mathcal {S}}}_{+}^n \left({\mathcal {S}}_{++}^n\right)$ be the cone of positive semidefinite (positive definite) matrices in ${\mathcal {S}}^n$. Consider the primal problem of convex quadratic optimization (CQO) over ${\mathcal {S}}_{+}^n$, denoted by CQSDO, in the standard form

and its Lagrangian dual problem

$$\begin{aligned}&\mathrm{(D)}\quad \max \quad b^\mathrm{T}y-\frac{1}{2}X\cdot {\mathcal {Q}}(X),\\&\sum _{i=1}^{m}y_{i}A_{i}-{\mathcal {Q}}(X)+S= C,\\&S\succeq 0, \end{aligned}$$

where $C\in {\mathcal {S}}^n$ and $b\in \mathbb {R}^{m}$ are given data, the notation $''\succeq ''$ denotes the positive semidefinite (positive definite) matrices, $A_{i}\in {\mathcal {S}}^n$ are linearly independent matrices and ${\mathcal {Q}}:{\mathcal {S}}^n\longrightarrow {\mathcal {S}}^n$ is a self-adjoint positive semidefinite linear operator on ${\mathcal {S}}^n$, i.e., for any $M,N\in {\mathcal {S}}^n$, ${\mathcal {Q}}(M)\cdot N=M\cdot {\mathcal {Q}}(N)$ and ${\mathcal {Q}}(M)\cdot M\geqslant 0$.

The CQSDO problems are the general state of semidefinite optimization (SDO) problems. In fact these problems can be reduced to SDO problems if ${\mathcal {Q}}(X)=0$. Additionally, they can also be reformulated as the semidefinite linear complementarity problems (SDLCPs). After the landmark paper of Karmarkar [1], interior-point methods (IPMs) have shown their powers and efficiency in solving the linear optimization (LO) problems and various classes of other mathematical programming such as complementarity problems (CPs), second-order cone optimization (SOCO) problems, SDO problems and CQSDO problems.

In last decade, some primal-dual IPMs for LO have been successfully extended to other optimization problems, especially CQSDO problems. Nie and Yuan [2] presented a potential reduction algorithm for solving CQSDO problems. They also designed a predictor-corrector IPM for CQSDO problems with $O(\sqrt{n} L)$ complexity bound. Toh [3] proposed an inexact primal-dual Mehrotra-type predictor-corrector (MPC) algorithm for CQSDO problems. Xiao et al. [4] suggested a smoothing Newton method for a type of inverse semidefinite quadratic optimization problems and proved the quadratic convergence of their method. Achache and Guerra [5] presented a primal-dual path-following interior-point algorithm for solving CQSDO problems using the Nesterov–Todd (NT) search direction and proved the complexity $O(\sqrt{n} L)$ for their algorithm.

Ai and Zhang [6], using the newly defined wide neighborhood of the central path in [7] proposed an interior-point algorithm for monotone linear complementarity problems (MLCPs) and proved the convergence analysis of their algorithm. After that, Li and Terlaky [8] extend the Ai–Zhang schem to SDO problems and proposed an interior-point algorithm with the same complexity as the best theoretical complexity bound for small-update methods. Analogously, Liu et al. [9] extended the wide neighborhood given by Ai and Zhang [6] to symmetric cone optimization (SCO) problems and suggested an infeasible interior-point algorithm with the same theoretical complexity bound as the best short-step path-following interior-point algorithms.

Recently, Liu et al. [10] proposed an MPC interior-point algorithm for SCO problems. Their algorithm is based on a new one-norm wide neighborhood, which is an even wider neighborhood than a negative infinity neighborhood. Liu et al. [11] used the one-norm wide neighborhood defined in [10] and presented an infeasible interior-point algorithm for SCO problems.

Motivated by Liu et al. [10, 11], we present a wide neighborhood feasible interior-point algorithm for CQSDO problems. We prove that its complexity coincides with the best theoretical iteration bound for CQSDO problems by small-update methods.

The paper is organized as follows: In Sect. 2, we recall the background and the basic concepts of Euclidean Jordan algebra ${\mathcal {S}}^n$. Section 3 introduces the basic idea of IPMs for solving CQSDO problems and describes the feasible wide neighborhood interior-point algorithm in more details. Section 4 is the important part of paper. In fact, it contains some lemmas which indicate how we choose the step size $\alpha$ in our algorithm. The complexity of algorithm is given in Sect. 4.1. In Sect. 5, we test the proposed algorithm for CQSDO problems with some numerical examples. Finally, the paper ends with some conclusions in Sect. 6.

2 Preliminaries

In this section, we briefly review and introduce Jordan algebra ${\mathcal {S}}^n$ as well as some of its basic properties. The Euclidean Jordan algebra ${\mathcal {S}}^n$ is an n-dimensional vector space over the field of $n\times n$ real symmetric matrices with the identity element I, symmetrized multiplication

$$\begin{aligned} X\circ S=\frac{XS+SX}{2} \end{aligned}$$

(2.1)

and the inner product $\langle X,S\rangle =X \cdot S={Tr}(X\circ S)={Tr}(X S)$. The space of positive semidefinite matrices denoted by $S_{+}^n$ is called the symmetric cone of squares of ${\mathcal {S}}^n$, while $S_{++}^n$ denotes the space of positive definite matrices. Let $A\in \mathbb {R}^{n\times n}$, the Lyapunov operator $L_{A}:{\mathcal {S}}^n\rightarrow {\mathcal {S}}^n$ defines as $L_{A}(X):=AX+XA^\mathrm{T},$ while the Lyapunov-like operator $\tilde{L}_{A}:{\mathcal {S}}^n\rightarrow {\mathcal {S}}^n$ defines as follows:

$$\begin{aligned} \tilde{L}_{A}:=\frac{1}{2}\left(AX+XA^\mathrm{T}\right). \end{aligned}$$

(2.2)

The operator $\tilde{L}_{A}$ is symmetric with respect to $\langle \cdot ,\cdot \rangle$, that is, for any matrix $X,S\in {\mathcal {S}}^n$, $\langle \tilde{L}_{A}(X), S\rangle =\langle X,\tilde{L}_{A}(S)\rangle$. Let $M=Q\varLambda (M)Q^\mathrm{T}$ be the eigenvalue decomposition of $M\in {\mathcal {S}}^n$, where $\varLambda (M)$ is the diagonal matrix of eigenvalues of the matrix M and Q is an orthonormal matrix, i.e., $QQ^\mathrm{T}=I$. We define $M^+$ and $M^-$ as the positive and negative parts of M as

$$\begin{aligned} M^+:=\sum _{{\lambda }_{i}\geqslant 0}{\lambda }_{i}q_{i}q_{i}^\mathrm{T}, \quad M^-:=\sum _{{\lambda }_{i}\leqslant 0}{\lambda }_{i}q_{i}q_{i}^\mathrm{T}, \end{aligned}$$

where $\lambda _{i}$ is the ith eigenvalue of the matrix M, and each column $q_i$ of Q is an eigenvector of M corresponding to the eigenvalue ${\lambda }_{i}$. For any $M\in {\mathcal {S}}^n$, the norm induced by the inner product $\langle \cdot ,\cdot \rangle$ is named as the Frobenius norm, which is given by

$$\begin{aligned} \left\Vert M \right\Vert _{F}:=\sqrt{{\sum _{i=1}^{n}\sigma ^{2}_{i}(M)}}= \sqrt{{\sum _{i=1}^{n}\lambda ^{2}_{i}(M)}}, \end{aligned}$$

where $\sigma _{i}(M)$ is the ith singular value of the symmetric matrix M. The other norms such as Schatten 1-norm and 2-norm are defined as follows:

$$\begin{aligned} \left\Vert M \right\Vert _{1}:=\sum _{i=1}^{n}\sigma _{i}(M)=\sum _{i=1}^{n}|\lambda _{i}(M)|, \quad \left\Vert M \right\Vert _{2}:=\max _{i}{\sigma _{i}(M)}=\max _{i}{|\lambda _{i}(M)|}. \end{aligned}$$

For a given $n\times n$ real matrix V and a given nonsingular matrix P, a symmetrization transformation defines as

$$\begin{aligned} H_{P}(V):=\frac{1}{2}\Big [PVP^{-1}+\left(PVP^{-1}\right)^\mathrm{T}\Big ]. \end{aligned}$$

(2.3)

In particular, if $P=I$, then for any symmetric matrix M, $H_{I}(M)=H(M)=M$. Here, we list some results which are required in our analysis.

Lemma 2.1

(Lemma 2.1 in [12]) Let $M, N\in {\mathcal {S}}^n$. Then, $\left\Vert \left(M+N\right)^+ \right\Vert _{1}\leqslant \left\Vert M^+ \right\Vert _{1}+\left\Vert N^+ \right\Vert _{1}$.

Lemma 2.2

(Lemma 2.3 in [12]) Let $P\in \mathbb {R}^{n\times n}$ be a nonsingular matrix. Then, for any $M\in {\mathcal {S}}^n$

$$\begin{aligned} \left\Vert M^+ \right\Vert _{1}\leqslant \left\Vert \left(H_{P}(M)\right)^+ \right\Vert _{1}. \end{aligned}$$

The following two lemmas will be used in the proof of the basic Lemma 2.5. For proof and more details, we refer the readers to Corollary 3.4.3 and Theorem 3.3.14 in [13].

Lemma 2.3

Let $A,B\in \mathbb {R}^{m\times n}$ have respective ordered singular values $\sigma _{1}(A)\geqslant \sigma _{2}(A)\geqslant \cdots \geqslant \sigma _{q}(A)\geqslant 0$, $\sigma _{1}(B)\geqslant \sigma _{2}(B)\geqslant \cdots \geqslant \sigma _{q}(B)\geqslant 0$, $q\equiv \min \{m,n\}$ and $\sigma _{1}(A+B)\geqslant \sigma _{2}(A+B)\geqslant \cdots \geqslant \sigma _{q}(A+B)\geqslant 0$ be the ordered singular values of $A+B$. Then,

$$\begin{aligned} \sum _{i=1}^{k}\sigma _{i}(A+B)\leqslant \sum _{i=1}^{k}\sigma _{i}(A)+\sum _{i=1}^{k}\sigma _{i}(B), \quad k=1,2,\cdots ,q. \end{aligned}$$

Lemma 2.4

Let $A\in \mathbb {R}^{n\times p}$ and $B\in \mathbb {R}^{p\times m}$ be given, let $q\equiv \min \{m,n,p\}$ and denote the ordered singular values of A, B and AB by $\sigma _{1}(A)\geqslant \sigma _{2}(A)\geqslant \cdots \geqslant \sigma _{\min \{n,p\}}(A)\geqslant 0$, $\sigma _{1}(B)\geqslant \sigma _{2}(B)\geqslant \cdots \geqslant \sigma _{\min \{m,p\}}(B)\geqslant 0$ and $\sigma _{1}(AB)\geqslant \sigma _{2}(AB)\geqslant \cdots \geqslant \sigma _{\min \{m,n\}}(AB)\geqslant 0$. Then,

$$\begin{aligned} \sum _{i=1}^{k}\sigma _{i}(AB)\leqslant \sum _{i=1}^{k}\sigma _{i}(A)\sigma _{i}(B), \quad k=1,2,\cdots ,q. \end{aligned}$$

The following lemma plays an important role in our analysis.

Lemma 2.5

Let $M,N\in {\mathcal {S}}^n$, then $\left\Vert M\circ N \right\Vert _{1}\leqslant \left\Vert M \right\Vert _{F}\left\Vert N \right\Vert _{F}$.

Proof

Due to (2.1), Lemmas 2.3 and 2.4, we have

$$\begin{aligned} \left\Vert M\circ N \right\Vert _{1}= & {} \frac{1}{2}\sum _{i=1}^{n}\sigma _{i}\left(MN+NM\right)\leqslant \frac{1}{2}\Big [\sum _{i=1}^{n}\sigma _{i}\left(MN\right)+\sum _{i=1}^{n}\sigma _{i}\left(NM\right)\Big ]\\ {}\leqslant & {} \sum _{i=1}^{n}\sigma _{i}(M)\sigma _{i}(N)\leqslant \Big [\sum _{i=1}^{n}{\sigma ^{2}_{i}(M)}\sum _{i=1}^{n}{\sigma ^{2}_{i}(N)}\Big ]^\frac{1}{2}=\left\Vert M \right\Vert _{F}\left\Vert N \right\Vert _{F}, \end{aligned}$$

which follows the desired result.

3 Interior-Point Algorithm for CQSDO Problems

In this section, we introduce the Schatten 1-norm wide neighborhood ${\mathcal {N}}_{1}(\tau ,\beta )$ and then we propose a feasible interior-point algorithm for CQSDO problems based on the wide neighborhood ${\mathcal {N}}_{1}(\tau ,\beta )$. For convenience of reference, we consider the feasibility and strictly feasibility sets of $(\mathrm{P})$ and $(\mathrm{D})$, respectively, as follows:

$$\begin{aligned} \mathcal {F}:= & {} \{(X,y,S):\, A_{i} \cdot X=b_{i},\,\,\, \sum _{i=1}^{m}y_{i}A_{i}-{\mathcal {Q}}(X)+S= C, \quad X,S\succeq 0 \},\\ \mathcal {F}^{0}:= & {} \{(X,y,S)\in \mathcal {F}: \quad X,S\succ 0 \}. \end{aligned}$$

We assume that the primal and dual problems $(\mathrm{P})$ and $(\mathrm{D})$ satisfy the interior-point condition (IPC). That is, $\mathcal {F}^{0}\ne \emptyset$. It is well known that under the IPC, finding an $\varepsilon$-approximate optimal solution of the primal and dual problems $(\mathrm{P})$ and $(\mathrm{D})$ is equivalent to solve the perturbed Karush-Kuhn-Tucker optimality conditions.

$$\begin{aligned} A_{i}\cdot X=b_{i},~~\sum _{i=1}^{m}y_{i}A_{i}-{\mathcal {Q}}(X)+S= C,~~ XS=\tau \mu I, ~~ X,S\succeq 0, \end{aligned}$$

(3.1)

where $\tau >0$ is the target parameter, $\mu :=\frac{X\cdot S}{n}$ is the normalized duality gap corresponding to (X, y, S) and the last equality is called the perturbed complementarity equation. Since the left-hand side of system (3.1) is a map from $S^{n}\times \mathbb {R}^{m}\times S^{n}$ to $\mathbb {R}^{n\times n}\times \mathbb {R}^{m}\times S^{n}$, this system is not square when X and S are restricted to $S^{n}$. Various remedies have been proposed since the middle of 1990s. A remedy is to use the so-called similar symmetrization operator $H_{P}:\mathbb {R}^{n\times n}\longrightarrow S^n$ introduced by Zhang [14] who suggested to replace the perturbed equation $XS=\tau \mu I$ by $H_{P}(XS)=\tau \mu I$ where $H_{P}(\cdot )$ is defined as (2.3). Thus, system (3.1) can be rewritten in equivalent form as follows:

$$\begin{aligned}&A_{i}\cdot X=b_{i},~~~ i=1,2,\cdots ,m,\nonumber \\&\sum _{i=1}^{m} y_{i}A_{i}-{\mathcal {Q}}(X)+S=C,\nonumber \\&H_{P}(XS)=\tau \mu I. \end{aligned}$$

(3.2)

The above system has a unique solution for any $\mu ,\tau >0$, the scaling matrix P which satisfies $PXSP^{-1}\in S^{n}$ and $X,S\succ 0$. This solution is denoted by $(X(\mu ),y(\mu ),S(\mu ))$ and is called the $\mu$-center of the problems (P) and (D). The set of all $\mu$-centers construct a guide curve in $\mathcal {F}^{0}$ so-called the central path. If $\mu \rightarrow 0$, then the limit of the central path exists and since the limit point satisfies the complementarity condition, it yields an $\varepsilon$-optimal solution of (P) and (D). To solve system (3.2), we use the perturbed Newton method which leads to the following linear system of equations for search direction $\left(\varDelta X,\varDelta y,\varDelta S\right)\in S^{n}\times \mathbb {R}^{m}\times S^{n}$:

$$\begin{aligned}&A_{i}\cdot \varDelta X=0,~~~ i=1,2,\cdots ,m, \nonumber \\&\sum _{i=1}^{m} \varDelta y_{i}A_{i}-{\mathcal {Q}}(\varDelta X)+\varDelta S=0,\nonumber \\&H_{P}(X\varDelta S+\varDelta X S)=\tau \mu I-H_{P}(XS). \end{aligned}$$

(3.3)

Different choices have been proposed for the nonsingular matrix P. For instance, Kojima et al. [15] used $P:=X^{-\frac{1}{2}}$ while Alizadeh et al. [16] and Monteiro [17], respectively, selected $P=I$ and $P=S^{\frac{1}{2}}$ as the scaling matrices. However, in our analysis, defining

$$\begin{aligned} W:=X^{\frac{1}{2}}\left(X^{\frac{1}{2}}SX^{\frac{1}{2}}\right)^{-\frac{1}{2}}X^{ \frac{1}{2}}=S^{-\frac{1}{2}}\left(S^{\frac{1}{2}}XS^{\frac{1}{2}}\right)^{ \frac{1}{2}}S^{-\frac{1}{2}}, \end{aligned}$$

(3.4)

we use the scaling matrix $P=W^{\frac{1}{2}}$ which was first introduced by Nesterov and Todd [18]. According to this choice, it is easy to check that $PXSP^{-1}\in S^n$ and $PXP=P^{-1}SP^{-1}$ [17].

Defining

$$\begin{aligned} \varDelta \hat{X}:=P\varDelta X P, ~~~\varDelta \hat{S}:=P^{-1}\varDelta SP^{-1}, \end{aligned}$$

(3.5)

and

$$\begin{aligned} \begin{array}{lll} \hat{X}:=PXP, \hat{S}:=P^{-1}SP^{-1},~~\hat{A}_{i}:=P^{-1}A_{i}P^{-1},\\ \hat{{\mathcal {Q}}}(\varDelta \hat{X}):=P^{-1}{\mathcal {Q}}(\varDelta {X})P^{-1}=P^{-1} {\mathcal {Q}}(P^{-1}{\varDelta {\hat{X}}}P^{-1})P^{-1}, \end{array} \end{aligned}$$

(3.6)

system (3.3) can be rewritten in the scaling form as follows:

$$\begin{aligned}&\hat{A_{i}}\cdot {\varDelta \hat{X}}=0,~~~ i=1,2,\cdots ,m,\nonumber \\&\sum _{i=1}^{m} \varDelta y_{i}\hat{A_{i}}-\hat{{\mathcal {Q}}}(\varDelta \hat{X})+\varDelta {\hat{S}}=0,\nonumber \\&H(\hat{X}{\varDelta \hat{S}}+{\varDelta \hat{X}}\hat{S})=\tau \mu I-\hat{X}\hat{S}, \end{aligned}$$

(3.7)

where, due to (3.6) and the fact $PXSP^{-1}\in S^n$, we have $\hat{X}\hat{S}=\hat{S}\hat{X}$ and $H({\hat{X}\hat{S}})=H({\hat{S}\hat{X}})=\hat{X}\hat{S}$. In this paper, in order to obtain the scaled search direction $\left(\varDelta \hat{X},\varDelta y,\varDelta \hat{S}\right)$, we decompose the right-hand side of the third equation in (3.7) to positive and negative parts and solve the following system:

$$\begin{aligned}&\hat{A_{i}}\cdot {\varDelta \hat{X}}=0,~~~ i=1,2,\cdots ,m,\nonumber \\&\sum _{i=1}^{m}\varDelta y_{i} \hat{A_{i}}-\hat{{\mathcal {Q}}}(\varDelta \hat{X})+\varDelta {\hat{S}}=0,\nonumber \\&H(\hat{X}{\varDelta \hat{S}}+{\varDelta \hat{X}}\hat{S})=\left(\tau \mu I-\hat{X}\hat{S}\right)^-+\sqrt{n}\left(\tau \mu I-\hat{X}\hat{S}\right)^+. \end{aligned}$$

(3.8)

Solving the new scaled system (3.8) and considering $\alpha \in [0,1]$ as a step size taken along $\left(\varDelta \hat{X},\varDelta y,\varDelta \hat{S}\right)$, the new iterate is given by

$$\begin{aligned} \left(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha )\right)=\left(\hat{X},y,\hat{S}\right)+\alpha \left(\varDelta \hat{X},\varDelta y,\varDelta \hat{S}\right). \end{aligned}$$

(3.9)

Most of interior-point algorithms generate a sequence of iterations in a small or the so-called negative infinity neighborhood of the central path defined as follows:

$$\begin{aligned} {\mathcal {N}}(\tau ,\beta ):= & {} \Big \{(X,y,S)\in \mathcal {F}^0: \left\Vert \tau \mu I-X^{\frac{1}{2}}SX^{\frac{1}{2}} \right\Vert _{F}\leqslant \beta \tau \mu \Big \}, \end{aligned}$$

(3.10)

$$\begin{aligned} {\mathcal {N}}_{\infty }^-(1-\tau ):= & {} \Big \{(X,y,S)\in \mathcal {F}^0: \lambda _{\min }(XS)\geqslant \tau \mu \Big \}, \end{aligned}$$

(3.11)

where $\tau ,\beta \in (0,1)$ and $\mu =\frac{X\cdot S}{n}$. Theoretically, IPMs based on the small neighborhood and short-step algorithms have a better iteration complexity bound in comparison with the algorithms based on the large neighborhood (large-update algorithms), while computational experience reveals that the large neighborhood algorithms usually perform better in practice.

Li and Terlaky [8] defined the wide neighborhood

$$\begin{aligned} {\mathcal {N}}_{F}(\tau ,\beta ):=\Big \{(X,y,S)\in \mathcal {F}^0: \left\Vert \left(\tau \mu I-X^{\frac{1}{2}}SX^{\frac{1}{2}}\right)^+ \right\Vert _{F}\leqslant \beta \tau \mu \Big \}, \end{aligned}$$

(3.12)

and proposed an $O(\sqrt{n}L)$ interior-point algorithm for SDO problems.

Ai [7] defined the $l_{1}$-norm neighborhood and proposed some neighborhood-following algorithms with the best iteration complexity for LO problems. Liu et al. [10], based on the $l_{1}$-norm wide neighborhood, presented an infeasible interior-point algorithm for SCO problems.

Motivated by Ai [7] and Liu et al. [10], we use the popular 1-norm wide neighborhood

$$\begin{aligned} {\mathcal {N}}_{1}(\tau ,\beta ):=\Big \{(X,y,S)\in \mathcal {F}^0: \left\Vert \left(\tau \mu I-X^{\frac{1}{2}}SX^{\frac{1}{2}}\right)^+ \right\Vert _{1}\leqslant \beta \tau \mu \Big \} \end{aligned}$$

(3.13)

of the central path. Due to the fact that the matrices $XS, SX, X^{\frac{1}{2}}SX^{\frac{1}{2}}, S^{\frac{1}{2}}XS^{\frac{1}{2}}$ and $\hat{X}^{\frac{1}{2}}\hat{S}\hat{X}^{\frac{1}{2}}$ have the same eigenvalues (Proposition 3.2 in [12]) and according to the definitions of the negative infinity and Schatten 1-norm neighborhoods in (3.11) and (3.13), we have the following lemma:

Lemma 3.1

Let $\beta , \tau \in (0,1)$ and $(X,y,S)\in {\mathcal {N}}_{1}(\tau ,\beta )$. Then,

$(\mathrm{i})$  ${\mathcal {N}}_{\infty }^-(1-\tau )\subseteq {\mathcal {N}}_{1}(\tau ,\beta )$.

$(\mathrm{ii})$  The neighborhood ${\mathcal {N}}_{1}(\tau ,\beta )$ is symmetric with respect to X and S and is a scaling invariant, that is, $(X,y,S)\in {\mathcal {N}}_{1}(\tau ,\beta )$ if and only if $(\hat{X},y,\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$.

The algorithm is described in more detail as follows. Assuming an initial solution $(X^{0}, y^0, S^{0})$ belongs to ${\mathcal {N}}_{1}(\tau ,\beta )$ as a starting point, using the search direction $(\varDelta \hat{X},\varDelta y,\varDelta \hat{S})$ and choosing a step size $\bar{\alpha }\in [0,1]$, the algorithm generates a new iterate as (3.9). The step size $\bar{\alpha }$ should be selected in the way that it guarantees the sufficient reduction of the duality gap $\mu (\alpha )$ and ensures that the newly generated point $(\hat{X}(\alpha ),y(\alpha ),\hat{S}(\alpha ))$ belongs to ${\mathcal {N}}_{1}(\tau ,\beta )$.

This procedure will be repeated until $\mu (\alpha )$ is small enough. At this stage, we have found an $\varepsilon$-approximate solution of the CQSDO problem. The generic framework of the algorithm can be stated as follows.

4 Analysis and the Step Size Calculation

The choice of the step size $\alpha$ in (3.9) is one of the most important parts of our analysis. Indeed, we require the largest step size $\bar{\alpha }$ such that it not only reduces the duality gap $\mu (\alpha )$ in each iteration but also it ensures that the new iterate $\left(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha )\right)$ belongs to ${\mathcal {N}}_{1}(\tau ,\beta )$. In following, we discuss how we choose the step size $\bar{\alpha }$ to guarantee the convergence of the generated points by the Algorithm  1. According to (3.9) and the third equation of (3.8), we have

$$\begin{aligned} H\left(\hat{X}(\alpha )\hat{S}(\alpha )\right)= & {} H(\hat{X}\hat{S})+\alpha H(\hat{X}\varDelta \hat{S}+\varDelta \hat{X}\hat{S})+\alpha ^{2}H(\varDelta \hat{X}\varDelta \hat{S})\nonumber \\= & {} \hat{X}\hat{S}+\alpha \left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right)+\alpha ^{2}H\left(\varDelta \hat{X}\varDelta \hat{S}\right)\nonumber \\= & {} \varPsi (\alpha )+\alpha ^{2}H\left(\varDelta \hat{X}\varDelta \hat{S}\right), \end{aligned}$$

(4.1)

where

$$\begin{aligned} \varPsi (\alpha )= & {} \hat{X}\hat{S}+\alpha \left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right)\nonumber \\= & {} (1-\alpha )\hat{X}\hat{S}+\alpha \tau \mu I+\alpha (\sqrt{n}-1)(\tau \mu I-\hat{X}\hat{S})^+ \end{aligned}$$

(4.2)

is a positive semidefinite matrix. Due to (4.1) and (4.2), we have

$$\begin{aligned} \mu (\alpha )= & {} \hat{\mu }(\alpha )=\frac{\mathrm{Tr}(\hat{X}( \alpha )\hat{S}(\alpha ))}{n}=\frac{\mathrm{Tr}\left(H\left( \hat{X}(\alpha )\hat{S}(\alpha )\right)\right)}{n}\nonumber \\= & {} \mu +\alpha \Big [(\tau -1)\mu +\frac{\sqrt{n}-1}{n} \mathrm{Tr}(\tau \mu I-\hat{X}\hat{S})^+\Big ]\nonumber \\&+\frac{\alpha ^{2}}{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S}). \end{aligned}$$

(4.3)

In order to derive the maximum step size $\bar{\alpha }$ such that $\mu (\bar{\alpha })\leqslant \mu (\alpha )$ for all $\alpha \in [0,\bar{\alpha }]$, we need to obtain some upper and lower bounds for the single term $\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})$ in (4.3). The following two lemmas help us to obtain these bounds in Lemma 4.3.

Lemma 4.1

Let $G=\tilde{L}_{\hat{S}}^{-1}\tilde{L}_{\hat{X}}$, $(\hat{X},\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$, $\beta \leqslant \frac{1}{2}$ and $\tau \leqslant \frac{1}{4}$. Then,

$$\begin{aligned} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^+ \right\Vert ^{2}_{F}\leqslant & {} \beta \tau \mu , \end{aligned}$$

(4.4)

$$\begin{aligned} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^- \right\Vert ^{2}_{F}\leqslant & {} n\mu . \end{aligned}$$

(4.5)

Proof

Due to (3.13), we have $\lambda _{\min }(\hat{X}\hat{S})\geqslant (1-\beta )\tau \mu$. Therefore,

$$\begin{aligned} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^+ \right\Vert ^{2}_{F}\leqslant & {} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{- \frac{1}{2}} \right\Vert ^{2}_{2}\left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert ^{2}_{F}\\\leqslant & {} \frac{1}{\lambda _{\min }(\hat{X}\hat{S})}\left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert ^{2}_{1}\\\leqslant & {} \frac{(\beta \tau \mu )^2}{(1-\beta )\tau \mu }\leqslant \beta \tau \mu , \end{aligned}$$

where the third and last inequalities, respectively, follow from $(\hat{X},\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$ and $\beta \leqslant \frac{1}{2}$. It implies the first inequality in the lemma. To prove inequality (4.5), we have

$$\begin{aligned}&\left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^- \right\Vert ^{2}_{F}\\\leqslant & {} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S}) \right\Vert ^{2}_{F}\\= & {} (\tau \mu I-\hat{X}\hat{S})\cdot (\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}})^{-1}(\tau \mu I-\hat{X}\hat{S})\\= & {} \tau \mu I \cdot (\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}})^{-1}\tau \mu I-2\tau \mu I\cdot I+\hat{X}\hat{S}\cdot I\\\leqslant & {} \left\Vert (\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}})^{-1} \right\Vert _{2}\tau \mu I \cdot \tau \mu I-2\tau \mu I\cdot I+\hat{X}\hat{S}\cdot I\\\leqslant & {} \frac{\tau ^{2}\mu ^{2}n}{\lambda _{\min }(\hat{X}\hat{S})}-2\tau \mu n+n\mu \leqslant n\mu , \end{aligned}$$

where the last inequality follows from $\lambda _{\min }(\hat{X}\hat{S})\geqslant (1-\beta )\tau \mu$ and $\beta \leqslant \frac{1}{2}$. This concludes the second inequality in the lemma and ends the proof.

Lemma 4.2

Let $G:=\tilde{L}_{\hat{S}}^{-1}\tilde{L}_{\hat{X}}, \beta \leqslant \frac{1}{2}$ and $\tau \leqslant \frac{1}{4}$. Then

$$\begin{aligned} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}\left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right) \right\Vert ^{2}_{F}\leqslant (1+\beta \tau )n\mu . \end{aligned}$$

Proof

Using Lemma 4.1 and the fact $M^+\cdot M^-=0$, the result can be easily concluded as follows:

$$\begin{aligned}&\left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}\left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right) \right\Vert ^{2}_{F}\\= & {} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^- \right\Vert _{F}^{2} + n \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}(\tau \mu I-\hat{X}\hat{S})^+ \right\Vert _{F}^{2}\\\leqslant & {} n\mu +\beta \tau n\mu =(1+\beta \tau )n\mu . \end{aligned}$$

This concludes the desired result.

The next lemma obtains some bounds for the single term $\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})$.

Lemma 4.3

Let $G:=\tilde{L}_{\hat{S}}^{-1}\tilde{L}_{\hat{X}}$. Then,

$$\begin{aligned} 0\leqslant \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\leqslant \frac{1}{4}(1+\beta \tau )n\mu . \end{aligned}$$

(4.6)

Proof

The left-hand side inequality follows directly from the second equation of system (3.8) and the positive semidefinite property of the operator ${\mathcal {Q}}$. To prove the right-hand side inequality, using the Lyapunov-like operator defined in (2.2), the third equation of system (3.8) can be rewritten as

$$\begin{aligned} \tilde{L}_{\hat{X}}(\varDelta \hat{S})+ \tilde{L}_{\hat{S}}(\varDelta \hat{X})=(\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+. \end{aligned}$$

(4.7)

Now, multiplying this equality by $(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}})^\frac{-1}{2}$ and taking squared norm on both sides, we derive

$$\begin{aligned}&\left\Vert G^{\frac{-1}{2}}\varDelta \hat{X}+G^{\frac{1}{2}}\varDelta \hat{S} \right\Vert ^{2}_{F}\\= & {} \left\Vert G^{\frac{-1}{2}}\varDelta \hat{X}-G^{\frac{1}{2}} \varDelta \hat{S} \right\Vert ^{2}_{F}+4\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\\= & {} \left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}\left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right) \right\Vert ^{2}_{F}. \end{aligned}$$

Combined with Lemma 4.2, the proof is completed.

The following lemma deduces that $\alpha =1$ is the largest step size that reduces the value of duality gap $\mu (\alpha )$ in each iteration.

Lemma 4.4

Let $(\hat{X},y,\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$, $\beta \leqslant \frac{1}{2}$ and $\tau \leqslant \frac{1}{4}$. Then, $\mu (\alpha )$ is strictly monotonically decreasing for $\alpha \in [0,1]$.

Proof

Taking the derivative with respect to $\alpha$ from $\mu (\alpha )$ defined in (4.3), we obtain

$$\begin{aligned} \mu '(\alpha )= & {} (\tau -1)\mu +\frac{\sqrt{n}-1}{n} \left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert _{1}+ \frac{2\alpha }{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\nonumber \\\leqslant & {} (\tau -1)\mu +\frac{\sqrt{n}-1}{n}\beta \tau \mu +\frac{2\alpha }{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S}). \end{aligned}$$

(4.8)

If $\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})=0$, then due to (4.8), we have $\mu '(\alpha )\leqslant (\tau +\beta \tau -1)\mu < 0$ for $\alpha \in [0,1]$. On the other hand, assuming $\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})>0$, using Lemma 4.3, we have

$$\begin{aligned} \frac{\left((1-\tau )\mu -\frac{\sqrt{n}-1}{n} \left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert _{1}\right)n}{2\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})}\geqslant \frac{2(1-\tau -\beta \tau )n\mu }{(1+\beta \tau )n\mu }>1, \end{aligned}$$

which implies $\mu '(\alpha )< 0$ for $\alpha \in [0,1]$. This completes the proof.

Due to the above lemma, the largest step size $\bar{\alpha }$ that guarantees $(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha ))$ belong to ${\mathcal {N}}_{1}(\tau ,\beta )$ will be calculated as follows:

$$\begin{aligned} \bar{\alpha }:=\max \{\alpha :(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha ))\in {\mathcal {N}}_{1}(\tau ,\beta ),~~\forall \alpha \in [0,1]\}, \end{aligned}$$

(4.9)

or equivalently

$$\begin{aligned} \bar{\alpha }:=\max \{\alpha :~ g(\alpha )\leqslant 0,~~\forall \alpha \in [0,1]\}, \end{aligned}$$

(4.10)

where

$$\begin{aligned} g(\alpha )=\left\{ \begin{array}{ll} \frac{\alpha }{\sqrt{n}}\left\Vert \left(H(\varDelta \hat{X}\varDelta \hat{S})\right)^- \right\Vert _{1}-\beta \tau \mu (\alpha ),~~ ~~\text{ if } \alpha <\frac{1}{\sqrt{n}}, \\ \alpha ^{2}\left\Vert \left(H(\varDelta \hat{X}\varDelta \hat{S})\right)^- \right\Vert _{1}-\beta \tau \mu (\alpha ),~~~~~\text{ if }~~\alpha \geqslant \frac{1}{\sqrt{n}}. \end{array} \right. \end{aligned}$$

(4.11)

Below, we explain that the definitions (4.9) and (4.10) are equivalent. To this end, we need to state the following lemma.

Lemma 4.5

Let $(\hat{X},y,\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$. Then, if $\alpha \geqslant \frac{1}{\sqrt{n}}$, we have

$$\begin{aligned} \left\Vert \left(\tau \mu (\alpha )I-\varPsi (\alpha )\right)^+ \right\Vert _{1}=0, \end{aligned}$$

(4.12)

and if $\alpha <\frac{1}{\sqrt{n}}$, we have

$$\begin{aligned} \left\Vert \left(\tau \mu (\alpha )I-\varPsi (\alpha )\right)^+ \right\Vert _{1}\leqslant (1-\alpha \sqrt{n})\beta \tau \mu (\alpha ). \end{aligned}$$

(4.13)

Proof

Using the facts $\varPsi (\alpha )\succeq 0$ and $\mu (\alpha )\leqslant \mu$ for all $\alpha \in [0,1]$, we have

$$\begin{aligned} \Big [\tau \mu (\alpha )I-\varPsi (\alpha )\Big ]^+\preceq & {} \Big [\tau \mu (\alpha )I-\frac{\mu (\alpha )}{\mu }\varPsi (\alpha )\Big ]^+ =\frac{\mu (\alpha )}{\mu }\Big [\tau \mu I-\varPsi (\alpha )\Big ]^+\\= & {} \frac{\mu (\alpha )}{\mu }\Big [ (1-\alpha )(\tau \mu I-\hat{X}\hat{S})^-\\&+(1-\alpha \sqrt{n})(\tau \mu I-\hat{X}\hat{S})^+\Big ]^+\\= & {} \frac{\mu (\alpha )}{\mu }(1-\alpha \sqrt{n})^+(\tau \mu I-\hat{X}\hat{S})^+. \end{aligned}$$

Let $1-\alpha \sqrt{n}>0$. Then, since $(\hat{X},y,\hat{S})\in {\mathcal {N}}_{1}(\tau ,\beta )$, it follows that

$$\begin{aligned} \left\Vert (\tau \mu (\alpha )I-\varPsi (\alpha ))^+ \right\Vert _{1}\leqslant & {} \frac{ \mu (\alpha )}{\mu }(1-\alpha \sqrt{n})\left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert _{1}\\\leqslant & {} (1-\alpha \sqrt{n})\beta \tau \mu (\alpha ). \end{aligned}$$

On the other hand, if $1-\alpha \sqrt{n}\leqslant 0$, then we have $\left\Vert (\tau \mu (\alpha )I-\varPsi (\alpha ))^+ \right\Vert _{1}=0$. The result is derived.

Due to Lemma 2.2, clearly $\left\Vert \left(\tau \mu (\alpha )I-{\hat{X}(\alpha )\hat{S}(\alpha )}\right)^+ \right\Vert _{1}\leqslant \beta \tau \mu (\alpha )$, if

$$\begin{aligned} \left\Vert \left(H\left(\tau \mu (\alpha )I-\hat{X}(\alpha )\hat{S}(\alpha )\right)\right)^+ \right\Vert _{1}= & {} \left\Vert \left(\tau \mu (\alpha )I-H\left(\hat{X}(\alpha )\hat{S}(\alpha )\right)\right)^+ \right\Vert _{1}\nonumber \\\leqslant & {} \beta \tau \mu (\alpha ). \end{aligned}$$

(4.14)

Using Lemma 2.1 and (4.1), inequality (4.14) holds if

$$\begin{aligned} \left\Vert (\tau \mu (\alpha )I-\varPsi (\alpha ))^+ \right\Vert _{1}+\alpha ^{2}\left\Vert \left(H(\varDelta \hat{X}\varDelta \hat{S})\right)^- \right\Vert _{1}\leqslant \beta \tau \mu (\alpha ). \end{aligned}$$

(4.15)

Therefore, Lemma 4.5 and (4.15) confirms the definition of $\bar{\alpha }$ in (4.10).

Below, we prove $(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha ))\in {\mathcal {N}}_{1}(\tau ,\beta )$ for all $\alpha \in [0,\bar{\alpha }]$.

Lemma 4.6

Let $\bar{\alpha }$ be defined as in (4.10). Then, for all $\alpha \in [0,\bar{\alpha }]$

$$\begin{aligned} (\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha ))\in {\mathcal {N}}_{1}(\tau ,\beta ). \end{aligned}$$

Proof

In order to prove $(\hat{X}(\alpha ), y(\alpha ),\hat{S}(\alpha ))\in {\mathcal {N}}_{1}(\tau ,\beta )$, due to the definition of ${\mathcal {N}}_{1}(\tau ,\beta )$ in (3.13), it suffices to show that $\left\Vert \left(\tau \mu (\alpha )I-\hat{X}^{\frac{1}{2}}(\alpha )\hat{S}(\alpha )\hat{X}^{\frac{1}{2}}(\alpha )\right)^+ \right\Vert _{1}\leqslant \beta \tau \mu (\alpha )$ and $\hat{X}(\alpha ), \hat{S}(\alpha )\succ 0$. To this end, due to Lemma 2.2 and (4.10), we have

$$\begin{aligned}&\left\Vert (\tau \mu (\alpha )I-\hat{X}^{\frac{1}{2}}(\alpha ) \hat{S}(\alpha )\hat{X}^{\frac{1}{2}}(\alpha ))^+ \right\Vert _{1}\\ \quad\leqslant & {} \left\Vert \left(H_{\hat{X}^{\frac{1}{2}}(\alpha )}(\tau \mu (\alpha ) I-\hat{X}^{\frac{1}{2}}(\alpha )\hat{S}(\alpha )\hat{X}^{\frac{1}{2}}(\alpha ))\right)^+ \right\Vert _{1}\\ \quad= & {} \left\Vert \left(\tau \mu (\alpha )I-H_{\hat{X}^{\frac{1}{2}}(\alpha )} \left(\hat{X}^{\frac{1}{2}}(\alpha )\hat{S}(\alpha )\hat{X}^{ \frac{1}{2}}(\alpha )\right)\right)^+ \right\Vert _{1}\\ \quad= & {} \left\Vert (\tau \mu (\alpha )I-\hat{X}(\alpha )\hat{S}(\alpha ))^+ \right\Vert _{1} \leqslant \beta \tau \mu (\alpha ). \end{aligned}$$

Moreover, to prove that $\hat{X}(\alpha )$ and $\hat{S}(\alpha )$ are positive definite matrices, it is easy to check that due to $\left\Vert (\tau \mu (\alpha )I-\hat{X}(\alpha )\hat{S}(\alpha ))^+ \right\Vert _{1}\leqslant \beta \tau \mu (\alpha ),$ we derive $\hat{X}(\alpha )\hat{S}(\alpha )\succ 0$.

Thus, we conclude that $\mathrm{det}(\hat{X}(\alpha ))\ne 0$ and $\mathrm{det}(\hat{S}(\alpha ))\ne 0$, for $\alpha \in [0,\bar{\alpha }]$(Lemma 3.3.1 in [19]). However, by continuity, since $\hat{X}, \hat{S}\succ 0$ it follows that $\hat{X}(\alpha ), \hat{S}(\alpha )\succ 0$. This concludes the result and ends the proof.

To complete our analysis, it suffices to derive a lower bound for the step size $\bar{\alpha }$. To this end, we need to recall Lemma 4.6 in [17] which plays an important role in our analysis.

Lemma 4.7

Let $U,V\in {\mathcal {S}}^{n}$ and $G\succ 0$. Then,

$$\begin{aligned} \left\Vert U \right\Vert _{F}\left\Vert V \right\Vert _{F}\leqslant & {} \sqrt{\mathrm{cond(G)}}\left\Vert G^{\frac{-1}{2}}U \right\Vert _{F}\left\Vert G^{ \frac{1}{2}}V \right\Vert _{F}\\\leqslant & {} \frac{\sqrt{\mathrm{cond(G)}}}{2}\left(\left\Vert G^{ \frac{-1}{2}}U \right\Vert ^{2}_{F}+\left\Vert G^{\frac{1}{2}}V \right\Vert ^{2}_{F}\right), \end{aligned}$$

where ${\mathrm{cond}}({G}):=\frac{\lambda _{\max }(G)}{\lambda _{\min }(G)}$.

Lemma 4.8

Let $G:=\tilde{L}_{\hat{S}}^{-1}\tilde{L}_{\hat{X}}$, $\beta \leqslant \frac{1}{2}$ and $\tau \leqslant \frac{1}{4}$. Then,

$$\begin{aligned} \left\Vert \varDelta \hat{X} \right\Vert _{F}\left\Vert \varDelta \hat{S} \right\Vert _{F}\leqslant \frac{9}{16}\sqrt{\mathrm{cond(G)}}\mathrm{n}\upmu . \end{aligned}$$

Proof

Multiplying (4.7) by $(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}})^\frac{-1}{2}$, taking squared norm on both sides and using Lemmas 4.2, 4.3 and 4.7, one has

$$\begin{aligned}&\left\Vert \varDelta \hat{X} \right\Vert _{F}\left\Vert \varDelta \hat{S} \right\Vert _{F}\\\leqslant & {} \frac{\sqrt{{\mathrm{cond}(G)}}}{2}\left(\left\Vert G^{\frac{-1}{2}}\varDelta \hat{X} \right\Vert ^{2}_{F}+\left\Vert G^{\frac{1}{2}}\varDelta \hat{S} \right\Vert ^{2}_{F}\right)\\= & {} \frac{\sqrt{{\mathrm{cond}(G)}}}{2}\left(\left\Vert G^{\frac{-1}{2}}\varDelta \hat{X}+G^{\frac{1}{2}}\varDelta \hat{S} \right\Vert ^{2}_{F}-2 \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\right)\\\leqslant & {} \frac{\sqrt{{\mathrm{cond}(G)}}}{2}\left\Vert G^{\frac{-1}{2}}\varDelta \hat{X}+G^{\frac{1}{2}}\varDelta \hat{S} \right\Vert ^{2}_{F}\\= & {} \frac{\sqrt{{\mathrm{cond}(G)}}}{2}\left\Vert \left(\tilde{L}_{\hat{X}}\tilde{L}_{\hat{S}}\right)^{-\frac{1}{2}}\left((\tau \mu I-\hat{X}\hat{S})^-+\sqrt{n}(\tau \mu I-\hat{X}\hat{S})^+\right) \right\Vert ^{2}_{F}\\\leqslant & {} \frac{\sqrt{{\mathrm{cond}(G)}}}{2}(1+\beta \tau )n\mu \leqslant \frac{9}{16}\sqrt{{\mathrm{cond}(G)}}n\mu , \end{aligned}$$

which follows the result.

Now, we are ready to obtain a lower bound for the step size $\bar{\alpha }$. The following lemma tasks this goal.

Lemma 4.9

Let $\bar{\alpha }$ be defined as (4.10). Then, $\bar{\alpha }\geqslant \frac{\beta \tau ^{2}}{\sqrt{{\mathrm{cond}(G)}n}}$.

Proof

From (4.11), we obtain $\bar{\alpha }\geqslant \frac{1}{\sqrt{n}}$ or $\bar{\alpha }<\frac{1}{\sqrt{n}}$. If $\bar{\alpha }\geqslant \frac{1}{\sqrt{n}}$, we immediately obtain the lower bound on $\bar{\alpha }$. Thus, we need to investigate the other case $\bar{\alpha }<\frac{1}{\sqrt{n}}$. According to Lemmas 2.5 and 4.8, for $\alpha :=\frac{\beta \tau ^{2}}{\sqrt{{\mathrm{cond}(G)}n}}$, we have

$$\begin{aligned} \frac{\alpha }{\sqrt{n}}\left\Vert \left( H(\varDelta \hat{X}\varDelta \hat{S})\right)^- \right\Vert _{1} -\beta \tau \mu (\alpha )\leqslant & {} \frac{\alpha }{\sqrt{n}} \left\Vert H(\varDelta \hat{X}\varDelta \hat{S}) \right\Vert _{1} -\beta \tau \mu (\alpha )\\\leqslant & {} \frac{\alpha }{\sqrt{n}}\left\Vert \varDelta \hat{X} \right\Vert _{F}\left\Vert \varDelta \hat{S} \right\Vert _{F} -\beta \tau \mu (\alpha )\\\leqslant & {} \frac{9}{16}\frac{\alpha }{\sqrt{n}}\sqrt{{\mathrm{cond}(G)}}n\mu -\beta \tau ^{2}\mu \\= & {} \left( \frac{9}{16}-1\right) \beta \tau ^{2}\mu \leqslant 0, \end{aligned}$$

• Algorithm 1: Feasible primal-dual wide neighborhood algorithm for CQSDO problems

where the third inequality follows from

$$\begin{aligned} \mu (\alpha )= & {} \mu +\alpha \Big [(\tau -1)\mu +\frac{\sqrt{n}-1}{n} \mathrm{Tr}(\tau \mu I-\hat{X}\hat{S})^+\Big ]\nonumber +\frac{\alpha ^{2}}{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\\\geqslant & {} \mu +\alpha \Big [(\tau -1)\mu +\frac{\sqrt{n}-1}{n} \mathrm{Tr}(\tau \mu I-\hat{X}\hat{S})^+\Big ]\\\geqslant & {} \mu + \alpha (\tau -1)\mu \geqslant \mu +(\tau -1)\mu =\tau \mu . \end{aligned}$$

The definition of $\bar{\alpha }$ in (4.10) follows the desired result and completes the proof.

4.1 Iteration Bound

In this subsection, we obtain the complexity bound of the Algorithm 1. The following lemma ensures that the complexity bound of the algorithm is polynomial.

Lemma 4.10

Let $\sqrt{{\mathrm{cond}(G)}}\leqslant \kappa <\infty$. Then, the Algorithm 1 requires at most $O(\kappa \sqrt{n}\log \varepsilon ^{-1})$ iterations. The output is an $\varepsilon$-approximate optimal solution.

Proof

By (4.3) and Lemma 4.3, we derive

$$\begin{aligned} \mu (\alpha )= & {} \mu +\alpha \Big [(\tau -1)\mu +\frac{\sqrt{n}-1}{n} \left\Vert (\tau \mu I-\hat{X}\hat{S})^+ \right\Vert _{1}\Big ]+\frac{\alpha ^{2}}{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\\\leqslant & {} \mu +\alpha \Big [(\tau -1)\mu +\frac{\sqrt{n}-1}{n} \beta \tau \mu +\frac{\alpha }{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\Big ]\\\leqslant & {} \mu +\alpha \Big [(\tau -1)\mu + \beta \tau \mu +\frac{\alpha }{n} \mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\Big ]\\= & {} \bigg [1-\alpha \Big [ 1-\tau -\beta \tau -\frac{\alpha }{n\mu }\mathrm{Tr}(\varDelta \hat{X}\varDelta \hat{S})\Big ]\bigg ]\mu \\\leqslant & {} \Big [1-[1-\tau -\beta \tau -\frac{1}{4}\alpha (1+\beta \tau )]\alpha \Big ]\mu \\\leqslant & {} \Big [1-[\frac{3}{4}-\tau -\frac{5}{4}\beta \tau ]\alpha \Big ]\mu = (1-\xi \alpha )\mu , \end{aligned}$$

where $\xi =[\frac{3}{4}-\tau -\frac{5}{4}\beta \tau ]$. Let $\bar{\alpha }_{0}=\frac{\beta \tau ^{2}}{\sqrt{{\mathrm{cond}(G)}n}}$, since $\mu (\alpha )$ is decreasing function with respect to $\alpha$, we have

$$\begin{aligned} \mu (\bar{\alpha })\leqslant \mu (\bar{\alpha }_{0})\leqslant (1-\xi \bar{\alpha }_{0})\mu . \end{aligned}$$

Since we need $\mu (\bar{\alpha })\leqslant \varepsilon \mu _{0}$, it suffices to have

$$\begin{aligned} (1-\xi \bar{\alpha }_{0})^{k}\mu _{0}\leqslant (1-\frac{\beta \tau ^{2}}{ \kappa \sqrt{n}}\xi )^{k}\mu _{0}\leqslant \varepsilon \mu _{0}, \end{aligned}$$

which results $\mu (\bar{\alpha })\leqslant \varepsilon$ for $k\geqslant \frac{\left(\kappa \sqrt{n}\log \varepsilon ^{-1}\right)}{\xi _{0}}$. This completes the proof.

Due to Lemma 36 in [20] for NT direction, the condition number of G is always 1. Therefore, we immediately conclude the following corollary.

Corollary 4.1

If in the path-following algorithm $P=W^{\frac{1}{2}}$ is chosen where W defined in (3.4), the iteration complexity of feasible Algorithm 1 is $O(\sqrt{n}\log \varepsilon ^{-1}).$

5 Numerical Results

In this section, we implement the proposed Algorithm 1 for some numerical experiments. It is well known that the choice of a suitable neighborhood plays an important role in both theoretical analysis and computational performance of interior-point algorithms for optimization problems. Theoretically, we have proved the complexity bound of the proposed Algorithm 1, which uses ${\mathcal {N}}_{1}(\tau ,\beta )$ as the neighborhood of central path, coincides with the best iteration bound for feasible short-step interior-point algorithms. Computationally, we will perform the proposed Algorithm 1 for some numerical examples. We also compare the computational performance of this algorithm with the case where we use the wide neighborhood ${\mathcal {N}}_{F}(\tau ,\beta )$ [defined in (3.12)] instead of ${\mathcal {N}}_{1}(\tau ,\beta )$ as the neighborhood of central path.

The numerical experiments are carried out on a PC with Intel (R) Pentium (R) Dual CPU at 2.20 GHz and 2 GB of physical memory. The PC runs MATLAB Version R2007a on Windows XP Enterprise 32-bit operating system.

Example 5.1

We consider the CQSDO problem whose primal-dual pair of (P) and (D) have the following date: [21]

$$\begin{aligned} A_1= & {} \left[ \begin{array}{lllll} 0&{} 1&{} 0&{} 0&{} 0\\ 1&{} 2&{} 0&{} 0&{} -1\\ 0&{} 0&{} 0&{} 0&{} 1\\ 0&{} 0&{} 0&{} -2&{} -1\\ 0&{} -1&{} 1&{} -1&{} -2 \end{array} \right] , ~~~A_2=\left[ \begin{array}{lllll} 0&{} 0&{} -2&{} 2&{} 0\\ 0&{} 2&{} 1&{} 0&{} 2\\ -2&{} 1&{} -2&{} 0&{} 1\\ 2&{} 0&{} 0&{} 0&{} 0\\ 0&{} 2&{} 1&{} 0&{} 2 \end{array} \right] , \\ A_3= & {} \left[ \begin{array}{lllll} 2&{} 2&{} -1&{} -1&{} 1\\ 2&{} 0&{} 2&{} 1&{} 1\\ -1&{} 2&{} 0&{} 1&{} 0\\ -1&{} 1&{} 1&{} -2&{} 0\\ 1&{} 1&{} 0&{} 0&{} -2 \end{array} \right] , ~~~C=\left[ \begin{array}{lllll} 2&{} 3&{} -3&{} 1&{} 1\\ 3&{} 4&{} 3&{} 1&{} 2\\ -3&{} 3&{} -2&{} 1&{} 2\\ 1&{} 1&{} 1&{} -4&{} -1\\ 1&{} 2&{} 2&{} -1&{} -2\\ \end{array} \right] , \\ {\mathcal {Q}}= & {} \left[ \begin{array}{lllll} 1&{} 0&{} 0&{} 0&{} 0\\ 0&{} 1&{} 0&{} 0&{} 0\\ 0&{} 0&{} 1&{} 0&{} 0\\ 0&{} 0&{} 0&{} 1&{} 0\\ 0&{} 0&{} 0&{} 0&{} 1 \end{array} \right] , ~~~b=\left[ \begin{array}{lllll} -2\\ 2\\ -2 \end{array} \right] . \end{aligned}$$

Example 5.2

Let the primal-dual SDO problem (a special class of CQSDO problems) be with the following date: [22]

$$\begin{aligned} A_1= & {} \left[ \begin{array}{lllll} -0.977\,8&{}\quad -0.764\,6&{}\quad -0.147\,6&{}\quad 1.324\,6&{}\quad 0.836\,8\\ -0.764\,6&{}\quad 0.885\,3&{}\quad -0.228\,6&{}\quad -0.288\,1&{}\quad -1.129\,6\\ -0.147\,6&{}\quad -0.228\,6&{}\quad 0.562\,1&{}\quad -0.180\,4&{}\quad 0.193\,3\\ 1.324\,6&{}\quad -0.288\,1&{}\quad -0.180\,4&{}\quad -0.052\,4&{}\quad 0.105\,3\\ 0.836\,8&{}\quad -1.129\,6&{}\quad 0.193\,3&{}\quad 0.105\,37&{}\quad 1.028\,2 \end{array} \right] , \\ A_2= & {} \left[ \begin{array}{lllll} 0.394\,6&{}\quad 0.251\,0&{}\quad 0.457\,0&{}\quad 0.483\,0&{}\quad -0.223\,7\\ 0.251\,0&{}\quad 0.615\,8&{}\quad -0.752\,5&{}\quad -0.240\,3&{}\quad 0.002\,1\\ 0.457\,0&{}\quad -0.752\,5&{}\quad 1.158\,7&{}\quad -0.102\,9&{}\quad 0.028\,1\\ 0.483\,0&{}\quad -0.240\,3&{}\quad -0.102\,9&{}\quad -0.176\,0&{}\quad -0.084\,4\\ -0.223\,7&{}\quad 0.002\,1&{}\quad 0.028\,1&{}\quad -0.084\,4&{}\quad 1.404\,7 \end{array} \right] , \\ A_3= & {} \left[ \begin{array}{lllll} -0.620\,2&{}\quad -0.012\,8 &{}\quad -0.543\,7&{}\quad 0.018\,6&{}\quad -0.239\,2\\ -0.012\,8&{}\quad 0.976\,5&{}\quad -0.038\,8&{}\quad -0.038\,7&{}\quad 1.362\,6\\ -0.543\,7&{}\quad -0.038\,8&{}\quad -0.450\,7&{}\quad 0.797\,5&{}\quad 0.220\,4\\ 0.018\,6&{}\quad -0.038\,7&{}\quad 0.797\,5&{}\quad 0.390\,1&{}\quad -1.008\,0\\ -0.239\,2&{}\quad 1.362\,6&{}\quad 0.220\,4&{}\quad -1.008\,0&{}\quad -2.669\,5 \end{array} \right] , \\ A_4= & {} \left[ \begin{array}{lllll} -0.759\,7&{}\quad -0.002\,2&{}\quad -1.036\,9&{}\quad 1.439\,5&{}\quad 0.747\,3\\ -0.002\,2&{}\quad 0.420\,1&{}\quad -2.463\,0&{}\quad 0.750\,7&{}\quad -0.078\,3\\ -1.036\,9&{}\quad -2.463\,0&{}\quad 0.089\,1&{}\quad 1.558\,9&{}\quad 0.282\,0\\ 1.439\,5&{}\quad 0.750\,7&{}\quad 1.558\,9&{}\quad -1.527\,6&{}\quad 1.277\,7\\ 0.747\,3&{}\quad -0.078\,3&{}\quad 0.282\,0&{}\quad 1.277\,7 &{}\quad 0.032\,0 \end{array} \right] , \\ A_5= & {} \left[ \begin{array}{lllll} 0.889\,2&{}\quad -1.154\,9&{}\quad -0.112\,2&{}\quad 0.825\,8&{}\quad -0.271\,4\\ -1.154\,9&{}\quad -0.960\,5&{}\quad 0.861\,0&{}\quad -0.228\,9&{}\quad -0.597\,5\\ -0.112\,2&{}\quad 0.861\,0&{}\quad -0.759\,9&{}\quad 0.275\,8&{}\quad 1.163\,9\\ 0.825\,8&{}\quad -0.228\,9&{}\quad 0.275\,8&{}\quad -0.368\,4&{}\quad 0.049\,7\\ -0.271\,4&{}\quad -0.597\,5&{}\quad 1.163\,9&{}\quad 0.049\,7&{}\quad 0.422\,7 \end{array} \right] , \\ C= & {} \left[ \begin{array}{lllll} 3.268\,0&{}\quad 1.574\,1&{}\quad 0.406\,4&{}\quad -2.563\,1&{}\quad -1.447\,7\\ 1.574\,1&{}\quad 1.484\,9&{}\quad 0.978\,6&{}\quad -3.334\,5&{}\quad 2.342\,5\\ 0.406\,4&{}\quad 0.978\,6&{}\quad 2.471\,7&{}\quad -0.478\,8&{}\quad -2.833\,5\\ -2.563\,1&{}\quad -3.334\,5&{}\quad -0.478\,8&{}\quad 8.593\,2&{}\quad -4.830\,6\\ -1.447\,7&{}\quad 2.342\,5&{}\quad -2.833\,5&{}\quad -4.830\,6&{}\quad 9.513\,0 \end{array} \right] , \\ b= & {} [4.619\,2, 19.903\,2, -10.519\,2, -7.719\,1, 1.382\,7]^\mathrm{T}. \end{aligned}$$

Example 5.3

Consider a number of SDO problems in which their data are generated randomly. More precisely, the test problems are generated as follows (See [23]).

As the input parameters, we input m and n as the number and dimension of the coefficient matrixes $A_{i}$, respectively. Using the input parameters m and n, MATLAB proceeds to generate m matrixes $R_{i}\in \mathbb {R}^{n\times n},~i=1,2,\cdots m$. Then, it takes $A_{i}=\frac{1}{2}(R_{i}+R_{i}^\mathrm{T})$, $b_{i}=Tr(A_{i})$ and $C=\sum _{i=1}^{m}A_{i}+I$ to obtain an SDO problem with the initial feasible point $\left(X^{0},y^{0},S^{0}\right)=\left(I,e,I\right)$.

Table 1 The numerical results of Algorithm 1 for Examples 5.1 and 5.2

Table 2 The numerical results of Algorithm 1 for Example 5.3

We solve these examples by using the proposed interior-point Algorithm 1. The parameters were chosen as $\beta =0.5$, $\tau =0.001$ and $\varepsilon =10^{-7}$. We also choose the initial feasible solutions $X^{0}=I$ for the primal problem (P) and $y=e$ and $S^{0}=I$ for the dual problem (D).

The numerical results for Examples 5.1 and 5.2 are summarized in Table 1, where “Iter.” denotes the number of iterations and “D.G” denotes the duality gap related to the primal and dual problems (P) and (D).

The numerical results for Example 5.3 are summarized in Table 2, where “Iter.” denotes the number of iterations and “CPU/s” denotes the CPU time (in seconds) required to obtain an $\varepsilon$-approximate optimal solution of the underlying problem.

In Table 3, solving Examples 5.1 and 5.2, we compare the number of required iterations of Algorithm 1 with the case where we use the wide neighborhood ${\mathcal {N}}_{F}(\tau ,\beta )$ instead of ${\mathcal {N}}_{1}(\tau ,\beta )$ in Algorithm 1.

The numerical results in Table 3 show that the iterations number of Algorithm 1, which uses the wide neighborhood ${\mathcal {N}}_{1}(\tau ,\beta )$, is slightly better than the where case we use the wide neighborhood ${\mathcal {N}}_{F}(\tau ,\beta )$ instead of ${\mathcal {N}}_{1}(\tau ,\beta )$ in Algorithm 1. Therefore, Algorithm 1 is efficient theoretically and practically.

Table 3 The number of required iterations

6 Concluding and Remarks

In this paper, we proposed a feasible interior-point algorithm based on the wide neighborhood ${\mathcal {N}}_{1}(\tau ,\beta )$ of the central path for CQSDO problems. At each iteration of the algorithm, the duality gap $\mu (\alpha )$ is reduced by the rate $1-O(\frac{1}{\sqrt{n}})$ and the complexity of the algorithm is $O(\sqrt{n}\log \varepsilon ^{-1})$, which coincides with the currently best -known complexity bound obtained so far for this class of optimization problems. We have implemented the proposed algorithm for some CQSDO and SDO problems to demonstrate that it is also practically efficient.