الگوریتم کارمارکار

الگوریتم کارمارکار توسط نراندرا کارمارکار در سال ۱۹۸۴ برای حل مسایلبرنامه‌ریزی خطی ارائه شد. این الگوریتم اولین الگوریتم کارا برای حل این مسایل در زمان چندجمله‌ای بود. روش بیضی نیز زمان اجرای چندجمله‌ای دارد،الگو:سخولی روش کارایی نیست.

اگر $n$ تعداد متغیرها و $L$ تعداد بیت‌های ورودی به الگوریتم باشد، الگوریتم کارمارکار به $O(n^{3.5}L)$ عمل روی اعداد $O(L)$ رقمی احتیاج دارد، درحالی که در روش بیضی به $O(n^{6}L)$ عمل نیاز است.الگو:سخزمان اجرای الگوریتم کارمارکار به شکل زیر است: الگو:چپ‌چین $O(n^{3.5}{L}^2\cdot \log L\cdot \log \log L)$ الگو:پایان چپ‌چین که در آن از ضرب به روش تبدیل سریع فوریه استفاده می‌کند.

الگوریتم کارمارکار از جمله روش‌های نقطهٔ داخلی است: حدس فعلی شرایط مجموعهٔ ممکن را برخلاف روش سیمپلکس رعایت نمی‌کند و با استفاده از کسر معین در هر تکرار، دقت جواب بهینه را بهبود می‌دهد.

الگوریتم

یک مسئلهٔ برنامه‌ریزی خطی را در شکل ماتریسی در نظر بگیرید: الگو:چپ‌چین

maximize cTx
subject to	Ax ≤ b.

الگو:پایان چپ‌چین که در آن c برداری n بعدی و b برداری m بعدی و ماتریس m × n)، A) بعدی است.الگو:سخ الگوریتم کارماکار کمی پیچیده است. یک مدل ساده‌تر که به آن روش affine-scaling گفته می‌شود، که به طور مختصر به شرح زیر است. دقت داشته باشید که این الگوریتم در حالی که در عمل کارا است ولی الگوریتم با زمان چندجمله‌ای نیست. الگو:چپ‌چین

Algorithm Affine-Scalling
 Input: A, b, c, $x^0$, stopping criterion, $\gamma$.

  $k\leftarrow 0$
 do while stopping criterion not satisfied
     $v^k\leftarrow b-A{x}^k$
     $D_v\leftarrow \mathrm{diag}(v_1^k,\dots ,v_m^k)$
     $h_x\leftarrow (A^T{D}_v^{-2}A{)}^{-1}c$
     $h_v\leftarrow -A{h}_x$
 if $h_v\ge 0$ then
 return unbounded
 end if
     $\alpha \leftarrow \gamma \cdot \min \{-v_i^k/(h_v{)}_i|(h_v{)}_i<0,i=1,\dots ,m\}$
     $x^{k+1}\leftarrow x^k+\alpha h_x$
     $k\leftarrow k+1$
 end do