# 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?

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.

• Thanks for an excellent answer! I know it's been a while, but how did you figure out that $\operatorname{diag}(KRdRK) = (K\odot K)(r\odot dr)$? Are there some properties of diagonals or tricks for manipulating them? May 25, 2023 at 21:59
• The relevant identity is $${\rm diag}\Big(A\;{\rm Diag}(x)\;B\Big) = \big(B^T\odot A\big)\,x$$
– greg
Jun 22, 2023 at 2:10

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

• While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review
– Jan
May 17, 2020 at 15:15
• Updated to include the derivation of the gradient from the reference. May 17, 2020 at 17:29