Karesel Programlama (QP)

Karesel programlama, min (1/2) x^T Q x + c^T x s.t. Ax ≤ b, x ≥ 0 kanonik formundaki problem sınıfıdır; Q ∈ R^(n×n) simetrik bir matristir, c ∈ R^n doğrusal terim ve kısıtlar tıpkı LP'deki gibi doğrusaldır. Problemin yapısı Q'nun işaretine göre belirlenir: (1) Q pozitif yarı-tanımlı ise QP dışbükeydir, KKT koşulları gerek-yeter optimum koşulları olur ve polinom zamanda iç-nokta veya etkin-küme (active-set) yöntemleri ile çözülür (Kozlov, Tarasov ve Khachiyan 1979 dışbükey QP'nin polinom çözülebilirliğini gösterdi); (2) Q tanımsız (indefinite) ise problem dışbükey değildir ve genel olarak NP-hard (Sahni 1974). Klasik formülasyon Markowitz'in (1952) ortalama-varyans portföy seçim modelidir: min (1/2) x^T Σ x s.t. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ kovaryans matrisi, μ beklenen getiri vektörü, R hedef getiri; etkin sınır (efficient frontier) farklı R seviyeleri için QP çözülerek elde edilir. Markowitz bu çalışmayla 1990 Nobel Ekonomi Ödülünü kazandı. QP ayrıca destek vektör makineleri eğitiminde (Cortes ve Vapnik 1995), model öngörülü kontrolde (MPC), least-squares with constraints, sequential quadratic programming (SQP, doğrusal-olmayan optimizasyonun iç döngüsü, Wilson 1963 / Han 1976 / Powell 1978) ve trajektör optimizasyonunda kullanılır. Çözüm algoritmaları: Wolfe (1959) etkin-küme yöntemi, Beale (1959) prensiplerini geliştirdi; iç-nokta predictor-corrector (Mehrotra 1992 mantığı QP'ye genişletilir); active-set yaklaşımı LP'nin simpleksiyle ortak köke sahiptir.