User gb - MathOverflow

When does the finite union of convex sets have a hole in it?

2013-04-27T00:26:56Z

Let $f_1, \dots, f_j$ be convex functions from $\mathbb{R}^n \to \mathbb{R}$. I am trying to develop a test that decides whether or not the set $\{x | f_1(x) \le k_1\} \cup \dots \cup \{x | f_n(x) \le k_n\}$ has a hole in it of any size (the alternative is that the set is homeomorphic to the unit ball, maybe plus a few lower-dimensional "fingers").

Is anything known about this problem?

Editing in some extra information that is specific to my particular use for this algorithm. In my algorithm, $n$ of the convex sets that I'm unioning together are the coordinate planes (i.e. $\{x | x_j = 0\}$), and there are exactly $n$ additional convex sets that I care about (so $j = 2n$).

What is the complexity of finding the number (mod 2) of multicolored edges on a loop?

2013-04-11T00:47:36Z

Let $C$ be a circuit that maps $n$-length bitstrings to elements of $\{0, 1, 2\}$. Arrange the $n$-length bitstrings in a giant loop: $0^n$ is connected to $1^n$ and $0^{n-1}1$, $0^{n-1}1$ is connected to $0^n$ and $0^{n-2}10$, etc. An edge of this loop is multicolored if it connects $x$ and $y$ but $C(x) \ne C(y)$.

I want to decide whether there are an even or odd number of multicolored edges on the loop. What is the computational complexity of this problem?

Geometric interpretations of matrix inverses

2013-02-05T17:41:16Z

$A$ is an invertible $n \times n$ matrix. Interpret each row of $A$ as a point in $\mathbb{R}^n$; then these $n$ points define a unique hyperplane in $\mathbb{R}^n$ that passes through each point (this hyperplane does not intersect the origin).

Under this geometric interpretation, $A^{-1}$ has an interesting property: the normal vector to the hyperplane is given by the row sums of $A^{-1}$ (i.e. $A^{-1} * 1$, where $1 = \langle 1, \dots, 1 \rangle^T$).

Within this same geometric interpretation of $A$, what other interesting properties does $A^{-1}$ have? Do the individual entries of $A^{-1}$ have geometric meaning? How about the column sums (besides the obvious row sums of $A^T$ intepretation)?

Is there a general process for conditioning a stochastic process above a boundary?

2013-01-08T07:59:17Z

$(X_t, Y_t)$ is a two-dimensional Markov stochastic process that runs on time interval $[0, t_f]$. Given its transition function $a(x, y | x', y')$, I would like to condition the process on $\inf_{s \in [0, t_f]} X_s \ge k$ and find the new transition function.

Can the problem be solved at this level of generality? Or must we dig into the specifics of $a$ to find a solution on a case-by-case basis?

Does this result exist in the literature?

2013-01-22T23:18:17Z

Cover a table with a tablecloth, crumple it up in the middle (while still leaving the edges hanging over the edge of the table), then stab the folds with a pin. You will almost surely poke an odd number of holes in the tablecloth, because one end of the pin is above the tablecloth, the other is below, and each hole indicates one instance of the pin changing sides (the only exception is if your stab lies perfectly tangent to a fold of the tablecloth).

I suspect that this generalizes. I hope that something like this is true:

Let $X$ be a subset of $\mathbb{R}^n \times \mathbb{R}^m$ that is homeomorphic to $\mathbb{R}^n$. For any $r \in \mathbb{R}^n$, let $D(r) = \{ s \in \mathbb{R}^m | (r, s) \in X \}$. Suppose $D(r)$ is never empty for any $r \in \mathbb{R}^n$. Then $D(r)$ almost always (with respect to Lebesgue measure) has an odd number of elements.

In other words, we have crumpled an $n$-dimensional tablecloth into $m$ additional dimensions (while still leaving it hanging over the edges of our $n$-dimensional table), then stabbed it with an $m$-dimensional pin, hopefully in an odd number of places.

Is this a known result? It smells a lot like Sperner's Lemma (which contains a similar statement about oddness), but I'm not entirely sure how.

Can we express a one-dimensional raised Bessel Bridge as a function of a single Brownian Motion?

2012-12-20T19:15:53Z

A Bessel Bridge is a Brownian Motion, conditioned such that $B(0) = B(1) = 0$ and $B([0, 1]) \ge 0$. A raised Bessel Bridge is a generalization of this: it's a Brownian Motion conditioned such that $C(0) = a, C(1) = b, C([0, 1]) \ge 0$ for some nonnegative constants $a, b$.

My end goal is to find a density function for the integral of a random realization of a raised Bessel Bridge. I plan to approach this problem as follows: the Feynman-Kac formula gives an expression for $E(e^{-u \int_0^1 V(x(t)) dt})$, where $x(t)$ is a Brownian Motion, $u$ is a constant, and $V$ is any function. If I choose $V$ such that $V(x(t))$ is a raised Bessel Bridge, then this information is sufficient to compute the desired density function (simply take a Fourier Transform).

So, my question: what function $V$ makes the process $V(x(t))$ a raised Bessel Bridge, where $x(t)$ is a Brownian Motion?

Can we efficiently compute a third Nash Equilibrium, given two?

2012-11-15T03:35:26Z

A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's payoff is $A_{ij}$ and player 2's payoff is $A_{ji}$. It is well known that the problem of computing a symmetric Nash Equillibrium in such a game is PPAD-complete (PPAD lies between P and NP but is probably intractable).

Wilson's Oddness Theorem states that there are an odd number of symmetric Nash Equilibria in such games. This gives rise to my question. Suppose we have found two equilibria of $A$. Given these, what is the computational complexity of computing one more?

Or, more generally - given $2k$ equilibria, what is the complexity of computing another?

Computing a density function for the integral of a stochastic process, given its transition function

2012-11-11T18:34:48Z

$P$ is a one-dimensional Markov stochastic process that runs on time interval $[0, t_f]$. I know its transition function: $P(0) = x_0$ and for any $0 \le t_a < t_b \le t_f$, the function $f(x_b | x_a, t_a, t_b)$ describes the probability that $P(t_b) = x_b$ given that $P(t_a) = x_a$ (so $f$ is a density function in its first parameter).

Now, let $I$ be the random variable described by $\int_0^{t_f} P(s) ds$ for a random realization of $P$. Is it possible to find a density function for $I$ in terms of $f$ and $x_0$?

Integrating a Bessel Bridge

2012-11-10T18:40:37Z

Preliminaries

An order-3 Bessel Process is the one-dimensional stochastic process $X$ described by $X(t) = \sqrt{W_1(t)^2 + W_2(t)^2 + W_3(t)^2}$, where each $W_k$ is an independent Brownian Motion. It is known that this process is equivalent to a Brownian Motion conditioned to always be positive.

A Bessel Bridge is a Bessel Process on time interval $[0, 1]$, conditioned to have start point $(0, x_0)$ and end point $(1, x_f)$.

My Question

I am trying to find a density function for the random variable $\int_0^1 \beta_3(t) dt$, where $\beta_3(t)$ is a random realization of an order-3 Bessel Bridge.

A Possibly Useful Fact

When $x_0 = x_f = 0$, the Bessel Bridge is called a Brownian Excursion Process, and the density function for its integral is known.

Thanks!

When is a sublevel set path-connected?

2012-10-09T22:14:57Z

I am trying to completely characterize the conditions on $f : \mathbb{R}^n \to \mathbb{R}$ under which $\{x | f(x) \le 0 \}$ is path-connected. There are many obvious conditions that are sufficient (e.g. $f$ concave), but is there any suite of conditions that is necessary and sufficient?

We can assume $f$ is continuous.

If you have any ideas or recommended reading, I'd love to hear about it. Thanks!

When is $\{ x \ge 0 | f(x) \le 0\}$ path-connected?

2012-10-08T18:57:10Z

I'm trying to determine the conditions on $f : \mathbb{R}^n_{\ge 0} \to \mathbb{R^n}$ under which $\{ x \ge 0 | f(x) \le 0 \}$ is path-connected. We can assume that $f$ is continuous and concave.

Any advice?

Does Quadratic Programming get easier when it's described by a diagonal matrix?

2012-09-24T17:20:33Z

Generally, Quadratic Programming solves the problem

$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$

In this form, Quadratic Programming is NP-hard. For my purposes, I happen to know that $b$ and $c$ are $0$ and $Q$ is diagonal. Thus, the problem looks like:

$$\text{Given }q, A, \text{ choose } x \text{ to maximize } q \cdot \langle x_1^2, \dots, x_n^2 \rangle \text{ subject to } Ax \le 0$$

Does the problem now admit an efficient solution?

The problem is not entirely theoretical, so I am somewhat interested in approximation methods if no exact solution can be found efficiently.

Edit: we can introduce the additional constraint $\sum_j x_j \le 1$ to prevent unbounded growth of optimization from scaling our solutions. This works because the condition $x \ge 0$ is already built into $A$.

Is the Simplex Method still polynomial when all inequalities are through the origin?

2012-04-24T20:47:16Z

Hello,

I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, or the program is unbounded; I'm only really interested in distinguishing between these two cases).

So here's how I think the algorithm would work: Step one is to pick a pivot variable. Step two - and here's where I think things break down - is to find the equation with the smallest value of the constant to the coefficient of the pivot variable. But since my inequalities all pass through the origin, the constant is 0 every time, so all equations are an equally valid choice for the pivot. This reduces the Simplex Method to a brute-force search of the set of basic variables, which would make it run in above-polynomial time.

Is this correct? Or am I missing some feature of the Simplex Method that handles this case?

Thanks in advance!

How do you tell if a system of linear inequalities has a solution?

2012-03-31T21:41:32Z

A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.

Finding the "top" or "bottom" vertex of a simplex

2012-03-03T02:57:21Z

A vertex $v$ of a simplex in $\mathbb{R}^n$ is a "top" vertex if there exists a point $p \neq v$ in the simplex with $v \ge p$ (i.e. $v_1 \ge p_1$, ... , $v_n \ge p_n$). Similarly, $v$ is a "bottom" vertex if there exists $p \neq v$ with $v \le p$.

It's not hard to show that any simplex has at least one top or bottom vertex. I'm looking for a test I can run (preferably in polynomial time) that identifies at least one such vertex, and whether it's top or bottom.

Thanks in advance for any advice!

How do you tell if the span of a set of vectors enters the most positive sector of a graph?

2012-02-29T22:08:35Z

I have $k$ linearly independent vectors in $\mathbb{R}^n$. I want to know if the span of these vectors (i.e. the set of points in $\mathbb{R}^n$ that can be described by linear combinations of these vectors) intersects the portion of $\mathbb{R}^n$ where all the axes are positive (e.g. the first quadrant in $\mathbb{R}^2$, the first octant in $\mathbb{R}^3$, etc.).

Is there a test I can run on my vectors that will answer this question?

Comment by GB

2013-04-27T02:49:52Z

Man, that is a cool answer you linked to. I do have a way to test intersections, so that will do perfectly.

Comment by GB

2013-04-27T01:09:32Z

1. Yes, it's the union, not the intersection of the sets (the intersection would be convex =) ). 2. Yes, I am attempting a floating-point algorithm. Rather than place restrictions on the sets, I'm hoping to use standard convex optimization techniques as a subroutine (the $\epsilon$-fudginess in these techniques is okay; I'd be fine with an algorithm that reports "the functions come within $\epsilon$ of being hole-less").

Comment by GB

2012-11-15T04:00:05Z

You can easily get down to $O(n \log n)$ by first sorting the array, then checking the subarray [0..0], then [0..1], then [0..2], etc.

Comment by GB

2012-11-11T19:10:10Z

Ah, yes it is, thank you. I just edited that detail into the post.

Comment by GB

2012-11-11T18:23:37Z

Computationally speaking, it is PPAD-complete to find a three-colored simplex per Sperner's Lemma. en.wikipedia.org/wiki/PPAD_(complexity)

Comment by GB

2012-10-08T19:21:15Z

Yes, the co-domain of $f$ is meant to be $\mathbb{R}^n$. By concave, I mean that it is concave on each index: for any $\lambda \in [0, 1]$, $f(\lambda x + (1 - \lambda)y) \ge \lambda f(x) + (1 - \lambda) f(y)$ (the inequality is pointwise). I think the sublevel set is only necessarily path-connected if the domain of $f$ is $\mathbb{R}^n$, not $\mathbb{R}^n_{\ge 0}$.

Comment by GB

2012-05-17T20:50:44Z

$t_f$ is finite, but I think $Z$ is still an infinitely large set. It's not hard to show that, on any neighborhood $N$ of some fixed $t$, $inf B(N) < B(t) < sup B(N)$ with probability 1, which implies that the path returns to $B(t)$ on any $N$ with probability 1. Apologies for misplacing this question, I guess I'm still figuring this place out. It did arise during research, but I'll admit it was a tangent rather than the actual research topic.

Comment by GB

2012-04-26T18:56:44Z

Hey, thanks for your response. I'm new to MO - for future reference, what about this is not an MO question? What sort of things should I be asking?

Comment by GB

2012-04-24T21:45:18Z

I looked into it more - you're completely right, and now I'm trying to remember why I was so sure Simplex was strongly polynomial in the first place. I may have found one of the cases on which it's exponential. I found a source that says there are no known strongly-polynomial linear programming algorithms, and the existence of such an algorithm is a major open question. Thanks for your help!

Comment by GB

2012-03-03T20:17:03Z

This is very helpful - thank you.