یک الگوریتم نقطه درونی شدنی برای مسائل مکمل خطی ترکیبی بر روی مخروط‌های متقارن
الموضوعات :مریم زنگی‌آبادی 1 , حسین منصوری 2 , محمد پیرحاجی 3
1 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
2 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
3 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
الکلمات المفتاحية: Mixed symmetric cone linear co, Feasible interior-point method, Convergence analysis, polynomial complexity,
ملخص المقالة :
در این مقاله، یک روش نقطه درونی شدنی برای حل مسائل مکمل خطی ترکیبی متقارن که یک کلاس کلی و جامع از مسائل مکمل خطی می‌یاشند ارائه خواهیم میشود. جهتهای جستجوگر نیوتن با استفاده از روش نسترو تاد متقارنسازی خواهند شد و با بکارگیری جبر جردن اقلیدسی همگرایی الگوریتم ارائه شده در این مقاله اثبات میشود. نشان داده میشود که پیچیدگی الگوریتم پیشنهادی منطبق بر بهترین کران پیچیدگی بدست آمده بوسیله روش‌های نقطه درونی شدنی برای حل مسائل بهینهسازی است.
1. Roos, C. A full-Newton step O (n) infeasible interior-point algorithm for linear optimiza- tion. SIAM J. Optim., 16 (4), 1110-1136 (2006)
2. Faraut, J., and Koranyi, A.: Analysis on Symmetric Cones. Oxford University Press, New York (1994)
3. Potra, F.A.: An O (n) infeasible-interiorpoint algorithm for LCP with quadratic conver-gence. Ann. Oper. Res., 62, 81-102 (1996)
4. Potra, F.A.: An infeasible interior-point method for linear complementarity problems over symmetric cones. in Proceedings of the 7th International Conference of Numerical Analysis and Applied Mathematics, Rethymno, Crete, Greece, 18-22 September (2009)
5. Wang, G.Q., Yue, Y., and Ci, X.Z.: Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. Fuzzy Inf. Eng., 4, 435-445 (2009)
6. Gu, G., Zangiabadi, M., and Roos, C.: Full Nesterov-Todd step interior-point methods for symmetric optimization. Eur. J. Oper. Res., 214(3), 473-484 (2011)
