یک الگوریتم نقطه درونی شدنی برای مسائل مکمل خطی ترکیبی بر روی مخروط‌های متقارن
محورهای موضوعی : آمارمریم زنگی‌آبادی 1 , حسین منصوری 2 , محمد پیرحاجی 3
1 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
2 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
3 - گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد، ایران
کلید واژه: Mixed symmetric cone linear co, Feasible interior-point method, Convergence analysis, polynomial complexity,
چکیده مقاله :
در این مقاله، یک روش نقطه درونی شدنی برای حل مسائل مکمل خطی ترکیبی متقارن که یک کلاس کلی و جامع از مسائل مکمل خطی می‌یاشند ارائه خواهیم میشود. جهتهای جستجوگر نیوتن با استفاده از روش نسترو تاد متقارنسازی خواهند شد و با بکارگیری جبر جردن اقلیدسی همگرایی الگوریتم ارائه شده در این مقاله اثبات میشود. نشان داده میشود که پیچیدگی الگوریتم پیشنهادی منطبق بر بهترین کران پیچیدگی بدست آمده بوسیله روش‌های نقطه درونی شدنی برای حل مسائل بهینهسازی است.
In this paper, we propose a feasible interior-point algorithm for mixed symmetric cone linear complementarity problems which are a general class of complementarity problems. The symmetrization of the search directions used in this paper is based on Nesterov and Todd scaling scheme. By using Euclidean Jordan algebra, we prove the convergence analysis of the proposed algorithm and show that the complexity bound of the algorithm matches the currently best known iteration bound for feasible interior-point methods.
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)