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

بهینه‌سازی استوار — برنامه‌ریزی ریاضی بدترین حالت

معرفی‌شده توسط
Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
سال
1970s theoretical roots; modern tractable form from late 1990s–2004
نوع
Mathematical programming framework

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

اندازه قلم

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

بهینه‌سازی استوار یک چارچوب برنامه‌ریزی ریاضی است که در اواخر دهه ۱۹۹۰ توسط بن-تال و نمیروفسکی فرمول‌بندی شد و در سال ۲۰۰۴ توسط برتزیمس و سیم (Bertsimas and Sim) به طور گسترده‌ای قابل حل گردید. این روش تصمیماتی را می‌یابد که تضمین می‌شود تحت هر سناریوی ممکن در یک مجموعه عدم قطعیت از پیش تعریف شده، عملکرد قابل قبولی خواهند داشت — به جای اینکه فرض شود مقادیر پارامترها دقیقاً مشخص هستند. به جای بهینه‌سازی برای یک نتیجه مورد انتظار واحد، بدترین حالت هزینه را در میان تمام تحقق‌های محتمل داده‌های نامشخص، به حداقل می‌رساند.

شهود پشت روش

بهینه‌سازی معمولی به اعدادی که به آن می‌دهید اعتماد می‌کند. بهینه‌سازی استوار می‌پرسد: اگر آن اعداد اشتباه باشند چه؟ — در یک محدوده مشخص؟ این روش تصمیمی را پیدا می‌کند که وقتی طبیعت بدترین ورودی ممکن را در آن محدوده انتخاب می‌کند، کمترین آسیب را وارد کند. به آن مانند طراحی پلی فکر کنید که نه برای تحمل بار متوسط، بلکه برای تحمل سنگین‌ترین بار قابل قبول طراحی شده است، با پذیرش هزینه عملکرد اندکی در حالت معمول در ازای تضمینی در حالت بد.

تاریخ

ریشه‌های نظری بهینه‌سازی استوار به سوستر (Soyster, 1971) و نظریه تصمیم مینی‌مکس والد (Wald, 1945) بازمی‌گردد. این حوزه توسط آرکادی نمیروفسکی و آهاران بن-تال در مجموعه‌ای از مقالات از سال ۱۹۹۷ به بعد، که در سال ۲۰۰۹ با مونوگراف آن‌ها با الغاوی به اوج خود رسید، پایه‌ای مدرن و قابل حل یافت. دیمیتریس برتزیمس و ملوین سیم (Bertsimas & Sim, 2004) فرمول‌بندی عدم قطعیت بودجه‌ای (چندوجهی) را معرفی کردند که خطی بودن مسئله اسمی را حفظ می‌کند و برنامه‌ریزی خطی استوار را به طور گسترده در دسترس قرار داد. از آن زمان، بهینه‌سازی استوار برای پوشش برنامه‌های صحیح، فرمول‌بندی‌های دو مرحله‌ای، و مجموعه‌های عدم قطعیت داده‌محور مشتق شده از مشاهدات تاریخی گسترش یافته است.

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

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

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

  • راه‌حل لزوماً محافظه‌کارانه‌تر از بهینه اسمی است؛ قیمت استواری می‌تواند در صورت بزرگ بودن مجموعه عدم قطعیت قابل توجه باشد.
  • تعریف یک مجموعه عدم قطعیت واقع‌بینانه نیازمند دانش دامنه است؛ یک مجموعه بد انتخاب شده ممکن است بیش از حد محافظه‌کارانه باشد یا نتواند اغتشاشات واقعی را پوشش دهد.
  • برای مسائل غیرمحدب یا برنامه‌های مختلط صحیح عمومی، بازسازی‌های استوار می‌توانند NP-hard باشند و به الگوریتم‌های تجزیه تخصصی نیاز دارند.
  • بهینه‌سازی استوار اطلاعات احتمال را در بر نمی‌گیرد؛ زمانی که یک توزیع قابل اعتماد در دسترس است، برنامه‌ریزی تصادفی ممکن است عملکرد مورد انتظار بالاتری را ارائه دهد.

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

نقاط قوت

  • تضمین‌های قطعی بدترین حالت را بدون نیاز به توزیع احتمال برای پارامترهای نامشخص فراهم می‌کند.
  • بازسازی‌ها برای مجموعه‌های عدم قطعیت محدب اغلب به اندازه مسئله اسمی قابل حل هستند — هیچ انفجار محاسباتی اضافی وجود ندارد.
  • سطح محافظه‌کاری مستقیماً از طریق اندازه و شکل مجموعه عدم قطعیت قابل کنترل است، که توازن استواری-عملکرد را صریح و شفاف می‌سازد.
  • در دامنه‌های متنوعی کاربرد دارد — زنجیره تأمین، مالی، طراحی مهندسی، سیستم‌های انرژی — هر جا که عدم قطعیت پارامتر محدود وجود دارد.

کاربردها

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

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

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

1

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

2

مسئله بهینه‌سازی در فرم مینی‌مکس (minimax) مطرح می‌شود: حداقل‌سازی هزینه حداکثری که عدم قطعیت خصمانه می‌تواند تحمیل کند، بر روی تصمیمات. به طور رسمی، هدف min_x max_{u in U} f(x, u) می‌شود، مشروط بر اینکه محدودیت‌ها برای همه u در مجموعه عدم قطعیت U برقرار باشند. این حداکثرسازی درونی، انتخاب بدترین تحقق پارامترهای نامشخص توسط طبیعت را مدل می‌کند.

3

برای مجموعه‌های عدم قطعیت محدب، مسئله مینی‌مکس از نظر تحلیلی معادل یک برنامه محدب قطعی است — اغلب یک برنامه مخروط مرتبه دوم برای مجموعه‌های بیضوی یا یک برنامه خطی برای مجموعه‌های چندوجهی. این بازسازی قابل حل، بینش کلیدی بن-تال و نمیروفسکی است: همتایان استوار بسیاری از مسائل کلاسیک، دشوارتر از مسئله اسمی نیستند. برای ساختارهای غیرمحدب، تجزیه بندر (Benders decomposition) مسئله را به یک مسئله اصلی و یک مسئله فرعی خصمانه تقسیم می‌کند که به صورت تکراری حل می‌شوند.

4

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

5

تحلیلگر قیمت استواری (price of robustness) را بررسی می‌کند: شکاف بین مقدار هدف اسمی (بدون عدم قطعیت) و مقدار بهینه استوار. یک مجموعه عدم قطعیت تنگ، شکاف کوچکی اما تضمین‌های ضعیف‌تری ایجاد می‌کند؛ یک مجموعه بزرگ، حفاظت قوی در بدترین حالت را با هزینه عملکرد بالاتر در سناریوهای معمول به همراه دارد. تحلیل حساسیت بر اندازه مجموعه عدم قطعیت، انتخاب نهایی سطح محافظه‌کاری را هدایت می‌کند.

دام‌های رایج

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

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

بهینه‌سازی استوار چگونه با برنامه‌ریزی تصادفی متفاوت است؟

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

قیمت استواری چیست؟

قیمت استواری، افزایش در مقدار هدف (برای یک مسئله کمینه‌سازی) در مقایسه با راه‌حل بهینه اسمی به دست آمده بدون در نظر گرفتن عدم قطعیت است. برتزیمس و سیم (Bertsimas & Sim, 2004) نشان دادند که برای فرمول‌بندی عدم قطعیت بودجه‌ای آن‌ها، این قیمت تنها به اندازه ریشه دوم تعداد پارامترهای نامشخص رشد می‌کند، که آن را در عمل ناچیز می‌سازد. بررسی این شکاف پس از حل ضروری است: اگر بسیار بزرگ باشد، مجموعه عدم قطعیت احتمالاً بیش از حد محافظه‌کارانه است.

کدام شکل مجموعه عدم قطعیت را باید انتخاب کنم؟

مجموعه‌های جعبه‌ای ساده‌ترین و محافظه‌کارانه‌ترین هستند — هر پارامتر به طور مستقل تغییر می‌کند. مجموعه‌های بیضوی (Ben-Tal & Nemirovski) اغتشاشات همبسته را در نرم اقلیدسی محدود می‌کنند و به برنامه‌های مخروط مرتبه دوم منجر می‌شوند. مجموعه‌های چندوجهی / با محدودیت بودجه (Bertsimas & Sim) تعداد پارامترهایی را که می‌توانند همزمان منحرف شوند کنترل می‌کنند، خطی بودن را حفظ کرده و محافظه‌کاری را کاهش می‌دهند. بر اساس دانش دامنه در مورد چگونگی وقوع همزمان اغتشاشات و کلاس حل‌کننده موجود، انتخاب کنید.

آیا بهینه‌سازی استوار می‌تواند متغیرهای تصمیم صحیح را مدیریت کند؟

بله، اما برنامه‌ریزی خطی و مختلط صحیح استوار به طور قابل توجهی دشوارتر است. همتایان استوار برنامه‌های خطی مختلط صحیح اغلب در بدترین حالت NP-hard هستند. تجزیه بندر و الگوریتم‌های تولید ستون و قید، رویکردهای استانداردی هستند، اما اندازه مسئله و پیچیدگی مجموعه عدم قطعیت باید قابل مدیریت نگه داشته شوند.

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

منابع

  1. Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.

    شابک: 9780691143682
    کپی شد.
  2. Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.

    باز کردن مرجع DOI
    کپی شد.