szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
quadratic programming (tsz. quadratic programmings)
- (informatika) kvadratikus programozás
A kvadratikus programozás (angolul: Quadratic Programming, QP) az optimalizálás egy speciális típusa, ahol a célfüggvény másodfokú (kvadratikus), de a feltételrendszer lineáris. Ez az egyik legalapvetőbb nemlineáris optimalizálási probléma, és számos gyakorlati alkalmazás alapja.
A kvadratikus programozás fontos szerepet játszik többek között:
- pénzügyi portfólióoptimalizálásban,
- gépi tanulásban (pl. SVM-ek),
- műszaki rendszerek irányításában,
- energiaelosztásban,
- közgazdaságtani modellezésben.
A QP általános alakja:
ahol:
a változók vektora,
szimmetrikus mátrix, amely a kvadratikus tagot adja (másodfokú rész),
a lineáris tag,
,
: egyenlőtlenségi korlátok,
,
: egyenlőségi korlátok.
3. Értelmezés
A célfüggvény:
egy másodfokú függvény: tartalmaz négyzetes tagokat és lineáris tagokat is. Ha
pozitív szemidefinit, a probléma konvex, így minden lokális minimum globális minimum is.
4. Mikor használjuk?
Kvadratikus programozást akkor használunk, ha:
- A célfüggvény kvadratikus (pl. négyzetes hibák minimalizálása)
- A korlátok lineárisak
- Gyorsabb megoldást akarunk, mint általános nemlineáris programozással
5. Tipikus alkalmazási példák
🧠 Gépi tanulás
- Támogató vektor gépek (SVM): a margin maximalizálása QP-probléma formájában fogalmazható meg.
💼 Pénzügy
- Portfólióoptimalizálás (Markowitz-modell): a várható hozam maximalizálása a kockázat (szórásnégyzet) minimalizálása mellett.
🏗️ Mérnöki alkalmazások
- Strukturális optimalizálás (pl. rudak elhelyezése minimális deformációval)
🧮 Regresszió és közelítés
- Kvadratikus közelítés hibaminimalizálással
6. Egy egyszerű példa
Cél:
Korlát:
Átalakítva:
- Kvadratikus rész:

- Lineáris rész:

- Egyenlőtlenség:

Ezt egy QP-megoldó program meg tudja oldani numerikusan.
7. Megoldási módszerek
🧮 KKT-feltételek (Karush–Kuhn–Tucker)
- Az optimalitás szükséges (és konvex esetben elegendő) feltételeit adják meg.
- A QP megoldása gyakran ezen feltételek alapján történik.
🧠 Active-set módszerek
- Aktív korlátokat határoznak meg és oldanak meg kisebb méretű egyenletrendszert.
- Kisebb problémákra gyors.
🧪 Interior-point módszerek
- Használható nagy dimenziójú QP-kre.
- Stabilabb és párhuzamosítható.
💡 QP-szolverek (használható eszközök):
quadprog
(MATLAB, R)
cvxpy
, osqp
, qpsolvers
(Python)
Gurobi
, CPLEX
, MOSEK
– ipari méretű optimalizálók
8. Python példa a cvxpy
könyvtárral
import cvxpy as cp
import numpy as np
# Adatok
Q = np.array(, ])
c = np.array()
A = np.array(])
b = np.array()
# Változók
x = cp.Variable(2)
# Célfüggvény
objective = cp.Minimize(0.5 * cp.quad_form(x, Q) + c @ x)
# Korlátok
constraints =
# Probléma definiálása és megoldása
prob = cp.Problem(objective, constraints)
prob.solve()
print("Optimális x:", x.value)
print("Minimum érték:", prob.value)
9. Konvex vs nem konvex QP
- Konvex QP: ha
pozitív szemidefinit ⇒ garantált globális minimum, gyors megoldás.
- Nemkonvex QP: ha
nem pozitív szemidefinit ⇒ több lokális minimum lehet, globális optimum keresése nehéz.
10. Összefoglalás
A kvadratikus programozás egy hatékony eszköz akkor, ha:
- A célfüggvény négyzetes, például szórás, energia, hibák négyzete
- A korlátok lineárisak
- A probléma konvex, vagy jól strukturált
Előnyei:
- Polinomiális idejű algoritmusok állnak rendelkezésre
- Széles körű gyakorlati alkalmazhatóság
- Egyszerűen használható könyvtárak segítik a bevezetést
Hátrányai:
- Nagy méretű nem konvex problémák esetén nehéz
- Bonyolult feltételek esetén modellezni nehezebb, mint LP-t