¿Por qué $\nabla f(x^*)+A^T\nu^*=0$ ¿llamadas "ecuaciones duales de viabilidad"?

Question

Para el siguiente problema de minimización convexa:

\begin{equation} \begin{array}{rl} \textrm{minimize} & f(x)\\ \textrm{subject to} & Ax=b, \end{array} \end{equation}

donde $f$ es diferenciable, las condiciones de optimalidad son: $$Ax^*=b, \qquad \nabla f(x^*)+A^T\nu^*=0.$$

En "Optimización convexa" de Boyd y Vandenberghe (p521), $Ax^*=b$ se llaman ecuaciones primarias de viabilidad y $\nabla f(x^*)+A^T\nu^*=0$ se llaman ecuaciones duales de viabilidad . La denominación del primero tiene mucho sentido para mí, ya que $Ax=b$ es un conjunto de ecuaciones que definen el conjunto factible del problema primario (dentro del dominio).

Sin embargo, no estoy tan seguro de por qué $\nabla f(x^*)+A^T\nu^*=0$ se denominan "ecuaciones duales de viabilidad"? ¿No es el problema dual un sin restricciones maximización cóncava:

$$\sup_{\nu} \left[\inf_{x\in \mathcal D} f(x)+\nu^T(Ax-b)\right]?$$

¿Es porque vemos la posibilidad de alcanzar el infimo dentro de los corchetes para un determinado $\nu$ como condición de viabilidad para el problema dual? (Esto sólo define el dominio del problema dual, ¿no?)

Answer 1

Basándome en nuestras discusiones, diría lo siguiente. Usando una convención de real extendido, el dominio $\mathcal{D}$ es absorbido por $f$ y el dual de Lagrange es \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x L(x,\nu) = \inf_x f(x) + \nu^T ( Ax - b ) \\ \end{array} No hay una restricción dual explícita para este problema, porque el multiplicador de Lagrange para una restricción de igualdad no tiene restricciones. En cambio, para una desigualdad restricción $Ax\leq b$ el problema dual tendría una restricción explícita $\nu \geq 0$ .

Sin embargo, sabemos que en la práctica suele haber valores de $\nu$ tal que $\inf_x L(x,\nu) = -\infty$ . Estos sirven como implícito restricción de $\nu$ reflejado en el dominio de $g$ . Es una práctica común identificar esas restricciones implícitas y hacerlas explícitas. (De hecho, esto es necesario si no se desea adoptar una convención de real extendido). Así que el dual se convierte en \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x f(x) + \nu^T ( Ax - b ) \\ \text{subject to} & -\infty < \inf_x f(x) + \nu^TAx \end{array} Esto es cierto incluso si $f$ no es diferenciable. Si $f$ es diferenciable en todo $\mathbb{R}^n$ entonces esto es equivalente a \begin{array}{ll} \text{maximize} & g(\nu) \triangleq \inf_x f(x) + \nu^T ( Ax - b ) \\ \text{subject to} & \exists x ~ \nabla f(x) + A^T \nu = 0 \end{array} [EDIT: como señala el OP, hay casos en los que no es realmente equivalente; más bien, es un suficiente condición]. Esto también será válido si $f(x)$ es diferenciable en un sentido extendido-real. Es decir, si:

• $\mathop{\textrm{dom}} f$ está abierto;
• $f$ es diferenciable en su dominio;
• $f$ sirve como barrera para su dominio; es decir, $f(x)\rightarrow +\infty$ como $x\rightarrow\mathop{\textrm{Bd}} \mathop{\textrm{dom}} f$ .

Nótese que esto excluye específicamente los casos en los que el dominio de $f$ está restringido "artificialmente", como el caso que consideramos en los comentarios.

De todos modos, con estos supuestos, es razonable llamar a $\nabla f(x) +A^T\nu=0$ una "restricción de viabilidad dual". [EDIT: Sigo manteniendo que esto es razonable en la práctica, a pesar de las excepciones encontradas por el OP]. Puede parecer un poco restrictivo exigir este supuesto al principio. Pero yo sugeriría que si las restricciones de dominio artificial se sustituyen por explícito En su lugar, las restricciones de igualdad y desigualdad son un poco más ligeras.