Programació quadràtica

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.

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.

"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 n variables i m 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 n -dimensional x, que ho farà

minimitzar	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
subjecte a	$A\mathbf {x} \preceq \mathbf {b} ,$

on x^T denota la transposició vectorial de x, i la notació Ax ⪯ b significa que cada entrada del vector Ax és menor o igual que l'entrada corresponent del vector b (desigualtat per components).

Mínims quadrats restringits

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

minimitzar	${\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}$
subjecte a	$A\mathbf {x} \preceq \mathbf {b} ,$

on Q = R^TR es desprèn de la descomposició de Cholesky de Q i c = −R^T d. 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 R genèrica no quadrada.

Generalitzacions

Quan es minimitza una funció f al voltant d'algun punt de referència x₀, Q s'estableix a la seva matriu hessiana H(f(x₀)) i c s'estableix al seu gradient ∇f(x₀). 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è Q és definit positiu, el problema és un cas especial del camp més general de l'optimització convexa.