Long-step path-following method

In this section, we start by stating the long-step path-following algorithm with the scaled search direction and then compare the heuristic choices of the centering parameter $\sigma$ with the proposed choices. First, we give the linear system for the scaled search direction,

$$\begin{pmatrix}A&-b&0&0&0\cr 0&-c&A^T&I&0\cr -c^T&0&b^T&0&-1\cr \... ...ma-1)r_3\cr -\bar{X}\bar{S}e+\sigma\mu e\cr -\tau\kappa+\sigma\mu\end{pmatrix}.$$ (4-3)

In algorithms, we denote $\phi=(x,\tau,y,s,\kappa)$ and all other 5-tuple vectors are also converted to $\triangle \phi$, $\phi^{(N)}$, and etc.

Algorithm 4.2   Given $(x^{(0)},\tau^{(0)}),(s^{(0)},\kappa^{(0)})\in\bar{K}$, $\sigma_{min}<\sigma_0<\sigma_{max},\gamma$
$\mu_0=((x^{(0)})^Ts^{(0)}+\tau^{(0)}\kappa^{(0)})/(k+1),$

$$% latex2html id marker 4010 \begin{array}{rl} \mbox{For} & N... ...u_{N+1},\sigma_{N+1},\gamma_{N+1}.\\ \mbox{end.}& \end{array}$$

In the basic algorithm, the parameter $\gamma_{N+1}$ is fixed for all iterations. Here, we consider that $\gamma$ can be changed at each iteration and propose a way to choose $\sigma_{N+1}$ and $\gamma_{N+1}.$ We also compare this choice with the heuristic choices of $\sigma_{N+1}$ and fixed $\gamma.$ Since the comparisons are based on the same algorithm, we only compare the number of iterations.

Let us consider three heuristic choices with fixed $\gamma=0.001$:

$$\begin{array}{rl} \mbox{H2}&\sigma =(\frac{\mu_{N+1}}{\mu_{N... ... \mbox{H4}&\sigma =(\frac{\mu_{N+1}}{\mu_{N}})^4. \end{array}$$

We now present the algorithm for choosing $\mu$ and $\sigma .$

Algorithm 4.3   $\sigma =(\frac{\mu_N}{\mu_{N-1}})^2;\sigma_{max}=0.9,\sigma=0.005$
$$\begin{array}{ll} \mbox{if }& \sigma >=\sigma_{max} \\ &\ga... ...\mbox{else}&\\ &\gamma=0.001;\\ \mbox{end}&\\ \end{array}$$

In the literature, authors seldom show exactly how $\gamma$ and $\sigma$ are chosen. Although these heuristic choices of $\sigma$ are mentioned frequently in the literature, practical algorithms must develop more robust methods to choose $\sigma .$ As one can see in Table 1, the performances of H2, H3, and H4 vary in each problem. The main idea of Algorithm4.3 is to use three heuristic choices and to change the size of the neighborhood according to the result of H2. If $\sigma$ is greater than $\sigma_{max}$, it follows that the descent of $\mu_{N+1}$ is small. One way to achieve larger descent is to have a larger neighborhood, i.e., choosing a smaller $\gamma.$ If $\sigma$ is less than $10\times\sigma_{min}$, it means that a large descent has been made. When $\mu_N$ is getting closer to the tolerance, it is important to pull the new point back to the central path, i.e., choosing larger $\gamma.$ If $\mu_N$ is still large, we use H4 to loosen the centering parameter. The reason is that the small value of H2 indicates that the current neighborhood is large enough to allow for a large descent. The following table shows the number of iterations for reaching the optimum using Algorithm 4.2 combined with the above four methods to choose $\sigma$ and $\gamma.$

Table 1: The number of iterations for different methods of choosing $\sigma .$

	Algorithm 4.3	H2	H3	H4
EX1-50	20	25	23	24
EX1-75	21	27	25	25
EX1-100	22	28	25	26
EX1-200	23	28	28	28
EX2-50	13	18	18	21
EX2-100	13	19	18	21
EX2-150	14	19	20	21
EX2-200	14	18	18	18
EX3-10-4	18	24	25	25
EX3-20-4	16	21	22	23
EX3-30-9	18	23	24	25
EX3-40-9	18	24	23	26
EX4-mark	18	27	25	27
EX4-return	23	30	30	29
EX4-risk	21	27	26	29
EX5-10	27	30	33	31
EX5-20	26	32	31	33
EX5-40	30	35	37	36
EX5-80	31	36	35	38
EX6-10	26	28	34	33
EX6-20	35	36	42	43
EX6-40	50	57	57	58
EX6-60	62	66	71	79
Total	559	678	690	721

According to this table, we see that the number of iterations using Algorithm 4.3 is overall less than using the heuristic choices. The average is about $6$ iterations less than H2, and H3, $7$ iterations less than H4. Since the problem is large, the running time for 6 or 7 iterations is still significant. Figure 1 from EX6-40 shows that $\mu_N$ decreases much more in Algorithm 4.3 than in the other three methods. Similar graphs can be obtained for each test case.