ساده‌سازی لاگرانژی

یکی از مسائل مهم در بهینه سازی ریاضی، ساده‌سازی لاگرانژی است که از روش های ساده سازی مسئله می‌باشد. این روش، یک مشکل دشوارِ بهینه سازی محدود را با کمک تقریب به یک مشکل ساده‌تر بدل می‌کند. یک راه حل برای مشکل ساده‌سازی‌شده، یک راه حل تقریبی برای مسئله اصلی است و اطلاعات مفیدی را در اختیار قرار می دهد.

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

مسئله‌ی بیشینه کردن تابع لاگرانژی از متغیرهای دوگانه (ضریب‌های لاگرانژی) مسئله دوگانه لاگرانژی است .

توضیحات ریاضی

فرض کنید به ما یک مسئله‌ی برنامه‌نویسی خطی داده شده به شکل زیر داده شده است که ${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle x\in \mathbb {R} ^{n}}$و ${\displaystyle A\in \mathbb {R} ^{m,n}}$:

مقدار ${\displaystyle c^{T}x}$را بیشینه کنید

با فرض این محدودیت که:

${\displaystyle Ax\leq b}$

اگر محدودیت‌های موجود در A را به دو دسته‌ی زیر تقسیم کنیم:

• ${\displaystyle A_{1}\in \mathbb {R} ^{m_{1},n}}$
• ${\displaystyle A_{2}\in \mathbb {R} ^{m_{2},n}}$

و با فرض اینکه می‌دانیم ${\displaystyle m_{1}+m_{2}=m}$است، می‌توان معادله را به صورت زیر نوشت:

مقدار ${\displaystyle c^{T}x}$را بیشینه کنید

با فرض این محدودیت‌ها که:

1. ${\displaystyle A_{1}x\leq b_{1}}$
2. ${\displaystyle A_{2}x\leq b_{2}}$

می‌توانیم محدودیت شماره‌ی ۲ را در صورت مسئله اعمال کنیم و مسئله را به این صورت تغییر دهیم:

مقدار ${\displaystyle c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)}$را بیشینه کنید

با فرض این محدودیت که:

1. ${\displaystyle A_{1}x\leq b_{1}}$

اگر لاندا ${\displaystyle \lambda =(\lambda _{1},\ldots ,\lambda _{m_{2}})}$ را به صورت وزن‌های نامنفی فرض کنیم، اگر محدودیت شماره‌ی ۲ را نقض کنیم جریمه خواهیم خورد و اگر محدودیت مورد نظر را ارضا کنیم شامل پاداش خواهیم شد.

این روش ساده‌سازی لاگرانژی از مشکل اصلی ما نامیده می‌شود.

محدودیت‌های راه حل ساده‌سازی لاگرانژ

یکی از ویژگی‌های کاربردی این راه‌حل آن است که برای هر مجموعه‌ی ثابت از مقادیر ${\displaystyle {\tilde {\lambda }}}$نتیجه‌ی بهینه‌ی ساده‌سازی لاگرانژی، از نتیجه‌ی بهینه‌ی مسئله‌ی اصلی کوچکتر نخواهد بود. برای آن‌که این موضوع اثبات شود، ${\displaystyle {\hat {x}}}$را راه حل بهینه‌ی مسئله‌ی اصلی در نظر بگیرید و ${\displaystyle {\bar {x}}}$را راه حل بهینه‌ی ساده‌سازی لاگرانژی در نظر بگیرید. در ادامه خواهیم داشت:

• ${\displaystyle c^{T}{\hat {x}}\leq c^{T}{\hat {x}}+{\tilde {\lambda }}^{T}(b_{2}-A_{2}{\hat {x}})\leq c^{T}{\bar {x}}+{\tilde {\lambda }}^{T}(b_{2}-A_{2}{\bar {x}})}$

نامعادله‌ی اول درست است زیرا ${\displaystyle {\hat {x}}}$در مسئله‌ی اصلی قابل قبول است و نامعادله‌ی دوم صحیح است زیرا ${\displaystyle {\bar {x}}}$اه حل بهینه برای آساده‌سازی اگرانژی است.

حرکت به سوی حل مسئله اصلی

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

${\displaystyle P(\lambda )}$را کمینه کنید

با در نظر گرفتن محدودیت:

• ${\displaystyle \lambda \geq 0}$

در حالی که ${\displaystyle P(\lambda )}$را به صورت زیر تعریف می‌کنیم:

${\displaystyle c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)}$را بیشینه کنید

با در نظر گرفتن نامعادله‌ی:

${\displaystyle A_{1}x\leq b_{1}}$

در نتیجه یک الگوریتم ساده‌سازی لاگرانژی به این صورت کار می‌کند که بازه‌ای از مقادیر ${\displaystyle \lambda }$قابل قبول را جستجو می‌کند تا نتیجه‌ی تولید شده توسط مسئله‌ی درونی ${\displaystyle P}$را کمینه کند. هر مقدار بازگشتی توسط ${\displaystyle P}$یک کاندیدا برای حد بالای مسئله است، که کوچکترین مقدار آن به عنوان بهترین حد بالا در نظر گرفته می‌شود. اگر افزون بر این، از یک تابع اکتشافی هیوریستیک (که با استفاده از مقدار ${\displaystyle {\bar {x}}}$که از ${\displaystyle P}$برگشته‌اند، دسته‌بندی شده‌اند.) استفاده کنیم، می‌توانیم روی مسئله تکرار انجام دهیم تا بهترین حد بالا و هزینه‌ی بهترین راه‌حل قابل قبول به اندازه‌ای که می‌خواهیم به جواب اصلی نزدیک شوند.

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

روش تقویت‌شده لاگرانژی از نظر ساختاری کاملاً شبیه به روش ساده‌سازی لاگرانژی است، اما یک جمله به آن اضافه می‌کند و پارامترهای دوگانه ${\displaystyle \lambda }$را با روشی اصولی‌تر به روز می کند. این روش در دهه 1970 معرفی شد و از آن موقع به صورت گسترده مورد استفاده قرار گرفته است.

روش مجازات از متغیرهای دوگانه استفاده نمی‌کند. بلکه محدودیت ها را حذف می‌کند و در عوض انحراف از محدودیت مجازات می‌کند. این روش از نظر مفهومی ساده است اما معمولاً روشهای تقویت‌شده لاگرانژی در عمل ترجیح داده می شوند زیرا روش مجازات در وضعیت‌های بدتنظیم‌شده به خوبی کار نمی‌کند.

منابع

کتاب‌ها

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.

Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. شابک ‎۱−۸۸۶۵۲۹−۰۰−۰ ISBN 1-886529-00-0.

Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc. pp. xiii+523. MR 1888251. Lemaréchal, Claude (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. Minoux, M. (1986). Mathematical programming: Theory and algorithms. Egon Balas (foreword) (Translated by Steven Vajda from the (1983 Paris: Dunod) French ed.). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique: Théorie et algorithmes. Editions Tec & Doc, Paris, 2008. xxx+711 pp. شابک ‎۹۷۸−۲−۷۴۳۰−۱۰۰۰−۳ MR2571910).

مقالات

Everett, Hugh, III (1963). "Generalized Lagrange multiplier method for solving problems of optimum allocation of resources". Operations Research. 11 (3): 399–417. doi:10.1287/opre.11.3.399. JSTOR 168028. MR 0152360. Archived from the original on 2011-07-24. Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "Lagrangian relaxation via ballstep subgradient methods". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241. Archived from the original on 26 July 2011. Retrieved 26 July 2019.