Programación semidefinida

---

La programación semidefinida ( SDP ) es un subcampo de la optimización convexa relacionado con la optimización de una función objetivo lineal (una función especificada por el usuario que el usuario desea minimizar o maximizar) sobre la intersección del cono de matrices semidefinidas positivas con un espacio afín . es decir, un espectroedro .

La programación semidefinida es un campo de optimización relativamente nuevo que tiene un interés creciente por varias razones. Muchos problemas prácticos en investigación de operaciones y optimización combinatoria pueden modelarse o aproximarse como problemas de programación semidefinida. En la teoría del control automático, los SDP se utilizan en el contexto de desigualdades de matrices lineales . Los SDP son, de hecho, un caso especial de programación de conos y pueden resolverse eficientemente mediante métodos de puntos interiores . Todos los programas lineales y programas cuadráticos (convexos)se puede expresar como SDP y, a través de jerarquías de SDP, se pueden aproximar las soluciones de los problemas de optimización polinomial. La programación semidefinida se ha utilizado en la optimización de sistemas complejos. En los últimos años, algunos problemas de complejidad de consultas cuánticas se han formulado en términos de programas semidefinidos.

Un problema de programación lineal es aquel en el que deseamos maximizar o minimizar una función objetivo lineal de variables reales sobre un politopo . En la programación semidefinida, en su lugar, usamos vectores con valores reales y se nos permite tomar el producto punto de los vectores; las restricciones de no negatividad en variables reales en LP ( programación lineal ) se reemplazan por restricciones de semidefinición en variables de matriz en SDP ( programación semidefinida ). Específicamente, un problema general de programación semidefinida se puede definir como cualquier problema de programación matemática de la forma

donde , y the son números reales y es el producto punto de y .${\displaystyle c_{i,j},a_{i,j,k}}$${\displaystyle b_{k}}$${\displaystyle x^{i}\cdot x^{j}}$${\ estilo de visualización x^{i}}$${\ estilo de visualización x^{j}}$

Se dice que una matriz es semidefinida positiva si es la matriz de Gram de algunos vectores (es decir, si existen vectores tales que para todos ). Si este es el caso, lo denotamos como . Tenga en cuenta que hay varias otras definiciones equivalentes de ser semidefinidas positivas, por ejemplo, las matrices semidefinidas positivas son matrices autoadjuntas que solo tienen valores propios no negativos .${\ estilo de visualización n \ veces n}$${\ estilo de visualización M}$${\displaystyle x^{1},\ldots,x^{n}}$${\displaystyle m_{i,j}=x^{i}\cdot x^{j}}$${\ estilo de visualización i, j}$${\displaystyle M\succeq 0}$

---