How is this dual function derived?

61 Views Asked by At

Say we have primal problem:

$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & Ax \le b\\ & x_i (1-x_i) = 0, \quad i \in [n]\end{array}$$

where $\le$ means component-wise greater than or equal to. The Lagrangian is

$$L(x, \mu, v) = - b^T\mu + (c+A^T\mu-v)^Tx- x^T \text{diag}(v)x$$

Minimizing over $x$ gives the dual function we get

$$g(\mu, v) = -b^T\mu - (1/4)\sum_{i=1}^n(c_i+a_i^T - v_i)^T/v_i$$

if $v \ge 0$ and $-\infty$ otherwise. $a_i$ is the $i$th column of $A$.

Can someone explain how this dual function is derived? I don't see how to show it's this expression.

Taking the gradient of $L$ should be $-2*\text{diag}(v)x + (c+A^T\mu - v) = 0$

Which implies $x^* = (-1/2)\text{diag}(v)^{-1}(c + A^T\mu - v)$

But substituting this into $L$ doesn't give this result.

1

There are 1 best solutions below

7
On BEST ANSWER

I think your approach looks good. If we let $N:=\mathrm{diag}(\nu)$, then the Lagrangian is $$ \mathcal{L}(x,\mu,\nu)=-\mu^Tb+(c+A^T\mu-\nu)^Tx+x^TNx $$ as you suggest. If $\nu>0$ then this expression has the unique minimizer $x^*$ given by $$ x^*=-\tfrac{1}{2}N^{-1}(c+A^T\mu-\nu) $$ Plugging this back into the Lagrangian, I get $$ \mathcal{L}(x^*,\mu,\nu)=-\mu^Tb-\tfrac{1}{4}(c+A^T\mu-\nu)N^{-1}(c+A^T\mu-\nu), $$ which, written in component form, is equal to $$ \mathcal{L}(x^*,\mu,\nu)=g(\mu,\nu)=-\mu^Tb-\tfrac{1}{4}\sum_{i=1}^n\frac{1}{\nu_i}\cdot(c_i+a_i^T\mu-\nu_i)^2. $$ This is the answer you suggest, assuming that $a_i\mapsto a_i^T\mu$ and the outer transpose should be a $2$.