4

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.

statmerkur
  • 325
DontWorry
  • 111
  • 8
  • 1
    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.) – Sangchul Lee Nov 04 '23 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$. – DontWorry Nov 04 '23 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. – statmerkur Nov 05 '23 at 23:52

2 Answers2

2

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

statmerkur
  • 325
  • 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}$. – DontWorry Nov 06 '23 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$. – statmerkur Nov 11 '23 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? – DontWorry Nov 11 '23 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$. – statmerkur Nov 12 '23 at 02:03
0

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.

MathIsArt
  • 865