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

بهینه سازی پاوَسته [ ۱] یا بهینه سازی مقید ( Constrained optimization ) ، گونه ای از بهینه سازی می باشد که در آن تابع هزینه نسبت به متغیرهایی و باوجود پاوَندی ( قیودی ) بر روی این متغیرها بهینه می شود. این پاوَندها می توانند به صورت نابرابری یا برابری باشند که در نتیجه آن قیود به صورت تساوی یا نامساوی باید برقرار شوند.
یک مسئله بهینه سازی پاوسته در حالت کلی به گونه زیر می تواند باشد:
min   f ( x ) s u b j e c t   t o   g i ( x ) = c i for  i = 1 , … , n Equality constraints   h j ( x ) ≤ d j for  j = 1 , … , m Inequality constraints
که در آن g i ( x ) = c i برای i = 1 , … , n و h j ( x ) ≤ d j برای j = 1 , … , M به ترتیب پاوندهای مساوی و نامساوی هستند، که باید برقرار شوند. همچنین f ( x ) تابع هزینه می باشد که باید با توجه به این قیود کمینه شود.
درصورتی که:
• تابع هزینه تابع محدبی باشد،
• پاوندهای نابرابری نیز تابع هایی محدب باشند،
• پاوندهای برابری توابعی هَمگر ( affine ) [ ۲] باشند،
آنگاه این یک مسئله بهینه سازی محدب خواهد بود.
به یاری شرایط کاروش–کون–تاکر، می توان شرط کافی برای جواب بهینه را پیدا کرد. [ ۳]
برای همین، نخست تابع لاگرانژین را به صورت زیر می نویسیم.
L ( x , λ , ν ) = f ( x ) + ∑ i n ν i ( g i ( x ) − c i ) + ∑ i m λ i ( h i ( x ) − d i )
که در آن λ = { λ i } i = 1 m و ν = { ν i } i = 1 n ضرایب لاگرانژ برای پاوندهای نامساوی و مساوی هستند که به ترتیب برابرند با { h i ( x ^ ) − d i } i ≤ 0 و { g j ( x ^ ) − c j } j = 0 .
سپس شرط لازم ( و نه کافی ) برای بهینگی نقطه x ∗ به کمک معادلات زیر، که به شرایط کاروش–کون–تاکر شناخته می شود، دست یافتنی است.
∇ x L ( x ∗ , λ ∗ , ν ∗ ) = 0 g i ( x ∗ ) − c i = 0 ,   for   i = 1 , … , n λ i ∗ ( h i ( x ∗ ) − d i ) = 0 ,   for   i = 1 , … , m λ i ∗ ≥ 0