Xrfgtjtk

I saw the solution of this question,but i have some problem

Q: min$_x c^T mathbf x$

$s.t. mathbf A mathbf x le mathbf b,mathbf x_i(1-mathbf x_i)=0,i=1,...,n,$ where $mathbf x =[x_1,...,x_n]^T$,find its dual function

Solution:

begin{align}
L(x, mu ,v) & = c^Tx+mu ^T(Ax-b)-sumlimits_{i=1}^{n}v_ix_i(1-x_i) \ & =c^Tx+mu ^T(Ax-b)-v^Tx+x^T diag(v)x \
end{align}

then minimizing over $x $ gives the dual function

$g(mu,v)=-b^Tmu - frac{1}{4} sumlimits_{i=1}^{n}(frac{c_i+a_i^T mu -v_i^2}{v_i})$,when $v ge 0$ ,otherwise,it is $-infty$

I want to ask

$1.$ why is $sumlimits_{i=1}^{n}v_ix_i(1-x_i)=v^Tx+x^T diag(v)x?$ it seems that $sumlimits_{i=1}^{n}v_i(1-x_i)=x^T diag(v)x, $ why?

$2.$Why is $ L(x, mu ,v)=g(mu,v)=-b^Tmu - frac{1}{4} sumlimits_{i=1}^{n}(frac{c_i+a_i^T mu -v_i^2}{v_i})$,when $v ge 0$

In terms of indices,

$$v^Tx = sumlimits_i v_ix_i, text{ and } x^Tdiag(v)x = sumlimits_i x_iv_ix_i$$

therefore their difference is $$v^Tx - x^Tdiag(v)x = sumlimits_i v_ix_i(1-x_i)$$

I suspect you have an extra "$+x^Tv$" term in $L(x,mu,nu)$ that does not belong.

Setting $L(x,mu,nu) = c^Tx + mu^T(Ax-b) - v^Tx + x^Tdiag(v)x$ we get the minimum by taking

$$dL = c^T + mu^TA - v^T + 2v^T x = 0$$

and solve that $2v^Tx = v^T - c^T - mu^TA$, in other words

$$x_i = frac1{2v_i}(v_i-c_i-sum_j mu_jA_{j,i})$$

Now plug this into $L(x,mu,nu)$ to get $g(mu,nu)$.

ADDED: Ok, the reason you aren't getting the desired solution of $g(mu,nu)$ is that it has been copied down incorrectly. The correct solution is

$$g(mu,nu) = begin{cases}-b^Tmu - (1/4)sum_{i=1}^n(c_i + a_i^Tmu - nu_i)^2/nu_i&nu geq 0\-infty&text{else}end{cases}$$

Note the placement of the square outside of the parentheses. This problem is 5.13 from Boyd's textbook, and you may check that this is the correct solution by searching for a file from Stanford's course EE364a, Winter 2007-08 titled hw5sol.pdf.

After making this change, you should check that the solution we arrived at above does give the correct answer.

Lastly, it's a little easier to check the solution if you write the Lagrangian like this:
$$L(x,mu,nu) = x^Ttext{diag}(nu)x + (c + A^Tmu - nu)^Tx - b^Tmu$$

The algebra works like this: if $vX^2 + cX = -c^2/4v$ then the solution is $X = -c/2v$