17
$\begingroup$

Consider the matrix-valued function $A: \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ defined as

$$ A( x ) := \left[ \begin{matrix} x_1 & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & x_2 & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & x_n \end{matrix} \right] $$

where $a_{i,j} \geq 0$ for all $i,j$. Define the matrix-valued function $F: \mathbb{R}^{ n } \rightarrow \mathbb{R}^{ n \times n }$ as

$$ F( x ) := \text{exp}( A(x) )$$

where $\text{exp}(\cdot)$ denotes the matrix exponential, i.e., $$\exp(A) := \sum_{k=0}^{\infty} \frac{A^k}{k!} = I + A + A^2/2 + A^3/6 + \cdots$$

Notice that $F$ is element-wise nonnegative, because it is the exponential of a Metzler matrix.

Let $f_{i,j} : \mathbb{R}^{ n } \rightarrow \mathbb{R}$ be the $(i,j)$-component of $F$, $f_{ij}(x) = F(x)_{ij}$.

Prove that, for all $i,j$, the function $f_{i,j}$ is convex.

Comment: I am trying to show that the second derivative of $f_{i,j}$ is nonnegative. I am also trying to show that the second derivative of $\mathbb{R} \ni t \mapsto \exp( A( x + t y ) )$ is nonnegative for all $x,y \in \mathbb{R}^n$.

$\endgroup$
  • $\begingroup$ What motivates this question? Why would you think it true? Have you been able to make any progress yourself towards a solution? $\endgroup$ – Jonas Dahlbæk Sep 26 '14 at 13:08
  • $\begingroup$ Why was the previous answer removed? $\endgroup$ – user693 Sep 27 '14 at 17:37
  • 3
    $\begingroup$ Doesn't convexity just follows from midpoint-convexity (that is trivial since we are considering the exponential of a linear map) and continuity? $\endgroup$ – Jack D'Aurizio Sep 30 '14 at 10:09
  • 1
    $\begingroup$ Mumble, maybe we need to know something about the eigenvectors of $A$. If they are non-negative, convexity follows. Otherwise, it might be non-trivial, or even false. $\endgroup$ – Jack D'Aurizio Sep 30 '14 at 10:13
  • $\begingroup$ Thanks a lot for your comments. Do you have a proof of mid-point convexity? $\endgroup$ – user693 Sep 30 '14 at 10:28
1
$\begingroup$

It suffices to show the convexity in the domain $\Omega=\{x_i>0,\ i=1,\dots,n\}$. Once this is done, to check that the standard definition of convexity holds for a generic couple of points $x$, $y$ you can choose a large $M>0$ so that, calling $\vec{M}=(M,\dots,M)$, both $x'=x+\vec{M}\in\Omega$ and $y'=y+\vec{M}\in\Omega$;
then you have $F(z+\vec{M})=\exp\left(A(z+\vec{M})\right)=\exp(A(z)+MI)=e^M F(z)$ for any $z$ lying on the segment which joins $x$ and $y$ and what you want to check follows from the definition of convexity with $x',y'$.

So let's show that $f_{ij}$ is convex in $\Omega$: it suffices to show that if a matrix $A$ has nonnegative coefficients and $D$ is a diagonal matrix then $\exp(A+tD)+\exp(A-tD)-2\exp(A)=t^2P+O(t^3)$, where $P$ has nonnegative coefficients (because then we deduce $\nabla^2 f_{ij}(x)[h,h]=\lim_{t\to 0}\frac{f_{ij}(x+th)+f_{ij}(x-th)-2f_{ij}(x)}{t^2}\ge 0$ for any vector $h$, so $\nabla^2 f_{ij}$ is positive semidefinite and $f_{ij}$ is convex).
By the definition of the exponential, we can just show the stronger statement that for any $k\ge 0$ $(A+tD)^k+(A-tD)^k-2A^k=t^2P+O(t^3)$, where again $P$ is some matrix with nonnegative coefficients.

Now notice that $(A+tD)^k+(A-tD)^k-2A^k=2t^2\sum_{0\le r<s\le k-1} A^rDA^{s-r-1}DA^{k-s-1}+O(t^3)$ because the terms of first order cancel out, while the term of second order in the Taylor expansion of $(A\pm tD)^k$ is $t^2\sum_{0\le r<s\le k-1}\Pi_{rs}$, where $\Pi_{rs}$ is the product of $k$ factors which are all equal to $A$ except for the $r$-th and $s$-th ones which are equal to $D$ (by the $0$-th factor we mean the first one, and so on). So $P=2\sum_{0\le r<s\le k-1} A^rDA^{s-r-1}DA^{k-s-1}$.
Calling $i_0:=i$, $i_k:=j$, we then discover that the $(i,j)$-th component of $\sum_{0\le r<s\le k-2} A^rDA^{s-r-1}DA^{k-s-2}$ is $$\sum_{0\le r<s\le k}\sum_{i_1,\dots,i_{k-1}}a_{i_0i_1}\cdots a_{i_{r-1}i_r}d_{i_ri_{r+1}}a_{i_{r+1}i_{r+2}}\dots a_{i_{s-1}i_s}d_{i_si_{s+1}}a_{i_{s+1}i_{s+2}}\cdots a_{i_{k-1}i_k}$$ but $D$ is diagonal and has the effect of "freezing the indices" for one step, i.e. in the sum we can take $i_r=i_{r+1}$ and $i_s=i_{s+1}$. Thus, by shifting all the indices, the big sum becomes $$\sum_{0\le r\le s\le k-2}\sum_{j_1,\dots,j_{k-3}}a_{j_0j_1}\cdots a_{j_{r-1}j_r}d_{j_r}a_{j_rj_{r+1}}\dots a_{j_{s-1}j_s}d_{j_s}a_{j_sj_{s+1}}\cdots a_{i_{k-3}i_{k-2}}$$ where we have put $d_j:=d_{jj}$ and the extremal indices are $j_0:=i$, $j_{k-2}:=j$.
Now we exchange the two sums and we are left to show that $$\sum_{0\le r\le s\le k-2}d_{j_r}d_{j_s}a_{j_0j_1}\cdots a_{j_{r-1}j_r}a_{j_rj_{r+1}}\dots a_{j_{s-1}j_s}a_{j_sj_{s+1}}\cdots a_{i_{k-3}i_{k-2}}\ge 0$$ for any fixed choice of indices $j_0,\dots,j_{k-2}$. The product of the coefficients of $A$ is nonnegative and independent of $(r,s)$, so we just have to show that $$\sum_{0\le r\le s\le k-2}d_{j_r}d_{j_s}\ge 0$$ which is clear as $2\sum_{0\le r\le s\le k-2}d_{j_r}d_{j_s}=2\sum_{0\le r\le k-2}d_{j_r}^2+2\sum_{0\le r<s\le k-2}d_{j_r}d_{j_s}=\sum_{0\le r\le k-2}d_{j_r}^2+\left(\sum_{0\le r\le k-2}d_{j_r}\right)^2\ge 0.$

$\endgroup$
  • $\begingroup$ @ Mizar , your second part does not work. Indeed, the Hessian $P"(x)=[p_{i,j}]$ is a symmetric matrix s.t., for every $i,j$, $p_{i,j}\geq 0$. Yet, that does not imply that $P"(x)$ is positive definite or even non-negative. $\endgroup$ – loup blanc Dec 9 '14 at 0:13
  • $\begingroup$ Of course you are right. I try to see if this can be fixed, otherwise I will delete the answer. $\endgroup$ – Mizar Dec 9 '14 at 7:35
  • $\begingroup$ Just replaced the bad argument with a more serious attempt. Let me know if it makes sense $\endgroup$ – Mizar Dec 20 '14 at 17:06
  • $\begingroup$ @ Mizar , the middle of your post is unclear (for me). I agree with the first part: it suffices (cf. also my last remark) to prove that $P=\sum_{r+s+t\leq k-2}A^rDA^sDA^t$ is $\geq 0$. In the second part you take $s\leq k-2$ (?) and, in line -4, you say that the product does not depend on $(r,s)$ ; yet, I see in line -6, some indices of the $(a_{i,j})$ that are equal to $j_r$ or $j_s$. In fact I think that the difficulty is in the factors of your $d_{j_r}d_{j_s}$. A last remark: for a complete proof, you "must" prove that $P>0$. $\endgroup$ – loup blanc Dec 20 '14 at 19:58
  • $\begingroup$ Well, the meaning of $r$ and $s$ changes at some time. At the beginning $r$ and $s$ are the positions of the two factors $D$, so we always have $r<s$; after the shift of the indices, i.e. when we use the $j_m$'s, $s$ decreases by $1$ (so the new $s$ satisfies $s\le k-2$). If you look carefully, in line -6 I wrote the indices $j_r$ and $j_s$ just to be a little more clear about what happens after the shift. That product could be written without mentioning $r$ and $s$. $\endgroup$ – Mizar Dec 20 '14 at 20:18
1
$\begingroup$

you will find the proof in

"Convexity of the cost functional in an optimal control problem for a class of positive switched systems" Patrizio Colaneri, Richard H. Middleton , Zhiyong Chen , Danilo Caporale , Franco Blanchini, Automatica 2014

$\endgroup$
  • $\begingroup$ Please give us a synopsis of the proof. This is not a reference-request question. $\endgroup$ – Marconius Oct 21 '15 at 0:37
  • $\begingroup$ So the proof goes along the lines: By Trotter formula $$ f_{i,j}(x) = e_i^\top\lim_{k\to\infty}\left(e^{\frac{A}{k}}e^{\frac{\text{diag}(x)}{k}}\right)^k e_j $$ $\endgroup$ – mcolombi Oct 21 '15 at 13:59

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.