miniatura|315x315px|Esquema de programació quadràtica seqüencial Esquema que explica la idea bàsica de l'algorisme SQP creat per a l'article de wikipedia SQP amb TikZ. La programació quadràtica (QP) és el procés de resolució de determinats problemes d'optimització matemàtica que impliquen funcions quadràtiques. Concretament, es busca optimitzar (minimitzar o maximitzar) una funció quadràtica multivariant subjecta a restriccions lineals sobre les variables. La programació quadràtica és un tipus de programació no lineal.
"Programació" en aquest context es refereix a un procediment formal per resoldre problemes matemàtics. Aquest ús data de la dècada de 1940 i no està específicament lligat a la noció més recent de "programació d'ordinadors". Per evitar confusions, alguns professionals prefereixen el terme "optimització", per exemple, "optimització quadrada".
Formulació del problema El problema de programació quadràtica amb variables i restriccions es pot formular de la següent manera. Donat:
un vector n -dimensional de valor real c, una matriu simètrica real n×n-dimensional Q, una matriu real m×n -dimensional A, i un vector real m -dimensional b,
l'objectiu de la programació quadràtica és trobar un vector -dimensional , que ho farà minimitzarsubjecte a on denota la transposició vectorial de , i la notació significa que cada entrada del vector és menor o igual que l'entrada corresponent del vector (desigualtat per components).
Mínims quadrats restringits Com a cas especial quan és simètrica positiva-definida, la funció de cost es redueix a mínims quadrats: minimitzarsubjecte a on es desprèn de la descomposició de Cholesky de i . Per contra, qualsevol programa de mínims quadrats restringit es pot emmarcar de manera equivalent com un problema de programació quadràtica, fins i tot per a una matriu genèrica no quadrada.
Generalitzacions Quan es minimitza una funció al voltant d'algun punt de referència , s'estableix a la seva matriu hessiana i s'estableix al seu gradient . Un problema de programació relacionat, la programació quadràtica restringida, es pot plantejar afegint restriccions quadràtiques a les variables.
Mètodes de solució Per a problemes generals s'utilitzen habitualment una varietat de mètodes, com ara
punt interior, conjunt actiu, Lagrangià augmentat, gradient conjugat, projecció de gradient, extensions de l'algorisme simplex.
En el cas en què és definit positiu, el problema és un cas especial del camp més general de l'optimització convexa.
Referències
Categoria:Algorismes