# Prove that $f(\mathbf{x}) = \mathbf{c}^T\mathbf{x} - \sum_{i=1}^{m} \log(b_i - \mathbf{a}_i^T\mathbf{x})$ is convex

Let's consider $$f \colon \mathbb{R}^n \to \mathbb{R}$$,

$$f(\mathbf{x}) = \mathbf{c}^T\mathbf{x} - \sum_{i=1}^{m} \log(b_i - \mathbf{a}_i^T\mathbf{x}),$$

with $$\mathbf{x} \in \mathbb{R}^n$$, $$\mathbf{c} \in \mathbb{R}^n$$, $$\mathbf{b} \in \mathbb{R}^m$$, $$\mathbf{a}_i \in \mathbb{R}^n$$, for $$i = 1,\ldots,m$$, so $$\mathbf{A} \in \mathbb{R}^{n\times m}$$.

• $$\mathbf{dom}f$$ contains the $$\mathbf{x}$$ for which the arguments of the logarithms are positive.

• (Note: I have also seen $$f$$ written as, $$f(\mathbf{x}) = \mathbf{c}^T\mathbf{x} - \operatorname{sum}(\log(\mathbf{b} - \mathbf{A}\mathbf{x}) )$$.)

I have to prove that $$f$$ is convex (most likely using the second derivative theorem).

I am not sure how to proceed. I have read that:

$$\nabla \biggl( \sum_{i=1}^{m} \log(b_i - \mathbf{a}_i^T\mathbf{x}) \biggr) = \sum_{i=1}^{m} \frac{1}{b_i - \mathbf{a}_i^T\mathbf{x}}\mathbf{a}_i$$

But I don't fully understand it.

• Hint. (1) $x \mapsto =-\log x$ is convex. (2) If $f$ is affine and $g$ is convex, then $g \circ f$ is also convex. (see this, for instance.) Nov 4, 2023 at 12:49
• Ok that is a way but I have to use the second derivative theorem ($\nabla^2 f(x) \succcurlyeq 0$) based on the hints I have. I am on confused on how I can calculate the gradient and the hessian of $f$. Nov 4, 2023 at 14:23
• @DontWorry Your comment suggests that you might not be familiar with matrix calculus. I've therefore written an answer with detailed calculations of the entries of the Hessian of $f$. Hope that helps. Nov 5, 2023 at 23:52

For $$j, k \in \{1, \ldots,n \}$$, we have $$\frac{\partial^2}{\partial x_j \partial x_k}\left(\mathbf c^\mathsf T \mathbf x\right) = \frac{\partial}{\partial x_j}\left(\frac{\partial}{\partial x_k}\left(\mathbf c^\mathsf T \mathbf x\right)\right) = \frac{\partial}{\partial x_j}\left(c_k\right) = 0$$ and \begin{align} \frac{\partial^2}{\partial x_j \partial x_k}\left(- \sum_{i=1}^{m} \ln\left(b_i - \mathbf a_i^\mathsf T\mathbf{x}\right)\right) &= \frac{\partial}{\partial x_j}\left(\frac{\partial}{\partial x_k}\left(- \sum_{i=1}^{m} \ln\left(b_i - \mathbf a_i^\mathsf T\mathbf{x}\right)\right)\right) \\ &= \frac{\partial}{\partial x_j}\left(\sum_{i=1}^m\frac{1}{b_i - \mathbf a_i^\mathsf T\mathbf{x}}\cdot \left(\mathbf a_i\right)_k\right) \\ &= \sum_{i=1}^m\frac{1}{\left(b_i - \mathbf a_i^\mathsf T\mathbf{x}\right)^2}\cdot \left(\mathbf a_i\right)_k \cdot \left(\mathbf a_i\right)_j. \end{align}

Therefore, the Hessian matrix of $$f$$ in $$\mathbf x$$ is given by $$\mathbf H_f(\mathbf x) = \sum_{i=1}^m \frac{1}{\left(b_i - \mathbf a_i^\mathsf T \mathbf x\right)^2} \mathbf a_i \mathbf a_i^\mathsf T.$$ Finally, $$\mathbf H_f$$ is positive semi-definite since $$\mathbf v^\mathsf T \left[\sum_{i=1}^m \frac{1}{\left(b_i - \mathbf a_i^\mathsf T \mathbf x\right)^2} \mathbf a_i \mathbf a_i^\mathsf T \right] \mathbf v = \sum_{i=1}^m \frac{1}{\left(b_i - \mathbf a_i^\mathsf T \mathbf x\right)^2} \mathbf v^\mathsf T\mathbf a_i \mathbf a_i^\mathsf T \mathbf v = \sum_{i=1}^m \frac{\left(\mathbf v^\mathsf T\mathbf a_i\right)^2}{\left(b_i - \mathbf a_i^\mathsf T \mathbf x\right)^2} \geq 0$$ for all $$\mathbf v, \mathbf x \in \mathbb R^n.$$

• Would it be possible to write the calculations with even more details or how short explanation? For example in $\sum_{i=1}^{m} \frac{1}{b_i - \mathbf{a}_i^T\mathbf{x}}\mathbf{a}_i$, how $\mathbf{a}_i^T$ appears on numerator as $\mathbf{a}_i$ without transpose? Also because $\mathbf{a}_i^T \mathbf{x}$ i would expect $a_{i1}x_1 + a_{i2}x_2+ \dot + a_{in}x_n$ so only one term would remain with each partial derivative but we end up with the whole vector $\mathbf{a_i}$. Nov 6, 2023 at 17:16
• @DontWorry In standard Euclidean space, the gradient of $\mathbf x\mapsto- \sum_{i=1}^{m}\ln\left(b_i-\mathbf a_i^\mathsf T\mathbf{x}\right)$ is the (column) vector whose $k$-th entry is given by $\frac{\partial}{\partial x_k}\left(-\sum_{i=1}^{m} \ln\left(b_i-\mathbf a_i^\mathsf T\mathbf{x}\right)\right).$ And we have$\frac{\partial}{\partial x_k}\left(- \sum_{i=1}^{m} \ln\left(b_i-\mathbf a_i^\mathsf T\mathbf{x}\right)\right)=\sum_{i=1}^m\frac{1}{b_i-\mathbf a_i^\mathsf T\mathbf{x}}\cdot\left(\mathbf a_i\right)_k,$ where $\left(\mathbf a_i\right)_k$ denotes the $k$-th entry of $\mathbf a_i$. Nov 11, 2023 at 12:36
• why after the first differentiation we get $\mathbf{a_i}$ while after the second differentiation we get $\mathbf{a_i^T}$, is it based on the fact that $\mathbf{H_f}$ has to be a $n \times n$ matrix, so we manipulate the dimensions of $\mathbf{a_i}$ in such a way to get what we want? Nov 11, 2023 at 14:53
• @DontWorry Have you had a look at the definition of a Hessian matrix? The Hessian matrix of $f$ evaluated at $\mathbf x$ is the $n \times n$ matrix whose $(j,k)$ entry is given by $\frac{\partial^2f}{\partial x_j \partial x_k}(\mathbf x)$. And the $(j,k)$ entry of $\mathbf a_i \mathbf a_i^\mathsf T$ equals $(\mathbf a_i)_j \cdot (\mathbf a_i)_k$. Nov 12, 2023 at 2:03

As mentioned in a comment, the easiest way to prove this is to realize that $$f$$ is a sum of convex functions. However, since you are interested in proving this by differentiation, I wanted to present a coordinate-free calculation to complement the answer obtained previously.

First, notice that

$$df = \mathbf{c}^\intercal d\mathbf{x} - \sum_{i} \frac{-\mathbf{a}_i^\intercal d\mathbf{x}}{b_i-\mathbf{a}_i^\intercal\mathbf{x}} = \left(\mathbf{c}+\sum_i\frac{\mathbf{a}_i}{b_i-\mathbf{a}_i^\intercal\mathbf{x}}\right)\cdot d\mathbf{x} = \nabla f\cdot d\mathbf{x},$$ Which shows that $$\nabla f$$ is the term in parentheses. To compute the second derivative $$\nabla^2 f$$, it suffices to notice that

$$d\nabla f = \sum_i \frac{\mathbf{a}_i\left(\mathbf{a}_i^\intercal d\mathbf{x}\right)}{\left(b_i - \mathbf{a}_i^\intercal\mathbf{x}\right)^2} = \left(\sum_i \frac{\mathbf{a}_i\mathbf{a}_i^\intercal}{\left(b_i-\mathbf{a}_i^\intercal\mathbf{x}\right)^2} \right)d\mathbf{x} = \left(\nabla^2f\right)d\mathbf{x},$$ Which agrees with what was presented earlier. From this it follows immediately that $$\mathbf{v}^\intercal\left(\nabla^2f\right)\mathbf{v}\geq 0$$ for any $$\mathbf{v}$$ since both the numerator and denominator are sums of quadratic terms.