Existence of step length for long-step method

In this section, we prove the existence of the step length $\alpha$ using the method described in [18]. See also [11] for an analysis of the semidefinite case. Here is the algorithm which we analyze in this section.

Algorithm 2.1   Given $\gamma$, $\sigma$, $(x^{(0)},\tau^{(0)}),(s^{(0)},\kappa^{(0)})\in int(\bar{K}),$
for $N=1, 2, \cdots$
Set $\phi=\phi^{(N-1)},$
Solve (1-6) for $\triangle \phi$
Find the largest $\alpha\in [0,1]$, such that $\phi^{(N-1)}+\alpha\triangle\phi\in N(\gamma),$
Update $\phi^{(N)},$
end.

Denote the maximal and minimal eigenvalues of $X^i$ by $\lambda_{\mbox{max}}(x^i)$ and $\lambda_{\mbox{min}}(x^i)$, respectively. From [9], we have that

$$\lambda_{\mbox{max}}(x^i)=x^i_1+\Vert x^i_{2:n_i}\Vert,\mbox{ and } \lambda_{\mbox{min}}(x^i)=x^i_1-\Vert x^i_{2:n_i}\Vert.$$

Since $X$ is the diagonal matrix consisting of $X^1,\cdots,X^k$, it follows that $\lambda_{\mbox{max}}(x)$ and $\lambda_{\mbox{min}}(x)$ are obtained from

$$\lambda_{\mbox{max}}(x)=max\{x^i_1+\Vert x^i_{2:n_i}\Vert,i=1:k\}, \mbox{and }$$

$$\lambda_{\mbox{min}}(x)=min\{x^i_1-\Vert x^i_{2:n_i}\Vert,i=1:k\}.$$

We now start to find upper bounds for vectors. We consider Algorithm 2.1, but we use (1-6) with the NT direction instead of (1-5).

First, we introduce a useful quantity $\nu_N$ defined by

$$\nu_N=\prod^{N-1}_{j=0}(1-\alpha_j(1-\sigma_j)),$$ (2-1)

where $\alpha_j$ is the step length and $\sigma_j$ is the centering parameter in the $j$-th iteration. According to Lemma 3.13 in [4] and the definitions of $r_1, r_2,r_3$ in Algorithm 2.1, we have

$$\begin{array}{rcl} r^{(N)}_i&=&\nu_Nr^{(0)}_i,\mbox{ }i=1,2,3\\ \mu_N&=&\nu_N\mu_0. \end{array}$$

We choose the initial point by the following:

$$\begin{array}{rl} \mbox{if }x^i,s^i\in K^q,&x^i=\delta e^{n_i... ... x^i=\delta =s^i,\mbox{ and } \tau =\delta =\kappa, \end{array}$$ (2-2)

where $\Vert(x^\ast,\tau^\ast,s^\ast,\kappa^\ast)\Vert _\infty\leq\delta.$ The following lemma gives the bound on

$$\nu\Vert(x^{(N)},\tau^{(N)},s^{(N)},k^{(N)})\Vert _\infty.$$

Lemma 2.2   Let the initial point be given by (2-2). For all $N\geq 0$, there exists $C_1>0$, such that

$$\nu\Vert(x^{(N)},\tau^{(N)},s^{(N)},k^{(N)})\Vert _\infty\leq C_1\mu_N.$$

Proof. For simplicity, we ignore the iteration index $(N)$ on the vectors. Let $(x^\ast,\tau^\ast,y^\ast,s^\ast,\kappa^\ast)$ be any primal-dual solution and define

$$\hat{\phi}=\nu_N\phi^{(0)} +(1-\nu_N)\phi^\ast-\phi.$$

It is easy to verify that $\hat{\phi}$ satisfies the following three equations:

$$\begin{array}{rcl} A\hat{x}-b\hat{\tau}&=&0,\\ A^T\hat{y}+\h... ...u}&=&0,\\ -c^T\hat{x}+b^T\hat{y}-\hat{\kappa}&=&0. \end{array}$$ (2-3)

Hence,

$$\begin{array}{rcl} \hat{x}^T\hat{s}+\hat{\tau}\hat{\kappa}&=&... ...at{y})+ \hat{\tau}(-c^T\hat{x}+b^T\hat{y})\\ &=&0. \end{array}$$ (2-4)

From (2-4), we have

$$\begin{array}{rcl} 0&=&\hat{x}^T\hat{s}+\hat{\tau}\hat{\kappa... ...st)\\ &+&(1-\nu_N)^2\chi^{{\ast}^T}\varsigma^\ast. \end{array}$$ (2-5)

Since $\bar{K}$ is self-dual and $(x^\ast,\tau^\ast,y^\ast,s^\ast,\kappa^\ast)$ is a solution, we have that

$$\begin{array}{rclc} \chi^T\varsigma^\ast+\varsigma^T\chi^\ast\geq 0, \mbox{ and } \chi^{\ast T}\varsigma^\ast=0. \end{array}$$

After inserting the above equations into (2-5), we obtain the following inequality,

$$\begin{array}{rcl} \nu_N(\chi^{{(0)}^T}\varsigma+\varsigma^{... ...0)}^T}\varsigma^\ast+\varsigma^{{(0)}^T}\chi^\ast). \end{array}$$

Next, we define the constant $\xi$ by

$$\xi=$$min$$\{$$min$$_{x^i\in K^q}\{x^{i(0)}_1,s^{i(0)}_1\},\mbox{min}_{x^i\in K^r}\{x... ...}, \mbox{min}_{x^i\in{\bf R}_+}\{x^{i(0)},s^{i(0)}\},\tau^{(0)},\kappa^{(0)}\},$$

where $x^{i(0)}_{1:2}$ are the first two entries of $x^i{^{(0)}}.$ By (2-2), we have that $\xi =\delta.$ One can also derive the following inequality based on the definition of the initial point,

$$\begin{array}{rcl} \xi\Vert(\chi,\varsigma)\Vert _\infty&\leq... ...eq&\varsigma^{{(0)}^T}\chi+\chi^{{(0)}^T}\varsigma. \end{array}$$

Therefore,

$$\begin{array}{rcl} \xi\nu_N\Vert(\chi,\varsigma)\Vert _\infty... ...\Vert(\chi^\ast,\varsigma^\ast)\Vert _1\mu_N/\mu_0. \end{array}$$

Since $\mu_0=\delta^2$,

$$C_1=(2(k+1)+\Vert(x^\ast,\tau^\ast,s^\ast,\kappa^\ast)\Vert _1/\delta)/\delta.$$

Furthermore, because $\Vert(x^\ast,\tau^\ast,s^\ast,\kappa^\ast)\Vert _1\leq 2(n+1)\delta,$ it follows that

$$C_1=2(k+n+2)/\delta.$$

Since we specifically discuss the system (1-6) with the NT search direction, we define the following notation for the scaled vectors at the $N$-th iteration:

$$D_1=(\Theta W)^{-1},$$     $$D_2=(\kappa^{1/2}\tau^{-1/2})^{-1},$$ and $$D=\begin{pmatrix}D_1&\cr &D_2\end{pmatrix}.$$

The next lemma gives bounds on the scaled vectors $\triangle\bar{x}=(D_1)^{-1}\triangle x$ and $\triangle\bar{s}=D_1\triangle s.$

Lemma 2.3   Applying the NT scaling scheme to (1-6), i.e., using $\bar{x}=\bar{s}$, there is a positive constant $C_2$, such that

$$\left\Vert(D)^{-1}\begin{pmatrix}\triangle x\cr \triangle\tau\end{pmatrix}\right\Vert\leq C_2\mu_N^{1/2},$$  $$\left\Vert(D)\begin{pmatrix}\triangle s\cr \triangle\kappa\end{pmatrix}\right\Vert\leq C_2\mu_N^{1/2},$$    for all $$N\geq0.$$

Proof. Let us define

$$\begin{array}{rcl} \hat{\phi}&=&\triangle\phi+\nu_N\phi^{(0)}+\nu_N\phi^\ast. \end{array}$$

It is easy to verify that $\hat{\phi}$ satisfies (2-3) and (2-4). In order to obtain the fourth equation in (1-6), we use the following expression

$$\begin{array}{rcl} &&\bar{S}T\Theta W\hat{x}+\bar{X}T(\Theta ... ...\ast)+\nu_N\bar{X}T(\Theta W)^{-1}(s^{(0)}-s^\ast). \end{array}$$

Since we consider the NT direction, i.e., $\bar{S}=\bar{X}$, we multiply by $T\bar{S}^{-1}$ from the left and obtain

$$D_1^{-1}\hat{x}+D_1\hat{s}=-T\bar{S}^{-1}(\bar{X}\bar{S}e-\sigma_N\mu_ne) +\nu_ND_1^{-1}(x^{(0)}-x^\ast)+\nu_ND_1(s^{(0)}-s^\ast).$$

Similarly,

$$D_2^{-1}\hat{\tau}+D_2\hat{\kappa}=-(\kappa\tau)^{-1/2}(\tau\kapp... ...\mu_N) +\nu_ND_2^{-1}(\tau^{(0)}-\tau^\ast)+\nu_ND_2(\kappa^{(0)}-\kappa^\ast).$$

We now consider the 2-norm of the vector,

$$\left\Vert D^{-1}\begin{pmatrix}\hat{x}\cr\hat{\tau}\end{pmatrix}... ...ft\Vert\begin{pmatrix}D_1\hat{s}\cr D_2\hat{\kappa}\end{pmatrix}\right\Vert^2.$$

On the other hand,

$$\begin{array}{rll} \left\Vert \begin{pmatrix}D_1^{-1}\hat{x}+... ...(\kappa^{(0)}-\kappa^\ast)\end{pmatrix}\right\Vert. \end{array}$$

Combining the above two observations, we obtain an upper bound,

$$\begin{array}{rll} \left\Vert\begin{pmatrix}D_1^{-1}\triangle... ...2(\kappa^{(0)}-\kappa^\ast)\end{pmatrix}\right\Vert \end{array}$$

We now need to show that each term in the right hand side of the above inequality is $O(\mu_N^{1/2}).$ First, we consider $\Vert(\bar{S}^i)^{-1}\Vert.$ From the property of $\bar{S}$ and the definition of $N(\gamma)$, we derive

$$\begin{array}{rcl} \left\Vert(\bar{S}^i)^{-1}\right\Vert&=&\l... ...T}Q^is^i}}\\ &\leq& \frac{1}{\sqrt{\gamma\mu_N}}. \end{array}$$

Hence,

$$\begin{array}{rcl} \left\Vert T\bar{S}^{-1}\right\Vert&=&\mbo... ...kappa\tau)^{-1/2}&\leq&\frac{1}{\sqrt{\gamma\mu_N}}.\end{array}$$

Thus,

$$\begin{array}{rcl} \left\Vert\begin{pmatrix}\bar{X}\bar{S}e-... ...a_N\mu_N)^2 +(\tau\kappa)^2\\ &\leq&(k+1)\mu_N^2. \end{array}$$

For the remaining terms in the inequality, we have

$$\begin{array}{ll} &\nu_N\left\Vert\begin{pmatrix}D_1^{-1}(x^{... ...^{(0)}-\kappa^\ast\end{pmatrix}\right\Vert\right\}. \end{array}$$ (2-6)

Since $\Vert D^{-1}\Vert=$ max $\{\Vert\Theta W\Vert,\kappa^{1/2}\tau^{-1/2}\}$, we find upper bounds for $\Vert\Theta W\Vert$ and $\kappa^{1/2}\tau^{-1/2}.$ So,

$$\begin{array}{rcl} \left\Vert\Theta W\right\Vert&\leq&\mbox{m... ... T\bar{S}^{-1}\Vert(\sum\sqrt{n_i})\Vert s\Vert _1, \end{array}$$

since $s=\Theta W\bar{s}.$ Thus,

$$\begin{array}{rcl} \Vert D^{-1}\Vert&\leq&\sum\sqrt{n_i}\Vert... ...\tau\end{pmatrix}\right\Vert _1/\sqrt{\gamma\mu_N}. \end{array}$$

Now (2-6) is bounded by

$$\frac{2C_1(\sum\sqrt{n_i}+1)(n+1)}{\sqrt{\gamma}}$$max$$\left\{\left\Vert\begin{pmatrix}x^{(0)}-x^\ast\cr\tau^{(0)}-\tau^... ...}-s^\ast\cr\kappa^{(0)}-\kappa^\ast\end{pmatrix}\right\Vert\right\}\mu_N^{1/2}.$$

Hence,

$$C_2=\left( k+1+4C_1(\sum\sqrt{n_i}+1)(n+1)\mbox{max} \left\{\left... ...r\kappa^{(0)}-\kappa^\ast\end{pmatrix}\right\Vert\right\}\right)/\sqrt{\gamma}.$$

If the initial point satisfies (2-2), then the next lemma follows immediately.

Lemma 2.4   Under the same conditions as in the previous lemma and if the initial point satisfies the (2-2), then

$$\left\Vert D^{-1}\begin{pmatrix}\triangle x\cr\triangle\tau\end{pmatrix}\right\Vert\leq C_3\mu_N^{1/2},$$ and $$\left\Vert D\begin{pmatrix}\triangle s\cr\triangle\kappa\end{pmatrix}\right\Vert\leq C_3\mu_N^{1/2}.$$

Proof. From(2-2), we have that

$$-\delta e_1\leq\begin{pmatrix}x^{(0)}-x^\ast\cr \tau^{(0)}-\tau^\ast\end{pmatrix}\leq\delta e_1,$$

where $e_1=[1,\cdots,1]^T.$ Then, we can derive the following two estimates,

$$\begin{array}{rcl} \left\Vert D^{-1}\begin{pmatrix}x^{(0)}-x^... ...\tau\end{pmatrix}\right\Vert _1/\sqrt{\gamma\mu_N}. \end{array}$$

It is easy to check that

$$C_3=4C_1(n+1)^{3/2}(\sum\sqrt{n_i}+1)/\sqrt{\gamma}.$$

The next lemma shows the existence of the step length $\alpha.$

Lemma 2.5   There exists $\bar\alpha\in [0,1]$ such that $(\chi(\alpha),\varsigma(\alpha))\in N(\gamma),$ for all $\alpha\in [0,\bar\alpha],$ where $(\chi(\alpha),\varsigma(\alpha))\in N(\gamma)$ is defined as $(\chi^{(N)},\varsigma^{(N)})+\alpha(\triangle \chi ,\triangle \varsigma).$

Proof. For simplicity, we consider the quadratic cone case only. By Lemma 2.4, we have

$$\triangle x^T\triangle s+\triangle\tau\triangle\kappa\leq \left\V... ...n{pmatrix}\triangle s\cr\triangle\kappa\end{pmatrix}\right\Vert\leq C_2^2\mu_N.$$

From the last two equations of the system (1-6), we obtain

$$\begin{array}{rcl} \varsigma^T\triangle \chi+\chi^T\triangle ... ...\kappa+\sigma_N\mu_N\\ &=&(\sigma_N-1)(k+1)\mu_N. \end{array}$$

In order to consider $N(\gamma),$ we estimate $\mu (\alpha)$ by

$$\begin{array}{rcl} \mu (\alpha)&=&\frac{1}{k+1}\{(\chi+\alph... ...\alpha\sigma_N\mu_N+\frac{\alpha^2C^2_2}{k+1}\mu_N. \end{array}$$

We now consider the conditions of $N(\gamma)$. We note that

$$\begin{array}{rcl} \tau (\alpha)\kappa (\alpha)-\gamma \mu(\a... ...q\alpha\sigma_N\mu_N(1-\gamma)-2\alpha^2C^2_2\mu_N. \end{array}$$

If

$$\alpha\leq\frac{\sigma_N(1-\gamma)}{2C^2_2}$$

holds, then

$$\tau (\alpha)\kappa (\alpha)\geq\gamma\mu (\alpha).$$

Therefore,

$$\bar{\alpha}= \left\{1,\frac{\sigma_N(1-\gamma)}{2C^2_2}\right\}.$$ (2-7)

A similar result in [9] is based on feasible initial points, however, the condition (2-7) is good for infeasible initial points.