American Institute of Mathematical Sciences

2014, 4(2): 141-150. doi: 10.3934/naco.2014.4.141

A weighted-path-following method for symmetric cone linear complementarity problems

 1 Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R., Iran

Received  June 2013 Revised  April 2014 Published  May 2014

In this paper a weighted-path-following interior-point algorithm for linear complementarity problem over symmetric cones is proposed that uses new search directions. The complexity results of the new algorithm derived and proved that the proposed algorithm has quadratically convergent with polynomial-time. We conclude that following the central path yields to the best iteration bound in this case as well.
Citation: Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
References:
 [1] M. Achache, A weighted-path-following method for the linear complementarity problem, Studia Univ. Babes-Bolyai, Informatica, XLIX (1) (2004), 61-73. [2] Z. Darvay, New interior-point algorithms in linear programming, Adv. Model. Optim., 5 (2003), 51-92. [3] J. Ding and T. Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems, Arabian Journal for Science and Engineering, 15 (1990), 679-685. [4] J. Faraut and A. Korányi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, Oxford Science Publications, 1994. [5] L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129. doi: 10.1007/s002090100286. [6] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2. [7] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357. doi: 10.1023/A:1009701824047. [8] O. Güler, Barrier functions in interior-point methods, Math. Oper. Res., 21 (1996), 860-885. doi: 10.1287/moor.21.4.860. [9] B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial, Primal-dual target-following algorithms for linear programming, Anna. Oper. Res., 62 (1996), 197-231. doi: 10.1007/BF02206817. [10] B. Kheirfam, A full Nesterov-Todd step feasible weighted primal-dual interior-point algorithm for symmetric optimization, J. Oper. Res. Soci. of China, 1 (2013), 467-481. [11] M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997), 86-125. doi: 10.1137/S1052623494269035. [12] G. Lesaja and C. Roos, Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones, J. Optim. Theory Appl., 150 (2011), 444-474. doi: 10.1007/s10957-011-9848-9. [13] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997), 1-42. doi: 10.1287/moor.22.1.1. [14] Y. E. Nesterov, M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8 (1998), 324-364. doi: 10.1137/S1052623495290209. [15] B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229. doi: 10.1137/040606557. [16] C. Roos and D. den Hertog, A polynomial method of approximate weighted centers for linear programming, Technical Report 89-13, Faculty of Technical Mathematics and Informatics, TU Delft, NL-2628 BL Delft, The Netherlands, 1994. [17] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones, Math. Program., 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z. [18] S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564. doi: 10.1287/moor.26.3.543.10582. [19] J. F. Sturm, Similarity and other spectral relations for symmetric cones, Algebra Appl., 312 (2000), 135-154. doi: 10.1016/S0024-3795(00)00096-3. [20] 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. [21] G. Q. Wang and Y. Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization, J. Optim. Theory Appl., 154 (2012), 966-985. doi: 10.1007/s10957-012-0013-x.

show all references

References:
 [1] M. Achache, A weighted-path-following method for the linear complementarity problem, Studia Univ. Babes-Bolyai, Informatica, XLIX (1) (2004), 61-73. [2] Z. Darvay, New interior-point algorithms in linear programming, Adv. Model. Optim., 5 (2003), 51-92. [3] J. Ding and T. Y. Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems, Arabian Journal for Science and Engineering, 15 (1990), 679-685. [4] J. Faraut and A. Korányi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, Oxford Science Publications, 1994. [5] L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129. doi: 10.1007/s002090100286. [6] L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86 (1997), 149-175. doi: 10.1016/S0377-0427(97)00153-2. [7] L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357. doi: 10.1023/A:1009701824047. [8] O. Güler, Barrier functions in interior-point methods, Math. Oper. Res., 21 (1996), 860-885. doi: 10.1287/moor.21.4.860. [9] B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial, Primal-dual target-following algorithms for linear programming, Anna. Oper. Res., 62 (1996), 197-231. doi: 10.1007/BF02206817. [10] B. Kheirfam, A full Nesterov-Todd step feasible weighted primal-dual interior-point algorithm for symmetric optimization, J. Oper. Res. Soci. of China, 1 (2013), 467-481. [11] M. Kojima, S. Shindoh and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997), 86-125. doi: 10.1137/S1052623494269035. [12] G. Lesaja and C. Roos, Kernel-based interior-point methods for monotone linear complementarity problems over symmetric cones, J. Optim. Theory Appl., 150 (2011), 444-474. doi: 10.1007/s10957-011-9848-9. [13] Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22 (1997), 1-42. doi: 10.1287/moor.22.1.1. [14] Y. E. Nesterov, M. J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8 (1998), 324-364. doi: 10.1137/S1052623495290209. [15] B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229. doi: 10.1137/040606557. [16] C. Roos and D. den Hertog, A polynomial method of approximate weighted centers for linear programming, Technical Report 89-13, Faculty of Technical Mathematics and Informatics, TU Delft, NL-2628 BL Delft, The Netherlands, 1994. [17] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithm to symmetric cones, Math. Program., 96 (2003), 409-438. doi: 10.1007/s10107-003-0380-z. [18] S. H. Schmieta and F. Alizadeh, Associative and Jordan algebras and polynomial time interior-point algorithms for symmetric cones, Math. Oper. Res., 26 (2001), 543-564. doi: 10.1287/moor.26.3.543.10582. [19] J. F. Sturm, Similarity and other spectral relations for symmetric cones, Algebra Appl., 312 (2000), 135-154. doi: 10.1016/S0024-3795(00)00096-3. [20] 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. [21] G. Q. Wang and Y. Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization, J. Optim. Theory Appl., 154 (2012), 966-985. doi: 10.1007/s10957-012-0013-x.
 [1] 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 [2] 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 [3] 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 [4] Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 445-467. doi: 10.3934/naco.2021017 [5] 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 [6] Hongwei Jiao, Junqiao Ma, Peiping Shen, Yongjian Qiu. Effective algorithm and computational complexity for solving sum of linear ratios problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022135 [7] 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 [8] Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145 [9] Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete and Continuous Dynamical Systems, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653 [10] Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 [11] Mariantonia Cotronei, Tomas Sauer. Full rank filters and polynomial reproduction. Communications on Pure and Applied Analysis, 2007, 6 (3) : 667-687. doi: 10.3934/cpaa.2007.6.667 [12] Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks and Heterogeneous Media, 2010, 5 (1) : 143-162. doi: 10.3934/nhm.2010.5.143 [13] Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44. [14] 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 [15] 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 [16] Tijana Levajković, Hermann Mena, Amjad Tuffaha. The stochastic linear quadratic optimal control problem in Hilbert spaces: A polynomial chaos approach. Evolution Equations and Control Theory, 2016, 5 (1) : 105-134. doi: 10.3934/eect.2016.5.105 [17] Louis Caccetta, Ian Loosen, Volker Rehbock. Computational aspects of the optimal transit path problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 95-105. doi: 10.3934/jimo.2008.4.95 [18] 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 [19] 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 [20] Kohei Ueno. Weighted Green functions of nondegenerate polynomial skew products on $\mathbb{C}^2$. Discrete and Continuous Dynamical Systems, 2011, 31 (3) : 985-996. doi: 10.3934/dcds.2011.31.985

Impact Factor: