DUALIDAD GAP EN PROGRAMACIÓN CONVEXA

Abstract

Siempre que se está planteando un problema de optimización cabe preguntarse si existe otro problema asociado al anterior que permita, entre otras cosas, resolver el primero en forma más sencilla, aprovechando las propiedades que el segundo tiene como pudiera ser la concavidad de la función objetivo, la menor dimensión, y/o la simplicidad de las restricciones, etc. Son los problemas primal y dual. Si además, como problema primal consideramos un programa convexo, el problema dual que lo caracteriza es tal que resuelto éste se puede resolver aquél, así como analizar su sensibilidad. Estructuramos este trabajo de la forma siguiente: En la sección 1 se desarrollan los conceptos básicossobre dualidad, entre ellos el de dualidad gap, enunciándose el teorema de la dualidad débil. La sección 2 está dedicada a las condiciones bajo las que coinciden las soluciones del problema primal y dual, (dualidad gap cero). Estas condiciones se basan en las propiedades de convexidad del problema original y la cualificación de Slater, justificándose mediante el teorema de dualidad fuerte (condición suficiente pero no necesaria). En la sección 3 se da una condición más general que la cualificación de Slater, llamada propiedad D, que en cierto sentido es una caracterización de la ausencia de la dualidad gap