详细信息    查看全文

• 作者：Soodabeh Asadi ; Hossein Mansouri…
• 关键词：Horizontal linear complementarity problem ; Infeasible interior ; point method ; Central path ; Kernel function
• 刊名：Journal of the Operations Research Society of China
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：4
• 期：1
• 页码：77-96
• 全文大小：493 KB
• 参考文献：1.Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984)MathSciNet CrossRef MATH
  2.Stoer, J., Wechs, M.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Math. Program. Ser. A 83(3), 407–423 (1998)MathSciNet MATH
  3.Asadi, S., Mansouri, H.: A full-Newton step infeasible-interior-point algorithm for \(P_*(\kappa )\) -horizontal linear complementarity problems. Yugosl. J. Oper. Res. 25(1), 57–72 (2015)MathSciNet CrossRef
  4.Asadi, S., Mansouri, H.: Polynomial interior-point algorithm for \(P_*(\kappa )\) horizontal linear complementarity problems. Numer. Algorithms 63(2), 385–398 (2013)MathSciNet CrossRef MATH
  5.Asadi, S., Mansouri, H., Zangiabadi, M.: A class of path-following interior-point methods for \(P_*(\kappa )\) -horizontal linear complementarity problems. J. Oper. Res. Soc. China 3(1), 17–30 (2015)MathSciNet CrossRef MATH
  6.Gurtuna, F., Petra, C., Potra, F.A., Shevehenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48(3), 453–485 (2011)MathSciNet CrossRef MATH
  7.Huang, Z.H.: Polynomiality of high-order feasible interior point method for solving the horizontal linear complementarity problems. J. Syst. Sci. Math. Sci. 20(4), 432–438 (2000)MATH
  8.Mansouri, H., Asadi, S.: A quadratically convergent \(O(\sqrt{n})\) interior-point algorithm for the \(P_*(\kappa )\) -matrix horizontal linear complementarity problem. J. Sci. Islam. Repub. Iran 23(3), 237–244 (2012)MathSciNet
  9.Wang, G.Q., Bai, Y.Q.: Polynomial interior-point algorithms for \(P_*(\kappa )\) horizontal linear complementarity problem. J. Comput. Appl. Math. 233(2), 248–263 (2009)MathSciNet CrossRef MATH
  10.Xiu, N., Zhang, J.: A smoothing Gauss-Newton method for the generalized HLCP. J. Comput. Appl. Math. 129(1–2), 195–208 (2001)MathSciNet CrossRef MATH
  11.Wang, G.Q., Yu, C.J., Teo, K.L.: A full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\) -linear complementarity problem. J. Glob. Optim. 59(1), 81–99 (2014)MathSciNet CrossRef MATH
  12.Wang, G.Q., Li, M.M., Fan, X.J., Wang, D.Z.: New complexity analysis of a full-Newton step feasible interior-point algorithm for \(P_*(\kappa )\) -LCP. Optim. Lett. 9(6), 1105–1119 (2015)MathSciNet CrossRef MATH
  13.Roos, C.: A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110–1136 (2006)MathSciNet CrossRef MATH
  14.Mansouri, H., Roos, C.: A new full-Newton step \(O (n)\) infeasible interior-point algorithm for semidefinite optimization. Numer. Algorithms 52(2), 225–255 (2009)MathSciNet CrossRef MATH
  15.Mansouri, H., Zangiabadi, M., Pirhaji, M.: A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems. Nonlinear Anal. Real World Appl. 12(1), 546–561 (2010)MathSciNet MATH
  16.Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step interior-point methods for symmetric optimization. Eur. J. Oper. Res. 214(3), 473–484 (2011)MathSciNet CrossRef MATH
  17.Bai, Y.Q., El Ghami, M., Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15(1), 101–128 (2004)MathSciNet CrossRef MATH
  18.Bai, Y.Q., Lesaja, G., Roos, C.: A new class of polynomial interior-point algorithms for \(P_*(\kappa )\) linear complementarity problems. Pac. J. Optim. 4(1), 19–41 (2008)MathSciNet MATH
  19.Zhang, L., Bai, Y.Q., Xu, Y.: A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function. Numer. Algorithms 61(1), 57–81 (2012)MathSciNet CrossRef MATH
  20.Darvay, Zs: New interior-point algorithms in linear optimization. Adv. Model. Optim. 5(1), 51–92 (2003)MathSciNet MATH
  21.Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems. Springer, Berlin (1991)CrossRef MATH
  22.El Ghami, M.: New primal-dual interior-point methods based on kernel functions. Ph.D Thesis, Delft University of Technology (2005)
  23.Pan, S., Li, X., He, S.: An infeasible primal-dual interior point algorithm for linear programs based on logarithmic equivalent transformation. J. Math. Anal. Appl. 314(2), 644–660 (2006)MathSciNet CrossRef MATH
  
• 作者单位：Soodabeh Asadi (1)
  Hossein Mansouri (1)
  Maryam Zangiabadi (1)
  
  1. Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, P.O. Box 115, Shahrekord, Iran
  
• 刊物主题：Operations Research, Management Science;
• 出版者：Springer Berlin Heidelberg
• ISSN：2194-6698

文摘

In this paper, we present a path-following infeasible interior-point method for \(P_*(\kappa )\) horizontal linear complementarity problems (\(P_*(\kappa )\)-HLCPs). The algorithm is based on a simple kernel function for finding the search directions and defining the neighborhood of the central path. The algorithm follows the central path related to some perturbations of the original problem, using the so-called feasibility and centering steps, along with only full such steps. Therefore, it has the advantage that the calculation of the step sizes at each iteration is avoided. The complexity result shows that the full-Newton step infeasible interior-point algorithm based on the simple kernel function enjoys the best-known iteration complexity for \(P_*(\kappa )\)-HLCPs.