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

Ayache Benhadid; Fateh Merahi

doi:10.3934/naco.2022003

Article Contents

2023, Volume 13, Issue 2: 224-238. Doi: 10.3934/naco.2022003

This issue Previous Article An improved projection algorithm for variational inequality problem with multivalued mapping Next Article Iterative method for solving split common fixed point problem of asymptotically demicontractive mappings in Hilbert spaces

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

Ayache Benhadid^, and
Fateh Merahi

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

Corresponding author: Ayache Benhadid
Corresponding author: Ayache Benhadid

Received: July 2021

Revised: January 2022

Early access: February 2022

Published: January 2023

Abstract / Introduction Full Text(HTML) Figure(1) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

FullText(HTML)

Figure 1. Generic algorithm

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Y. Q. Bai, M. 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. Bai, G. Lesaja, C. Roos, G. 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. Bai, G. 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. Bouaafia, D. 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. Bouaafia, D. 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. Cai, L. Li, M. El Ghami, T. 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 Ghami, Z. A. Guennoun, S. 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 Ghami, I. D. Ivanov, C. 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 Ghami, G. 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. Li, J. Y. Tao, M. El Ghami, X. 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. Peng, C. 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. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, 2002.
[19]	J. Peng, C. 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. Peng, C. 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. Peyghami, S. 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. Sajad, F. J. Alireza, R. 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. Wang, Y. 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. Wang, Y. Q. Bai, Y. 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.