7
$\begingroup$

Let $C$ be a symmetric positive definite matrix such that $0\leq c_{ij} \leq 1$, $c_{ii}=1$, and define $f$ as $$f(x)=\sum_{i}x_{i}\log(\sum_{j}c_{ij}x_{j})$$ for positive vectors $x$ (in fact let's assume that $\sum_i x_i = 1$). From every computational test I have done, this function appears to be convex, but I cannot figure out why. Can anyone offer any advice for going about it? It looks a lot like negative entropy but with a linear term inside the log. Also, the individual summands are not convex, but their sum always appears to be.

Edit: The Hessian is $$h_{ij} = \sum_{k}\frac{c_{ki}c_{kj}x_{k}}{(\boldsymbol{c}_{k}^{\top}\boldsymbol{x})^{2}}-\frac{c_{ij}}{\sum_{k}c_{ik}x_{k}}-\frac{c_{ji}}{\sum_{k}c_{jk}x_{k}}$$

Edit 2: and the quadratic form for $n=2$ is $$\begin{array}{c} -v_{1}{\left(v_{1}{\left(\frac{c_{11}^{2}x_{1}}{{\left(c_{11}x_{1}+c_{12}x_{2}\right)}^{2}}+\frac{c_{21}^{2}x_{2}}{{\left(c_{21}x_{1}+c_{22}x_{2}\right)}^{2}}-\frac{2\,c_{11}}{c_{11}x_{1}+c_{12}x_{2}}\right)}+v_{2}{\left(\frac{c_{11}c_{12}x_{1}}{{\left(c_{11}x_{1}+c_{12}x_{2}\right)}^{2}}+\frac{c_{21}c_{22}x_{2}}{{\left(c_{21}x_{1}+c_{22}x_{2}\right)}^{2}}-\frac{c_{12}}{c_{11}x_{1}+c_{12}x_{2}}-\frac{c_{21}}{c_{21}x_{1}+c_{22}x_{2}}\right)}\right)}\\ -v_{2}{\left(v_{1}{\left(\frac{c_{11}c_{12}x_{1}}{{\left(c_{11}x_{1}+c_{12}x_{2}\right)}^{2}}+\frac{c_{21}c_{22}x_{2}}{{\left(c_{21}x_{1}+c_{22}x_{2}\right)}^{2}}-\frac{c_{12}}{c_{11}x_{1}+c_{12}x_{2}}-\frac{c_{21}}{c_{21}x_{1}+c_{22}x_{2}}\right)}+v_{2}{\left(\frac{c_{12}^{2}x_{1}}{{\left(c_{11}x_{1}+c_{12}x_{2}\right)}^{2}}+\frac{c_{22}^{2}x_{2}}{{\left(c_{21}x_{1}+c_{22}x_{2}\right)}^{2}}-\frac{2\,c_{22}}{c_{21}x_{1}+c_{22}x_{2}}\right)}\right)} \end{array}$$

Edit 3: And per Geoffrey Irving's suggestion, if I set $y=Cx$, then the hessian is $h_{ij} = \frac{b_{ij}}{y_{i}}+\frac{b_{ji}}{y_{j}}$ for off-diagonals and $h_{ii} = \frac{2\,b_{ii}}{y_{i}}-\frac{\sum_{k}b_{ik}y_{k}}{y_{i}^{2}}$, where $b_{ij}$ is an entry of $C^{-1}$.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ computing the Hessian of this function seems doable. Does it have a simple form? Can you include the Hessian in your post? $\endgroup$
    – Thomas Kojar
    Commented Sep 9 at 19:25
  • $\begingroup$ @ThomasKojar it was kind of ugly in sagemath, but I'll share what I have, thank you! $\endgroup$
    – Tom Solberg
    Commented Sep 9 at 19:27
  • 1
    $\begingroup$ @PietroMajer my mistake, the minus sign shouldn't have been there! Thank you! $\endgroup$
    – Tom Solberg
    Commented Sep 9 at 20:13
  • 1
    $\begingroup$ @GeoffreyIrving good idea! I'll work out the corresponding terms for that one as well and edit... $\endgroup$
    – Tom Solberg
    Commented Sep 9 at 21:14
  • 1
    $\begingroup$ The function simplifies to $$ \begin{align} f(x) &= \sum_i x_i \log\left(x_i + \sum_{j \neq i} c_{ij} x_j\right) \\\\ &= \underbrace{\sum_i x_i \log(x_i)}_{\text{diagonal terms}} + \underbrace{\sum_i x_i \log\left(1 + \frac{\sum_{j \neq i} c_{ij} x_j}{x_i}\right)}_{\text{off-diagonal terms}}\end{align}$$ The first expression is convex. The second one is concave. $\endgroup$
    – ndrwnaguib
    Commented Nov 16 at 22:27

0

Reset to default

You must log in to answer this question.