يك الگوريتم نقطه دروني شدني براي مسائل مكمل خطي تركيبي بر روي مخروط‌هاي متقارن

A path-following feasible interior-point algorithm for mixed symmetric cone linear complementarity problems

در اين مقاله، يك روش نقطه دروني شدني براي حل مسائل مكمل خطي تركيبي متقارن كه يك كلاس كلي و جامع از مسائل مكمل خطي مي‌ياشند ارائه خواهيم مي­شود. جهت­هاي جستجوگر نيوتن با استفاده از روش نسترو تاد متقارن­سازي خواهند شد و با بكارگيري جبر جردن اقليدسي همگرايي الگوريتم ارائه شده در اين مقاله اثبات مي­شود. نشان داده مي­شود كه پيچيدگي الگوريتم پيشنهادي منطبق بر بهترين كران پيچيدگي بدست آمده بوسيله روش‌هاي نقطه دروني شدني براي حل مسائل بهينه­سازي است.

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.