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

فرض کنید به ما یک مسئله‌ی برنامه‌نویسی خطی داده شده به شکل زیر داده شده است که ${\displaystyle x\in \mathbb {R} ^{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 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 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 \lambda }$

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

کتاب‌ها

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.{{}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

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]. Vol. 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]. Vol. 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 (ed.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Vol. 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.