# 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.
"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$^T$R 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$_0$, Q s'estableix a la seva matriu hessiana H(f(x$_0$)) i c s'estableix al seu gradient ∇f(x$_0$). 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.

## Referències

* ↑ «Quadratic programming - Cornell University Computational Optimization Open Textbook - Optimization Wiki» (en anglès). [Consulta: 11 maig 2024].
* ↑ «Quadratic Optimization Problems» (en anglès). [Consulta: 11 maig 2024].
* ↑ «CHAPTER 2: QUADRATIC PROGRAMMING» (en anglès). [Consulta: 11 maig 2024].
* ↑ «[https://ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004/8a2f7cda0c6c448c17e8a8272697f55c_lec4_quad_form.pdf Quadratic Functions, Optimization, and Quadratic Forms]» (en anglès). [Consulta: 12 maig 2024].