بهینه‌سازی مقید

بهینه‌سازی پاوَسته یا بهینه‌سازی مقید

بهینه‌سازی پاوَسته یا بهینه‌سازی مقید (Constrained optimization)، گونه‌ای از بهینه‌سازی می‌باشد که در آن تابع هزینه نسبت به متغیرهایی و باوجود پاوَندی (قیودی) بر روی این متغیرها بهینه می‌شود. این پاوَندها می‌توانند به‌صورت نابرابری یا برابری باشند که در نتیجه آن قیود به‌صورت تساوی یا نامساوی باید برقرار شوند.

فرم کلی

یک مسئله بهینه‌سازی پاوسته در حالت کلی به گونه زیر می‌تواند باشد:

${\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\leq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}$

که در آن $g_{i}(x)=c_{i}$ برای $i=1,\ldots ,n$ و $h_{j}(x)\leq d_{j}$ برای $j=1,\ldots ,M$ به‌ترتیب پاوندهای مساوی و نامساوی هستند، که باید برقرار شوند. همچنین $f(x)$ تابع هزینه می‌باشد که باید با توجه به این قیود کمینه شود.

درصورتی که:

1. تابع هزینه تابع محدبی باشد،
2. پاوندهای نابرابری نیز تابع‌هایی محدب باشند،
3. پاوندهای برابری توابعی هَمگر (affine) باشند،

آنگاه این یک مسئله بهینه‌سازی محدب خواهد بود.

شرط لازم جواب

به یاری شرایط کاروش–کون–تاکر، می‌توان شرط کافی برای جواب بهینه را پیدا کرد.

برای همین، نخست تابع لاگرانژین را به‌صورت زیر می‌نویسیم.

$L(x,\lambda ,\nu )=f(x)+\sum _{i}^{n}\nu _{i}{\big (}g_{i}(x)-c_{i}{\big )}+\sum _{i}^{m}\lambda _{i}{\big (}h_{i}(x)-d_{i}{\big )}$

که در آن $\lambda =\{\lambda _{i}\}_{i=1}^{m}$ و $\nu =\{\nu _{i}\}_{i=1}^{n}$ ضرایب لاگرانژ برای پاوندهای نامساوی و مساوی هستند که به ترتیب برابرند با $\{h_{i}({\hat {x}})-d_{i}\}_{i}\leq 0$ و $\{g_{j}({\hat {x}})-c_{j}\}_{j}=0$.

سپس شرط لازم (و نه کافی) برای بهینگی نقطه $x^{*}$ به کمک معادلات زیر، که به شرایط کاروش–کون–تاکر شناخته می‌شود، دست‌یافتنی است.

${\begin{array}{rcll}\nabla _{x}L(x^{*},\lambda ^{*},\nu ^{*})=0\\g_{i}(x^{*})-c_{i}=0,~{\mbox{for}}~i=1,\ldots ,n\\\lambda _{i}^{*}(h_{i}(x^{*})-d_{i})=0,~{\mbox{for}}~i=1,\ldots ,m\\\lambda _{i}^{*}\geq 0\end{array}}$

که در آن $\{\lambda _{i}^{*}\}_{i=1}^{m}$ و $\{\nu _{i}^{*}\}_{i=1}^{n}$ ضرایب بهینه لاگرانژ هستند که از طریق آن، پاسخ بهینه (حتما بهینه محلی و نه لزوما بهینه سراسری) بدست‌ می‌آید.

اثبات

در اینجا اثبات می‌شود که هیچ نقطه دیگری در همسایگی $x^{*}$، مانند ${\hat {x}}$، پیدا نمی‌شود که پاوندهای $\{h_{i}({\hat {x}})-d_{i}\}_{i}\leq 0$ و $\{g_{j}({\hat {x}})-c_{j}\}_{j}=0$ را برقرار کند اما مقداری بهینه‌تر از $x^{*}$ داشته باشد. یعنی هرگز نمی‌توانیم داشته باشیم: $f(x^{*})>f({\hat {x}})$ .

$L(x,\lambda ^{*},\nu ^{*})$ که تابعی از متغیر $x$ می باشد محدب است. دلیل محدب بودن تابع این است که این تابع ترکیبی خطی از توابع محدبِ $f(x)$ و $h_{i}(x)$ و $g_{i}(x)$ می‌باشد. بنابر این با توجه به شرط نخست کاروش–کون–تاکر، یعنی $\nabla _{x}L(x^{*},\lambda ^{*},\nu ^{*})=0$، داریم:

$L(x^{*},\lambda ^{*},\nu ^{*})\leq L({\hat {x}},\lambda ^{*},\nu ^{*})$

از آنجا که برای ${\hat {x}}$ داشتیم: $\{h_{i}({\hat {x}})-d_{i}\}_{i}\leq 0$، پیامد آن $\{\lambda _{i}^{*}{\big (}\{h_{i}({\hat {x}})-d_{i}\}_{i}{\big )}\leq 0\}_{i}$ است و با نگرش به اینکه: $\{g_{j}({\hat {x}})-c_{j}\}_{j}=0$ داریم:

$L(x^{*},\lambda ^{*},\nu ^{*})\leq L({\hat {x}},\lambda ^{*},\nu ^{*})\leq f({\hat {x}})+\sum _{i}^{m}\lambda _{i}^{*}(h_{i}({\hat {x}})-d_{i})\leq f({\hat {x}})$

از سوی دیگر با توجه به برقراری شرایط کاروش–کون–تاکر برای $x^{*}$، $\lambda ^{*}$ و $\nu ^{*}$، می توان افزود:

$f(x^{*})=L(x^{*},\lambda ^{*},\nu ^{*})\leq L({\hat {x}},\lambda ^{*},\nu ^{*})\leq f({\hat {x}})$

پس داریم:

$f(x^{*})\leq f({\hat {x}})$

بنابراین برای هر نقطه در همسایگی $x^{*}$ مانند ${\hat {x}}$، مقدار تابع بیشتر خواهد بود که نشان می‌دهد شرایط کاروش–کون–تاکر، موجب بهینگی نقطه $x^{*}$ می‌شود.

شرط کافی و لازم جواب

چنانچه مسئله بالا‌گفته شده، یک مسئله محدب باشد، آنگاه شرایط کاروش–کون–تاکر نقطه‌ سراسری (global) بهینه را بدست می‌دهد.

اثبات

می‌خواهیم نشان دهیم که برای هر نقطه $x$ ای که در شرایط تساوی و نامساوی بگنجد، مقدار تابع هزینه در آن بیشتر از نقطه‌ $x^{*}$ ایست که از شرایط کاروش–کون–تاکر برمی‌آید، یعنی $f(x^{*})\leq f(x)$. در صورتی که مسئله بهینه‌سازی محدب باشد، آنگاه تابع لاگرانژین $L(x,\lambda ^{*},\nu ^{*})$ محدب خواهد بود. دلیل آن این است که تابع‌های $f(x)$ و $h_{i}(x)$ محدب هستند و $\lambda _{i}^{*}\geq 0$ و تابع $g_{i}(x)$ نیز همگر (affine) است که علامت $\nu$ مهم نمی‌شود. در نتیجه با توجه به ویژگی تابع محدب داریم:

$L(x^{*},\lambda ^{*},\nu ^{*})-L(x,\lambda ^{*},\nu ^{*})\leq \nabla _{x}L(x^{*},\lambda ^{*},\nu ^{*})^{\top }(x^{*}-x)$

از آنجا که $\nabla _{x}L(x^{*},\lambda ^{*},\nu ^{*})=0$ (شرط نخست کاروش–کون–تاکر)، داریم:

$L(x^{*},\lambda ^{*},\nu ^{*})\leq L(x,\lambda ^{*},\nu ^{*})$

با نگاه به شرایط کاروش–کون–تاکر، داریم:

$f(x^{*})=L(x^{*},\lambda ^{*},\nu ^{*})\leq L(x,\lambda ^{*},\nu ^{*})$

اما از آنجا که برای نقطه $x$ شرایط تساوی و نامساوی برقرار است، داریم:

$f(x^{*})=L(x^{*},\lambda ^{*},\nu ^{*})\leq L(x,\lambda ^{*},\nu ^{*})\leq f(x)$

که سرانجام به رابطه زیر می‌رسیم.

$f(x^{*})\leq f(x)$

روش‌های حل

بهینه‌سازی پاوسته به برابری (Equality Constrained Optimization)

روش جایگزینی

در این روش با توجه به قید تساوی، مسئله به یک بهینه‌سازی نامقید تبدیل می‌شود. برای این منظور باید مقادیر متغیرها باتوجه به قید در تابع هزینه جایگزین شوند. برای مسائل بسیار ساده، مثلاً توابع دو متغیره که دارای قید تساوی هستند، استفاده از روش جایگزینی گزینه مناسبی است. ایده اصلی این است که قیود را در تابع هزینه جایگزین کنیم تا یک تابع ترکیبی ایجاد شود که تأثیر قیود را در بر می‌گیرد. برای مثال، فرض کنید هدف بیشینه کردن $f(x,y)=x\cdot y$ مشروط به $x+y=10$ باشد. قید مذکور به این معنی است که $y=10-x$ . این تساوی را می‌توان در تابع اصلی وارد کرد، یعنی $p(x)=x(10-x)=10x-x^{2}$حال اگر مشتق را نسبت به $x$ حساب کنیم و متغییری که مشتق را صفر می‌کند بیابیم، خواهیم داشت: ${\frac {\partial p}{\partial x}}=10-2x=0$ . این معادله ساده به $x=5$ و $y=10-5=5$ می‌‌انجامد که تابع $f(x,y)=x\cdot y$ را به شرط $x+y=10$ بیشینه می‌کند.

روش ضرایب لاگرانژ

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

بهینه‌سازی پاوسته به نابرابری (Inequality Constrained Optimization)

شرایط کاروش–کون–تاکر

اگر بهینه‌سازی محدب باشد، شرایط کاروش–کون–تاکر شرطی کافی و لازم برای نقطه بهینه سراسری (global) خواهد بود. جز این، شرط KKT تنها شرط لازم خواهد بود.

به یاری شرایط کاروش–کون–تاکر، می‌توان مسئله را با به‌کارگیری از روش پیش‌بینی-ویرایش حل کرد. برای این منظور معمولاً لازم است تا شرط محدب بودن مسئله بهینه‌سازی درنگریسته شود.

جستارهای وابسته

• بهینه‌سازی
• کمترین مربعات