5. Karush-Kuhn-Tucker feltételek [Cri00], [Boy04]

A Karush-Kuhn-Tucker (KKT) feltételek nemlineáris optimalizálási feladatok megoldását biztosító feltételek. A problémakör a Lagrange multiplikátoros módszer általánosításának tekinthető. Míg a Lagrange multiplikátoros módszer olyan feltételes szélsőérték-keresési feladatok megfoldásánál alkalmazható, ahol a feltételek egyenlőség formájában vannak megfogalmazva, a KKT optimalizálásnál az egyenlőség típusú feltételek helyett vagy azok mellett egyenlőtlenség típusú feltételek (is) szerepelnek.

Tekintsük a következő nemlineáris optimalizálási feladatot egy XNMathType@MTEF@5@5@+=feaagCart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaacbaGaa8hwaiabgAOinlabl2riHoaaCaaaleqabaGaamOtaaaaaaa@3B28@ konvex tartománnyal. Legyen f(x)xXMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadAgadaqadaqaaiaahIhaaiaawIcacaGLPaaacaaMf8UaaCiEaiabgIGiolaadIfaaaa@4179@ egy konvex[10] folytonosan differenciálható függvény és legyenek a gi(x)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadEgadaWgaaWcbaGaamyAaaqabaGcdaqadaqaaiaahIhaaiaawIcacaGLPaaaaaa@3DAE@i=1, …, M és a hj(x)=0MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIgadaWgaaWcbaGaamOAaaqabaGcdaqadaqaaiaahIhaaiaawIcacaGLPaaacqGH9aqpcaaIWaaaaa@3F70@j=1, …, L függvények affin[11] függvények.

Keressük

minxNf(x)-etxX úgy, hogy közben agi(x)0   és ahj(x)=0   feltételek is teljesüljenek.MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOabaeqabaWaaCbeaeaacaqGTbGaaeyAaiaab6gaaSqaaiaahIhacqGHiiIZtuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGqbaiab=1risnaaCaaameqabaGaamOtaaaaaSqabaGccaWGMbWaaeWaaeaacaWH4baacaGLOaGaayzkaaGaaeylaiaabwgacaqG0bGaaeilaiaabccacaWH4bGaeyicI4SaaeiwaiaabccacaqG6dGaae4zaiaabMhacaqGSaGaaeiiaiaabIgacaqGVbGaae4zaiaabMhacaqGGaGaae4AaiaabApacaqG6bGaaeOyaiaabwgacaqGUbGaaeiiaiaabggaaeaacaWGNbWaaSbaaSqaaiaadMgaaeqaaOWaaeWaaeaacaWH4baacaGLOaGaayzkaaGaeyyzImRaaGimaiaabccacaqGGaGaaeiiaiaabMoacaqGZbGaaeiiaiaabggaaeaacaWGObWaaSbaaSqaaiaadQgaaeqaaOWaaeWaaeaacaWH4baacaGLOaGaayzkaaGaeyypa0JaaGimaiaabccacaqGGaGaaeiiaiaabAgacaqGLbGaaeiBaiaabshacaqGPdGaaeiDaiaabwgacaqGSbGaaeyzaiaabUgacaqGGaGaaeyAaiaabohacaqGGaGaaeiDaiaabwgacaqGSbGaaeOAaiaabwgacaqGZbGaaei=aiaabYgacaqGQbGaaeyzaiaab6gacaqGLbGaae4Aaiaab6caaaaa@9606@ (F.45)

Definiáljunk egy általánosított Lagrange függvényt a következő formában:

L(x,α,β)=f(x)i=1Mαigi(x)j=1Lβjhj(x)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadYeadaqadaqaaiaahIhacaGGSaGaaCySdiaacYcacaWHYoaacaGLOaGaayzkaaGaeyypa0JaamOzamaabmaabaGaaCiEaaGaayjkaiaawMcaaiabgkHiTmaaqahabaGaeqySde2aaSbaaSqaaiaadMgaaeqaaaqaaiaadMgacqGH9aqpcaaIXaaabaGaamytaaqdcqGHris5aOGaam4zamaaBaaaleaacaWGPbaabeaakmaabmaabaGaaCiEaaGaayjkaiaawMcaaiabgkHiTmaaqahabaGaeqOSdi2aaSbaaSqaaiaadQgaaeqaaaqaaiaadQgacqGH9aqpcaaIXaaabaGaamitaaqdcqGHris5aOGaamiAamaaBaaaleaacaWGQbaabeaakmaabmaabaGaaCiEaaGaayjkaiaawMcaaaaa@60CE@ (F. 46)

ahol αi0MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeg7aHnaaBaaaleaacaWGPbaabeaakiabgwMiZkaaicdaaaa@3E57@ és βjMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabek7aInaaBaaaleaacaWGQbaabeaakiabgIGioprr1ngBPrwtHrhAYaqeguuDJXwAKbstHrhAGq1DVbacfaGae8xhHifaaa@4816@ Lagrange multiplikátorok.

Annak szükséges és elégséges feltétele, hogy egy xXMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahIhadaahaaWcbeqaaiabgEHiQaaakiabgIGiolaabIfaaaa@3D9A@ a fenti feladat optimuma legyen az, hogy létezzenek olyan (α,β) MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaabmaabaGaaCySdmaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahk7adaahaaWcbeqaaiabgEHiQaaaaOGaayjkaiaawMcaaiaabccaaaa@40B7@ , α[0,)MMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahg7adaahaaWcbeqaaiabgEHiQaaakiabgIGiopaajibabaGaaGimaiaacYcacqGHEisPaiaawUfacaGLPaaadaahaaWcbeqaaiaad2eaaaaaaa@42A8@ , βLMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahk7adaahaaWcbeqaaiabgEHiQaaakiabgIGioprr1ngBPrwtHrhAYaqeguuDJXwAKbstHrhAGq1DVbacfaGae8xhHi1aaWbaaSqabeaacaWGmbaaaaaa@48B2@ változók, hogy

xL(x,α,β)=L(x,α,β)x=0βL(x,α,β) =L(x,α,β)β=0αigi(x)=0,    i=1,,M gi(x)0,   i=1,,M αi0,   i=1,,M MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOabaeqabaacceGae83bIe9aaSbaaSqaaiaahIhaaeqaaOGaamitamaabmaabaGaaCiEamaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahg7adaahaaWcbeqaaiabgEHiQaaakiaacYcacaWHYoWaaWbaaSqabeaacqGHxiIkaaaakiaawIcacaGLPaaacqGH9aqpdaWcaaqaaiabgkGi2kaadYeadaqadaqaaiaahIhadaahaaWcbeqaaiabgEHiQaaakiaacYcacaWHXoWaaWbaaSqabeaacqGHxiIkaaGccaGGSaGaaCOSdmaaCaaaleqabaGaey4fIOcaaaGccaGLOaGaayzkaaaabaGaeyOaIyRaaGjcVlaayIW7caWH4baaaiabg2da9iaahcdaaeaacqWFhis0daWgaaWcbaGaaCOSdaqabaGccaWGmbWaaeWaaeaacaWH4bWaaWbaaSqabeaacqGHxiIkaaGccaGGSaGaaCySdmaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahk7adaahaaWcbeqaaiabgEHiQaaaaOGaayjkaiaawMcaaiaabccacqGH9aqpdaWcaaqaaiabgkGi2kaadYeadaqadaqaaiaahIhadaahaaWcbeqaaiabgEHiQaaakiaacYcacaWHXoWaaWbaaSqabeaacqGHxiIkaaGccaGGSaGaaCOSdmaaCaaaleqabaGaey4fIOcaaaGccaGLOaGaayzkaaaabaGaeyOaIyRaaGjcVlaayIW7caWHYoaaaiabg2da9iaahcdaaeaacaaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaeqySde2aa0baaSqaamaaBaaameaacaWGPbaabeaaaSqaaiabgEHiQaaakiaadEgadaWgaaWcbaGaamyAaaqabaGcdaqadaqaaiaahIhadaahaaWcbeqaaiabgEHiQaaaaOGaayjkaiaawMcaaiabg2da9iaaicdacaGGSaGaaeiiaiaabccacaqGGaGaaeiiaiaadMgacqGH9aqpcaqGXaGaaeilaiablAciljaabYcacaWGnbGaaeiiaaqaaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caWGNbWaaSbaaSqaaiaadMgaaeqaaOWaaeWaaeaacaWH4bWaaWbaaSqabeaacqGHxiIkaaaakiaawIcacaGLPaaacqGHLjYScaaIWaGaaiilaiaabccacaqGGaGaaeiiaiaadMgacqGH9aqpcaqGXaGaaeilaiablAciljaabYcacaWGnbGaaeiiaaqaaiaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7caaMi8UaaGjcVlaayIW7cqaHXoqydaqhaaWcbaWaaSbaaWqaaiaadMgaaeqaaaWcbaGaey4fIOcaaOGaeyyzImRaaGimaiaacYcacaqGGaGaaeiiaiaabccacaWGPbGaeyypa0JaaeymaiaabYcacqWIMaYscaqGSaGaamytaiaabccaaaaa@74E0@ , (F.47)

(x,α,β) MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaabmaabaGaaCiEamaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahg7adaahaaWcbeqaaiabgEHiQaaakiaacYcacaWHYoWaaWbaaSqabeaacqGHxiIkaaaakiaawIcacaGLPaaacaqGGaaaaa@438E@ -ra igaz, hogy bármely  xNMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaabccacaWH4bGaeyicI48efv3ySLgznfgDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFDeIudaahaaWcbeqaaiaad6eaaaaaaa@47F4@ és α[0,)MMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahg7acqGHiiIZdaqcsaqaaiaaicdacaGGSaGaeyOhIukacaGLBbGaayzkaaWaaWbaaSqabeaacaWGnbaaaaaa@4182@ és βLMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahk7acqGHiiIZtuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGqbaiab=1risnaaCaaaleqabaGaamitaaaaaaa@478C@ mellett

 L(x,α,β) L(x,α,β) L(x,α,β)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaabccacaWGmbWaaeWaaeaacaWH4bWaaWbaaSqabeaacqGHxiIkaaGccaGGSaGaaCySdiaacYcacaWHYoaacaGLOaGaayzkaaGaeyizImQaaeiiaiaadYeadaqadaqaaiaahIhadaahaaWcbeqaaiabgEHiQaaakiaacYcacaWHXoWaaWbaaSqabeaacqGHxiIkaaGccaGGSaGaaCOSdmaaCaaaleqabaGaey4fIOcaaaGccaGLOaGaayzkaaGaaeiiaiabgsMiJkaadYeadaqadaqaaiaahIhacaGGSaGaaCySdmaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahk7adaahaaWcbeqaaiabgEHiQaaaaOGaayjkaiaawMcaaaaa@5AED@ (F.48)

vagyis xMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahIhadaahaaWcbeqaaiabgEHiQaaaaaa@3B31@ egy nyeregpont (saddle point).

Elsődleges és másodlagos feladat

Az SVM-nél felmerülő elsődleges (primal) optimalizálási feladat minimumkeresési feladat egyenlőtlenség típusú mellékfeltételekkel.

Keressük

minxRNf(x)-etxX úgy, hogy közben agi(x)0   feltételek is teljesüljenek.MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOabaeqabaWaaCbeaeaacaqGTbGaaeyAaiaab6gaaSqaaiaahIhacqGHiiIZtCvAUfKttLearyqsTbNCP5gDG0evGmfAHr2B3bacfaGae8Nuai1aaWbaaWqabeaacaWGobaaaaWcbeaakiaadAgadaqadaqaaiaahIhaaiaawIcacaGLPaaacaqGTaGaaeyzaiaabshacaqGSaGaaeiiaiaahIhacqGHiiIZcaqGybGaaeiiaiaabQpacaqGNbGaaeyEaiaabYcacaqGGaGaaeiAaiaab+gacaqGNbGaaeyEaiaabccacaqGRbGaaeO9aiaabQhacaqGIbGaaeyzaiaab6gacaqGGaGaaeyyaaqaaiaadEgadaWgaaWcbaGaamyAaaqabaGcdaqadaqaaiaahIhaaiaawIcacaGLPaaacqGHLjYScaaIWaGaaeiiaiaabccacaqGGaGaaeOzaiaabwgacaqGSbGaaeiDaiaabMoacaqG0bGaaeyzaiaabYgacaqGLbGaae4AaiaabccacaqGPbGaae4CaiaabccacaqG0bGaaeyzaiaabYgacaqGQbGaaeyzaiaabohacaqG8dGaaeiBaiaabQgacaqGLbGaaeOBaiaabwgacaqGRbGaaeOlaaaaaa@8902@ (F.49)

A megfelelő általánosított Lagrange függvény

L(x,α)=f(x)i=1Mαigi(x)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadYeadaqadaqaaiaahIhacaGGSaGaaCySdaGaayjkaiaawMcaaiabg2da9iaadAgadaqadaqaaiaahIhaaiaawIcacaGLPaaacqGHsisldaaeWbqaaiabeg7aHnaaBaaaleaacaWGPbaabeaaaeaacaWGPbGaeyypa0JaaGymaaqaaiaad2eaa0GaeyyeIuoakiaadEgadaWgaaWcbaGaamyAaaqabaGcdaqadaqaaiaahIhaaiaawIcacaGLPaaaaaa@50D9@ (F.50)

Feltételezve, hogy (x,α)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaabmaabaGaaCiEamaaCaaaleqabaGaey4fIOcaaOGaaiilaiaahg7adaahaaWcbeqaaiabgEHiQaaaaOGaayjkaiaawMcaaaaa@3FD7@ egyértelmű minimum, minden rögzített α0MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahg7acqGHLjYScaWHWaaaaa@3CD0@ mellett definiálható egy Lagrange függvény,

Q(α):=minxL(x,α)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadgfadaqadaqaaiaahg7aaiaawIcacaGLPaaadaWfqaqaaiaabQdacqGH9aqpcaqGTbGaaeyAaiaab6gaaSqaaiaahIhaaeqaaOGaamitamaabmaabaGaaCiEaiaacYcacaWHXoaacaGLOaGaayzkaaaaaa@47CC@ (F.51)

mely egyedül αMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahg7aaaa@3A51@ függvénye.

Ennek megfelelően megfogalmazható a duális (dual) optimalizálási feladat:

maximalizáljuk   Q(α)-túgy hogy  αi0     i=1,2,,M,MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOabaeqabaGaaeyBaiaabggacaqG4bGaaeyAaiaab2gacaqGHbGaaeiBaiaabMgacaqG6bGaaey4aiaabYgacaqGQbGaaeyDaiaabUgacaqGGaGaaeiiaiaabccacaWGrbWaaeWaaeaacaWHXoaacaGLOaGaayzkaaGaaeylaiaabshaaeaacaqG6dGaae4zaiaabMhacaqGGaGaaeiAaiaab+gacaqGNbGaaeyEaiaabccacaqGGaGaeqySde2aaSbaaSqaaiaadMgaaeqaaOGaeyyzImRaaGimaiaabccacaqGGaGaaeiiaiaabccacaqGGaGaamyAaiabg2da9iaabgdacaqGSaGaaeOmaiaabYcacqWIMaYscaqGSaGaamytaiaacYcaaaaa@6763@ (F.52)

ahol Q(α)-tMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadgfadaqadaqaaiaahg7aaiaawIcacaGLPaaacaqGTaGaaeiDaaaa@3E57@ duális kritériumfüggvénynek nevezzük. A duális feladat megoldása nem feltétlenül egyszerűbb, mint az eredeti feladat megoldása. A duális feladat előnye, hogy a duális kritériumfüggvény csak αMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahg7aaaa@3A51@ függvénye.

Az SVM esetén a duális feladat az αiMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeg7aHnaaBaaaleaacaWGPbaabeaaaaa@3BCD@ Lagrange multiplikátorok kvadratikus függvénye.

Q(α)=αT112αTKαMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadgfadaqadaqaaiaahg7aaiaawIcacaGLPaaacqGH9aqpcaWHXoWaaWbaaSqabeaacaWGubaaaOGaaCymaiabgkHiTmaalaaabaGaaGymaaqaaiaaikdaaaGaaCySdmaaCaaaleqabaGaamivaaaakiaahUeacaWHXoaaaa@478F@ (F.53)

az αiMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeg7aHnaaBaaaleaacaWGPbaabeaaaaa@3BCD@ Lagrange multiplikátorokra vonatkozó feltételekkel: αi0MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeg7aHnaaBaaaleaacaWGPbaabeaakiabgwMiZkaaicdaaaa@3E57@ és i=1Pαidi=0MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaaqadabaGaeqySde2aaSbaaSqaaiaadMgaaeqaaOGaamizamaaBaaaleaacaWGPbaabeaaaeaacaWGPbGaeyypa0JaaGymaaqaaiaadcfaa0GaeyyeIuoakiabg2da9iaaicdaaaa@451F@ , ahol di i=1,2,…,P az SVM feladatnál megfogalmazott kívánt válaszokat jelöli. Az SVM duális feladatát kvadratikus programozással oldhatjuk meg.



[10] Egy valós értékű f(x)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadAgadaqadaqaaiaahIhaaiaawIcacaGLPaaaaaa@3C89@xNMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaahIhacqGHiiIZtuuDJXwAK1uy0HMmaeHbfv3ySLgzG0uy0HgiuD3BaGqbaiab=1risnaaCaaaleqabaGaamOtaaaaaaa@4751@ függvény konvex, ha   x,uNMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaabccacqGHaiIicaqGGaGaaCiEaiaacYcacaWH1bGaeyicI48efv3ySLgznfgDOjdaryqr1ngBPrginfgDObcv39gaiuaacqWFDeIudaahaaWcbeqaaiaad6eaaaaaaa@4B15@ és bármely λ(0,1)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeU7aSjabgIGiopaabmaabaGaaGimaiaacYcacaaIXaaacaGLOaGaayzkaaaaaa@3FFA@ mellett f(λx+(1λ)u)λf(x)+(1λ)f(u)MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadAgadaqadaqaaiabeU7aSjaahIhacqGHRaWkdaqadaqaaiaaigdacqGHsislcqaH7oaBaiaawIcacaGLPaaacaWH1baacaGLOaGaayzkaaGaeyizImQaeq4UdWMaamOzamaabmaabaGaaCiEaaGaayjkaiaawMcaaiabgUcaRmaabmaabaGaaGymaiabgkHiTiabeU7aSbGaayjkaiaawMcaaiaadAgadaqadaqaaiaahwhaaiaawIcacaGLPaaaaaa@5519@ . Egy kétszer differenciálható függvény konvex, ha a második deriváltakból képezett Hesse mátrix pozitív definit.

[11] Egy affin függvény felírható az alábbi formában: f(x)=Ax+bMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadAgadaqadaqaaiaahIhaaiaawIcacaGLPaaacqGH9aqpcaWHbbGaaCiEaiabgUcaRiaahkgaaaa@4127@ , ahol A valamilyen mátrix és b egy vektor. Egy affin függvény egyben konvex is.