Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C33, Secondary: 90C51.


    \begin{equation} \\ \end{equation}
  • [1]

    M. Achache, A weighted-path-following method for the linear complementarity problem, Studia Univ. Babes-Bolyai, Informatica, XLIX (1) (2004), 61-73.


    Z. Darvay, New interior-point algorithms in linear programming, Adv. Model. Optim., 5 (2003), 51-92.


    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.


    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.


    L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Mathematicsche Zeitschrift, 239 (2002), 117-129.doi: 10.1007/s002090100286.


    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.


    L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity, 1 (1997), 331-357.doi: 10.1023/A:1009701824047.


    O. Güler, Barrier functions in interior-point methods, Math. Oper. Res., 21 (1996), 860-885.doi: 10.1287/moor.21.4.860.


    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.


    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.


    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.


    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.


    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.


    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.


    B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones, SIAM J. Optim., 16 (2006), 1211-1229.doi: 10.1137/040606557.


    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.


    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.


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(83) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint