Estoy leyendo Convexa de la Optimización de la Prof. Boyd y tengo algunas dudas sobre el importante uso apropiado de cono convexo de optimización. Otro de generalizar las desigualdades, hay algún otro uso correcto de cono convexo de optimización?
Respuesta
¿Demasiados anuncios?
Una forma estándar de programación lineal (LP) es un problema de optimización de la forma \begin{align} \text{minimize} & \quad c^T x \\ \text{subject to} & \quad Ax = b , \\ & \quad x \geq 0. \end{align}
Si expresamos la restricción $x \geq 0$$x \in \Omega$, donde $\Omega$ es no negativo orthant (que es un cerrado convexo de cono), entonces podemos ver una manera de generalizar el modelo estándar de LP a una clase más amplia de problemas. Un "cono" es un problema de optimización de la forma \begin{align} \text{minimize} & \quad \langle c, x \rangle \\ \text{subject to} & \quad Ax = b , \\ & \quad x \in C, \end{align} donde $C$ es un cerrado convexo de cono. (Ahora $C$ no tiene que ser el no negativo orthant.)
Hay dos especialmente interesantes los casos:
1) $C$ es un de segundo orden de cono, o, más generalmente, $C = C_1 \times \cdots \times C_m$ donde cada una de las $C_i$ es un de segundo orden de cono. En este caso, nuestro programa de cono se llama un "segundo orden de cono de programa" (SOCP).
2) $C$ es positivo semidefinite cono, o, más generalmente, $C = C_1 \times \cdots \times C_m$ donde cada $C_i$ es positivo semidefinite cono. En este caso, nuestro cono programa que se llama un "semidefinite programa" (SDP).
¿Por qué estos dos casos especialmente interesante? Por dos razones:
1) Muchos de los problemas prácticos que puede ser expresado como SOCPs o como Pes. (Véase el Boyd y Vandenberghe libro de texto durante muchos ejemplos, así como trucos para expresar los problemas de optimización convexa como SOCPs o Pes.)
2) Eficiente de algoritmos de punto interior métodos) para resolver problemas de programación lineal se puede generalizar, rendimiento de algoritmos eficientes para la resolución de SOCPs y Pes.
Y ¿qué es tan especial acerca de la segunda orden de cono y la positiva semidefinite cono que hace que sea posible para resolverlos de manera eficiente con métodos de punto interior? Tiene que ver con el hecho de que estos conos, como el no negativo orthant, se "auto-dual" y "simétrico". Pero esperemos que alguien puede dar más detalles acerca de este punto. Una buena referencia para este tipo de material es la conferencia "Simétrica conos" en Vandenberghe del c 236 notas: http://www.seas.ucla.edu/~vandenbe/ee236c.html
Otro punto de vista es que si queremos desarrollar convexa de la teoría de la optimización en la configuración de un verdadero producto interior espacio, debemos averiguar cuál es la declaración de $x \leq y$ debe decir. Y esto nos lleva a descubrir el concepto de un cono convexo.
