A full step infeasible interior-point method for Cartesian \(P_{*}(\kappa )\)

详细信息    查看全文

• 作者：B. Kheirfam
• 关键词：Cartesian \(P_*(\kappa )\) ; linear complementarity problem ; Infeasible interior ; point method ; Polynomial complexity
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：10
• 期：3
• 页码：591-603
• 全文大小：475 KB
• 参考文献：1.Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, Oxford Science Publications, New York (1994)MATH
  2.Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239(1), 117–129 (2002)CrossRef MathSciNet MATH
  3.Faybusovich, L.: Euclidean Jordan algebras and interior-point algorithms. Positivity 1(4), 331–357 (1997)CrossRef MathSciNet MATH
  4.Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov–Todd step infeasible interior-point method for symmetric optimization. Eur. J. Oper. Res. 214(3), 473–484 (2011)CrossRef MathSciNet MATH
  5.Kheirfam, B.: An interior-point method for Cartesian \(P_*(\kappa )\) -linear complementarity problem over symmetric cones. ORiON 30(1), 41–58 (2014)CrossRef
  6.Kheirfam, B.: A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems. J. Optim. Theory Appl. 161(3), 853–869 (2014)CrossRef MathSciNet MATH
  7.Kheirfam, B., Mahdavi-Amiri, N.: A full Nesterov–Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem. Bull. Iran. Math. Soc. 40(3), 541–564 (2014)MathSciNet MATH
  8.Kheirfam, B., Mahdavi-Amiri, N.: A new interior-point algorithm based on modified Nesterov–Todd direction for symmetric cone linear complementarity problem. Optim. Lett. 8(3), 1017–1029 (2014)CrossRef MathSciNet MATH
  9.Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538. Springer, Berlin (1991)CrossRef
  10.Liu, Z., Sun, W.: An infeasible interior-point algorithm with full-Newton step for linear optimization. Numer. Algorithms 46, 173–188 (2007)CrossRef MathSciNet MATH
  11.Luo, Z.Y., Xiu, N.H.: Path-following interior point algorithms for the Cartesian \(P_*(\kappa )\) -LCP over symmetric cones. Sci. China Ser. A: Math. 52(8), 1769–1784 (2009)CrossRef MathSciNet MATH
  12.Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1–42 (1997)CrossRef MathSciNet 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)CrossRef MathSciNet MATH
  14.Roos, C.: An improved and simplified full-Newton step \(O(n)\) infeasible interior-point method for linear optimization. SIAM J. Optim. 25(1), 102–114 (2015)CrossRef MathSciNet
  15.Roos, C., Terlaky, T., Vial, J.-P.H.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)MATH
  16.Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96(3), 409–438 (2003)CrossRef MathSciNet MATH
  17.Vieira, M.V.C.: Jordan algebraic approach to symmetric optimization. Ph.D. thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands (2007)
  18.Wang, G.Q., Bai, Y.Q.: A class of polynomial interior-point algorithms for the Cartesian \(P\) -Matrix linear complementarity problem over symmetric cones. J. Optim. Theory Appl. 152(3), 739–772 (2012)CrossRef MathSciNet MATH
  19.Wang, G.Q., Kong, L.C., Tao, J.Y., Lesaja, G.: Improved complexity analysis of full Nesterov–Todd step feasible interior-point method for symmetric optimization. J. Optim. Theory Appl. doi:10.​1007/​s10957-014-0696-2
  20.Wang, G.Q., Lesaja, G.: Full Nesterov–Todd step feasible interior-point method for the Cartesian \(P_*(\kappa )\) -SCLCP. Optim. Methods Softw. 28(3), 600–618 (2013)CrossRef MathSciNet MATH
  21.Wang, G.Q., Yu, C.J., Teo, K.L.: A new full Nesterov–Todd step feasible interior-point method for convex quadratic symmetric cone optimization. Appl. Math. Comput. 221, 329–343 (2013)CrossRef MathSciNet
  22.Zhang, L., Sun, L., Xu, Y.: Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming. Optimization 62(2), 169–191 (2013)CrossRef MathSciNet MATH
  
• 作者单位：B. Kheirfam (1)
  
  1. Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

In this paper, a new full Nesterov–Todd step infeasible interior-point method for Cartesian \(P_*(\kappa )\) linear complementarity problem over symmetric cone is considered. Our algorithm starts from a strictly feasible point of a perturbed problem, after a full Nesterov–Todd step for the new perturbed problem the obtained strictly feasible iterate is close to the central path of it, where closeness is measured by some merit function. Furthermore, the complexity bound of the algorithm is the best available for infeasible interior-point methods.