Programación Semidefinida

Programación Semidefinida (SDP) es una subrama de la optimización convexa cuyo interés principal yace en la optimización de una función objetiva lineal (una función especificada por el usuario, que dicho usuario busca minimizar o maximizar) sobre la intersección del cono de matrices positivo semidefinidas con un espacio afín, i.e., un espectrahedro.La programación semidefinida es una rama relativamente nueva de optimización que está recibiendo creciente atención por varias razones.Muchos problemas prácticos en investigación de operaciones y optimización combinatoria pueden ser modelados o aproximados por programas semidefinidos.La programación semidefinida ha sido utilizada en la optimización de sistemas complejos.En cambio, en programación semidefinida utilizamos vectores con entradas reales y podemos tomar el producto punto de vectores; las restricciones de no-negatividad en variables reales en LP (programación lineal) son reemplazadas por restricciones de semidefinición en las variables matriciales en PSD (programación semidefinida).Podemos reescribir el programa matemático dado en la sección anterior equivalentemente de la siguiente manera Dónde la entradason simétricas, y los productos interiores de arriba están bien definidos.Notemos que si añadimos variables de holgura apropiadamente, este PSD puede ser convertido a uno de la forma Por conveniencia, un PSD puede ser especificado ligeramente diferente, pero forma equivalente.Por ejemplo, las expresiones lineales que tienen variables escalares no negativas pueden ser añadidas a la especificación del programa.Análogamente a programación lineal, dado un PSD general de la forma (el problema primal o P-PSD), definimos el programa semidefinido (D-PSD) dual comoEsto es porque donde la última desigualdad es porque ambas matrices son positivas semidefinidas, y el resultado de esta función es a veces referido como brecha de dualidad.Diferente que para programas lineales, sin embargo, no cualquier PSD satisface dualidad fuerte; en general, el valor del PSD dual puede ser estrictamente menor al valor del programa primal.(i) Supongamos que el problema primal (P-SDP) está acotado abajo y es estrictamente viable (i.e., existeResolver este PSD nos da los valores mínimos y máximos de, el problema puede ser reformulado como lo siguiente: En esta formulación, el objetivo es una función lineal en las variableses la matriz cuadrada con valores en el diagonales iguales a los elementos del vectorEl primer algoritmo de aproximación basado en un PSD se debe a Michel Goemans y David P. Williamson (JACM, 1995).Este problema puede ser expresado como un programa entero cuadrático: A no ser que P = NP, no podemos solucionar este problema de maximización eficientemente.Finalmente, un procedimiento de redondeo se necesita para obtener una partición.Goemans y Williamson sencillamente escogen un hiperplano de manera uniformemente aleatoria que pase a través del origen y dividen los vértices según el lado del hiperplano en el que sus vectores correspondientes yacen.[1]​ Hay varios tipos de algoritmos para solucionar PSDs.Estos algoritmos producen el valor del PSD hasta un error aditivo deen un tiempo que es polinomial con respecto al tamaño de la descripción del programa yEstos pueden ser usados para detectar falta de viabilidad estricta, para eliminar columnas y filas redundantes, y también para reducir la medida de la matriz variable.Estos métodos son robustos y eficaces para problemas PSD lineales generales.Métodos de primer orden para la optimización cónica evitan la computación, almacenando y factorizando una matriz Hessiana grande y escalan a problemas mucho más grandes que métodos de punto interior, bajo algún coste en exactitud.[4]​ Este método requiere en cada paso la proyección hacia el cono de matrices semidefinidas.Esta heurística es muy eficiente para una clase especial de problemas PSD lineares.Los algoritmos basados en el Método Lagrangiano Aumentado (PENSDP) son similares en comportamiento a los métodos de punto interior y pueden ser especializados a algunos problemas de gran escala.[5]​ Se han propuesto también algoritmos que solucionan PSDs aproximadamente.