How to derive the gradient and Hessian of the Volumetric barrier $v$ I'm reading the monograph Convex Optimization: Algorithms and Complexity . In Section 2.3, the author discusses an algorithm of Vaidya. He makes the following definition:
Definition 1:  Let $A \in \mathbb{R}^{m \times n}$ where the $i^{t h}$ row is $a_{i} \in \mathbb{R}^{n},$ and let $b \in \mathbb{R}^{m} .$ We
consider the logarithmic barrier $F$ for the polytope $\left\{x \in \mathbb{R}^{n}: A x>b\right\}$
defined by
$$
F(x)=-\sum_{i=1}^{m} \log \left(a_{i}^{\top} x-b_{i}\right)
$$
Definition 2:  The volumetric barrier $v$ is defined by
$$
v(x)=\frac{1}{2} \log \operatorname{det}\left(\nabla^{2} F(x)\right)
$$
Note that we have $$
\nabla^{2} F(x)=\sum_{i=1}^{m} \frac{a_{i} a_{i}^{\top}}{\left(a_{i}^{\top} x-b_{i}\right)^{2}}
$$
Now, the author claims that we can easily prove the following results:
$$
\nabla v(x)=-\sum_{i=1}^{m} \sigma_{i}(x) \frac{a_{i}}{a_{i}^{\top} x-b_{i}}
$$
$$
\nabla^{2} v(x) \succeq \sum_{i=1}^{m} \sigma_{i}(x) \frac{a_{i} a_{i}^{\top}}{\left(a_{i}^{\top} x-b_{i}\right)^{2}}
$$
where we introduce the leverage score
$$
\sigma_{i}(x)=\frac{\left(\nabla^{2} F(x)\right)^{-1}\left[a_{i}, a_{i}\right]}{\left(a_{i}^{\top} x-b_{i}\right)^{2}}
$$
(Here, it seems that the author does not explain the notation $[a,a]$, but I guess that it refers to the dot product)
Unfortunately, I have no idea how these results are shown. Can anyone help?
 A: Denote the elementwise/Hadamard product for two matrices of equal dimensions as $$A\odot B$$
and the trace/Frobenius product as $$A:B = \operatorname{Tr}(A^TB)$$
For typing convenience, define some auxiliary variables
$$\eqalign{
y &= Ax-b,\quad&r = y^{\odot-1} \quad({\rm hadamard\, inverse}) \\
Y &= \operatorname{Diag}(y), &R = \operatorname{Diag}(r) \\
}$$
and their differentials
$$\eqalign{
R\,Y &= I &\implies R\,dY = -Y\,dR \\
r\odot y &= {\tt1} &\implies r\odot dy = -y\odot dr \\
Yr = Ry &= {\tt1} &\implies R\,dy = -Y\,dr \\
dy &= A\,dx \\
dr &= (RY)dr \\
   &= R(-R\,dy) \\
   &= -R^2A\,dx  \\
}$$
Using these variables, the gradient ($g$) and hessian ($H$) of the log barrier can be calculated.
$$\eqalign{
F &= -{\tt1}:\log(y) \\
dF &= -{\tt1}:r\odot dy = -r:dy = -A^Tr:dx \\
\frac{\partial F}{\partial x} &= -A^Tr \;\doteq\; g \\
\\
dg &= -A^Tdr = A^TR^2A\,dx \\
\frac{\partial g}{\partial x} &= A^TR^2A \;\doteq\; H \\
}$$
The following quantities
$$\eqalign{
dH &= 2A^TR\,dR\,A \\
K &= AH^{-1}A^T \\
w &= \operatorname{diag}(K) \\
W &= \operatorname{Diag}(w) = I\odot K \\
}$$
will be useful in calculating the gradient ($p$) and hessian ($Q$) of the volumetric barrier.
$$\eqalign{
 v &= \tfrac{1}{2}\log\det H \\
dv &= \tfrac{1}{2}\,d\operatorname{tr}\log H \\
   &= \tfrac{1}{2}\,H^{-T}:dH \\
   &= H^{-1}:A^TR\,dR\,A \\
   &= \left(AH^{-1}A^T\right):\operatorname{Diag}(r\odot dr) \\
   &= w:(r\odot dr) \\
   &= -(r\odot w):(R^2A\,dx) \\
   &= -A^TR^3w:dx \\
\frac{\partial v}{\partial x} &= -A^TR^3w \;\doteq\; p \\
\\
dp &= -A^T(3R^2dR)\,w - A^TR^3dw \\
   &= -3A^TR^2W\,dr
    + A^TR^3\operatorname{diag}\left(AH^{-1}dH\,H^{-1}A^T\right) \\
   &= 3A^TR^2WR^2A\,dx + 2A^TR^3\operatorname{diag}(KR\,dR\,K) \\
   &= 3A^TR^2WR^2A\,dx + 2A^TR^3(K\odot K)(r\odot dr) \\
   &= 3A^TR^2WR^2A\,dx + 2A^TR^3(K\odot K)R\,dr \\
   &= 3A^TR^3(YWY)R^3A\,dx - 2A^TR^3(K\odot K)R^3A\,dx \\
   &= A^TR^3\big(3YWY-2K\odot K\big)R^3A\,dx \\
\frac{\partial p}{\partial x}
   &= A^TR^3\big(3YWY-2K\odot K)R^3A \;\doteq\; Q \\
}$$
So there are the gradients and hessians in matrix notation.
The author's expression for the leverage is unclear. My best guess is
$$\eqalign{
\sigma &= \operatorname{Diag}\left(RAH^{-1}A^TR\right) = RWR \\
}$$
then, for example you could write the above gradient and hessian as
$$\eqalign{
p &= -A^T\sigma r \\
Q &= 3(A^TR\sigma RA) - 2A^TR^3(K\odot K)R^3A \\
}$$
The use of the $\succeq$ symbol suggests that he purposely omitted the coefficient of $3$ and the negative $(K\odot K)$ term; perhaps they weren't important for his subsequent calculations.
A: Vaidya proves these as Lemmas 1 and 2 in (P.M. Vaidya, 1996). We reproduce the derivation of the gradient below. 
For ease of notation, define $\rho_i(x) := \frac{a_i a_i^{\top}}{(a_i^\top x-b_i)^2}$ and $H(x):=\nabla^2F(x)$. We use the following approximation: $\det(I+tA) = 1+t\cdot{\rm Tr}(A)+o(t^2)$. Let $h$ be an arbitrary direction vector. 
\begin{align}
   2\cdot v(x+th) = \log\det[H(x+th)]&= \log\det\bigg[\sum_i \frac{a_i a_i^{\top}}{(a_i^\top (x+th)-b_i)^2}\bigg]\\
           &=\log\det\bigg[\sum_i \frac{a_i a_i^{\top}}{(a_i^\top x-b_i)^2}\cdot \bigg(1-\frac{2ta_i^\top h}{(a_i^\top x-b_i)}+o(t^2)\bigg)\bigg]\\
           &= \log\det\bigg[H(x)-\sum_i \rho_i(x) \cdot\bigg(\frac{2ta_i^\top h}{(a_i^\top x-b_i)} + o(t^2)\bigg) \bigg]\\
           &= \log\det[\ H(x)\ ]\\
&+\log\det\bigg[  I-\sum_i H(x)^{-1/2}\rho_i(x)H(x)^{-1/2} \cdot\bigg(\frac{2ta_i^\top h}{(a_i^\top x-b_i)}+o(t^2)\bigg) \bigg]\\
           &= \log\det[\ H(x)\ ]+\log\bigg[ 1-\sum_i\frac{2ta_i^\top h}{(a_i^\top x-b_i)}\cdot 
 {\rm Tr}(H(x)^{-1/2}\rho_i(x)H(x)^{-1/2})+o(t^2)\bigg]\\
           &= \log\det[\ H(x)\ ] - \sum_i\frac{2ta_i^\top h}{(a_i^\top x-b_i)}\cdot 
 {\rm Tr}(H(x)^{-1/2}\rho_i(x)H(x)^{-1/2})+o(t^2).\tag{1}\label{eq_res_1}
\end{align}
Next we show that ${\rm Tr}(H(x)^{-1/2}\rho_i(x)H(x)^{-1/2})=\sigma_i(x)$. To this end observe
\begin{align}
{\rm Tr}(H(x)^{-1/2}\rho_i(x)H(x)^{-1/2})={\rm Tr}(H(x)^{-1}\cdot\rho_i(x))&=\frac{{\rm Tr}(H(x)^{-1}a_i a_i^{\top})}{(a_i^\top x-b_i)^2}\\
&=\frac{a_i^{\top}H(x)^{-1}a_i}{(a_i^\top x-b_i)^2}\\
&=\sigma_i(x).
\end{align}
Now we can compute the following directional derivative
\begin{align}
\lim_{t\to 0}\ \frac{   v(x+th)-v(x)}{t}=-\sum_i \sigma_i(x)\cdot 
 \frac{a_i^\top h}{a_i^\top x-b_i}
\end{align}
Since $\nabla v(x)$ is the unique vector which, for all $w\in \mathbb{R}^n$, satisfies $\langle \nabla v(x), w\rangle = \frac{d v(x+tw)}{dt}\big|_{t=0}$, and as the choice of $h$ was arbitrary, we can conclude that 
$$\nabla v(x) := -\sum_{i}\sigma_i(x) \cdot\frac{a_i}{a_i^\top x-b_i}.$$
