An improved infeasible‎ ‎interior-point method for symmetric cone linear complementarity‎ ‎problem

Document Type : ORO2013

Authors

1 Faculty of‎ ‎Mathematical Sciences‎, ‎Sharif‎ ‎University of Technology‎, ‎Tehran‎, ‎Iran.

2 Azarbaijan Shahid Madani University, ‎Tabriz‎, ‎Iran.

Abstract

We present an improved version of a full Nesterov-Todd step infeasible interior-point method for linear complementarity
problem over symmetric cone (Bull. Iranian Math. Soc., 40(3), 541-564, (2014)). In the earlier version, each iteration consisted of one so-called feasibility step and a few -at most three - centering steps. Here, each iteration consists of only a feasibility step. Thus, the new algorithm demands less work in each iteration and admits a simple analysis of complexity bound. The complexity result coincides with the best-known iteration bound for infeasible interior-point methods.

Keywords

Main Subjects

References

J. Faraut and A. Koranyi, Analysis on Symmetric Cones, Oxford Math. Monogr., Clarendon Press, New York, 1994.
L. Faybusovich, Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math. 86 (1997), no. 1, 149--175.
L. Faybusovich, Euclidean Jordan algebras and interior-point algorithms, Positivity 1 (1997), no. 4, 331--357.
L. Faybusovich, A Jordan-algebraic approach to potential-reduction algorithms, Math. Z. 239 (2002), no. 1, 117--129.
G. Gu, M. Zangiabadi and C. Roos, Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, European J. Oper. Res. 214 (2011), no. 3, 473--484.
B. Kheirfam and N. Mahdavi-Amiri, A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optim. Lett. 8 (2014), no. 3, 1017--1029.
B. Kheirfam and N. Mahdavi-Amiri, An infeasible interior-point algorithm based on modi_ed Nesterov and Todd directions for symmetric linear complementarity problem, Optimization 64 (2015), no. 7, 1577--1591.
B. Kheirfam and N. Mahdavi-Amiri, A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem, Bull. Iranian Math. Soc. 40 (2014), no. 3, 541--564.
Y. E. Nesterov and M. J. Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22 (1997), no. 1, 1--42.
B. K. Rangarajan, Polynomial convergence of infeasible interior-point methods over symmetric cones, SIAM J. Optim. 16 (2006), no. 4, 1211--1229.
C. Roos, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim. 16 (2006), no. 4, 1110--1136.
C. Roos, T. Terlaky and J. Ph. Vial, Theory and Algorithms for Linear Optimization; An Interior-Point Approach, John Wiley & Sons, Chichester, 1997.
C. Roos, An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization, SIAM J. Optim. 25 (2015), no. 1, 102--114.
S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior-point algorithms to symmetric cones, Math. Program. 96 (2003), no. 3, 409--438.
J. F. Sturm, Similarity and other spectral relations for symmetric cones, Algebra Appl. 312 (2000), no. 1-3, 135--154.
Bulletin of the Iranian Mathematical Society
Volume 42, Issue 7 (Special Issue)
December 2016
Pages 55-66

Files

History

  • Receive Date: 08 March 2016
  • Revise Date: 13 June 2016
  • Accept Date: 14 December 2016

Share

How to cite

Statistics