Convex QP Solver؛ پیاده‌سازی حل عددی بهینه‌سازی مقید

پیاده‌سازی Python برای حل برنامه‌ریزی درجه‌دو محدب با روش primal-dual interior-point و Mehrotra predictor-corrector، همراه با اعتبارسنجی عددی و مقایسه با solverهای مرجع.

گفت‌وگو درباره مسئله مشاهده راهکار مرتبط

زمینه

بخش مهمی از مسائل تصمیم‌گیری صنعتی را می‌توان به مسائل constrained optimization تبدیل کرد. در این پروژه تمرکز روی پیاده‌سازی یک solver برای convex quadratic programming است؛ جایی که هم مدل ریاضی و هم رفتار عددی الگوریتم اهمیت دارد.

مسئله

صورت مسئله برنامه‌ریزی درجه‌دو محدب

\min_x \; \frac{1}{2}x^T P x + q^T x \quad \text{s.t.} \quad Ax=b,\; Gx\le h

هدف، ساخت هسته‌ای بود که علاوه بر حل مسئله، diagnostics مربوط به stationarity، primal feasibility، complementarity و duality gap را نیز در اختیار بگذارد.

محدودیت‌ها و الزامات

حفظ شرایط ریاضی لازم برای convex QP
حل KKT system در مسیر dense یا sparse
کنترل فاصله از مرز قیود با fraction-to-boundary
اعتبارسنجی عددی با مجموعه‌ای از مسائل
مقایسه خروجی با solverهای مرجع OSQP و Clarabel
آزمون unit، property-based و API

رویکرد

هسته solver بر primal-dual interior-point و نسخه Mehrotra predictor-corrector بنا شده است. سیستم KKT در مسیر dense با NumPy و در مسیر sparse با SciPy SuperLU حل می‌شود و لایه validation از حل عددی جدا نگه داشته شده است.

text

QP Model -> Validation -> IPM / Mehrotra
                       -> KKT System
                       -> Residual Diagnostics

تصمیم‌ها و مصالحه‌ها

تصمیم	دلیل
Primal-dual interior-point	مناسب برای ساخت یک مسیر حل عمومی برای convex QP با قیود.
Mehrotra predictor-corrector	بهبود مسیر مرکزی با یک گام پیش‌بین و اصلاح‌کننده.
Dense + sparse KKT paths	امکان مقایسه و استفاده متناسب با ساختار مسئله.
Reference solver comparison	اعتبارسنجی عددی فقط به تست داخلی محدود نماند.
Diagnostics به‌عنوان خروجی	موفقیت حل فقط به x نهایی خلاصه نشود.

نتیجه

خروجی یک solver برای Convex QP با رویکرد پژوهش‌محور است که diagnostics عددی و validation در برابر رفتار solverهای مرجع دارد. README پروژه 84 تست موفق، 93 درصد پوشش منبع solver و توافق با OSQP و Clarabel را گزارش می‌کند. این پروژه نشان می‌دهد که می‌توان از صورت‌بندی ریاضی و ساختار مسئله تا طراحی الگوریتم، پیاده‌سازی عددی و اعتبارسنجی مستقل پیش رفت.

عمق فنی

Primal-dual interior-point و Mehrotra predictor-corrector
KKT residuals: stationarity، primal feasibility، complementarity و duality gap
Dense NumPy و sparse SciPy SuperLU
Property-based tests و numerical validation corpus
CLI و REST API با OpenAPI/Swagger

شواهد

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

GitHub — Convex Quadratic Programming Solver

Repository شامل solver، validation، benchmarks، مستندات ریاضی، تست‌ها و API است.

باز کردن منبع

راهکارهای مرتبط

مدل‌سازی، الگوریتم و بهینه‌سازی

آموزش‌های ریاضی مرتبط

از مسئله واقعی تا مدل ریاضی بهینه‌سازی KKT و روش‌های interior-point؛ وقتی قیود وارد بازی می‌شوند Residual چیست و چرا جواب عددی را باید بررسی کرد؟

مسئله بهینه‌سازی یا تصمیم‌گیری دارید؟

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

گفت‌وگو درباره مسئله