why is $\sum\limits_{i=1}^{n}v_ix_i(1-x_i)=v^Tx+x^T diag(v)x?$ and its dual function

66 Views Asked by At

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)-\sum\limits_{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^T\mu - \frac{1}{4} \sum\limits_{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 $\sum\limits_{i=1}^{n}v_ix_i(1-x_i)=v^Tx+x^T diag(v)x?$ it seems that $\sum\limits_{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^T\mu - \frac{1}{4} \sum\limits_{i=1}^{n}(\frac{c_i+a_i^T \mu -v_i^2}{v_i})$,when $v \ge 0$

1

There are 1 best solutions below

5
On

In terms of indices,

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

therefore their difference is $$v^Tx - x^Tdiag(v)x = \sum\limits_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^T\mu - (1/4)\sum_{i=1}^n(c_i + a_i^T\mu - \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^T\text{diag}(\nu)x + (c + A^T\mu - \nu)^Tx - b^T\mu$$

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