Karesel Programlama (KP)
Quadratic Programming (QP) · Ayrıca şöyle bilinir: QP Optimization, Quadratic Optimization, Convex Quadratic Programming, İkinci Dereceden Programlama
Karesel Programlama (KP), hedef fonksiyonunun karesel ve kısıtlarının doğrusal olduğu bir sınırlı matematiksel optimizasyon türüdür. Frank ve Wolfe (1956) tarafından gradyan tabanlı uygun yön algoritmasıyla biçimlendirilen KP, operasyon araştırmaları, finans, makine öğrenmesi ve mühendislik tasarımında, doğrusal fizibilite koşullarına tabi olarak dışbükey (veya dışbükey olmayan) bir karesel maliyetin minimize edilmesi gerektiği her yerde temel oluşturur.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Hedefiniz gerçekten karesel (örneğin, varyans minimizasyonu, kısıtlı en küçük kareler, SVM'lerde marj maksimizasyonu) ve kısıtlarınız doğrusal olduğunda KP kullanın. Dışbükey KP küresel bir optimallik garanti eder; dışbükey olmayan KP (belirsiz Q) dal-ve-sınır yöntemleri gerektirebilir. Hedef doğrusal ise doğrusal programlamayı, kısıtların kendisi karesel veya matris değerli olduğunda ikinci dereceden koni veya yarı-kesin programlamayı tercih edin. Problem boyutu, Q'nun seyreklik derecesi ve mevcut çözücüler (OSQP, Gurobi, CPLEX, quadprog) uygulama seçimini yönlendirmelidir.
Güçlü yönler & sınırlılıklar
- Dışbükey KP için polinom zamanında çözülebilirlik, verimli, küresel olarak optimal çözümler garanti eder.
- KKT çarpanları aracılığıyla hem eşitlik hem de eşitsizlik kısıtlarını yerel olarak ele alır.
- Büyük seyrek problemler için geçerli olan olgun, yüksek performanslı çözücüler tarafından yaygın olarak desteklenir.
- Doğrusal programlama (dejeneratif KP) ile genel doğrusal olmayan optimizasyon arasında elverişli bir orta zemin oluşturur.
- Dışbükey olmayan KP (belirsiz veya pozitif yarı-kesin olmayan Q) en kötü durumda NP-zor'dur.
- Bellek ve hesaplama maliyeti, yoğun Q matrisleri için problem boyutuna göre karesel olarak ölçeklenir.
- Q neredeyse tekil olduğunda veya kısıtlar neredeyse gereksiz olduğunda sayısal kararsızlık ortaya çıkabilir.
- Frank–Wolfe yöntemi, optimuma yakın yerlerde aktif-küme veya iç-nokta yöntemlerine kıyasla yavaş (alt-doğrusal) yakınsar.
SSS
KP, doğrusal programlamadan nasıl farklıdır?
Doğrusal programlamada hem hedef hem de kısıtlar doğrusaldır, bu nedenle optimal çözüm her zaman fizibil politop'un bir köşesinde yer alır. KP'de hedef kareseldir, bu nedenle optimum iç kısımda yer alabilir. Bu daha zengin yapı, KP'nin LP'nin yapamadığı varyans, enerji ve marj problemlerini modellemesini sağlar, ancak aynı zamanda çözmek için daha gelişmiş algoritmalar gerektirir.
Bir KP probleminin benzersiz bir küresel minimuma sahip olacağı ne zaman garanti edilir?
Hedefin Hessian matrisi Q kesin pozitif kesin olduğunda (tüm özdeğerler kesin pozitif) ve fizibil bölge boş olmadığında bir KP problemi benzersiz bir küresel minimuma sahiptir. Eğer Q sadece pozitif yarı-kesin ise minimum benzersiz olmayabilir; eğer Q belirsiz ise problem birden fazla yerel minimuma sahip dışbükey olmayan bir problem olabilir ve küresel çözüm genellikle NP-zor'dur.
Pratik KP problemleri için hangi çözücü kullanılmalıdır?
Küçük ila orta boyutlu yoğun problemler için quadprog (MATLAB/R) veya SLSQP yöntemli scipy.optimize.minimize erişilebilir seçeneklerdir. Büyük seyrek dışbükey KP'ler için OSQP (açık kaynak) ve Gurobi veya CPLEX (ticari) en gelişmiş iç-nokta ve aktif-küme uygulamalarını sunar. Seçim, problem boyutuna, seyrek yapıya, gerçek zamanlı gereksinimlere ve lisanslama kısıtlarına bağlıdır.
Kaynaklar
- Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2), 95–110. DOI: 10.1002/nav.3800030109 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 2). Quadratic Programming (QP). ScholarGate. https://scholargate.app/tr/optimization/quadratic-programming
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Dışbükey OptimizasyonOptimizasyon↔ karşılaştır
- Doğrusal ProgramlamaOptimizasyon↔ karşılaştır