quadratic programming

Üdvözlöm, Ön a quadratic programming szó jelentését keresi. A DICTIOUS-ban nem csak a quadratic programming 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 quadratic programming szót egyes és többes számban mondani. Minden, amit a quadratic programming szóról tudni kell, itt található. A quadratic programming szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Aquadratic programming é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)

  1. (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.



2. A kvadratikus programozási probléma matematikai formája

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