Linear system

Here, we will discuss some computational issues in second order cone programming, especially the linear system (1-6). Denote by $[r_1,r_2,r_3,r_4,r_5]^T$ the right hand side of (1-6). The augmented system following from (1-6) is

$$\begin{pmatrix}-(\bar{X}T(\Theta W)^{-1})^{-1}\bar{S}T\Theta W-\f... ...matrix}=\begin{pmatrix}r_2-\Theta WT\bar{X}^{-1}r_4+mc\cr r_1+mb\end{pmatrix},$$

where $m=\frac{\tau}{\kappa}(r_3+r_5/\tau).$ We use the NT direction, i.e., $\bar{X}=\bar{S}$, apply the Sherman-Morrison-Woodury formula to the coefficient matrix, and denote

$$\begin{array}{rcl} p=\begin{pmatrix}p_1 \cr p_2\end{pmatrix}&... ...x}r2-\Theta WT\bar{X}^{-1}r_4 \cr r_1\end{pmatrix}. \end{array}$$ (4-1)

Hence,

$$\begin{pmatrix}\triangle x\cr\triangle y\end{pmatrix}=\begin{pmatrix}q_1\cr q_2\end{pmatrix}+h\begin{pmatrix}p_1\cr p_2\end{pmatrix}, h=\frac{m-\frac{\tau}{\kappa}\begin{pmatrix}-c^T & b^T\end{pmatrix}q}{1+\frac{\tau}{\kappa}\begin{pmatrix}-c^T& b^T\end{pmatrix}p}.$$ (4-2)

The next lemma follows immediately.

Lemma 4.1   $h=\triangle \tau .$

Proof.

$$\begin{array}{rcl} \triangle\tau -h&=&\frac{\tau}{\kappa}(r_... ...a}\begin{pmatrix}-c^T & b^T\end{pmatrix}p)\cr &=&0. \end{array}$$

Moreover, the normal equations are

$$\begin{array}{rcl} A(\Theta W)^{-2}A^Tp_2&=&b+A(\Theta W)^{-... ...Theta W)^{-2}(r_2-\Theta WT\bar{X}^{-1}r_4-A^Tq_2). \end{array}$$

Subsequently, the search direction can be computed as follows:

$$\begin{array}{rcl} \triangle\tau&=&h,\cr \triangle x&=& q_1+... ...kappa&=&-\frac{\kappa}{\tau}\triangle\tau+r_5/\tau. \end{array}$$

Furthermore, one can rewrite $\triangle s$ as

$$\triangle s=r_2-A^Tq_2+\triangle\tau(c-A^Tp_2).$$

Two vectors $r_2-A^Tq_2$ and $c-A^Tp_2$ have been calculated while computing $p_1$ and $q_1.$ Because of the definition of $W^i$, $(W^i)^{2}$ and $(W^i)^{-2}$ are easy to obtain:

$$\begin{array}{rcl} (W^i)^{-2}&=&-Q^i-2Q^iw^i(1-2(w^i)^TQ^iw... ...\begin{pmatrix}-w^i_1&(w^i_{2:n_i})^T\end{pmatrix}, \end{array}$$

since $1-2(w^i)^TQ^iw^i=-1.$