بهینه‌سازی دو مرحله‌ای

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

فرمولاسیون ریاضی مسئله

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

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)$

subject to: $G_{i}(x,y)\leq 0$, for $i\in \{1,2,\ldots ,I\}$;

$y\in \arg \min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$

where

$F,f:R^{n_{x}}\times R^{n_{y}}\to R$

$G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R$

$X\subseteq R^{n_{x}}$

$Y\subseteq R^{n_{y}}.$

در فرمولاسیون بالا، $F$ نماد تابع هدف سطح بالایی و $f$ نماد تابع هدف سطح پایینی است. مشابهاً $x$ نماد بردار تصمیم سطح بالایی و $y$ نماد بردار تصمیم سطح پایینی است.$G_{i}$ و $g_{j}$ نماد توابع قید نابرابری به ترتیب در سطوح بالایی و پایینی هستند. اگر تابع هدفی قرار است حداکثرسازی شود، این معادل حداقل سازی منفی آن است. فرمولاسیون بالا قدر به نشان دادن قیود برابری نیز هست زیرا این‌ها می‌توان به سادگی به صورت قیود نابرابری بازنویسی کرد: مثلاً، $h(x)=0$ را می‌توان به صورت $\{h(x)\leq 0,\ -h(x)\leq 0\}$ نوشت.

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Bilevel optimization». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۸ دسامبر ۲۰۱۵.