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

Behrouz Kheirfam

doi:10.3934/naco.2014.4.141

Article Contents

2014, Volume 4, Issue 2: 141-150. Doi: 10.3934/naco.2014.4.141

This issue Previous Article Existence and convergence results for best proximity points in cone metric spaces Next Article Auxiliary signal design for failure detection in differential-algebraic equations

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

Behrouz Kheirfam^1,

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

Received: June 2013

Revised: April 2014

Published: May 2014

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C33, Secondary: 90C51.

Citation:

Related Papers

Cited by

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.