1
$\begingroup$

This problem comes from Boyd & Vandenberghe Convex Optimization, example 3.9 in page 81.


enter image description here


All derivations make sense for me except the last step which says:

$$g(w)=b^TWb-b^TWA(A^TWA)^{-1}A^TWb =\sum_{i=1}^nw_ib_i^2-\sum_{i=1}^nw_i^2b_i^2a_i^T(\sum_{j=1}^nw_ja_ja_j^T)^{-1}a_i$$

However, I figure it out as:

$$g(w)=b^TWb-b^TWA(A^TWA)^{-1}A^TWb =\sum_{i=1}^nw_ib_i^2-\sum_{i=1}^nw_ib_ia_i^T(\sum_{j=1}^nw_ja_ja_j^T)^{-1}\sum_{k=1}^nw_kb_ka_k$$

where $W=diag(w),w=[w_1,w_2,...,w_n]^T,b{\in}R^n,A{\in}R^{n{\times}m},A=\begin{bmatrix}a_1^T\\a_2^T\\\vdots\\a_n^T \end{bmatrix},a_i{\in}R^m$. And $A^TWA\succ0$.

So I actually want to know why $$\sum_{i=1}^nw_i^2b_i^2a_i^T(\sum_{j=1}^nw_ja_ja_j^T)^{-1}a_i=\sum_{i=1}^nw_ib_ia_i^T(\sum_{j=1}^nw_ja_ja_j^T)^{-1}\sum_{k=1}^nw_kb_ka_k$$

Thank you!

$\endgroup$
0
$\begingroup$

Let

$$\mathrm C := \mathrm A^{\top} \mathrm W \,\mathrm A = \begin{bmatrix} | & | & & |\\ \mathrm a_1 & \mathrm a_2 & \dots & \mathrm a_n\\ | & | & & |\end{bmatrix} \begin{bmatrix} w_1 & & & \\ & w_2 & & \\ & & \ddots & \\ & & & w_n\end{bmatrix} \begin{bmatrix} — \mathrm a_1^{\top} — \\ — \mathrm a_2^{\top} —\\ \vdots\\ — \mathrm a_n^{\top} —\end{bmatrix} = \sum_{k=1}^n w_k \begin{bmatrix} | \\ \mathrm a_k\\ | \end{bmatrix} \begin{bmatrix} | \\ \mathrm a_k\\ | \end{bmatrix}^{\top}$$

Assuming that $\rm C$ is invertible,

$$\begin{array}{rl} \mathrm b^\top \mathrm W \,\mathrm A \left( \mathrm A^{\top} \mathrm W \,\mathrm A \right)^{-1} \mathrm A^\top \mathrm W \,\mathrm b &= \mathrm b^\top \mathrm W \,\mathrm A \,\mathrm C^{-1} \mathrm A^\top \mathrm W \,\mathrm b\\ &= \mathrm b^\top \begin{bmatrix} — w_1 \mathrm a_1^{\top} — \\ — w_2 \mathrm a_2^{\top} —\\ \vdots\\ — w_n \mathrm a_n^{\top} —\end{bmatrix} \begin{bmatrix} | & | & & |\\ w_1 \mathrm C^{-1} \mathrm a_1 & w_2 \mathrm C^{-1} \mathrm a_2 & \dots & w_n \mathrm C^{-1} \mathrm a_n\\ | & | & & |\end{bmatrix} \mathrm b\\ &= \mathrm b^\top \begin{bmatrix} w_1^2 \, \mathrm a_1^{\top} \mathrm C^{-1} \mathrm a_1 & w_1 w_2 \, \mathrm a_1^{\top} \mathrm C^{-1} \mathrm a_2 & \cdots & w_1 w_n \, \mathrm a_1^{\top} \mathrm C^{-1} \mathrm a_n\\ w_2 w_1 \, \mathrm a_2^{\top} \mathrm C^{-1} \mathrm a_1 & w_2^2 \, \mathrm a_2^{\top} \mathrm C^{-1} \mathrm a_2 & \cdots & w_2 w_n \, \mathrm a_2^{\top} \mathrm C^{-1} \mathrm a_n\\ \vdots & \vdots & \ddots & \vdots\\ w_n w_1 \, \mathrm a_n^{\top} \mathrm C^{-1} \mathrm a_1 & w_n w_2 \, \mathrm a_n^{\top} \mathrm C^{-1} \mathrm a_2 & \cdots & w_n^2 \, \mathrm a_n^{\top} \mathrm C^{-1} \mathrm a_n\\\end{bmatrix} \mathrm b\\ &= \displaystyle\sum_{i=1}^n \sum_{j=1}^n b_i b_j w_i w_j \, \mathrm a_i^{\top} \mathrm C^{-1} \mathrm a_j\end{array}$$

It seems that Boyd & Vandenberghe claim that

$$\displaystyle\sum_{i=1}^n \sum_{j=1}^n b_i b_j w_i w_j \, \mathrm a_i^{\top} \mathrm C^{-1} \mathrm a_j = \displaystyle\sum_{i=1}^n b_i^2 w_i^2 \, \mathrm a_i^{\top} \mathrm C^{-1} \mathrm a_i$$

or, in other words, that

$$\mathrm a_i^{\top} \mathrm C^{-1} \mathrm a_j = 0 \qquad \text{if} \qquad i \neq j$$

It is not obvious to me why this claim is true. If I figure it out, I will update this answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.