TransWikia.com

When is the log-permanent concave?

MathOverflow Asked by Bill Bradley on January 9, 2021

Let $operatorname{PSD}_n$ be the cone of $ntimes n$ semidefinite positive matrices. For any $Xin operatorname{PSD}_n$, define $$f(X)=log(det(X)).$$ Then $f$ is a concave function on $operatorname{PSD}_n$. This fact has some significance in convex optimization.

Is there an analogous result for the permanent? In particular, if we define
$$g(X)=log(operatorname{Perm}(X)),$$ can we identify some non-trivial set $M$ of matrices over which $g$ is concave (or convex for that matter)?

(I’m hoping for some set larger than "diagonal matrices".)


EDIT: In the comments below, Mark L. Stone included a reference to a very interesting theorem; here’s the relevant part.

Let $H_n$ be the set of $ntimes n$ Hermitian matrices. For $X,Yin H_n$, we say that $Xpreccurlyeq Y$ iff $Y-X$ is semidefinite positive. Let $S_n$ be the group of permutations on $n$ objects, and $G$ a subgroup of $S_n$.

We define a function $d:H_n rightarrow R$ for an irreducible character $chi$ of $G$ by:
$$d(X)=sum_{sigmain G} chi(sigma) prod_{i=1}^{n} X_{sigma(i),i}$$

(Note that the determinant and the permanent are instances of this function, as are, I think, the immanants.)

Theorem: If $X,Yin H_n$, $0 preccurlyeq Y preccurlyeq X$ and $0leq lambda leq 1$, then $d$ is convex, i.e.,
$$ d(lambda X + (1-lambda)Y) leq lambda d(X) + (1-lambda)d(Y) $$

In particular, that holds for the permanent. However, this result doesn’t quite answer my original question, in that there is no fixed set $M$ that works— it requires a relationship between $X$ and $Y$. (Is there some way to lift this result with a matrix exponential to get $M=operatorname{PSD}_n$?)

One Answer

Just a suggestion, not a complete answer.

Consider the set of matrices with positive elements. The permanent (or whenever the "character" of the immanent) is a posynomial (polynomial with positive coefficients). Making a change of variables for each element as $x=e^y$ and taking log of the permanent, one gets it in the form of a log-sum-exp function. This function is convex in $y$.

Hope this helps.

Answered by DSM on January 9, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP