Nonlinear programming — برنامه‌ریزی غیرخطی

برنامه‌ریزی غیرخطی (NLP) — شاخه‌ای از برنامه‌ریزی ریاضی و تحقیق در عملیات است که به مسائل بهینه‌سازی می‌پردازد؛ در این مسائل، تابع هدف و/یا حداقل یکی از قیدها، توابع غیرخطی از متغیرهای تصمیم هستند.

NLP تعمیمی از برنامه‌ریزی خطی است و امکان مدل‌سازی طیف گسترده‌تری از سیستم‌ها و فرآیندهای واقعی را فراهم می‌کند؛ جایی که روابط بین متغیرها دقیقاً متناسب نیستند (یعنی با منحنی‌ها و نه خطوط مستقیم توصیف می‌شوند).

موضوع و هدف

برنامه‌ریزی غیرخطی برای یافتن راه‌حل‌های بهینه در موقعیت‌هایی به کار می‌رود که:

• وابستگی شاخص هدف (سود، هزینه، کارایی و غیره) به پارامترهای کنترلی غیرخطی است (برای مثال، بازده نزولی نسبت به مقیاس، هزینه‌های درجه دوم).
• قیدهای منابع یا فرآیندهای فناورانه با روابط غیرخطی توصیف می‌شوند (برای مثال، واکنش‌های شیمیایی، قوانین فیزیکی، وابستگی‌های اقتصادی).

مسائل NLP در حوزه‌های بسیاری پدیدار می‌شوند:

• طراحی مهندسی (بهینه‌سازی سازه‌ها و فرآیندها).
• اقتصاد و مالیه (بهینه‌سازی پرتفوی با در نظر گرفتن ریسک، مدل‌سازی بازار).
• فناوری شیمیایی (بهینه‌سازی رژیم‌های کاری راکتورها).
• Machine Learning (آموزش شبکه‌های عصبی، روش بردار پشتیبان).
• مدیریت فرآیندهای تولیدی. لجستیک (با در نظر گرفتن هزینه‌های غیرخطی).

صورت‌بندی ریاضی مسئله NLP

مسئله کلی برنامه‌ریزی غیرخطی به شکل زیر فرموله می‌شود:

لازم است مجموعه‌ای از مقادیر متغیرهای تصمیم یافت شود که تابع هدف غیرخطی را بیشینه یا کمینه کند. در عین حال، مقادیر متغیرها باید دستگاه قیدها را برآورده سازند؛ این قیدها می‌توانند به صورت نامساوی (برای مثال، «مقدار A باید کمتر یا مساوی B باشد») یا به صورت تساوی (برای مثال، «مقدار C باید دقیقاً برابر D باشد») بیان شوند. نکته مهم این است که حداقل یکی از توابع توصیف‌کننده هدف یا قیدها غیرخطی است. اغلب شرایط نامنفی بودن متغیرها نیز افزوده می‌شود، یعنی الزام به اینکه مقادیر آن‌ها بزرگ‌تر یا مساوی صفر باشند.

مجموعه تمام مجموعه‌های مقادیر متغیرهایی که قیدها را برآورده می‌سازند، ناحیه جواب‌های مجاز (ناحیه شدنی) را تشکیل می‌دهند.

تفاوت‌ها با برنامه‌ریزی خطی

برنامه‌ریزی غیرخطی تفاوت‌های اساسی با برنامه‌ریزی خطی (LP) دارد:

• غیرخطی بودن: تابع هدف یا قیدها (یا هر دو) حاوی وابستگی‌های غیرخطی هستند.
• ویژگی‌های ناحیه شدنی: ناحیه جواب‌های مجاز در NLP می‌تواند ناتحدب باشد (برخلاف LP که ناحیه مجاز همواره یک چندوجهی محدب است).
• ویژگی‌های بهینه: جواب بهینه در NLP لزوماً در رأس ناحیه مجاز قرار ندارد و می‌تواند روی مرز یا داخل ناحیه باشد. در NLP ممکن است بهینه‌های محلی وجود داشته باشند که بهینه سراسری نیستند.
• پیچیدگی حل: مسائل NLP به طور کلی به مراتب پیچیده‌تر از مسائل LP هستند. هیچ الگوریتم جهانی واحدی، مشابه روش سیمپلکس، برای تمام مسائل NLP وجود ندارد.

چالش‌ها و دشواری‌های اصلی NLP

حل مسائل برنامه‌ریزی غیرخطی با دشواری‌هایی همراه است:

• وجود اکسترمم‌های محلی: اکثر روش‌های NLP تنها یافتن بهینه محلی (جوابی که در یک همسایگی خاص بهترین است) را تضمین می‌کنند. یافتن بهینه سراسری (بهترین جواب در کل ناحیه مجاز) مسئله‌ای دشوار است، به‌ویژه برای مسائل ناتحدب.
• ناتحدبی: اگر مسئله تحدب نداشته باشد (تابع هدف یا ناحیه مجاز ناتحدب باشند)، ممکن است بهینه‌های محلی متعددی وجود داشته باشد و روش‌های گرادیانی استاندارد در یکی از آن‌ها «گیر کنند».
• پیچیدگی محاسباتی: الگوریتم‌های حل NLP اغلب به منابع محاسباتی بسیار بیشتری نسبت به LP نیاز دارند.

کلاس‌های مهم مسائل NLP

علیرغم پیچیدگی کلی، زیرکلاس‌های مهمی از مسائل NLP وجود دارند که برای آن‌ها روش‌های حل کارآمدی توسعه یافته است:

• برنامه‌ریزی محدب: مسئله کمینه‌سازی یک تابع محدب روی مجموعه محدب جواب‌های مجاز (یا بیشینه‌سازی تابع مقعر). ویژگی کلیدی: هر کمینه محلی همچنین کمینه سراسری نیز هست. این امر جستجوی جواب بهینه را به طور قابل توجهی ساده‌تر می‌کند.
• برنامه‌ریزی درجه دوم: تابع هدف درجه دوم است و تمام قیدها خطی هستند.
• برنامه‌ریزی تفکیک‌پذیر: تابع هدف و قیدها را می‌توان به صورت مجموع توابعی نوشت که هر یک تنها به یک متغیر وابسته است.

روش‌های حل مسائل NLP

روش‌های حل مسائل برنامه‌ریزی غیرخطی (NLP)

I. روش‌های بهینه‌سازی بدون قید (بهینه‌سازی بدون محدودیت):

• روش‌های گرادیانی (روش تندترین شیب، روش گرادیان‌های مزدوج)؛
• روش نیوتن و روش‌های شبه‌نیوتنی (برای مثال، BFGS)؛
• روش‌های با استفاده از تقریب ماتریس هسی.

II. روش‌های بهینه‌سازی با قید (بهینه‌سازی با محدودیت):

• روش‌های تبدیل:
  • روش توابع جریمه (penalty methods)؛
  • روش توابع سد (barrier methods).
• روش‌های جستجوی مستقیم جهت:
  • روش جهت‌های ممکن.
• روش‌های مبتنی بر شرایط بهینگی:
  • روش‌های Karush-Kuhn-Tucker (شرایط KKT)؛
  • روش ضرایب لاگرانژ.
• روش‌های تکراری:
  • برنامه‌ریزی درجه دوم متوالی (SQP)؛
  • روش‌های نقطه داخلی.

III. روش‌های بهینه‌سازی سراسری:

• روش‌های هیوریستیک و فراابتکاری:
  • الگوریتم‌های ژنتیک؛
  • شبیه‌سازی تبرید؛
  • جستجو با ممنوعیت (tabu search).
• روش‌های قطعی:
  • شاخه و کران (branch and bound)؛
  • الگوریتم‌های بهینه‌سازی سراسری برای مسائل با ساختار خاص.

همچنین ببینید

• تحقیق در عملیات
• بهینه‌سازی
• برنامه‌ریزی خطی
• برنامه‌ریزی محدب
• تابع هدف
• قیدها
• ناحیه جواب‌های مجاز

منابع

• بازارا م.، شتی ک. برنامه‌ریزی غیرخطی. نظریه و الگوریتم‌ها. — مسکو: میر، ۱۹۸۲.
• فیاکو آ.، مک‌کورمیک گ. برنامه‌ریزی غیرخطی. روش‌های کمینه‌سازی بدون قید متوالی. — مسکو: میر، ۱۹۷۲.
• هیمل‌بلاو د. برنامه‌ریزی غیرخطی کاربردی. — مسکو: میر، ۱۹۷۵.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)