ساده‌سازی لاگرانژی
یکی از مسائل مهم در بهینه سازی ریاضی، ساده‌سازی لاگرانژی است که از روش های ساده سازی مسئله می‌باشد. این روش، یک مشکل دشوارِ بهینه سازی محدود را با کمک تقریب به یک مشکل ساده‌تر بدل می‌کند. یک راه حل برای مشکل ساده‌سازی‌شده، یک راه حل تقریبی برای مسئله اصلی است و اطلاعات مفیدی را در اختیار قرار می دهد.
این روش، روی نقض کردن محدودیت‌های نامعادله را با کمک یک ضریب لاگرانژ بازخورد منفی می‌دهد که باعث می‌شود این نقض کردن‌ها هزینه داشته باشد. در بهینه‌سازی، به جای استفاده از محدودیت‌های نامعادله(که غیرقابل ساده‌سازی هستند) از این هزینه‌های اضافه شده استفاده می‌شود. در کاربردهای عملیاتی، این مشکل ساده‌سازی‌شده اغلب راحت‌تر از مشکل اصلی حل می‌شود.
مسئله‌ی بیشینه کردن تابع لاگرانژی از متغیرهای دوگانه (ضریب‌های لاگرانژی) مسئله دوگانه لاگرانژی است .
فرض کنید به ما یک مسئله‌ی برنامه‌نویسی خطی داده شده به شکل زیر داده شده است که formula_1formula_2و formula_3:
مقدار formula_4را بیشینه کنید
با فرض این محدودیت که:
formula_5
اگر محدودیت‌های موجود در A را به دو دسته‌ی زیر تقسیم کنیم:
و با فرض اینکه می‌دانیم formula_8است، می‌توان معادله را به صورت زیر نوشت:
مقدار formula_4را بیشینه کنید
با فرض این محدودیت‌ها که:
می‌توانیم محدودیت شماره‌ی ۲ را در صورت مسئله اعمال کنیم و مسئله را به این صورت تغییر دهیم:
مقدار formula_12را بیشینه کنید
با فرض این محدودیت که:
اگر لاندا formula_14 را به صورت وزن‌های نامنفی فرض کنیم، اگر محدودیت شماره‌ی ۲ را نقض کنیم جریمه خواهیم خورد و اگر محدودیت مورد نظر را ارضا کنیم شامل پاداش خواهیم شد.
این روش ساده‌سازی لاگرانژی از مشکل اصلی ما نامیده می‌شود.
یکی از ویژگی‌های کاربردی این راه‌حل آن است که برای هر مجموعه‌ی ثابت از مقادیر formula_15نتیجه‌ی بهینه‌ی ساده‌سازی لاگرانژی، از نتیجه‌ی بهینه‌ی مسئله‌ی اصلی کوچکتر نخواهد بود. برای آن‌که این موضوع اثبات شود، formula_16را راه حل بهینه‌ی مسئله‌ی اصلی در نظر بگیرید و formula_17را راه حل بهینه‌ی ساده‌سازی لاگرانژی در نظر بگیرید. در ادامه خواهیم داشت:
نامعادله‌ی اول درست است زیرا formula_16در مسئله‌ی اصلی قابل قبول است و نامعادله‌ی دوم صحیح است زیرا formula_17اه حل بهینه برای آساده‌سازی اگرانژی است.
نامعادله‌ی فوق به ما می گوید اگر حداکثر مقدار به دست آمده از مشکل آرامش را کمینه کنیم، در رسیدن به مقدار هدف مسئله اصلی خود محدودیت محکم‌تری به دست می آوریم. بنابراین می‌توانیم به جای بررسی مشکلی که به صورت جزئی دوگانه شده است، به بررسی مشکل اصلی بپردازیم.
formula_21را کمینه کنید
با در نظر گرفتن محدودیت:
در حالی که formula_21را به صورت زیر تعریف می‌کنیم:
formula_12را بیشینه کنید
با در نظر گرفتن نامعادله‌ی:
formula_10
در نتیجه یک الگوریتم ساده‌سازی لاگرانژی به این صورت کار می‌کند که بازه‌ای از مقادیر formula_26قابل قبول را جستجو می‌کند تا نتیجه‌ی تولید شده توسط مسئله‌ی درونی formula_27را کمینه کند. هر مقدار بازگشتی توسط formula_27یک کاندیدا برای حد بالای مسئله است، که کوچکترین مقدار آن به عنوان بهترین حد بالا در نظر گرفته می‌شود. اگر افزون بر این، از یک تابع اکتشافی هیوریستیک (که با استفاده از مقدار formula_17که از formula_27برگشته‌اند، دسته‌بندی شده‌اند.) استفاده کنیم، می‌توانیم روی مسئله تکرار انجام دهیم تا بهترین حد بالا و هزینه‌ی بهترین راه‌حل قابل قبول به اندازه‌ای که می‌خواهیم به جواب اصلی نزدیک شوند.
روش تقویت‌شده لاگرانژی از نظر ساختاری کاملاً شبیه به روش ساده‌سازی لاگرانژی است، اما یک جمله به آن اضافه می‌کند و پارامترهای دوگانه formula_26را با روشی اصولی‌تر به روز می کند. این روش در دهه 1970 معرفی شد و از آن موقع به صورت گسترده مورد استفاده قرار گرفته است.
روش مجازات از متغیرهای دوگانه استفاده نمی‌کند. بلکه محدودیت ها را حذف می‌کند و در عوض انحراف از محدودیت مجازات می‌کند. این روش از نظر مفهومی ساده است اما معمولاً روشهای تقویت‌شده لاگرانژی در عمل ترجیح داده می شوند زیرا روش مجازات در وضعیت‌های بدتنظیم‌شده به خوبی کار نمی‌کند.
Bertsekas, Dimitri P. (1999). "Nonlinear Programming: 2nd Edition." Athena Scientific. .