# Tag Info

18

Let $$f(x,y):=4x^{2}+4y^{2}-4xy-4y+1 + \frac{4}{\pi^2}\Bigl( \sin^{2}(\pi x)+ \sin^{2}(\pi y) + \sin^{2}(\pi y-\pi x) \Bigr).$$ I will show that $$\min_{0\leq x\leq y\leq 1}f(x,y)=\min_{0\leq x\leq 1/3}f(x,2x).\tag{\ast}$$ This suffices, because the minimum of the one-variable function $f(x,2x)$ is easy to analyze numerically: it occurs around $x_0\approx ... 17 In three dimensions you don’t need to go beyond lattices to see the failure of universal optimality. When the potential function is sufficiently steep (e.g., a narrow Gaussian), the face-centered cubic lattice is optimal, but for wide Gaussians the body-centered cubic beats it. You can see this using Poisson summation (the face-centered and body-centered ... 13 There has been recently a flurry of new results on provable nonconvex methods which can be guaranteed to converge to the global optimum. In other cases, the non-convex problem itself is shown to have no spurious local optima. The classical case is the singular value decomposition (SVD) which is non-convex but yet solvable. This is because only the top ... 11 Here's an example to show that the infimum is not always attained: Consider the standard Hopf map$\pi:S^3\to S^2$, which is not null-homotopic, of course, so it follows that the area of the graph in$S^3\times S^2$of any differentiable map$f:S^3\to S^2$that is homotopic to$\pi$is strictly greater than the area of the graph of a constant map, i.e., of$...

9

First, let's assume $a=1$; for other values we can scale a solution with $\sqrt{a}$. So we want to minimize $H=\sum_{i,j} (1-\|x_i-x_j\|^2)^2$. I globally optimized the problem numerically for $n=4$ and $n=5$ and obtained as solutions for $n=4$, the square with side length $\sqrt{\frac{2}{3}}\approx0.8165$, giving $H_4=\frac{2}{3}$ for $n=5$, the ...

9

Let $F(x,y)$ denote the left-hand side of your inequality. It is easy to see that $|\nabla F(x,y)|\sqrt2/n<0.002$ if $0<x<y<1$, where $n:=6600$. A direct calculation shows that $F(i/n,j/n)>0.5021\dots$ for all integers $i,j$ such that $0\le i\le j\le n$. It follows that $F(x,y)>0.502-0.002=1/2$ if $0<x<y<1$, as desired. Details ...

6

Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses: Then the answer vector $v$ must connect to one of the corners of the shaded boxes. Instead of first collecting the boxes, try the following zig-zag algorithm: start from the origin and poll the up and right nearest lattice points. One of them is closer ...

6

In Maple you can just do with(Optimization): g := (your function): Minimize(g,iterationlimit = 200); On my machine this takes only about 1.5 seconds to return the following: [2.35579022955789696*10^(-9), [x0 = .696531801759957, x1 = .286105658731833, x10 = .342973444356395, x11 = .728732510532874, x2 = .226824733028582, x3 = .551288843437034, x4 = ....

6

$\newcommand{\R}{\mathbb{R}}$ An advantage of my previous answer was that, while the computer calculations were pretty heavy there, the logic was extremely simple; virtually no thinking or ingenuity was needed. On the other hand, one can use a bit of thinking in order to greatly reduce the amount of calculations. More specifically, one can use second-order ...

5

Let $p \in \mathbb{R}[x_1, \ldots, x_n]$. The set $S=\{x \in \mathbb{R}^n: p(x) \geq 0\}$ is compact if and only if there is a natural number $N$ and polynomials $g_i, h_i \in \mathbb{R}[x_1, \ldots, x_n]$, such that $N-\sum_{i=1}^n x_i^2 = \sum_{i=1}^rg_i^2+p \sum_{i=1}^s h_i^2$. It is easy to see that this criterion is sufficient. Schmüdgen's ...

5

My initial intuition was incorrect. It seems we can sometimes solve this explicitly, and the minimizer does not have full support; my argument is incomplete (as discussed below), but I think it's reasonably convincing anyway. I'm also only going to discuss $a=1$ (initially, I thought that was the general case, but of course that's not true because of the $1$ ...

5

Rewrite the inequality in question as \begin{equation*} f(u+v)\le f(u)+f(v) \end{equation*} for $u,v$ in $\mathbb R_+^4$, where \begin{equation*} f(u):=-\left(\left(\frac{1}{\sqrt{u_1}}+\frac{1}{\sqrt{u_2}}+\frac{1}{\sqrt{u_3}} +\frac{1}{\sqrt{u_4}}\right) \sqrt{u_1 u_2 u_3 u_4}\right)^{2/3}. \end{equation*} Note that the function $f$ is positive ...

5

I believe that in general, without any additional assumptions about the manifolds, the answer is in the negative. A counterexample can be found for mappings between annuli. Let $A=A(r,R)$ and $A_*=A(r_*,R_*)$, $0<r<R<\infty$, $0<r_*<R_*<\infty$ be annuli in the plane. If $$\frac{R_*}{r_*}<\frac{1}{2}\left(\frac{R}{r}+\frac{r}{R}\right) ... 5 No, it is not; in fact, 2(n-1) is a local maximum. Let B be a Hermitian matrix such that |B_{ij}|=1 and B_{ii}=1. We denote its eigenvalues by \mu (not to confuse them with eigenvalues of A). It is easy to see that always \mu\le n: if (x_1,\dots,x_n) is an eigenvector and |x_i|=\max_j|x_j| then$$|\mu x_i|=\left|\sum_j B_{ij}x_j\right|\le \...

5

OK, it's late and I may be wrong but I think that you can obtain the $2d$ points by using any set of orthonormal basis vectors $\{v_1,\ldots,v_d\}$ and their negatives. Now if $n$ is such that a Hadamard matrix exists, you could take the rows of $H$ an $n\times n$ Hadamard matrix in its $\pm 1$ formulation, and its negative. If you then remove the first ...

4

This kind of problem is known in the literature as a nonlinear state-space system identification. Several algorithms have been proposed in the literature to solve these problems. I think a good starting point would be (1) and the references therein, in particular the works of L. Ljung. As far I know, in general if you don't have a good initial estimate of ...

4

In a quite large range of the parameters we can approximate the fraction by a Taylor series to obtain $$f(x) = \frac{1}{x!}\frac{1}{\frac{-\log c}{\binom{x+n-1}{n-1}} + \mathcal{O}\left(\frac{\log^2 c}{\binom{x+n-1}{n-1}^2}\right)} = \left(1+ \mathcal{O}\left(\frac{\log^2 c}{\binom{x+n-1}{n-1}^2}\right)\right)\frac{\binom{x+n-1}{n-1}}{-x!\log c},$$ which ...

4

To solve a polynomial system, I would try Bertini which is a homotopy-continuation numerical solver that parallelizes extremely well. You can also try to attack the optimization problem directly with semi-definite programming as explained by Dima Pasechnik.

4


3

If the coefficients of your linear expressions are integers and you want the variables $x_i$ to be integers as well then the problem can be written as an integer program: \begin{align*} \text{Maximize }\sum_{i=1}^m&c_iy_i\\ \text{subject to }My_i &\leqslant M-1+\sum_{j=1}^na_{ij}x_j &&i\in\{1,\ldots,m\},\\ x_j &\in\mathbb{Z}&&j\in\...

3

Your problem is a special case of a Fractional Linear Program, so as such following the recipe provided on Wikipedia you should be able to solve it by using a reformulation to an equivalent linear program (need to ensure though that the denominator is strictly positive). Once you've transformed it into an LP, use a usual solver (e.g., CVX)

Only top voted, non community-wiki answers of a minimum length are eligible