| Title:
|
A novel kernel function bridging iteration bounds in interior-point algorithms for linear programming (English) |
| Author:
|
Touil, Imene |
| Author:
|
Fathi-Hafshejani, Sajad |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
61 |
| Issue:
|
1 |
| Year:
|
2025 |
| Pages:
|
18-31 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Kernel functions play an important role in designing and analyzing interior-point methods. They are not only used for determining search directions but also for measuring the distance between the given iterate and the $\mu$-center in the algorithms. Currently, interior-point methods based on kernel functions are among the most effective methods for solving different types of optimization problems and are very active research area in mathematical programming. Therefore, in this work, we introduce a novel kernel function that bridges the gap between the iteration bounds for large-update and small-update methods. To the best of our knowledge, we are the first to achieve these results. (English) |
| Keyword:
|
linear programming |
| Keyword:
|
primal-dual interior point methods |
| Keyword:
|
kernel functions |
| Keyword:
|
complexity analysis |
| Keyword:
|
large- and small-update methods |
| MSC:
|
90C05 |
| MSC:
|
90C51 |
| DOI:
|
10.14736/kyb-2025-1-0018 |
| . |
| Date available:
|
2025-04-07T09:33:10Z |
| Last updated:
|
2025-04-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152923 |
| . |
| Reference:
|
[1] Achache, M.: A new primal-dual path-following method for convex quadratic programming..Comput. Appl. Math. 25 (2006), 1, 97-110. MR 2267615, |
| Reference:
|
[2] Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization..SIAM J. Optim. 5 (1995), 13-51. MR 1315703, |
| Reference:
|
[3] Bai, Y. Q., Roos, C.: A primal-dual interior-point method based on a new kernel function with linear growth rate..In: Proc. Industrial Optimization Symposium and Optimization Day 2002. MR 1972215 |
| Reference:
|
[4] Bai, Y. Q., Ghami, M. El, Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization..SIAM J. Optim. 15 (2004), 101-128. MR 2112978, |
| Reference:
|
[5] Bouafia, M., Benterki, D., Yassine, A.: 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. MR 3527709, |
| Reference:
|
[6] Boudjellal, N., Roumili, H., Benterki, D.: A primal-dual interior point algorithm for convex quadratic programming based on a new parametric kernel function..Optimization 70 (2020) 8, 1-22. MR 4293597, |
| Reference:
|
[7] Bouhenache, Y., Chikouche, W., Touil, I., Fathi-Hafshejani, S.: Complexity analysis of primal-dual interior-point methods for convex quadratic programming based on a new twice parameterized kernel function..J. Math. Model. 12 (2024), 2, 247-265. MR 4777340 |
| Reference:
|
[8] Choi, B. K., Lee, G. M.: On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function..Nonlinear Anal. 71 (2009), 2628-2640. MR 2672034, |
| Reference:
|
[9] Ghami, M. El, Guennoun, Z. A., Bouali, S., Steihaug, T.: Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term..J. Comput. Appl. Math. 236 (2012), 3613-3623. MR 2923494, |
| Reference:
|
[10] Guerdouh, S., Chikouche, W., Touil, I.: An efficient primal-dual interior point algorithm for linear optimization problems based on a novel parameterized kernel function with a hyperbolic barrier term..2021. halshs-03228790. MR 4601347 |
| Reference:
|
[11] Fathi-Hafshejani, S., Mansouri, H., Peyghami, M. R., Chen, S.: Primal-dual interior-point method for linear optimization based on a kernel function with trigonometric growth term..Optimization (2018), 1029-4945. MR 3882993, |
| Reference:
|
[12] Fathi-Hafshejani, S., Moaberfard, Z.: An interior-point algorithm for linearly constrained convex optimization based on kernel function and application in non-negative matrix factorization..Optim. Engrg. 21 (2020), 1019-1051. MR 4125721, |
| Reference:
|
[13] Karmarkar, N. K.: A new polynomial-time algorithm for linear programming..In: Proc. 16th Annual ACM Symposium on Theory of Computing 4 (1984), 373-395. MR 0779900 |
| Reference:
|
[14] Nesterov, R. E., Nemirovskii, A. S.: Interior-Point Ploynomial Methods in Convex Programming..Society for Industrial and Applied Mathematics 1994. MR 1258086 |
| Reference:
|
[15] Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization..Math. Program. 93 (2002), 129-171. Zbl 1007.90037, MR 1912271, |
| Reference:
|
[16] Peyghami, M. R., Fathi-Hafshejani, S., Chen, S.: A primal-dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions..Oper. Res. Lett. 44 (2016), 319-323. MR 3503107, |
| Reference:
|
[17] Roos, C., Terlaky, T., Vial, J. Ph.: Theory and algorithms for linear optimization..In: An interior point Approach. John Wiley and Sons, Chichester 1997. MR 1450094 |
| Reference:
|
[18] Touil, I., Benterki, D., Yassine, A.: A feasible primal-dual interior point method for linear semidefinite programming..J. Comput. Appl. Math. 312 (2017), 216-230. MR 3557876, |
| Reference:
|
[19] Touil, I., Benterki, D.: A primal-dual interior-point method for the semidefinite programming problem based on a new kernel function..J. Nonlinear Funct. Anal. (2019), Article ID 25. |
| Reference:
|
[20] Touil, I., Chikouche, W.: Primal-dual interior point methods for semidefinite programming based on a new type of kernel functions..Filomat. 34 (2020), 12, 3957-3969. MR 4290825, |
| Reference:
|
[21] Touil, I., Chikouche, W.: Polynomial-time algorithm for linear programming based on a kernel function with hyperbolic-logarithmic barrier term..PJM 11 (2022), 127-135. MR 4447022 |
| Reference:
|
[22] Touil, I., Chikouche, W.: Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems..Acta Math. Sinica (Engl. Ser.) 38 (2022), 1, 44-67. MR 4375772, |
| Reference:
|
[23] Wang, G. Q., Bai, Y. Q., Roos, C.: Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function..J. Math. Model. Algorithms Oper. Res. 4 (2005), 4, 409-433. MR 2231552, |
| . |
