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.^[1]

"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".^[2]

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	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
subjecte a	${\displaystyle 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).^[3]

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	${\displaystyle {\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}}$
subjecte a	${\displaystyle 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.^[4]

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

1. «Quadratic programming - Cornell University Computational Optimization Open Textbook - Optimization Wiki» (en anglès). [Consulta: 11 maig 2024].
2. «Quadratic Optimization Problems» (en anglès). [Consulta: 11 maig 2024].
3. «CHAPTER 2: QUADRATIC PROGRAMMING» (en anglès). [Consulta: 11 maig 2024].
4. «[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].