9
$\begingroup$

Let $A$ be a real matrix (not necessarily symmetric) whose off-diagonal elements are all non-negative, so that the elements of the matrix exponential $\exp(A)$ are all non-negative. Let $\mathbf x$ be a vector whose elements are all non-negative. Let $\sum(\cdot)$ denote the sum of all the terms in a vector.

I hypothesise that the function $f(t) = \log \,\sum\big(\exp(At)\, \mathbf x\big)$ is a convex function of $t$.

Note that '$\log$' in this formula is an ordinary logarithm while '$\exp$' is a matrix exponential. From playing around with this I haven't found an easy way to show it, but I haven't found an obvious counterexample either. So my question is, is $f(t) = \log\, \sum\big(\exp(At)\, \mathbf x\big)$ a convex function of $t$, if the entries of $A$ and $\mathbf x$ are non-negative?

For the avoidance of doubt, and for ease of searching for counterexamples, here is some Python code that calculates $f(t)$. (A and x should be numpy arrays of the appropriate dimensions.)

import numpy as np
import scipy.linalg as spl

def f(t, A, x):
    return np.log(np.sum(spl.expm(A*t).dot(x)))

Notes

  1. Originally I was using the convention that "convex" means a downward curve, i.e. the second derivative is never positive. However, Jonas Meyer points out in a comment that there are examples where the second derivative is consistently positive. So now I guess my question is, can the second derivative of $f(t)$ change sign as a function of $t$?

  2. I'm mostly only interested in part of the function where $t>0$, though in examples it seems to work for $t<0$ as well, until the sum of the elements becomes negative.

  3. It might be necessary to make additional assumptions about $A$ and $\mathbf x$, e.g. that $\exp(A)$ is irreducible, or that $\mathbf x$ has all positive elements. If that's the case I'd like to know.

  4. The motivation has to do with growing populations in biology. It's equivalent to asking whether the per capita rate of population growth is always non-increasing in a simple model of a growing (or shrinking) population.

  5. This question is obviously closely related but not the same, and my hypothesis doesn't seem to immediately follow from that result.

  6. The result will be true if the elements of $\exp(At)$ are log-convex, which would be a generally useful result to know about if it's true. It turns out not to be the case that all the elements of $\exp(At)$ are either consistently all convex upward or convex downward; they can change from one to the other as a function of $t$. See my related MathOverflow question. This makes me skeptical that the hypothesis in this (Math.SE) question is true.

Here is an example of what it tends to look like. For this example, $$ A = \begin{pmatrix}1,1\\4,1\end{pmatrix}, \qquad \mathbf{x} = \begin{pmatrix}1\\0\end{pmatrix}. $$

enter image description here

$\endgroup$
  • $\begingroup$ So my first reflex when you gave that context was to make up an example with a negative eigenvalue. This is easy to do, and if $x$ is such an eigenvector then $|e^{At} x|$ is decreasing...but then it is still log-convex (exponentials are both log-convex and log-concave), and at any rate such an $x$ must have negative entries. So I think the only way to get a counterexample will be with complex eigenvalues. This is impossible in 2D (check that $(a_{11}+a_{22})^2-4(a_{11}a_{22}-a_{12}a_{21}) = (a_{11}-a_{22})^2 + 4a_{12} a_{21} \geq (a_{11}-a_{22})^2 \geq 0$) but it is already possible in 3D. $\endgroup$ – Ian Feb 20 '17 at 3:02
  • $\begingroup$ Thanks for the helpful comment. The fact that a log of a sum of exponentials is convex is one motivation for the hypothesis, but I agree the possibility of complex eigenvalues makes it not immediately clear. $\endgroup$ – Nathaniel Feb 20 '17 at 3:04
  • 1
    $\begingroup$ When I've played around with randomly generated examples, whenever there were complex eigenvalues in 3D they had negative real part. That meant that the real or imaginary parts of these eigenvectors provided an "irrelevant counterexample", i.e. they failed to satisfy the conclusion but they also failed to have nonnegative entries. So I think you might be good... $\endgroup$ – Ian Feb 20 '17 at 6:43
  • 1
    $\begingroup$ With diagonal $2$-by-$2$ examples you can have $f''>0$ instead of $f''<0$. So is that a couterexample for you? E.g., take $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$, $x=(1,1)^T$. $\endgroup$ – Jonas Meyer Feb 28 '17 at 2:45
  • 1
    $\begingroup$ @JonasMeyer that's odd - thank you very much. That example makes sense now that I see it. I suppose now I have to change the question to ask whether the second derivative can change sign. $\endgroup$ – Nathaniel Feb 28 '17 at 3:23
1
$\begingroup$

Ok, so I can finally put this question to bed with a numerical example. Here is a plot of $\log Z$ against $t$ for some particular non-negative matrix $A$:

enter image description here

The second derivative clearly changes sign twice, once at around 0.3 and again just after 0.5.

It's probably not worth printing the whole matrix here since it's $100\times 100$ and there must be smaller, more instructive examples, but it was generated with the following rather arbitrary Python code:

n = 100
A = np.random.random((n,n)) # should be a Metzler matrix
A = np.exp(W*2)
A = W - np.eye(n)
A[np.random.random((n,n))>0.02] = 1e-3

(The point was to put the leading eigenvalue close to the cloud of other eigenvalues that random matrices tend to exhibit.)

$\endgroup$
0
$\begingroup$

Here is a random counter example:

A =

0.3384042   0.1355143   0.2244029   0.0094600   0.3658720
0.7335746   0.5823969   0.9182229   0.8483730   0.9743839
0.3992142   0.6501968   0.8946143   0.8120155   0.5938882
0.8255626   0.0570781   0.2135843   0.8498636   0.1053567
0.4915833   0.7814256   0.1870035   0.4286809   0.6484581

x =

0.384444
0.441505
0.623156
0.016760
0.791119

This produces this function like this: enter image description here

Looks pretty convex (although I am not sure if you are probably after concavity), but its not. Around zero there is slightly decreasing derivative…

$\endgroup$
  • $\begingroup$ It doesn't look remotely like that when I plot it. Are you sure you're calculating it correctly? $\endgroup$ – Nathaniel Feb 28 '17 at 1:48
  • $\begingroup$ (By the way, in my experience there is no consistent convention for the meaning of 'convex' vs 'concave', except that they're the opposite of each other. Perhaps it's a physics versus mathematics thing. For me, in this context, 'convex' means the second derivative is less than or equal to zero, as per the plot in the question. I'll edit to make that clear.) $\endgroup$ – Nathaniel Feb 28 '17 at 1:49
  • 1
    $\begingroup$ Oh, I just realized that by $|\cdot|$ you meant the sum of the elements (and not the sum of the absolute values) - quite unfortunate notation I think. Since $\exp(At)$ has some negative entries, this makes the difference. $\endgroup$ – Dirk Feb 28 '17 at 6:55
  • $\begingroup$ Also I have never seen any ambiguity about what is a convex or concave function, also in physics. $\endgroup$ – Dirk Feb 28 '17 at 7:01
  • $\begingroup$ I changed the notation in the question. In physics the entropy is referred to as a convex function, but it's concave according to your convention. Not sure there's much value in discussing that issue further. $\endgroup$ – Nathaniel Feb 28 '17 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.