User david s-d - MathOverflow

Singularity structure of integrals of rational functions

2011-02-25T03:45:48Z

Suppose I have a convergent integral of the form $\int_0^1dx_1\dots\int_0^1 dx_n \frac{P(x_i)}{Q(x_i)}$, where $P$ and $Q$ are polynomial functions of $n$ nonnegative real variables $x_i$. Let the coefficients of the various monomials in $Q$ be $a_k$. Depending on the structure of $Q$, the integral could develop singularities in the limit that some of the coefficients $a_k$ vanish. For example, the integral $\int_0^1 dx\frac 1 {a+x}$ goes like $-\log a$ as $a\to 0$. Is there a systematic way to extract the structure of these singularities for general multidimensional integrals?

The particular example I'm interested in is the following: I'd like to determine the singularities of

$\begin{eqnarray} \int_0^1 d\lambda_1\int_0^1 d\lambda_2 \int_0^1d\alpha_1 \int_0^1d\alpha_2 \frac{\alpha_1\alpha_2}{(\lambda_2\alpha_1\alpha_2+\lambda_1\alpha_1\alpha_2+a\alpha_2\lambda_1^2+b\alpha_1\lambda_2^2+c\alpha_1\alpha_2)^2}, \end{eqnarray}$

as $a,b,$ and $c$ tend to zero. If necessary, it's alright to assume they all tend to zero at the same rate. I naively expect a leading singularity that looks like $\log a \log b \log c$, followed by sub-leading singularities that look like $\log a \log b$ times some convergent integral, $\log b \log c$ times some other convergent integral, etc.. For my purposes, these $\log$-squared terms suffice, but I'd be interested to know how to systematically go further.

Continuous Linear Programming: Estimating a Solution

2010-07-24T23:54:10Z

I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the convex space is piecewise curved -- that is, it has faces, edges, and vertices, but the edges aren't straight and the faces aren't flat. Instead of being specified by a finite number of linear inequalities, I have a continuously infinite number. I'm interested in estimating solutions numerically, and my current method is to approximate the surface by a polytope, which means discretizing the continuously infinite number of constraints into a very large finite number of constraints. Unfortunately, typical linear programming algorithms run in something like cubic-time in the number of constraints, so I'm getting a huge performance hit as I make the discretization finer. Firstly, I'm interested to know if this kind of problem has been studied before, and what's been done. Secondly, I'm looking for good strategies for approaching my problem numerically (good LP packages, suggested algorithms, optimizations, etc.).

For concreteness, here is a simplified version of the problem I'm trying to solve:

I have $N$ fixed functions $f_i:[0,\infty]\to \mathbb{R}$. I want to find $x_i$ $(i=1,\dots,N)$ that minimize $\sum_{i=1}^N x_i f_i(0)$, subject to the constraints:

$\sum_{i=1}^N x_i f_i(1) = 1$, and

$\sum_{i=1}^N x_i f_i(y) \geq 0$ for all $y>2$

More succinctly, if we define the function $F(y)=\sum_{i=1}^N x_i f_i(y)$, then I want to minimize $F(0)$ subject to the condition that $F(1)=1$, and $F(y)$ is positive on the entire interval $[2,\infty)$. Note that this latter positivity condition is really an infinite number of linear constraints on the $x_i$'s, one for each $y$. A specific $y_0$ restricts me to the half-space $F(y_0) \geq 0$ in the space of $x_i$'s. As I vary $y_0$ between 2 and infinity, these half-spaces change continuously, carving out a curved convex shape. The geometry of this shape depends implicitly (and in a complicated way) on the functions $f_i$.

The reason I suspect there should be an approach that's better than just discretizing the number of constraints is that continuity of the $f_i$'s implies a kind of local structure on the space of constraints that becomes invisible under discretization. If we sit on the boundary of our convex space (so that at least N constraints are saturated, corresponding to some $y_k$), and we want to move along the boundary, then generically only those constraints corresponding to small neighborhoods of the $y_k$ are important. Sometimes when the function $F(y)$ develops a new zero, new $y$ can become important, but this is nongeneric.

NOTE: I asked this question first on stackoverflow.net, and was told it was a nonstandard enough CS problem that I should ask about it here.

Comment by David S-D

2010-07-27T02:38:32Z

Thanks, Noah. Your answer is extremely clear, and I really appreciate the obvious time and care you took in answering. The functions I'm working with are ratios of hypergeometric functions which can be approximated as polynomials plus polynomials times dying exponentials. I'll have to think about whether I can usefully approximate them in a way that allows a "positive semidefinite"-ness interpretation of their positivity.

Comment by David S-D

2010-07-25T13:26:15Z

Thanks, this sounds very promising. I'll look at the references you mentioned.

Comment by David S-D

2010-07-25T13:23:10Z

The f_i are not polynomials, but become polynomials asymptotically as y -> infinity. Thus, it's easy to check positivity at infinity by just examining leading coefficients in the asymptotic polynomials. In practice, I've found that checking positivity on some large interval, say [2, 50), along with asymptotic positivity, tends to be enough in my case. So for simplicity, feel free to replace the constraints above with those. What do you mean by "semidefinite program"?