Linear complementarity problem
ریاضیاتی اصلاح کے نظریہ میں، لکیری تکمیل کا مسئلہ (ایل سی پی) اکثر کمپیوٹیشنل میکانکس میں پیدا ہوتا ہے اور ایک خاص معاملے کے طور پر معروف کواڈریٹک پروگرامنگ کو گھیرے ہوئے ہے۔ اسے کوٹل اور ڈینٹزگ نے 1968 میں تجویز کیا تھا۔ تشکیل ایک حقیقی میٹرکس M اور ویکٹر q کو دیکھتے ہوئے، لکیری تکمیل کا مسئلہ ایل سی پی (q، M) ویکٹرز z اور w کی تلاش کرتا ہے جو مندرجہ ذیل رکاوٹوں کو پورا کرتے ہیں: (یعنی، ان دونوں ویکٹرز کا ہر جزو غیر منفی ہے) یا مساوی طور پر یہ تکمیل کی شرط ہے، کیونکہ اس کا مطلب یہ ہے کہ، سب کے لیے، زیادہ سے زیادہ ایک مثبت ہو سکتا ہے۔ اس مسئلے کے حل کے وجود اور انفرادیت کے لیے ایک کافی شرط یہ ہے کہ M متناسب مثبت-یقینی ہو۔ اگر M ایسا ہے جس میں ہر q کا حل ہے، تو M ایک Q میٹرکس ہے۔ اگر M ایسا ہے جس کا ہر q کے لیے منفرد حل ہے، تو M ایک P-میٹرکس ہے۔ یہ دونوں خصوصیات کافی اور ضروری ہیں۔ ویکٹر ڈبلیو ایک سست متغیر ہے، اور اس لیے عام طور پر زیڈ ملنے کے بعد اسے خارج کر دیا جاتا ہے۔ اس طرح، مسئلہ کو اس طرح بھی وضع کیا جا سکتا ہے: (تکمیل کی حالت) کنویکس کواڈریٹک-منیمائزیشن: کم سے کم حالات لکیری تکمیل کے مسئلے کا حل تلاش کرنا کواڈریٹک فنکشن کو کم سے کم کرنے سے وابستہ ہے جو رکاوٹوں کے تابع ہے۔ یہ رکاوٹیں اس بات کو یقینی بناتی ہیں کہ f ہمیشہ غیر منفی ہے۔ کم از کم f، z پر 0 ہے اگر اور صرف اس صورت میں جب z لکیری تکمیل کے مسئلے کو حل کرتا ہے۔ اگر M مثبت قطعی ہے، تو (سختی سے) کنویکس کیو پی کو حل کرنے کے لیے کوئی بھی الگورتھم ایل سی پی کو حل کر سکتا ہے۔ خاص طور پر ڈیزائن کردہ بیس ایکسچینج پیوٹنگ الگورتھم، جیسے کہ لیمکے کا الگورتھم اور ڈینٹزگ کے سمپلیکس الگورتھم کا ایک قسم کئی دہائیوں سے استعمال ہوتا رہا ہے۔ کثیر الجہتی وقت کی پیچیدگی کے علاوہ، اندرونی نقطہ کے طریقے بھی عملی طور پر موثر ہیں۔ نیز، ایک کواڈریٹک-پروگرامنگ مسئلہ جسے کم سے کم موضوع کے ساتھ ساتھ کیو سمیٹرک کے ساتھ بیان کیا گیا ہے، وہی ہے جو ایل سی پی کو حل کرتا ہے۔ اس کی وجہ یہ ہے کہ کیو پی مسئلے کے کروش-کوہن-ٹکر حالات کو اس طرح لکھا جا سکتا ہے: v کے ساتھ غیر منفی رکاوٹوں پر لگرینج ضرب، λ عدم مساوات کی رکاوٹوں پر ضرب، اور s عدم مساوات کی رکاوٹوں کے لیے سست متغیرات۔ چوتھی شرط متغیرات کے ہر گروپ کی تکمیل سے حاصل ہوتی ہے جس میں اس کے کے کے ٹی ویکٹرز (زیادہ سے زیادہ لگرینج ملٹی پلیئرز) ہوتے ہیں۔ اس صورت میں، اگر x پر غیر منفی رکاوٹ کو کم کیا جاتا ہے، تو ایل سی پی کے مسئلے کی جہت کو عدم مساوات کی تعداد تک کم کیا جا سکتا ہے، جب تک کہ Q غیر واحد ہو (جس کی ضمانت دی جاتی ہے اگر یہ مثبت قطعی ہو)۔ ضرب v اب موجود نہیں ہیں، اور پہلے کے کے ٹی شرائط کو اس طرح دوبارہ لکھا جا سکتا ہے: یا: دونوں اطراف کو A سے پہلے ضرب دینا اور b کو گھٹانا ہم حاصل کرتے ہیں: بائیں طرف، دوسری کے کے ٹی شرط کی وجہ سے، s ہے۔ تبدیل کرنا اور دوبارہ ترتیب دینا: اب کال کرنا ہمارے پاس ایل سی پی ہے، سلیک متغیر s اور ان کے لگرینج ضرب λ کے درمیان تکمیل کے تعلق کی وجہ سے۔ ایک بار جب ہم اسے حل کر لیتے ہیں، تو ہم پہلی کے کے ٹی شرط کے ذریعے λ سے x کی قیمت حاصل کر سکتے ہیں۔ آخر میں، مساوات کی اضافی رکاوٹوں کو سنبھالنا بھی ممکن ہے: اس سے لگرینج ملٹی پلیئرز کا ایک ویکٹر متعارف ہوتا ہے، جس کی جہت ایک جیسی ہوتی ہے۔ اس بات کی تصدیق کرنا آسان ہے کہ ایل سی پی نظام کے لیے ایم اور کیو کا اظہار اب اس طرح کیا جاتا ہے: λ سے اب ہم مساوات کے x اور لگرینج ضرب دونوں کی اقدار کو بازیافت کر سکتے ہیں: در حقیقت، زیادہ تر کیو پی حل کرنے والے ایل سی پی کی تشکیل پر کام کرتے ہیں، بشمول اندرونی نقطہ طریقہ، پرنسپل/تکمیلی محور، اور فعال سیٹ طریقے۔ ایل سی پی کے مسائل کو کرس کراس الگورتھم کے ذریعے بھی حل کیا جا سکتا ہے، اس کے برعکس، لکیری تکمیل کے مسائل کے لیے، کرس کراس الگورتھم صرف اس صورت میں ختم ہوتا ہے جب میٹرکس کافی میٹرکس ہو۔ ایک کافی میٹرکس مثبت-یقینی میٹرکس اور پی-میٹرکس دونوں کی عمومی شکل ہے، جس کے بنیادی نابالغ ہر ایک مثبت ہوتے ہیں۔ اس طرح کے ایل سی پیز کو اس وقت حل کیا جا سکتا ہے جب انہیں اورینٹڈ-میٹرائڈ تھیوری کا استعمال کرتے ہوئے تجریدی طور پر وضع کیا جائے۔ تکمیل نظریہ طبیعیات انجن امپلس/رکاوٹ قسم کے طبیعیات کے انجن بھی دیکھیں جو کھیلوں کے لیے اس نقطہ نظر کا استعمال کرتے ہیں۔ رابطہ حرکیات غیر متزلزل نقطہ نظر کے ساتھ رابطہ حرکیات۔ بمیٹریکس گیمز کو ایل سی پی تک کم کیا جا سکتا ہے۔ مزید پڑھنے کے لیے حوالہ جات بیرونی روابط ایل سی پی سولیو-لیمکے کے الگورتھم کے سی میں لکیری تکمیل کے مسئلے سکونوس/عددی اوپن سورس جی پی ایل کے نفاذ اور ایل سی پیز اور ایم ایل سی پیز لکیری الجبرا ریاضیاتی اصلاح کو حل کرنے کے دیگر طریقوں کو حل کرنے کے لیے GAUSS میں ایک آسان طریقہ کار۔