¿Función conjugada de log-sum-exp?

Question

En Boyd's Libro de optimización convexa En el ejemplo 3.25 se encuentra la función conjugada $f^*(y):=\sup_{x\in\text{dom}(f)}(y^Tx-f(x))$ de la función log-sum-exp $f(x):=\log(\sum_{i=1}^ne^{x_i})$ . En primer lugar, el gradiente de $y^Tx-f(x)$ se toma para cumplir la condición:

$$ y_i=\frac{e^{x_i}}{\sum_{j=1}^ne^{x_j}}\quad i=1,...,n $$

donde vemos que una solución para $y$ existe si y sólo si $y\succ 0$ y $\textbf{1}^Ty=1$ . Entonces el libro simplemente dice:

Sustituyendo la expresión de $y_i$ en $y^Tx-f(x)$ obtenemos $f^*(y)=\sum_{i=1}^ny_i\log(y_i)$ .

Hasta ahora no he tenido éxito en derivar esto. ¿Cómo se puede proceder? Todo lo que veo es:

$$ y^Tx-f(x)=\sum_{i=1}^ny_ix_i-\log(\sum_{i=1}^ne^{x_i})=\frac{\sum_{i=1}^nx_ie^{x_i}}{\sum_{j=1}^ne^{x_j}}-\log(\sum_{i=1}^ne^{x_i}) $$

Pero a partir de aquí no sé cómo proceder.

Answer 1

Quizás sea más fácil sustituir la expresión por $x_i$ en términos de $y_i$ : $$y_i=\frac{e^{x_i}}{\sum_{j=1}^ne^{x_j}}=\frac{e^{x_i}}{e^{f(x)}} \Leftrightarrow x_i = \log y_i + f(x)$$ Entonces, utilizando el hecho de que $1^Ty=1$ la expresión se simplifica a: $$ \begin{aligned} y^Tx - f(x) &= \sum_{i=1}^n y_i x_i - f(x) \\ &= \sum_{i=1}^n y_i (\log y_i + f(x)) -f(x) \\ &= \sum_{i=1}^n y_i \log y_i + \sum_{i=1}^n y_i f(x) -f(x)\\ &= \sum_{i=1}^n y_i \log y_i \end{aligned} $$

Answer 2

$\def\T{^{\mathrm{T}}} \def\e{\mathrm{e}}$ Porque $$ y\T x - f(x) = \frac{\sum\limits_{k = 1}^n x_k \e^{x_k}}{\sum\limits_{k = 1}^n \e^{x_k}} - \ln\left( \sum_{k = 1}^n \e^{x_k} \right) $$ y \begin{align*} \sum_{k = 1}^n y_k \ln y_k &= \sum_{k = 1}^n \frac{\e^{x_k}}{\sum_{j = 1}^n \e^{x_j}} \left( \ln \e^{x_k} - \ln \sum_{j = 1}^n \e^{x_j} \right)\\ &= \sum_{k = 1}^n \frac{\e^{x_k} \ln \e^{x_k}}{\sum_{j = 1}^n \e^{x_j}} - \sum_{k = 1}^n \e^{x_k} \cdot \frac{\ln \sum_{j = 1}^n \e^{x_j}}{\sum_{j = 1}^n \e^{x_j}}\\ &= \frac{\sum_{k = 1}^n \e^{x_k} \ln \e^{x_k}}{\sum_{j = 1}^n \e^{x_j}} - \left( \sum_{k = 1}^n \e^{x_k} \right) \cdot \frac{\ln \sum_{j = 1}^n \e^{x_j}}{\sum_{j = 1}^n \e^{x_j}}\\ &= \frac{\sum\limits_{k = 1}^n x_k \e^{x_k}}{\sum\limits_{k = 1}^n \e^{x_k}} - \ln\left( \sum_{k = 1}^n \e^{x_k} \right), \end{align*} entonces $$ y\T x - f(x) = \sum_{k = 1}^n y_k \ln y_k. $$