کمینه‌سازی مجموع یک تابع خطی و یک تابع کسری خطی با به‌کارگیری نمایش درجه‌دوی مخروطی: مسائل پیوسته و گسسته
نویسندگان: Ashkan Fakhri و Mehdi Ghatee
منتشرشده در:
Optimization: A Journal of Mathematical Programming and Operations Research، جلد 65، 2016 — شمارهٔ 5.
چکیده:
این مقاله می‌کوشد مجموع یک تابع خطی و یک تابع کسری خطی را روی مجموعه‌ای محدب و بسته که با چند قید خطی و درجه‌دو مخروطی تعریف شده است، کمینه کند. ابتدا برخی شرایط لازم و کافی برای شبه‌محدب‌بودن مسئله را ارائه می‌کنیم. برای هر یک از این شرایط، با چند فرض معقول، یک بازصورت‌بندی مناسب از مسئله به‌شکل برنامه‌ریزی مخروط مرتبهٔ دوم (SOCP) بیان و یک رویهٔ حل جدید و قابل‌استفاده پیشنهاد می‌شود. کارایی بازصورت‌بندی‌های پیشنهادی با آزمایش‌های عددی نشان داده می‌شود. در گام دوم، توجه خود را به متغیرهای دودویی محدود می‌کنیم و شرطی کافی برای بازنمایی‌پذیری به‌شکل SOCP به دست می‌آوریم. با استفاده از نتایج تجربی بر نمونه‌های تصادفی نشان می‌دهیم که بازصورت‌بندی مخروطی پیشنهادی، در مقایسه با روش شناخته‌شدهٔ خطی‌سازی کارآمدتر است و برش‌های مناسب‌تری برای الگوریتم شاخه‌وکران تولید می‌کند.