A Predictor-Corrector Algorithm for P ∗(κ)-Linear Complementarity Problems Based on a Specific Self-Regular Proximity Function

详细信息    查看全文

• 作者：B. Kheirfam ; K. Ahmadi
• 关键词：Predictor ; corrector algorithm ; Self ; regular functions ; Linear complementarity problems ; Polynomial complexity ; 90C33 ; 90C51
• 刊名：Acta Mathematica Vietnamica
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：41
• 期：1
• 页码：103-120
• 全文大小：446 KB
• 参考文献：1.Bai, Y.Q., El Ghami, M., Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13(3), 766–782 (2003)CrossRef MathSciNet MATH
  2.Jansen, B., Roos, C., Terlaky, T., Ye, Y.: Improved complexity using high-order corrections for primal-dual Dikin affine scaling. Math. Program., Series B 76, 117–130 (1997)MathSciNet MATH
  3.Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Computer Science, vol. 538. Springer-Verlag, Berlin (1991)
  4.Lesaja, G., Roos, C.: Unified analysis of kernel-based interior point methods for P ∗(κ)-linear complementarity problems. SIAM J. Optim. 20(6), 3011–3039 (2010)CrossRef MathSciNet
  5.Mizuno, S., Todd, M.J., Ye, Y.: On adaptive-step primal-dual interior point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)CrossRef MathSciNet MATH
  6.Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual interior-Point Algorithms. Princeton University Press, Princeton, NJ (2002)
  7.Peng, J., Roos, C., Terlaky, T.: Self regular functions and new search directions for linear and semidefinite optimization. Math. Program. Series A 93, 129–171 (2002)CrossRef MathSciNet MATH
  8.Peng, J., Terlaky, T., Zhao, Y.: A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function. SIAM J. Optim. 15(4), 1105–1127 (2005)CrossRef MathSciNet MATH
  9.Renegar, J.: A mathematical view of interior point methods in convex optimization. MPS/ SIAM Ser. Optim. 3, SIAM, Philadelphia, 2001 62, 537–551 (1993)
  10.Stoer, J., Wechs, M.: The complexity of high-order predictor-corrector methods for solving sufficient linear complementarity problems. Optim. Methods Softw. 10, 393–417 (1998)CrossRef MathSciNet MATH
  11.Väliaho, H.: P ∗-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)MathSciNet MATH
  12.Ye, Y., Anstreicher, K.: On quadratic and \(O(\sqrt {n}L)\) convergence of a predictor-corrector algorithm for LCP. Math. Program., Series A 62, 537–551 (1993)CrossRef MathSciNet MATH
  13.Zhongyi, L., Wenyu, S.: An infeasible interior-point algorithm with full-Newton step for linear optimization. Numer. Algorithms 46, 173–188 (2007)CrossRef MathSciNet MATH
  
• 作者单位：B. Kheirfam (1)
  K. Ahmadi (1)
  
  1. Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Islamic Republic of Iran
  
• 刊物主题：Mathematics, general;
• 出版者：Springer Singapore
• ISSN：2315-4144

文摘

First-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior point methods. In Peng et al. (SIAM J. Optim. 15(4):1105–1127, 2005), based on a specific proximity function, a wide neighborhood of the central path is defined which matches the standard large neighborhood defined by the infinity norm. In this paper, we extend the predictor-corrector algorithm proposed for linear optimization in Peng et al. (SIAM J. Optim. 15(4):1105–1127, 2005) to P _∗(κ)-linear complementarity problems. Our algorithm performs two kinds of steps. In corrector steps, we use the specific self-regular proximity function to compute the search directions. The predictor step is the same as the predictor step of standard predictor-corrector method in the interior point method literature. We prove that our predictor-corrector algorithm has an \({\mathcal {O}}\left ((1+2\kappa )\sqrt {n}\log n\log \frac {(x^{0})^{T} s^{0}}{\epsilon }\right )\) iteration bound, which is the best known iteration complexity for problems of this type. Keywords Predictor-corrector algorithm Self-regular functions Linear complementarity problems Polynomial complexity