Dual of the barrier transformed linear program $\min_{x \in \mathbb{R}^n} \left\{ c^T x - \mu \sum_{j=1}^n \log(x_j) : Ax = b; x \geq 0 \right\}$

127 Views Asked by At

Dual of the following linear program \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & c^T x \ -\mu \sum_{j=1}^n \log(x_j) \\ \text{subject to }\quad & Ax = b\\ & x \geq 0 \ , \end{align} where $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$.


Partial attempt

Defining, $X = {\rm diag}(x)$ and $1$ as a column vector of all ones.

Forming the Lagrangian such that \begin{align} L(x,y,z) &= c^T x - \mu 1^T \log(x) + y^T\left( Ax - b\right) - z^T(x) \ . \end{align}

The dual can be obtained as \begin{align} g(y,z) := \inf_x L(x,y,z) \end{align}

So, \begin{align} 0 \in \frac{\partial L}{\partial x} \Longrightarrow c - \mu X^{-1} 1 + A^T y - z = 0 \ . \end{align}

Now, how to proceed and derive the dual. or is there some other way to derive the dual? Thank you so much for your help.