-
Previous Article
A new methodology for solving bi-criterion fractional stochastic programming
- NACO Home
- This Issue
-
Next Article
Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable
A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions
Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas Sétif1. Sétif. Algérie |
In an attempt to improve theoretical complexity of large-update methods, in this paper, we propose a primal-dual interior-point method for $ P_{\ast}\left( \kappa \right) $-horizontal linear complementarity problem. The method is based on a class of parametric kernel functions. We show that the corresponding algorithm has $ O\left( \left( 1+2\kappa \right) p^{2}n^{\frac{2+p}{2\left( 1+p\right) }}\log \frac{n}{\epsilon }\right) $ iteration complexity for large-update methods and we match the best known iteration bounds with special choice of the parameter $ p $ for $ P_{\ast }\left(\kappa \right) $-horizontal linear complementarity problem that is $ O\left(\left( 1+2\kappa \right) \sqrt{n}\log n\log \frac{n}{\epsilon }\right) $. We illustrate the performance of the proposed kernel function by some comparative numerical results that are derived by applying our algorithm on five kernel functions.
References:
[1] |
M. Achache,
Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast }\left(\kappa \right)$-LCP, RAIRO-Oper. Res., 50 (2016), 131-143.
doi: 10.1051/ro/2015020. |
[2] |
M. Achache and N. Tabchouche,
Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function, Optimization, 67 (2018), 1211-1230.
doi: 10.1080/02331934.2018.1462356. |
[3] |
S. Asadi and H. Mansouri,
Polynomial interior-point algorithm for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, Numer. Algorithms, 63 (2013), 385-398.
doi: 10.1007/s11075-012-9628-0. |
[4] |
S. Asadi, H. Mansouri and M. Zangiabadi,
A class of path-following interior-point methods for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, J. Oper Res Soc China, 3 (2015), 17-30.
doi: 10.1007/s40305-015-0070-6. |
[5] |
S. Asadi, M. Zangiabadi and H. Mansouri,
An infeasible interior-point algorithm with full-Newton steps for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems based on a kernel function, J. Appl. Math. Comput., 50 (2016), 15-37.
doi: 10.1007/s12190-014-0856-4. |
[6] |
Y. Q. Bai, M. El Ghami and C. Roos,
A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM J. Optim., 13 (2003), 766-782.
doi: 10.1137/S1052623401398132. |
[7] |
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. |
[8] |
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. |
[9] |
M. Bouafia, D. Benterki and A. Yassine,
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. |
[10] |
Ch. Chennouf, Extension d'une Méthode de Point Intérieur au Problème Complémentaire Linéaire avec $P_{\ast }\left(\kappa \right)-$matrice, Mémoire de Master $2, $ Université Ferhat Abbas Sétif1, Algérie, 2018. |
[11] |
G. M. Cho and M. K. Kim,
A new large-update interior point algorithm for $P_{\ast}\left(\kappa \right)$ LCPs based on kernel functions, Appl. Math. Comput., 182 (2006), 1169-1183.
doi: 10.1016/j.amc.2006.04.060. |
[12] |
G. M. Cho,
A new large–update interior point algorithm for $P_{\ast}\left(\kappa \right)$ linear complementarity problems, J. Comput. Appl. Math., 216 (2008), 256-278.
doi: 10.1016/j.cam.2007.05.007. |
[13] |
G. M. Cho,
Large–update interior point algorithm for $P_{\ast }$-linear complementarity problem, J. Inequalities Appl., 363 (2014), 1-12.
doi: 10.1186/1029-242X-2014-363. |
[14] |
R. W. Cottle, J. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992.
![]() ![]() |
[15] |
M. El Ghami and T. Steihaug,
Kernel–function based primal-dual algorithms for $P_{\ast }\left(\kappa \right) $ linear comlementarity problem, RAIRO-Oper. Res., 44 (2010), 185-205.
doi: 10.1051/ro/2010014. |
[16] |
M. El Ghami and G. Q. Wang, Interior–point methods for $P_{\ast}\left(\kappa \right) $ linear comlementarity problem based on generalized trigonometric barrier function, International Journal of Applied Mathematics, (2017), 11–33.
doi: 10.12732/ijam.v30i1.2. |
[17] |
S. Fathi-Hafshejani and A. Fakharzadeh Jahromi,
An interior point method for $P_{\ast}\left(\kappa \right) $-horizontal linear complementarity problem based on a new proximity function, J. Appl. Math. Comput., 62 (2020), 281-300.
doi: 10.1007/s12190-019-01284-9. |
[18] |
S. Fathi-Hafshejani, H. Mansouri and M. Peyghamic,
An interior-point algorithm for $P_{\ast }\left(\kappa \right) $-linear complementarity problem based on a new trigonometric kernel functions, Journal of Mathematical Modeling, 5 (2017), 171-197.
|
[19] |
P. Ji, M. Zhang and X. Li,
A Primal-dual large-update interior-point algorithm for $P_{\ast}(\kappa)$-LCP based on a new class of kernel functions, Acta Mathematicae Applicatae Sinica, English Series, 34 (2018), 119-134.
doi: 10.1007/s10255-018-0729-y. |
[20] |
M. Kojima, N. Megiddo, T. Noma and A. Yoshise,
A unified approach to interior point algorithms for linear complementarity problems: A summary, Operations Research Letters, 10 (1991), 247-254.
doi: 10.1016/0167-6377(91)90010-M. |
[21] |
Y. Lee, Y. Cho and G. Cho, Kernel function based interior-point methods for horizontal linear complementarity problems, Journal of Inequalities and Applications, (2013), Article number: 215.
doi: 10.1186/1029-242X-2013-215. |
[22] |
G. Lesaja and C. Roos,
Unified analysis of kernel–based interior–point methods for $P_{\ast } (\kappa) $-LCP, SIAM Journal on Optimization, 20 (2010), 3014-3039.
doi: 10.1137/090766735. |
[23] |
J. Peng, C. Roos and T. Terlaky,
Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program., Ser., 93 (2002), 129-171.
doi: 10.1007/s101070200296. |
[24] |
Z. G. Qian and Y. Q. Bai,
Primal-dual interior point algorithm with dynamic step-size based on kernel function for linear programming, Journal of Shanghai University (English Edition), 9 (2005), 391-396.
doi: 10.1007/s11741-005-0021-2. |
[25] |
M. Reza Peyghami, S. Fathi Hafshejani and L. Shirvani,
Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, 2 (2014), 74-85.
doi: 10.1016/j.cam.2013.04.039. |
[26] |
C. Roos, T. Terlaky and J. Ph. Vial, Theory and Algorithms for Linear optimization. An Interior Point Approach, John Wiley and Sons, Chichester, 1997. |
[27] |
G. Q. Wang and Y. Q. Bai,
Polynomial interior-point algorithm for $P_{\ast}\left(\kappa \right)$ horizontal linear complementarity problem, J. Comput. Appl. Math., 233 (2009), 248-263.
doi: 10.1016/j.cam.2009.07.014. |
[28] |
S. J. Wright, Primal-Dual Interior Point Methods, SIAM, 1997.
doi: 10.1137/1.9781611971453. |
show all references
References:
[1] |
M. Achache,
Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast }\left(\kappa \right)$-LCP, RAIRO-Oper. Res., 50 (2016), 131-143.
doi: 10.1051/ro/2015020. |
[2] |
M. Achache and N. Tabchouche,
Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function, Optimization, 67 (2018), 1211-1230.
doi: 10.1080/02331934.2018.1462356. |
[3] |
S. Asadi and H. Mansouri,
Polynomial interior-point algorithm for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, Numer. Algorithms, 63 (2013), 385-398.
doi: 10.1007/s11075-012-9628-0. |
[4] |
S. Asadi, H. Mansouri and M. Zangiabadi,
A class of path-following interior-point methods for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, J. Oper Res Soc China, 3 (2015), 17-30.
doi: 10.1007/s40305-015-0070-6. |
[5] |
S. Asadi, M. Zangiabadi and H. Mansouri,
An infeasible interior-point algorithm with full-Newton steps for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems based on a kernel function, J. Appl. Math. Comput., 50 (2016), 15-37.
doi: 10.1007/s12190-014-0856-4. |
[6] |
Y. Q. Bai, M. El Ghami and C. Roos,
A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM J. Optim., 13 (2003), 766-782.
doi: 10.1137/S1052623401398132. |
[7] |
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. |
[8] |
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. |
[9] |
M. Bouafia, D. Benterki and A. Yassine,
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. |
[10] |
Ch. Chennouf, Extension d'une Méthode de Point Intérieur au Problème Complémentaire Linéaire avec $P_{\ast }\left(\kappa \right)-$matrice, Mémoire de Master $2, $ Université Ferhat Abbas Sétif1, Algérie, 2018. |
[11] |
G. M. Cho and M. K. Kim,
A new large-update interior point algorithm for $P_{\ast}\left(\kappa \right)$ LCPs based on kernel functions, Appl. Math. Comput., 182 (2006), 1169-1183.
doi: 10.1016/j.amc.2006.04.060. |
[12] |
G. M. Cho,
A new large–update interior point algorithm for $P_{\ast}\left(\kappa \right)$ linear complementarity problems, J. Comput. Appl. Math., 216 (2008), 256-278.
doi: 10.1016/j.cam.2007.05.007. |
[13] |
G. M. Cho,
Large–update interior point algorithm for $P_{\ast }$-linear complementarity problem, J. Inequalities Appl., 363 (2014), 1-12.
doi: 10.1186/1029-242X-2014-363. |
[14] |
R. W. Cottle, J. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992.
![]() ![]() |
[15] |
M. El Ghami and T. Steihaug,
Kernel–function based primal-dual algorithms for $P_{\ast }\left(\kappa \right) $ linear comlementarity problem, RAIRO-Oper. Res., 44 (2010), 185-205.
doi: 10.1051/ro/2010014. |
[16] |
M. El Ghami and G. Q. Wang, Interior–point methods for $P_{\ast}\left(\kappa \right) $ linear comlementarity problem based on generalized trigonometric barrier function, International Journal of Applied Mathematics, (2017), 11–33.
doi: 10.12732/ijam.v30i1.2. |
[17] |
S. Fathi-Hafshejani and A. Fakharzadeh Jahromi,
An interior point method for $P_{\ast}\left(\kappa \right) $-horizontal linear complementarity problem based on a new proximity function, J. Appl. Math. Comput., 62 (2020), 281-300.
doi: 10.1007/s12190-019-01284-9. |
[18] |
S. Fathi-Hafshejani, H. Mansouri and M. Peyghamic,
An interior-point algorithm for $P_{\ast }\left(\kappa \right) $-linear complementarity problem based on a new trigonometric kernel functions, Journal of Mathematical Modeling, 5 (2017), 171-197.
|
[19] |
P. Ji, M. Zhang and X. Li,
A Primal-dual large-update interior-point algorithm for $P_{\ast}(\kappa)$-LCP based on a new class of kernel functions, Acta Mathematicae Applicatae Sinica, English Series, 34 (2018), 119-134.
doi: 10.1007/s10255-018-0729-y. |
[20] |
M. Kojima, N. Megiddo, T. Noma and A. Yoshise,
A unified approach to interior point algorithms for linear complementarity problems: A summary, Operations Research Letters, 10 (1991), 247-254.
doi: 10.1016/0167-6377(91)90010-M. |
[21] |
Y. Lee, Y. Cho and G. Cho, Kernel function based interior-point methods for horizontal linear complementarity problems, Journal of Inequalities and Applications, (2013), Article number: 215.
doi: 10.1186/1029-242X-2013-215. |
[22] |
G. Lesaja and C. Roos,
Unified analysis of kernel–based interior–point methods for $P_{\ast } (\kappa) $-LCP, SIAM Journal on Optimization, 20 (2010), 3014-3039.
doi: 10.1137/090766735. |
[23] |
J. Peng, C. Roos and T. Terlaky,
Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program., Ser., 93 (2002), 129-171.
doi: 10.1007/s101070200296. |
[24] |
Z. G. Qian and Y. Q. Bai,
Primal-dual interior point algorithm with dynamic step-size based on kernel function for linear programming, Journal of Shanghai University (English Edition), 9 (2005), 391-396.
doi: 10.1007/s11741-005-0021-2. |
[25] |
M. Reza Peyghami, S. Fathi Hafshejani and L. Shirvani,
Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, 2 (2014), 74-85.
doi: 10.1016/j.cam.2013.04.039. |
[26] |
C. Roos, T. Terlaky and J. Ph. Vial, Theory and Algorithms for Linear optimization. An Interior Point Approach, John Wiley and Sons, Chichester, 1997. |
[27] |
G. Q. Wang and Y. Q. Bai,
Polynomial interior-point algorithm for $P_{\ast}\left(\kappa \right)$ horizontal linear complementarity problem, J. Comput. Appl. Math., 233 (2009), 248-263.
doi: 10.1016/j.cam.2009.07.014. |
[28] |
S. J. Wright, Primal-Dual Interior Point Methods, SIAM, 1997.
doi: 10.1137/1.9781611971453. |
Inn | |||||
Time |
Inn | |||||
Time |
Inn | |||||
Time |
Inn | |||||
Time |
Inn | Time | Inn | Time | Inn | Time | |
Inn | Time | Inn | Time | Inn | Time | |
Inn | Time | Inn | Time | Inn | Time | |
Inn | Time | Inn | Time | Inn | Time | |
[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] |
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, 2022 doi: 10.3934/naco.2022003 |
[3] |
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 |
[4] |
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 |
[5] |
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 |
[6] |
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 |
[7] |
Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911 |
[8] |
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 |
[9] |
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 |
[10] |
Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 |
[11] |
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 |
[12] |
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 |
[13] |
Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial and Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153 |
[14] |
Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259 |
[15] |
Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53 |
[16] |
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 |
[17] |
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 |
[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] |
Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial and Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569 |
[20] |
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 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]