Programació quadràtica

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 Plantilla:Mvar variables i Plantilla:Mvar 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 Plantilla:Mvar -dimensional Plantilla:Math, que ho farà

minimitzar	$\frac{1}{2}{𝐱}^{\mathrm{T}}Q𝐱+{𝐜}^{\mathrm{T}}𝐱$
subjecte a	$A𝐱⪯𝐛,$

on Plantilla:Math denota la transposició vectorial de Plantilla:Math, i la notació Plantilla:Math significa que cada entrada del vector Plantilla:Math és menor o igual que l'entrada corresponent del vector Plantilla:Math (desigualtat per components).

Mínims quadrats restringits

Com a cas especial quan Plantilla:Math és simètrica positiva-definida, la funció de cost es redueix a mínims quadrats:

minimitzar	$\frac{1}{2}\Vert R𝐱-𝐝{\Vert }^2$
subjecte a	$A𝐱⪯𝐛,$

on Plantilla:Math es desprèn de la descomposició de Cholesky de Plantilla:Math i Plantilla:Math. 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 Plantilla:Math genèrica no quadrada.

Generalitzacions

Quan es minimitza una funció Plantilla:Mvar al voltant d'algun punt de referència Plantilla:Math, Plantilla:Mvar s'estableix a la seva matriu hessiana Plantilla:Math i Plantilla:Math s'estableix al seu gradient Plantilla:Math. 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è Plantilla:Mvar és definit positiu, el problema és un cas especial del camp més general de l'optimització convexa.