یک روش نقطه درونی نشدنی با گام کامل NT با پیچیدگی (O(n برای حاصل‌ضرب دکارتی P_*(k) –HLCP روی مخروطهای متقارن با استفاده از تحدب نمایی
محورهای موضوعی : آماربهروز خیرفام 1 , معصومه حقیقی 2
1 - گروه ریاضی کاربردی (بهینه سازی)، دانشکده علوم پایه، دانشگاه شهید مدنی آذربایجان، تبریز، ایران
2 - گروه ریاضی کاربردی (بهینه سازی)، دانشکده علوم پایه، دانشگاه شهید مدنی آذربایجان، تبریز، ایران
کلید واژه: Horizontal linear complementar, Cartesian P_*(k), infeasible interior-point meth, polynomial complexity, symmetric cone,
چکیده مقاله :
در این مقاله، با استفاده از خاصیت تحدب نمایی یک تابع مانع، یک روش نقطه درونی نشدنی را برای مساله حاصل‌ضرب دکارتی مکملی خطی افقی روی مخروطهای متقارن ارایه میدهیم. در این روش، از گام‌های کامل نسترو-تاد استفاده کرده و نشان میدهیم که الگوریتم منظور شده خوش تعریف است. کران تکرار الگوریتم با بهترین کران تکرار شناخته شده برای مسایل حاصل‌ضرب دکارتی مکملی خطی افقی روی مخروطهای متقارن منطبق است. هزینه اجرای یک تکرار عملیات حسابی است.
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.
[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#