¿Por qué la función dual de Lagrange es cóncava?

Question

En un libro que estoy leyendo ( Optimización convexa de Boyd y Vandenberghe) dice

Me cuesta entender la última frase. ¿Por qué se puede concluir la concavidad a partir de un mínimo puntual de una familia de funciones afines?

Answer 1

Porque el lagrangiano $L(x,\lambda,\mu)$ es afín en $\lambda$ y $\mu$ la función dual de Lagrange $d(\lambda,\nu) = \inf_{x\in \mathcal{D}}L(x,\lambda,\nu)$ es siempre cóncava porque es el mínimo puntual de un conjunto de funciones afines, que siempre es cóncava. (También se puede demostrar que el el sumo de un conjunto de funciones convexas es convexo .)

Answer 2

El libro al que se hace referencia es Optimización convexa por Boyd y Vandenberghe. Para ver mejor el "mínimo puntual", consideremos un ligero cambio/abuso de la notación: $L_x(\xi) = L(x, \lambda, \nu)$ donde $\xi = (\lambda, \nu)$ . Para un $x$ , $L_x(\xi)$ es afín en $\xi$ así que $\{L_x(\xi) \,:\, x \in \mathcal{D}\}$ es una familia de funciones afines y su mínimo puntual es $$g(\xi) = \inf_x \,\{L_x(\xi)\,:\,x\in\mathcal{D}\}$$ Ahora podemos utilizar el puntero de @A.. para demostrar que $g$ es cóncavo mostrando el epígrafe de $-g$ es convexo. Para un determinado $\xi$ tenemos $g(\xi) \le L_x(\xi)$ para cualquier $L_x$ de la familia para que $(\xi, -g(\xi))$ siempre está "por encima" de $(\xi, -L_x(\xi)$ ) por lo tanto $\rm{epi}(-g) \subset \bigcap_x \rm{epi}(-L_x)$ .

Answer 3

La concavidad de la función dual es una propiedad muy poco intuitiva.

Una forma de demostrarlo es utilizar el hecho de que una función es convexa si y sólo si su epígrafe es un conjunto convexo. El epígrafe de una función $f(\vec x)$ es el conjunto de puntos "por encima" de esa función: $$\left\{(\vec x,y) \mid y \geq f(\vec x)\right\}$$

Para la función dual tenemos el mínimo puntual de una familia de funciones afines: $$D(\vec \lambda, \vec \nu) = \inf_{\vec x} \mathcal{L}(\vec x,\vec \lambda, \vec \nu) = \inf_{\vec x} A(\vec x) \begin{bmatrix} \vec \lambda \\ \vec \nu \end{bmatrix} + \vec b(\vec x)$$

Es decir, podemos reescribir el Lagrangiano para que tenga la forma $A\vec \lambda + \vec b$ para alguna matriz $A$ y el vector $\vec b$ que ambos dependen de $\vec x$ .

En términos generales, "puntualmente" significa que podemos elegir diferentes valores para $\vec x$ dependiendo del valor de $\vec \lambda$ .

El epígrafe de $\mathcal{L}$ es para cualquier valor de $\vec x$ va a ser un conjunto convexo, ya que una vez $\vec x$ es fija la función es afín, y las funciones afines son tanto convexas como cóncavas. Si le damos la vuelta a esta noción, podemos observar las epígrafes negativas, o el conjunto de puntos "por debajo" de la función. Este epígrafe negativo de $D$ va a ser la intersección de los eopígrafos negativos de todas las funciones posibles que se forman fijando todos los valores posibles de $\vec x$ . La intersección de conjuntos convexos es un conjunto convexo, por lo que este epígrafe negativo es un conjunto convexo. El epígrafe negativo de una función es un conjunto convexo si y sólo si la función es cóncava, por lo que la función dual $D$ ¡debe ser cóncavo!

Ayuda un poco dibujar esto en una hoja de papel.

Answer 4

Creo que es más fácil visualizar el caso de maximización, en el que el sup es convexo. Digamos que cambias un multiplicador en la dirección que relaja su restricción, entonces el lagrangiano, al ser afín en el multiplicador, es al menos linealmente mejor respecto al cambio y probablemente hay espacio para mejorar por encima de la linealidad debido a la relajación, de ahí que obtengas convexidad. De hecho, la restricción evaluada en el óptimo actual es un subgradiente del lagrangiano. En términos del epígrafe, después de cambiar el multiplicador te quedarás al menos en el mismo miembro afín de la familia, pero también puedes escalar al siguiente.