A full NT-step O(n) infeasible interior-point method for Cartesian P_*(k) –HLCP over symmetric cones using exponential convexity

Subject Areas : Statistics

B.  Kheirfam ¹ (Professor, Department of Applied Mathematics (Optimization), Azarbaijan Shahid Madani University, Tabriz, Iran)
M.  Haghighi ² (Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran)

Received: 2017-12-12 Accepted : 2018-09-03 Published : 2018-11-22

Keywords: مساله‌ مکملی خطی افقی, حاصل‌ضرب دکارتی, روش نقطه درونی نشدنی, پیچیدگی چندجمله‌ای, مخروط متقارن,

Abstract :

In this paper, by using the exponential convexity property of a barrier function, we propose an infeasible interior-point method for Cartesian P_*(k) horizontal linear complementarity problem over symmetric cones. The method uses Nesterov and Todd full steps, and we prove that the proposed algorithm is well define. The iteration bound coincides with the currently best iteration bound for the Cartesian P_*(k) horizontal linear complementarity problem over symmetric cones.

References:

[1]  G. Dantzig,   “Linear Programming and Extensions,” Princeton University Press, Princeton, N.J. , (1963)  

 

[2]  V. Klee, J.  Minty, “How good is the simplex algorithm? In Inequalities,” III (Proc. Third Sympos.,           Univ. California, Los Angeles, calif., 1969; dedicated to the memory of Theodore S. Motzkin), pp. 159-175. Academic Press, New York, (1972)

 

[3]  L.G. Khachiyan, “A polynomial algorithm in linear programming,” Dokl. Akad. Nauk SSSR , vol  244, pp. 1093-1096,  (1979)

 

[4]  N. Karmarkar,   “New polynomial-time algorithm for linear programming,”  Combinattorica,  vol 4, pp. 373-395, (1984)

 

[5]  M. Kojima,  N.  Megiddo, S. Mizuno, “A primal-dual infeasible-interiorpoint algorithm for linear programming,”  Mathematical Programming  vol 61, pp. 263-280,  (1993)

 

[6]  M. Kojima,  N. Megiddo, T. Noma,  A. Yoshise,  “A Unified Approach to Interior Point                                                            Algorithms for Linear Complementarity Problems,”  Lecture Notes in Comput. Sci. 538, (1991)       Springer-Verlag, Berlin.

  [7]  F. Gurtuna, C. Petra, F.A. Potra, O.

Shevchenko, A. Vancea,“Corrector-predictor methods  for sufficient linear complementarity problems,                                                          ”  Computational Optimization and Applications,  vol 48, pp. 453-485, (2011)

[8]  B.  Kheirfam,   “A predictor-corrector interior-point algorithm for -horizontal linear             complementarity problem,”  Numerical  Algorithms, vol 66,  pp. 349-361,  (2014)   

[9]  Z.Y. Luo,  N.H.  Xiu,   “Path-following interior point algorithms for the Cartesian -LCP       over symmetric cones,”  Science in China Series A: Mathematics,  vol. 52, pp. 1769-1784,  (2009)

[10]  S.H.  Schmieta,  F.  Alizadeh,  “Extension of primal-dual interior-point algorithm to symmetric      cones,”  Mathematical  Programming, vol 96,  pp. 409-438,  (2003)                                                    

[11]  B. Kheirfam,   “An interior-point method for Cartesian -linear complementarity problem  over symmetric cones,”  ORiON  vol 30, pp. 41-58,  (2014)

 

[12]  W. Wang, H. Bi,  H.  Liu,  “A full-Newton step interior-point algorithm for linear optimization based on a finite barrier,”  Operations  Research  Letters., vol 44, pp. 750-753, (2016)

 

[13]  J. Peng,  C. , Roos, T. Terlaky,   “Self-regular functions and new search directions for linear and        semidefinite optimization,”  Mathematical  Programming,  vol 93, pp. 129-171, (2002)

 

[14]  G. Q. Wang,  Y. Q. Bai,   “A class of polynomial interior-point algorithms for the Cartesian -Matrix linear complementarity problem over symmetric cones,”  Journal of  Optimization Theory  and Applications,  vol 152, pp. 739-772,  (2012) 

 

[15]  G. Lesaja, G.Q.  Wang, D.T.  Zhu,  “Interior-point methods for Cartersian -linear   complementarity problems over symmetric cones based on the eligible kernel functions,”  Optimization              Methods  and  Software,  vol 27, pp. 827-843,  (2012)

 

[16] B.  Kheirfam,  “A generic interior-point algorithm for monotone symmetric cone linear  complementarity problems based on a new kernel function,”  Journal of  Mathematical  Modelling  and  Algorithms in  Operations  Research, vol 13, pp. 471-491, (2014)

 

[17]  C.  Roos,  “A full-Newton step  infeasible interior-point algorithm for linear  optimization,”  SIAM Journal on  Optimization,  vol 16, pp. 1110-1136, (2006)

 

[18]  B. Kheirfam,  “A new complexity analysis for full-Newton step infeasible interior-point  algorithm for horizontal linear complementarity problems,”  Journal of  Optimization Theory  and Applications,  vol 161, pp. 853-869,  (2014)

 

[19]  C.  Roos,   “An improved and simplified full-Newton step  infeasible interior-point method for linear optimization,”  SIAM Journal on Optimization,  vol 25, pp. 102-114,  (2015)

 

[20] B.  Kheirfam,   “A full step infeasible interior-point method for Cartesian -SCLCP,” Optimization  Letters,  vol10, pp. 591-603,  (2016)

   

[21]  B. Kheirfam,   “An improved full-Newton step  infeasible interior-point method for  horizontal linear complementarity problem,”  Numerical  Algorithms, vol 71, pp. 491-503,  (2016)

 

[22]  J. Faraut,  A.  Korányi, “Analysis on symmetric cones, Oxford Mathematical Monographs,”  The       Clarendon Press Oxford University Press, New York, (1994)

 

[23]  L.  Faybusovich,  “A Jordan-algebraic approach to potential-reduction algorithms,”  Mathematics  Z., vol 239, pp. 117-129, (2002)

 

[24] B.  Kheirfam,  N. Mahdavi-Amiri, “A new interior-point algorithm based on modified  Nesterov-Todd direction for symmetric cone linear complementarity problem,”  Optimization  Letters, vol 8,      pp. 1017-1029,  (2014)

 

[25]  B.  Kheirfam,  N.  Mahdavi-Amiri,  “ An infeasible interior-point algorithm based on modified  Nesterov and Todd directions for symmetric linear complementarity problem,”  Optimization  vol 64, pp.        1577-1591,  (2015)

 

[26]  B. Kheirfam,  “An improved and modified infeasible interior-point method for symmetric optimization,”  Asian-European Journal of Mathematics,  vol 9, 1650059 (13 pages),  (2016)

 

[27]  J. Peng,  C.  Roos, T. Terlaky, “Self-regularity: a new paradigm for primal-dual interior-point algorithms,”  Princeton Series in Applied Mathematics, Princeton University Press, Princeton,  (2002)

 

[28]  Y. Q. Bai,  M. El Ghami,  C.  Roos,   “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,”  SIAM  Journal on Optimization, vol 15, pp. 101-128, ( 2004)     

[29]  M. V. C. Vieira,   “Jordan algebraic approach to symmetric optimization,”  Ph.D. thesis, Delft  University of Technology,  (2007)

     

[30]  G. Q. Wang,  Y. Q. Bai,   “A new full Nesterov-Todd step primal-dual path-following  interior-point algorithm for symmetric optimization,”  Journal of Optimization Theory and Applications, vol 154, pp.  966-985,  (2012)

 

[31]  F.A. Potra,  J.  Stoer, “On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP,”  SIAM Journal on Optimization, vol 20,  pp. 1333-1363,  (2009)

[32]  Gu, G.,  “Full-step interior-point methods for symmetric optimization,”  Ph.D. thesis, Delft              University of Technology, 2009#