doi: 10.3934/naco.2022003
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Department of Mathematics, Faculty of Mathematics and Computer Science, Batna 2 University, Batna, Algeria

Corresponding author: Ayache Benhadid

Received  July 2021 Revised  January 2022 Early access February 2022

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.

Citation: Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, doi: 10.3934/naco.2022003
References:
[1]

Y. Q. BaiM. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization, SIAM. J. Optim., 15 (2004), 101-128.  doi: 10.1137/S1052623403423114.

[2]

Y. Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, Proceedings of the 9th Australian Optimization Day, 2002.

[3]

Y. Q. BaiG. LesajaC. RoosG. Q. Wang and M. Ghami, A class of large- and small-update primal-dual interior-point algorithm for linear optimization, Journal of Optimization Theory and Application, 138 (2008), 341-359.  doi: 10.1007/s10957-008-9389-z.

[4]

Y. Q. BaiG. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Analysis: Theory, Methods and Applications, 70 (2009), 3584-3602.  doi: 10.1016/j.na.2008.07.016.

[5]

A. Benhadid and K. Saoudi, A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound, Communications in Mathematics, 28 (2020), 27-41.  doi: 10.2478/cm-2020-0003.

[6]

A. Benhadid, K. Saoudi and F. Merahi, An interior point approach for linear complementarity problem using new parametrized kernel function, Optimization, 2021. doi: 10.1080/02331934.2021.1945051.

[7]

M. BouaafiaD. Benterki and Y. Adnan, An efficient parameterized logarithmic kernel function for linear optimization, Optim. Lett., 12 (2018), 1079-1097.  doi: 10.1007/s11590-017-1170-5.

[8]

M. BouaafiaD. Benterki and Y. Adnan, An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term, J. Optim. Theory Appl., 170 (2016), 528-545.  doi: 10.1007/s10957-016-0895-0.

[9]

X. Z. Cai, G. Q. Wang, M. El Ghami and Y. J. Yue, Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term, Abstract and Applied Analysis, 11 (2014), Artical ID 710158. doi: 10.1155/2014/710158.

[10]

X. Z. CaiL. LiM. El GhamiT. Steihaug and G. Q. Wang, A new parametric kernel function yielding the best known iteration bounds of interior-point methods for the Cartesian $ P_{*}(\kappa) $-LCP over symmetric cones, Pacific Journal of Optimization, 13 (2017), 547-570. 

[11]

M. El GhamiZ. A. GuennounS. Bouali and T. Steihaug, Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term, J. Comput. Appl. Math, 236 (2012), 3613-3623.  doi: 10.1016/j.cam.2011.05.036.

[12]

M. El GhamiI. D. IvanovC. Roos and T. Steihaug, A polynomial-time algorithm for LO based on generalized logarithmic barrier functions, Int. J. Appl. Math., 21 (2008), 99-115. 

[13]

M. El GhamiG. Q. Wang and T. Steihaug, Primal-dual algorithms for semidefinite optimization problems based on kernel-function with trigonometric barrier term, International Journal of Applied Mathematics, 32 (2019), 333-356. 

[14]

N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4 (1984), 373-395.  doi: 10.1007/BF02579150.

[15]

L. LiJ. Y. TaoM. El GhamiX. Z. Cai and G. Q. Wang, A new parametric kernel function with a trigonometric barrier term for $ P_{*}(\kappa) $-linear complementarity problems, Pacific Journal of Optimization, 13 (2017), 255-278. 

[16]

N. Megiddo, Pathways to the optimal set in linear programming, Progress in Mathematical Programming: Interior Point and Related Methods, Springer, New York, (1989), 131–158.

[17]

J. PengC. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, European Journal of Operational Research, 143 (2002), 234-256.  doi: 10.1016/S0377-2217(02)00275-8.

[18] J. PengC. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, 2002. 
[19]

J. PengC. Roos and T. Terlaky, A new and efficient large-update interior point method for linear optimization, J. Comput. Technol., 6 (2001), 61-80. 

[20]

J. PengC. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171.  doi: 10.1007/s101070200296.

[21]

M. R. PeyghamiS. F. Hafshejani and L. Shirvani, Complexity of interior point methods for linear optimization based on a new trigonometric kernel function, J. Comput. Appl. Math., 255 (2014), 74-85.  doi: 10.1016/j.cam.2013.04.039.

[22]

M. R. Peyghami and S. F. Hafshejani, Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function, Numer. Algorithms, 67 (2014), 33-48.  doi: 10.1007/s11075-013-9772-1.

[23]

C. Roos, T. Terlaky and J. P. Vial, Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester, 1997.

[24]

F. H. SajadF. J. AlirezaR. P. Mohammad and C. Shengyuan, Complexity of interior point methods for a class of linear complementarity problems using a kernel function with trigonometric growth term, J. Optim. Theory Appl., 178 (2018), 935-949.  doi: 10.1007/s10957-018-1344-z.

[25]

G. Sonnevend, An "analytic center" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, In System Modelling and Optimization (eds. A. Prekopa, J. Szelezsan and B. Strazicky), Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985. Lecture Notes in Control and Information Science, 84, Springer, Berlin 1986. doi: 10.1007/BFb0043914.

[26]

M. V. C. Vieira, Jordan algebraic approach to symmetric optimization, Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.

[27]

G. Q. WangY. Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, J. Math. Model. Algorithms, 4 (2005), 409-433.  doi: 10.1007/s10852-005-3561-3.

[28]

G. Q. WangY. Q. BaiY. Liu and M. Zhang, A new primal-dual interior-point algorithm for convex quadratic optimization, J. Shanghai Univ., 12 (2008), 189-196.  doi: 10.1007/s11741-008-0301-3.

[29]

Y. Ye, Interior Point Algorithms, Theory and Analysis, Wiley, Chichester, 1997. doi: 10.1002/9781118032701.

show all references

References:
[1]

Y. Q. BaiM. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization, SIAM. J. Optim., 15 (2004), 101-128.  doi: 10.1137/S1052623403423114.

[2]

Y. Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, Proceedings of the 9th Australian Optimization Day, 2002.

[3]

Y. Q. BaiG. LesajaC. RoosG. Q. Wang and M. Ghami, A class of large- and small-update primal-dual interior-point algorithm for linear optimization, Journal of Optimization Theory and Application, 138 (2008), 341-359.  doi: 10.1007/s10957-008-9389-z.

[4]

Y. Q. BaiG. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Analysis: Theory, Methods and Applications, 70 (2009), 3584-3602.  doi: 10.1016/j.na.2008.07.016.

[5]

A. Benhadid and K. Saoudi, A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound, Communications in Mathematics, 28 (2020), 27-41.  doi: 10.2478/cm-2020-0003.

[6]

A. Benhadid, K. Saoudi and F. Merahi, An interior point approach for linear complementarity problem using new parametrized kernel function, Optimization, 2021. doi: 10.1080/02331934.2021.1945051.

[7]

M. BouaafiaD. Benterki and Y. Adnan, An efficient parameterized logarithmic kernel function for linear optimization, Optim. Lett., 12 (2018), 1079-1097.  doi: 10.1007/s11590-017-1170-5.

[8]

M. BouaafiaD. Benterki and Y. Adnan, An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term, J. Optim. Theory Appl., 170 (2016), 528-545.  doi: 10.1007/s10957-016-0895-0.

[9]

X. Z. Cai, G. Q. Wang, M. El Ghami and Y. J. Yue, Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term, Abstract and Applied Analysis, 11 (2014), Artical ID 710158. doi: 10.1155/2014/710158.

[10]

X. Z. CaiL. LiM. El GhamiT. Steihaug and G. Q. Wang, A new parametric kernel function yielding the best known iteration bounds of interior-point methods for the Cartesian $ P_{*}(\kappa) $-LCP over symmetric cones, Pacific Journal of Optimization, 13 (2017), 547-570. 

[11]

M. El GhamiZ. A. GuennounS. Bouali and T. Steihaug, Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term, J. Comput. Appl. Math, 236 (2012), 3613-3623.  doi: 10.1016/j.cam.2011.05.036.

[12]

M. El GhamiI. D. IvanovC. Roos and T. Steihaug, A polynomial-time algorithm for LO based on generalized logarithmic barrier functions, Int. J. Appl. Math., 21 (2008), 99-115. 

[13]

M. El GhamiG. Q. Wang and T. Steihaug, Primal-dual algorithms for semidefinite optimization problems based on kernel-function with trigonometric barrier term, International Journal of Applied Mathematics, 32 (2019), 333-356. 

[14]

N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4 (1984), 373-395.  doi: 10.1007/BF02579150.

[15]

L. LiJ. Y. TaoM. El GhamiX. Z. Cai and G. Q. Wang, A new parametric kernel function with a trigonometric barrier term for $ P_{*}(\kappa) $-linear complementarity problems, Pacific Journal of Optimization, 13 (2017), 255-278. 

[16]

N. Megiddo, Pathways to the optimal set in linear programming, Progress in Mathematical Programming: Interior Point and Related Methods, Springer, New York, (1989), 131–158.

[17]

J. PengC. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, European Journal of Operational Research, 143 (2002), 234-256.  doi: 10.1016/S0377-2217(02)00275-8.

[18] J. PengC. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, 2002. 
[19]

J. PengC. Roos and T. Terlaky, A new and efficient large-update interior point method for linear optimization, J. Comput. Technol., 6 (2001), 61-80. 

[20]

J. PengC. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171.  doi: 10.1007/s101070200296.

[21]

M. R. PeyghamiS. F. Hafshejani and L. Shirvani, Complexity of interior point methods for linear optimization based on a new trigonometric kernel function, J. Comput. Appl. Math., 255 (2014), 74-85.  doi: 10.1016/j.cam.2013.04.039.

[22]

M. R. Peyghami and S. F. Hafshejani, Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function, Numer. Algorithms, 67 (2014), 33-48.  doi: 10.1007/s11075-013-9772-1.

[23]

C. Roos, T. Terlaky and J. P. Vial, Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester, 1997.

[24]

F. H. SajadF. J. AlirezaR. P. Mohammad and C. Shengyuan, Complexity of interior point methods for a class of linear complementarity problems using a kernel function with trigonometric growth term, J. Optim. Theory Appl., 178 (2018), 935-949.  doi: 10.1007/s10957-018-1344-z.

[25]

G. Sonnevend, An "analytic center" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, In System Modelling and Optimization (eds. A. Prekopa, J. Szelezsan and B. Strazicky), Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985. Lecture Notes in Control and Information Science, 84, Springer, Berlin 1986. doi: 10.1007/BFb0043914.

[26]

M. V. C. Vieira, Jordan algebraic approach to symmetric optimization, Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007.

[27]

G. Q. WangY. Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, J. Math. Model. Algorithms, 4 (2005), 409-433.  doi: 10.1007/s10852-005-3561-3.

[28]

G. Q. WangY. Q. BaiY. Liu and M. Zhang, A new primal-dual interior-point algorithm for convex quadratic optimization, J. Shanghai Univ., 12 (2008), 189-196.  doi: 10.1007/s11741-008-0301-3.

[29]

Y. Ye, Interior Point Algorithms, Theory and Analysis, Wiley, Chichester, 1997. doi: 10.1002/9781118032701.

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 [12]
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 [7]
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 [17]
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 [19]
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
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 [12]
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 [7]
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 [17]
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 [19]
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 [12]
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 [7]
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 [17]
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 [19]
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
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 [12]
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 [7]
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 [17]
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 [19]
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 [12]
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 [7]
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 [17]
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 [19]
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
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 [12]
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 [7]
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 [17]
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 [19]
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
[1]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[2]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[3]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[4]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[5]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[6]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

[7]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[8]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107

[9]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[10]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial and Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[11]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[12]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[13]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[14]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036

[15]

Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control and Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167

[16]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control and Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012

[17]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial and Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[18]

Kyoungsun Kim, Gen Nakamura, Mourad Sini. The Green function of the interior transmission problem and its applications. Inverse Problems and Imaging, 2012, 6 (3) : 487-521. doi: 10.3934/ipi.2012.6.487

[19]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2579-2598. doi: 10.3934/jimo.2021082

[20]

Enrique Fernández-Cara, Arnaud Münch. Numerical null controllability of semi-linear 1-D heat equations: Fixed point, least squares and Newton methods. Mathematical Control and Related Fields, 2012, 2 (3) : 217-246. doi: 10.3934/mcrf.2012.2.217

 Impact Factor: 

Metrics

  • PDF downloads (237)
  • HTML views (111)
  • Cited by (0)

Other articles
by authors

[Back to Top]