Skip to content
بازگشت به نتایج جست‌وجو

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

معرفی‌شده توسط
Jorge Nocedal & Stephen Wright
سال
2006
نوع
Continuous mathematical optimization
خانواده
Mathematical programming

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

برنامه‌ریزی غیرخطی (NLP) شاخه‌ای از بهینه‌سازی ریاضی است که به مسائلی می‌پردازد که در آن‌ها تابع هدف یا حداقل یکی از قیود، غیرخطی است. این حوزه که به طور جامع توسط خورخه نودال و استفان رایت در متن اثرگذار سال ۲۰۰۶ آن‌ها تدوین شده است، شامل الگوریتم‌های مبتنی بر گرادیان — از جمله برنامه‌ریزی ترتیبی درجه دوم (SQP)، روش‌های نقطه درونی، و رویکردهای شبه-نیوتن — برای یافتن راه‌حل‌های بهینه محلی یا سراسری برای مسائل تصمیم‌گیری پیوسته است که در مهندسی، اقتصاد و علوم فیزیکی پدیدار می‌شوند.

شهود پشت روش

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

تاریخ

مبانی نظری برنامه‌ریزی غیرخطی به شرایط KKT که توسط کاروش (۱۹۳۹) و کوهن و تاکر (۱۹۵۱) استخراج شد، بازمی‌گردد. الگوریتم‌های عملی در دهه‌های ۱۹۶۰ تا ۱۹۸۰ با توسعه روش‌های SQP، رویکردهای لاگرانژی افزوده، و به‌روزرسانی‌های شبه-نیوتن از جمله BFGS (۱۹۷۰) تسریع شدند. ویرایش دوم کتاب بهینه‌سازی عددی نوشته نودال و رایت در سال ۲۰۰۶ به یک مرجع قطعی تبدیل شد و نظریه همگرایی، چارچوب‌های جستجوی خطی و ناحیه اعتماد، و روش‌های نقطه درونی را در یک رویکرد مدرن منسجم ترکیب کرد.

چه زمانی استفاده شود

زمانی از برنامه‌ریزی غیرخطی استفاده کنید که تابع هدف یا قیود را نتوان بدون اتلاف قابل توجه دقت خطی‌سازی کرد و متغیرهای تصمیم پیوسته باشند. تنظیمات معمول شامل طراحی مهندسی با قیود قوانین فیزیکی، بهینه‌سازی سبد سهام با معیارهای ریسک غیرخطی، و رگرسیون با فرم‌های مدل غیرخطی است. مفروضات کلیدی این است که f و c حداقل دو بار به طور پیوسته مشتق‌پذیر هستند (برای حل‌کننده‌های مبتنی بر گرادیان) و شرایط احراز صلاحیت قید برقرار است. هنگامی که متغیرها صحیح هستند، پسوندهای برنامه‌ریزی غیرخطی عدد صحیح مختلط (MINLP) اعمال می‌شوند. برای مسائل محدب، روش‌های نقطه درونی بهینگی سراسری را تضمین می‌کنند؛ برای مسائل غیرمحدب، تنها تضمین‌های محلی وجود دارد.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

تحلیلگر یک تابع هدف اسکالر f(x) را برای کمینه‌سازی یا بیشینه‌سازی بر روی متغیرهای تصمیم x در R^n، همراه با قیود تساوی c_i(x) = 0 و قیود نامساوی c_j(x) >= 0 تعریف می‌کند. شناسایی اینکه کدام قیود در یک راه‌حل کاندید فعال هستند و آیا شرایط منظم بودن (شرایط احراز صلاحیت قید) برقرار است، در این مرحله حیاتی است و تعیین می‌کند که کدام نظریه بهینگی اعمال می‌شود.

فرمول
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

شرایط کاروش-کوهن-تاکر (KKT) شرایط لازم مرتبه اول برای یک بهینه محلی را فراهم می‌کند. این شرایط نیازمند ایستایی لاگرانژی، لَختی مکمل برای ضرایب نامساوی (lambda_j c_j = 0)، امکان‌پذیری دوگان (lambda_j >= 0) و امکان‌پذیری اولیه است. الگوریتم‌ها به طور تکراری تکرارهایی را می‌سازند که این شرایط را به طور فزاینده‌ای دقیق‌تر برآورده می‌کنند، و شرایط کفایت مرتبه دوم تأیید می‌کنند که یک نقطه ایستایی واقعاً یک کمینه محلی است.

فرمول
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

در هر تکرار k، یک الگوریتم جهت جستجو p_k را محاسبه می‌کند — معمولاً از طریق تقریب شبه-نیوتن B_k از هسین (مانند BFGS) یا یک سیستم مشتق مرتبه دوم دقیق — و طول گام alpha_k را که شرایط ولف یا آرمیو را برآورده می‌کند. روش‌های SQP یک زیرمسئله درجه دوم برای p_k حل می‌کنند، در حالی که روش‌های نقطه درونی جملات مانع را برای مدیریت قیود نامساوی اضافه می‌کنند و تکرارها را به سمت داخل ناحیه ممکن هدایت می‌کنند.

فرمول
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

پایان زمانی رخ می‌دهد که هم نرم گرادیان لاگرانژی و هم حداکثر نقض قید به زیر تلرانس‌های تعیین شده (epsilon و delta) برسند. از آنجایی که NLP به طور کلی غیرمحدب است، الگوریتم‌ها ممکن است به بهینه‌های محلی همگرا شوند؛ در صورت نیاز به بهینگی سراسری، استفاده مکرر از نقاط شروع مختلف یا استراتژی‌های جستجوی سراسری (مانند شاخه و کران، چند نقطه‌ای) توصیه می‌شود.

فرمول
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

دام‌های رایج

  • نادیده گرفتن شرایط احراز صلاحیت قید و اعمال کورکورانه شرایط KKT در نقاط تباهیده یا ناممکن منجر به راه‌حل‌های کاذب می‌شود.
  • استفاده از متغیرهای با مقیاس‌بندی ضعیف باعث تقریب‌های هسین بدحالت و همگرایی کند یا ناموفق می‌شود.
  • پذیرش اولین کمینه محلی یافت شده بدون شروع‌های مجدد متعدد در تنظیمات غیرمحدب ممکن است به طور قابل توجهی بهینه سراسری را از دست بدهد.
  • تقریب‌های گرادیان تفاضل متناهی خطای عددی ایجاد می‌کنند؛ مشتق‌گیری تحلیلی یا خودکار به شدت ترجیح داده می‌شود.

پرسش‌های متداول

آیا هر برنامه خطی نیز یک برنامه غیرخطی است؟

بله. برنامه‌ریزی خطی یک حالت خاص از NLP است که در آن هم تابع هدف و هم تمام قیود آفین هستند. با این حال، LP الگوریتم‌های سیمپلکس و نقطه درونی را می‌پذیرد که از خطی بودن بهره می‌برند و بسیار کارآمدتر از حل‌کننده‌های عمومی NLP هستند؛ استفاده از یک حل‌کننده عمومی NLP برای یک LP اتلاف‌کننده است اما از نظر ریاضی معتبر است.

چه زمانی می‌توانم اطمینان داشته باشم که یک نقطه KKT یک کمینه سراسری است؟

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

تفاوت بین روش‌های SQP و نقطه درونی چیست؟

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

روش‌های مرتبط

منابع

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    شابک: 978-0-387-30303-1
    کپی شد.