Nonlinear programming — غیر خطی پروگرامنگ

غیر خطی پروگرامنگ (NLP) — یہ ریاضیاتی پروگرامنگ اور آپریشنز ریسرچ کی ایک شاخ ہے، جو اُن اصلاحی مسائل سے متعلق ہے جہاں مقصدی فنکشن اور/یا کم از کم ایک پابندی، فیصلہ سازی متغیرات کی غیر خطی فنکشنز ہوں۔

NLP خطی پروگرامنگ کا تعمیم ہے اور یہ حقیقی نظاموں اور عمل کے ایک وسیع تر طبقے کی ماڈلنگ کی اجازت دیتا ہے، جہاں متغیرات کے درمیان انحصار سختی سے متناسب نہیں ہوتے (یعنی وہ سیدھی لکیروں کی بجائے منحنی خطوط سے بیان ہوتے ہیں)۔

موضوع اور مقصد

غیر خطی پروگرامنگ اُن حالات میں بہترین حل تلاش کرنے کے لیے استعمال ہوتی ہے جب:

• مقصدی اشارے (منافع، اخراجات، کارکردگی وغیرہ) کا قابلِ انتظام پیرامیٹرز پر انحصار غیر خطی ہو (مثلاً پیمانے کی گھٹتی ہوئی واپسی، مربعی اخراجات)۔
• وسائل یا تکنیکی عمل پر پابندیاں غیر خطی تعلقات سے بیان ہوں (مثلاً کیمیائی تعاملات، طبیعی قوانین، اقتصادی روابط)۔

NLP کے مسائل بہت سے شعبوں میں پیدا ہوتے ہیں:

• انجینئری ڈیزائن (ڈھانچوں اور عمل کی اصلاح)۔
• معاشیات اور مالیات (خطرے کے ساتھ پورٹ فولیو کی اصلاح، مارکیٹ ماڈلنگ)۔
• کیمیائی ٹیکنالوجی (ری ایکٹر حالات کی اصلاح)۔
• Machine Learning (Neural Networks کی تربیت، support vector machines)۔
• پیداواری عمل کا انتظام۔ لاجسٹکس (غیر خطی اخراجات کو مدنظر رکھتے ہوئے)۔

NLP کے مسئلے کی ریاضیاتی تشکیل

غیر خطی پروگرامنگ کا عمومی مسئلہ مندرجہ ذیل طریقے سے بیان کیا جاتا ہے:

فیصلہ سازی متغیرات کی اقدار کا ایسا مجموعہ تلاش کرنا مطلوب ہے جو غیر خطی مقصدی فنکشن کو زیادہ سے زیادہ یا کم سے کم کرے۔ اس کے ساتھ ہی متغیرات کی اقدار کو پابندیوں کے نظام کو پورا کرنا چاہیے، جو عدم مساوات (مثلاً "مقدار A مقدار B سے کم یا مساوی ہونی چاہیے") اور مساوات (مثلاً "مقدار C بالکل D کے برابر ہونی چاہیے") دونوں صورتوں میں ہو سکتی ہیں۔ اہم بات یہ ہے کہ مقصد یا پابندیوں کو بیان کرنے والی کم از کم ایک فنکشن غیر خطی ہو۔ اکثر متغیرات کی غیر منفی ہونے کی شرط بھی شامل کی جاتی ہے، یعنی یہ تقاضا کہ ان کی اقدار صفر سے زیادہ یا مساوی ہوں۔

متغیرات کی اقدار کے تمام مجموعوں کا مجموعہ جو پابندیوں کو پورا کرتے ہوں، قابلِ قبول حلوں کا خطہ (ق ق خ) تشکیل دیتا ہے۔

خطی پروگرامنگ سے فرق

غیر خطی پروگرامنگ خطی پروگرامنگ (LP) سے اہم طریقوں سے مختلف ہے:

• غیر خطیت: مقصدی فنکشن یا پابندیاں (یا دونوں) غیر خطی تعلقات پر مشتمل ہوں۔
• ق ق خ کی خصوصیات: NLP میں قابلِ قبول حلوں کا خطہ غیر محدب (non-convex) ہو سکتا ہے (LP کے برعکس جہاں ق ق خ ہمیشہ ایک محدب کثیر الاضلاع ہوتا ہے)۔
• اصلاح کی خصوصیات: NLP میں بہترین حل لازمی طور پر ق ق خ کے کونے پر نہیں ہوتا، یہ حد پر یا خطے کے اندر ہو سکتا ہے۔ NLP میں مقامی اصلاح (local optima) موجود ہو سکتی ہے جو عالمی اصلاح (global optima) نہ ہو۔
• حل کی پیچیدگی: NLP کے مسائل عموماً LP کے مسائل سے کہیں زیادہ پیچیدہ ہوتے ہیں۔ تمام NLP مسائل کے لیے simplex method جیسا کوئی واحد عالمی الگورتھم موجود نہیں ہے۔

NLP کی بنیادی مشکلات اور چیلنجز

غیر خطی پروگرامنگ کے مسائل کو حل کرنا کئی مشکلات سے دوچار ہے:

• مقامی انتہاؤں کا وجود: NLP کے اکثر طریقے صرف مقامی اصلاح (کسی ہمسایگی میں بہترین حل) کی ضمانت دیتے ہیں۔ عالمی اصلاح (پورے ق ق خ میں بہترین حل) کی تلاش ایک پیچیدہ کام ہے، خاص طور پر غیر محدب مسائل کے لیے۔
• غیر محدبیت: اگر مسئلہ محدب نہ ہو (مقصدی فنکشن یا ق ق خ غیر محدب ہو) تو متعدد مقامی اصلاح موجود ہو سکتی ہے، اور معیاری gradient طریقے ان میں سے کسی ایک میں "پھنس" سکتے ہیں۔
• حسابی پیچیدگی: NLP حل کرنے کے الگورتھم اکثر LP کے مقابلے میں کہیں زیادہ حسابی وسائل کا تقاضا کرتے ہیں۔

NLP مسائل کے اہم طبقات

عمومی پیچیدگی کے باوجود، NLP مسائل کے اہم ذیلی طبقات موجود ہیں جن کے لیے مؤثر حل کے طریقے تیار کیے گئے ہیں:

• محدب پروگرامنگ: محدب مجموعے پر محدب فنکشن کو کم سے کم کرنے کا مسئلہ (یا مقعر فنکشن کو زیادہ سے زیادہ کرنا)۔ اہم خاصیت: کوئی بھی مقامی کم از کم بیک وقت عالمی کم از کم بھی ہوتا ہے۔ اس سے بہترین حل کی تلاش نمایاں طور پر آسان ہو جاتی ہے۔
• Quadratic Programming: مقصدی فنکشن مربعی ہو اور تمام پابندیاں خطی ہوں۔
• Separable Programming: مقصدی فنکشن اور پابندیوں کو فنکشنز کے مجموع کے طور پر ظاہر کیا جا سکے، جن میں سے ہر ایک صرف ایک متغیر پر منحصر ہو۔

NLP مسائل کے حل کے طریقے

غیر خطی پروگرامنگ (NLP) کے مسائل حل کرنے کے طریقے

I. غیر مشروط اصلاح کے طریقے (پابندیوں کے بغیر اصلاح):

• Gradient طریقے (تیز ترین نزول کا طریقہ، conjugate gradient طریقہ)؛
• Newton کا طریقہ اور quasi-Newton طریقے (مثلاً BFGS)؛
• Hessian تخمینہ کاری کا استعمال کرنے والے طریقے۔

II. مشروط اصلاح کے طریقے (پابندیوں کے ساتھ اصلاح):

• تبدیلی کے طریقے:
  • Penalty functions کا طریقہ (penalty methods)؛
  • Barrier functions کا طریقہ (barrier methods)۔
• سمت کی براہِ راست تلاش کے طریقے:
  • ممکنہ سمتوں کا طریقہ۔
• اصلاح کی شرائط پر مبنی طریقے:
  • Karush-Kuhn-Tucker کے طریقے (KKT-شرائط)؛
  • Lagrange ضرب کاروں کا طریقہ۔
• تکراری طریقے:
  • Sequential Quadratic Programming (SQP)؛
  • داخلی نقاط کے طریقے۔

III. عالمی اصلاح کے طریقے:

• Heuristic اور meta-heuristic طریقے:
  • Genetic algorithms؛
  • Simulated annealing؛
  • Tabu search۔
• قطعی طریقے:
  • Branch and bound؛
  • خصوصی ساخت والے مسائل کے لیے عالمی اصلاح کے الگورتھم۔

کتابیات

• بازارا ایم، شیتی کے۔ غیر خطی پروگرامنگ۔ نظریہ اور الگورتھم۔ — ماسکو: میر، 1982۔
• فیاکو اے، میک-کورمک جی۔ غیر خطی پروگرامنگ۔ متسلسل غیر مشروط کم سے کم کاری کے طریقے۔ — ماسکو: میر، 1972۔
• ہمل بلاو ڈی۔ اطلاقی غیر خطی پروگرامنگ۔ — ماسکو: میر، 1975۔
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

یہ بھی دیکھیں

• آپریشنز ریسرچ
• اصلاح
• خطی پروگرامنگ
• محدب پروگرامنگ
• مقصدی فنکشن
• پابندیاں
• قابلِ قبول حلوں کا خطہ