User jules - MathOverflow

The Isoperimetric problem for domains constrained to lie between two parallel planes

2013-05-12T01:17:51Z

It is well known that for a given volume $V$, a sphere is the shape that minimizes the surface area. I am interested in the same problem under the constraint that the shape must lie between the planes $x=-a$ and $x=a$, i.e. all its points $(x,y,z)$ must have $-a \leq x \leq a$. Obviously, if $V\leq\frac{4}{3}\pi(2a)^3$ then the shape is still a sphere since the sphere with the right volume fits entirely between the planes. However if the volume becomes larger, the sphere can not fit between the planes and it will have to be flattened. My question is: what is this shape? This question is about the 3 dimensional case.

From here I'll describe what I have found out so far.

Since the problem is completely symmetric in the $y,z$ directions, the solution can be represented as the rotation of the graph of a function $r(x)$ around the $x$ axis. Then the volume of this function rotated around the $x$ axis will be:

$$V=\int_{-a}^a\pi r(x)^2 dx$$

and the area will be:

$$A = \pi r(-a)^2 + \pi r(a)^2 + \int_{-a}^a2\pi r(x)\sqrt{1+r'(x)^2}dx$$

(the first two terms are for the disk shaped sides pressed against the plane, and the last term is for the surface of revolution between the planes)

Numerical minimization by discretizing $r$ into a piecewise linear function has produced these results:

The final 3D shapes are these 2D shapes rotated around the horizontal axis. From left to right the distance $a$ is decreasing, thus constraining the shapes more and more. The solution appears to be of the form $r(x) = \sqrt{a^2-x^2}+b$, but on closer inspection it seems that this is not the case. The top and bottom are not exact half circles. For the almost spherical case, and for the very elongated case (with $a$ small), they are very close to half circles, but in the intermediate case there is quite a bit of difference.

By the method of calculus of variations I have derived a differential equation that $r$ should satisfy:

$$\sqrt{1+r'^2} + \lambda r = \frac{d}{dx} \frac{rr'}{\sqrt{1+r'^2}}$$

Where $\lambda$ is some real number dependent on the parameters of the problem ($V$ and $a$). And indeed, the function $r(x) = \sqrt{a^2-x^2}$ satisfies this equation as expected (indicating that with no constraint the minimal surface is a sphere), but $r(x) = \sqrt{a^2-x^2}+b$ unfortunately does not for $b\neq0$.

It would of course be awesome to have a complete solution, but I would also be very happy with asymptotic special cases, particularly the case where the sphere is only a little compressed (so the case where $V$ is only a little greater than $\frac{4}{3}\pi(2a)^3$, i.e. the green shape in the picture).

Thanks for your help!

Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently

2011-08-17T03:18:59Z

What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?

Do we have to calculate $A^{-1}b$, or is this not necessary?

edit: I forgot to mention that A is symmetric and positive definite and sparse (so usually you'd use the conjugate gradient method).

What I have is a convex quadratic $x^TAx + b^Tx$. The minimum of this is at $2Ax+b=0$, and if you plug this minimum into the original form, then you get $x^T(-b/2)+b^Tx=b^Tx/2$ and this leads you to have to compute $-1/4\cdot b^TA^{-1}b$. So another way to pose the question is: can you find the height at the minimum faster than the location of the minimum?

Injections to binary sequences that preserve order

2011-03-19T11:54:20Z

Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary sequences is the dictionary ordering (e.g. 001001 <= 01).

For a finite set this is easy: arrange the set in order and assign an increasing sequence of binary sequences.

For the natural numbers this is also easy: send a number n to the sequence that starts with n ones (a similar solution works for negative numbers).

For the rationals this is already a bit more difficult. I believe the following works: Take the Stern-Brocot tree. Start at the root and walk down to the rational number. Every time you go left, write a 0. Every time you go right, write a 1. Finally write another 1.

So an equivalent formulation seems to be: can we arrange S into a binary tree such that the elements are arranged in order from left to right as in the Stern-Brocot tree.

My question is: can this be done for any countable set with a total order? The question came up in a discussion whether radix sort can be used to sort any set (radix sort can sort binary sequences).

The Frechet derivative and Lagrange multipliers on Banach spaces

2011-01-26T16:40:43Z

I am interested in questions of the following form: minimize $H(f)$ given $G(f) = 0$ where $H$ and $G$ are operators of type $X \to R$ where $X = R \to R$. An example is:

Minimize $$H(f) = \int_{-1}^1\sqrt{1+f'(x)^2}$$

Under the conditions that:

$$G(f) = \int_{-1}^1f(x) = \pi/2 $$ $$f(-1) = f(1) = 0$$

That is, find a function f on [-1,1] with area under the curve equal to $\pi/2$, minimizing the path length (the answer to this example is a half-circle $f(x) = \sqrt{1-x^2}$, I believe).

Other examples of operators that can occur in the minimize or in the condition are:

$$A(f) = f(1)$$

$$B(f) = \int_a^b E(x,f(x),f'(x))dx $$

(i.e. an integral of an expression containing $x$, $f(x)$ and $f'(x)$).

The way to solve these kind of problems seem to be Lagrange multipliers on Banach spaces. How does one do this?

Is this problem solvable in polynomial time?

2010-06-07T01:13:08Z

Let's start with a picture: http://i.imgur.com/P1k8T.png What you see here are boxes and circles inside the boxes. Each circle is connected to zero or more boxes. One box is the primary box, it's the grey one. Here is another example (the top box is the primary box): http://i.imgur.com/ibOIO.png (I apologize for the crappy drawings).

The goal is to select a subset of all circles such that:

If a circle is selected, then all the boxes it is connected to must be selected.
If a box is selected then one of the circles in it must be selected.
The primary box is selected.
The sum of the numbers in the selected circles is minimal.

In the top picture the optimal selection of circles has been colored blue. In the bottom picture there are two optimal solutions: select the 3 in the top box and the 1 in the right box. Other solution: select the 2 in the top box, the 1 in the left box and the 1 in the right box.

My question is: is this solvable in polynomial time, or if not is it possible to approximate it? If the graph is tree structured then dynamic programming can solve the problem, but diamond structures seem to complicate the problem.

I have asked this problem on stackoverflow.com, but that doesn't seem to get very far and I thought maybe this is a more appropriate place?

Comment by Jules

2011-08-17T10:21:37Z

Thanks! So computing the whole inverse is essentially not harder than computing just one entry of it. On the other hand this only lets you compute diagonal entries of a matrix with special structure, so perhaps there is a better method.

Comment by Jules

2011-08-17T03:30:20Z

Thanks for your answer. I added extra information namely that A is symmetric and positive definite. What is the reason that this cannot be done more efficiently than first forming $A^{-1}b$?

Comment by Jules

2011-03-19T13:34:32Z

Indeed! Thanks.

Comment by Jules

2011-03-19T12:39:26Z

In general given two binary sequences a < b, there are infinitely many binary sequences below, between and above a and b (unless a=0).

Comment by Jules

2011-03-19T12:37:39Z

Just send $\infty$ to 1 and a number n to 0 and then n ones.

Comment by Jules

2011-01-26T19:32:24Z

Thanks! The Calculus of Variations is exactly what I'm looking for. Do you recommend a particular document to learn about it? I found maths.ed.ac.uk/~jmf/Teaching/Lectures/CoV.pdf. Can you post your answer as an answer so that I can accept it?

Comment by Jules

2011-01-26T17:59:09Z

Can you give a little more information about the physical background of the problem? How can you mix even one $\int p(x)f(x)$? You seem to be mixing uncountably many things there?

Comment by Jules

2011-01-26T17:39:37Z

Perhaps Frechet derivatives on Banach spaces can help here. What you'd want to say is d{the L1 norm}/dp = 0, except that p is a function not a number. Frechet derivatives generalize taking derivatives to taking derivatives by functions. That is, if you have an operator H : (R -> R) -> R, you can find H'. The solution in this case would be the solution to H'(p) = 0. I believe that H'(p) = 0 will reduce to a differential equation for p.

Comment by Jules

2011-01-26T17:10:05Z

Willie Wong, I rewrote the question using LaTeX.

Comment by Jules

2011-01-26T16:49:21Z

Hmm yes you are right...how about the problem with the additional constraint f(0) = f(1) = 0?

Comment by Jules

2010-06-10T16:38:47Z

If you don't have a bound on t_i then the problem is trivial. You can get arbitrarily close by just making t_i huge and s small.

Comment by Jules

2010-06-10T15:34:04Z

Perhaps you can search for s around maxCi/M, it seems that the total error can be reduced by roughly a factor of 3 versus just picking s=maxCi/M.

Comment by Jules

2010-06-10T12:49:09Z

Correction: choose s round $max C_i/M$.

Comment by Jules

2010-06-10T12:48:03Z

For a given s the problem is easy. We want to minimize $|t_i*s - C_i|$, so suppose we could solve it exactly: $t_i = C_i/s$. Now we have to try only 2 candidates per $t_i$: $min(M,floor(C_i/s))$ and $min(M,ceil(C_i/s))$. So for a given s we can solve the problem quickly. I did this for a sample input and plotted s versus the resulting error $\sum |t_i*s-C_i|$. The result i.imgur.com/zcKOW.png The error is very high if you choose s much to small or much too large. Choosing s around $max {t_i}/M$ seems to get good results, perhaps good enough for your purposes.

Comment by Jules

2010-06-07T17:01:16Z

That settles this question. Thanks!