User jules - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:57:54Z http://mathoverflow.net/feeds/user/6210 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130385/the-isoperimetric-problem-for-domains-constrained-to-lie-between-two-parallel-pla The Isoperimetric problem for domains constrained to lie between two parallel planes Jules 2013-05-12T01:17:51Z 2013-05-13T19:32:55Z <p>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. <strong>My question is: what is this shape?</strong> This question is about the 3 dimensional case.</p> <p>From here I'll describe what I have found out so far.</p> <p>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:</p> <p>$$V=\int_{-a}^a\pi r(x)^2 dx$$</p> <p>and the area will be:</p> <p>$$A = \pi r(-a)^2 + \pi r(a)^2 + \int_{-a}^a2\pi r(x)\sqrt{1+r'(x)^2}dx$$</p> <p>(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)</p> <p>Numerical minimization by discretizing $r$ into a piecewise linear function has produced these results: <img src="https://dl.dropboxusercontent.com/u/388822/shapes.png" alt="alt text"></p> <p>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, <em>and</em> 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.</p> <p>By the method of calculus of variations I have derived a differential equation that $r$ should satisfy:</p> <p>$$\sqrt{1+r'^2} + \lambda r = \frac{d}{dx} \frac{rr'}{\sqrt{1+r'^2}}$$</p> <p>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$.</p> <p>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).</p> <p>Thanks for your help!</p> http://mathoverflow.net/questions/73028/numerical-linear-algebra-how-to-compute-bta-1b-efficiently Numerical linear algebra: how to compute $b^TA^{-1}b$ efficiently Jules 2011-08-17T03:18:59Z 2011-08-27T14:19:03Z <p>What is the most efficient way to compute $b^TA^{-1}b$ for a given $A$ and $b$?</p> <p>Do we have to calculate $A^{-1}b$, or is this not necessary?</p> <p>edit: I forgot to mention that A is symmetric and positive definite and sparse (so usually you'd use the conjugate gradient method).</p> <p>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?</p> http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order Injections to binary sequences that preserve order Jules 2011-03-19T11:54:20Z 2011-03-19T13:30:39Z <p>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 &lt;= 01).</p> <p>For a finite set this is easy: arrange the set in order and assign an increasing sequence of binary sequences.</p> <p>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).</p> <p>For the rationals this is already a bit more difficult. I believe the following works: Take the <a href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree" rel="nofollow">Stern-Brocot tree</a>. 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.</p> <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/53373/the-frechet-derivative-and-lagrange-multipliers-on-banach-spaces The Frechet derivative and Lagrange multipliers on Banach spaces Jules 2011-01-26T16:40:43Z 2011-01-26T20:18:45Z <p>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:</p> <p>Minimize $$H(f) = \int_{-1}^1\sqrt{1+f'(x)^2}$$</p> <p>Under the conditions that:</p> <p>$$G(f) = \int_{-1}^1f(x) = \pi/2$$ $$f(-1) = f(1) = 0$$</p> <p>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).</p> <p>Other examples of operators that can occur in the minimize or in the condition are:</p> <p>$$A(f) = f(1)$$</p> <p>$$B(f) = \int_a^b E(x,f(x),f'(x))dx$$</p> <p>(i.e. an integral of an expression containing $x$, $f(x)$ and $f'(x)$).</p> <p>The way to solve these kind of problems seem to be Lagrange multipliers on Banach spaces. How does one do this?</p> http://mathoverflow.net/questions/27297/is-this-problem-solvable-in-polynomial-time Is this problem solvable in polynomial time? Jules 2010-06-07T01:13:08Z 2010-08-09T09:18:08Z <p>Let's start with a picture: <a href="http://i.imgur.com/P1k8T.png" rel="nofollow">http://i.imgur.com/P1k8T.png</a> 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): <a href="http://i.imgur.com/ibOIO.png" rel="nofollow">http://i.imgur.com/ibOIO.png</a> (I apologize for the crappy drawings).</p> <p>The goal is to select a subset of all circles such that:</p> <ol> <li>If a circle is selected, then all the boxes it is connected to must be selected.</li> <li>If a box is selected then <em>one of</em> the circles in it must be selected.</li> <li>The primary box is selected.</li> <li>The sum of the numbers in the selected circles is minimal.</li> </ol> <p>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.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/73028/numerical-linear-algebra-how-to-compute-bta-1b-efficiently Comment by Jules Jules 2011-08-17T10:21:37Z 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. http://mathoverflow.net/questions/73028/numerical-linear-algebra-how-to-compute-bta-1b-efficiently Comment by Jules Jules 2011-08-17T03:30:20Z 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$? http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order/58919#58919 Comment by Jules Jules 2011-03-19T13:34:32Z 2011-03-19T13:34:32Z Indeed! Thanks. http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order/58918#58918 Comment by Jules Jules 2011-03-19T12:39:26Z 2011-03-19T12:39:26Z In general given two binary sequences a &lt; b, there are infinitely many binary sequences below, between and above a and b (unless a=0). http://mathoverflow.net/questions/58917/injections-to-binary-sequences-that-preserve-order/58918#58918 Comment by Jules Jules 2011-03-19T12:37:39Z 2011-03-19T12:37:39Z Just send $\infty$ to 1 and a number n to 0 and then n ones. http://mathoverflow.net/questions/53373/the-frechet-derivative-and-lagrange-multipliers-on-banach-spaces Comment by Jules Jules 2011-01-26T19:32:24Z 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 <a href="http://www.maths.ed.ac.uk/~jmf/Teaching/Lectures/CoV.pdf" rel="nofollow">maths.ed.ac.uk/~jmf/Teaching/Lectures/CoV.pdf</a>. Can you post your answer as an answer so that I can accept it? http://mathoverflow.net/questions/37363/approximating-a-probability-distribution-by-a-mixture Comment by Jules Jules 2011-01-26T17:59:09Z 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? http://mathoverflow.net/questions/37363/approximating-a-probability-distribution-by-a-mixture Comment by Jules Jules 2011-01-26T17:39:37Z 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 -&gt; R) -&gt; 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. http://mathoverflow.net/questions/53373/the-frechet-derivative-and-lagrange-multipliers-on-banach-spaces Comment by Jules Jules 2011-01-26T17:10:05Z 2011-01-26T17:10:05Z Willie Wong, I rewrote the question using LaTeX. http://mathoverflow.net/questions/53373/the-frechet-derivative-and-lagrange-multipliers-on-banach-spaces Comment by Jules Jules 2011-01-26T16:49:21Z 2011-01-26T16:49:21Z Hmm yes you are right...how about the problem with the additional constraint f(0) = f(1) = 0? http://mathoverflow.net/questions/27636/non-linear-mixed-integer-programming-question Comment by Jules Jules 2010-06-10T16:38:47Z 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. http://mathoverflow.net/questions/27636/non-linear-mixed-integer-programming-question Comment by Jules Jules 2010-06-10T15:34:04Z 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. http://mathoverflow.net/questions/27636/non-linear-mixed-integer-programming-question Comment by Jules Jules 2010-06-10T12:49:09Z 2010-06-10T12:49:09Z Correction: choose s round $max C_i/M$. http://mathoverflow.net/questions/27636/non-linear-mixed-integer-programming-question Comment by Jules Jules 2010-06-10T12:48:03Z 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 <a href="http://i.imgur.com/zcKOW.png" rel="nofollow">i.imgur.com/zcKOW.png</a> 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. http://mathoverflow.net/questions/27297/is-this-problem-solvable-in-polynomial-time/27342#27342 Comment by Jules Jules 2010-06-07T17:01:16Z 2010-06-07T17:01:16Z That settles this question. Thanks!