# Stuck in concavity proof of least squares cost as a function of weights

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

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!

• Yeah, In fact I can figure out that g is composed of a linear function(which is both concave and convex) and negative sum of matrix fractional function(which is concave). But, I cannot deduce the same formula as the book – Finley Jul 25 '17 at 10:25
• – Rodrigo de Azevedo Jul 25 '17 at 22:47

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.