How to derive the gradient and Hessian of the Volumetric barrier $v$

Question

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?

Answer 1

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.

Answer 2

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}.$$