بهینه‌سازی مقید
بهینه‌سازی مقید (Constrained optimization)، گونه‌ای از بهینه‌سازی می‌باشد که در آن تابع هزینه نسبت به متغیرهایی و باوجود قیودی بر روی این متغیرها بهینه می‌شود. این قیدها می‌توانند به‌صورت نامساوی یا مساوی باشند که در نتیجه آن قیود به‌صورت تساوی یا نامساوی باید برقرار شوند.
یک مسئله بهینه‌سازی مقید در حالت کلی به گونه زیر می‌تواند باشد:
formula_1
که در آن formula_2 برای formula_3 و formula_4 برای formula_5 به‌ترتیب قیدهای مساوی و نامساوی هستند، که باید برقرار شوند. همچنین formula_6 تابع هزینه می‌باشد که باید با توجه به این قیود کمینه شود.
درصورتی که:آنگاه این یک مسئله بهینه‌سازی محدب خواهد بود.
به یاری شرایط کاروش–کون–تاکر، می‌توان شرط کافی برای جواب بهینه را پیدا کرد.
برای همین، نخست تابع لاگرانژین را به‌صورت زیر می‌نویسیم.
formula_7
که در آن formula_8 و formula_9 ضرایب لاگرانژ برای قیدهای نامساوی و مساوی هستند که به ترتیب برابرند با formula_10 و formula_11.
سپس شرط لازم (و نه کافی) برای بهینگی نقطه formula_12 به کمک معادلات زیر، که به شرایط کاروش–کون–تاکر شناخته می‌شود، دست‌یافتنی است.
formula_13
که در آن formula_14 و formula_15 ضرایب بهینه لاگرانژ هستند که از طریق آن، جواب بهینه (حتما بهینه محلی و نه لزوما بهینه سراسری) بدست‌ می‌آید.
در اینجا اثبات می‌شود که هیچ نقطه دیگری در همسایگی formula_16، مانند formula_17، پیدا نمی‌شود که قیدهای formula_10 و formula_11 را برقرار کند اما مقداری بهینه‌تر از formula_12 داشته باشد. یعنی هرگز نمی‌توانیم داشته باشیم: formula_21 .
formula_22 که تابعی از متغیر formula_23 می باشد محدب است. دلیل محدب بودن تابع این است که این تابع ترکیبی خطی از توابع محدبِ formula_6 و formula_25 و formula_26 می‌باشد. بنابر این با توجه به شرط نخست کاروش–کون–تاکر، یعنی formula_27، داریم:
formula_28
از آنجا که برای formula_29 داشتیم: formula_30، پیامد آن formula_31 است و با نگرش به اینکه: formula_11 داریم:
formula_33
از سوی دیگر با توجه به برقراری شرایط کاروش–کون–تاکر برای formula_12، formula_35 و formula_36، می توان افزود:
formula_37
پس داریم:
formula_38
بنابراین برای هر نقطه در همسایگی formula_16 مانند formula_17، مقدار تابع بیشتر خواهد بود که نشان می‌دهد شرایط کاروش–کون–تاکر، موجب بهینگی نقطه formula_12 می‌شود.
چنانچه مسئله بالا‌گفته شده، یک مسئله محدب باشد، آنگاه شرایط کاروش–کون–تاکر نقطه‌ سراسری (global) بهینه را بدست می‌دهد.
می‌خواهیم نشان دهیم که برای هر نقطه formula_23 ای که در شرایط تساوی و نامساوی بگنجد، مقدار تابع هزینه در آن بیشتر از نقطه‌ formula_43 ایست که از شرایط کاروش–کون–تاکر برمی‌آید، یعنی formula_44. در صورتی که مسئله بهینه‌سازی محدب باشد، آنگاه تابع لاگرانژین formula_22 محدب خواهد بود. دلیل آن این است که تابع‌های formula_6 و formula_25 محدب هستند و formula_48 و تابع formula_26 نیز همگر (affine) است که علامت formula_50 مهم نمی‌شود. در نتیجه با توجه به ویژگی تابع محدب داریم:
formula_51
از آنجا که formula_52 (شرط نخست کاروش–کون–تاکر)، داریم:
formula_53
با نگاه به شرایط کاروش–کون–تاکر، داریم:
formula_54
اما از آنجا که برای نقطه formula_23 شرایط تساوی و نامساوی برقرار است، داریم:
formula_56
که سرانجام به رابطه زیر می‌رسیم. formula_57
در این روش با توجه به قید تساوی، مسئله به یک بهینه‌سازی نامقید تبدیل می‌شود. برای این منظور باید مقادیر متغیرها باتوجه به قید در تابع هزینه جایگزین شوند. برای مسائل بسیار ساده، مثلاً توابع دو متغیره که دارای قید تساوی هستند، استفاده از روش جایگزینی گزینه مناسبی است. ایده اصلی این است که قیود را در تابع هزینه جایگزین کنیم تا یک تابع ترکیبی ایجاد شود که تأثیر قیود را در بر می‌گیرد. برای مثال، فرض کنید هدف بیشینه کردن formula_58 مشروط به formula_59 باشد. قید مذکور به این معنی است که formula_60 . این تساوی را می‌توان در تابع اصلی وارد کرد، یعنی formula_61حال اگر مشتق را نسبت به formula_62 حساب کنیم و متغییری که مشتق را صفر می‌کند بیابیم، خواهیم داشت: formula_63 . این معادله ساده به formula_64 و formula_65 می‌‌انجامد که تابع formula_58 را به شرط formula_59 بیشینه می‌کند.
در این روش به کمک روش ضرایب لاگرانژ، مسئله به یک بهینه‌سازی نامقید تبدیل می‌شود. وانگهی متغیرهای مسئله جدید، برابر متغیرهای قبلی و متغیرهای لاگرانژ به تعداد قیدهای تساوی است.
اگر بهینه‌سازی محدب باشد، شرایط کاروش–کون–تاکر شرطی کافی و لازم برای نقطه بهینه سراسری (global) خواهد بود. جز این، شرط KKT تنها شرط لازم خواهد بود.
به یاری شرایط کاروش–کون–تاکر، می‌توان مسئله را با به‌کارگیری از روش پیش‌بینی-ویرایش حل کرد. برای این منظور معمولاً لازم است تا شرط محدب بودن مسئله بهینه‌سازی درنگریسته شود.