• PDF
• Cite
• Share
Article Contents  Article Contents

# Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term

• Kernel functions play an important role in the complexity analysis of the interior point methods (IPMs) for linear optimization (LO). In this paper, an interior-point algorithm for LO based on a new parametric kernel function is proposed. By means of some simple analysis tools, we prove that the primal-dual interior-point algorithm for solving LO problems meets $O\left(\sqrt{n} \log(n) \log(\frac{n}{\varepsilon}) \right)$, iteration complexity bound for large-update methods with the special choice of its parameters.

Mathematics Subject Classification: Primary: 90C05, 90C51; Secondary: 90C31.

 Citation: • • Figure 1.  Generic algorithm

Table 4.  Comparison for $p = 3, n = 6$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 15079 116  0.98 929 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 36917 116  0.98 2432 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 11550 116  0.98 476 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 9053 116  0.98 553 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 3475 116 0.98 64 5

Table 5.  Comparison for $p = 5, n = 10$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 21696 121  0.98 1423 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 37948 121  0.98 2137 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 16713 121  0.98 606 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 12242 121  0.98 651 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 5754 121 0.98 104 5

Table 6.  Comparison for $p = 10, n = 20$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 38278 128  0.98 2613 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 51198 128  0.98 2307 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 25553 128  0.98 857 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 21549 128  0.98 897 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 13054 128 0.98 269 5
• Figures(1)

Tables(3)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint