-
Previous Article
Direct method to solve linear-quadratic optimal control problems
- NACO Home
- This Issue
-
Next Article
An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems
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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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. Google Scholar |
[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] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[2] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[3] |
Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247 |
[4] |
Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617 |
[5] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
[6] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
[7] |
Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133 |
[8] |
Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021014 |
[9] |
Vakhtang Putkaradze, Stuart Rogers. Numerical simulations of a rolling ball robot actuated by internal point masses. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 143-207. doi: 10.3934/naco.2020021 |
[10] |
Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933 |
[11] |
Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 |
[12] |
Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709 |
[13] |
Hyeong-Ohk Bae, Hyoungsuk So, Yeonghun Youn. Interior regularity to the steady incompressible shear thinning fluids with non-Standard growth. Networks & Heterogeneous Media, 2018, 13 (3) : 479-491. doi: 10.3934/nhm.2018021 |
[14] |
Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018 |
[15] |
Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022 |
[16] |
Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 |
[17] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[18] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
[19] |
Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 |
[20] |
Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]