|
|
|
|
یک روش نقطه درونی نشدنی با گام کامل نیوتن اصلاح شده برای مساله مکملی خطی یکنوا
|
|
|
|
|
|
|
|
نویسنده
|
خیرفام بهروز ,مهدوی امیری نظام الدین
|
|
منبع
|
پژوهش هاي رياضي - 1400 - دوره : 7 - شماره : 4 - صفحه:749 -763
|
|
چکیده
|
با استفاده از یک جهت جستجوی جدید، یک روش نقطه درونی نشدنی را برای مساله مکملی خطی یکنوا ارائه می‌دهیم . در این الگوریتم، تنها از یک گام شدنی استفاده می‌شود و نشان می‌دهیم که این ویژگی برای به دست آوردن یک روش با زمان چند جمله‌ای کافی است. کران تکرار الگوریتم با بهترین کران تکرار شناخته شده برای مسایل مکملی خطی تطابق دارد. به‌علاوه، نتایج عددی نشان می‌دهند که الگوریتم جدید عملکرد مطلوبی دارد.
|
|
کلیدواژه
|
مساله مکملی خطی، روش نقطه درونی نشدنی، پیچیدگی چندجمله ای
|
|
آدرس
|
دانشگاه شهید مدنی آذربایجان, گروه ریاضی کاربردی, ایران, دانشگاه صنعتی شریف, دانشکدۀ علوم ریاضی, ایران
|
|
پست الکترونیکی
|
nezamm@sharif.edu
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a full-modified-newton step infeasible interior-point method for monotone linear complementarity problem
|
|
|
|
|
Authors
|
kheirfam behrouz ,mahdavi-amiri nezameddin
|
|
Abstract
|
by using a new search direction, we propose an infeasibleinterior-point method for monotone linear complementarity problem. thealgorithm uses only one feasibility step in each iteration, and we prove thatit suffices in order to obtain a polynomial-time method. the iteration boundcoincides with the currently best iteration bound for linear complementarityproblems. moreover, the numerical results show that the new algorithm hasa good performance.
|
|
Keywords
|
linear complementarity problem ,infeasible interior-point method ,polynomial complexity
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|