0

We have the minimization function: $$ \begin{align*} \text{minimize}~ f(x) &= \sum_{i=1}^{n} x_i \log x_i\\ \text{subject to}~ Ax &= b \end{align*} $$

And we want to find the Lagrangian dual. The first step is to find the conjugate which is $$ f^*(y) = \sum_{i=1}^{n} e^{y_i-1} $$

Let us have the variable $v$ for the equality constraint, how do we get the function $g(v)$?

We know that what we have to end up with, is the maximization problem $$ \text{maximize}~ -b^T v - n - e^{-v - 1} \sum_{i=1}^p \exp(-a_i^T v) $$

TilManG4
  • 67
  • 6

1 Answers1

0

The lagrange function of this problem is $$ g(x,v) = \sum_{i=1}^n x_i log(x_i) + \sum_{i=1}^n (v^TA)_i x_i-b^Tv. $$ Differentiate it w.r.t. $x_i$, to get $x_i = e^{-1-(v^TA)_i}$ for all $i$. On substituting $x_i$ in the above function we get $$ -\sum_{i=1}^n e^{-1-(v^TA)_i} - b^Tv, $$ we maximize it to obtain the lagrange dual function. It is different from what is stated, please do tell me if there seems to be a mistake.

Cherryblossoms
  • 917