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

So we start with a rational $r=\frac{p}{q}$. 1) Say $2\not|p,2\not|q$. Then taking $x=q\pi$, we get: $$f_r(x)=\cos(x)+\cos(rx)=\cos(q\pi)+\cos(p\pi)=-2$$ so $r$ is not the argmax. 2) Say $2$ divides exactly one of $p,q$. Then there exists an odd integer $k$ that solves the congruence equation: $$kp=q+1 \pmod{2q}$$ we take $x=k\pi$, and we have: $$f_r(x)=-1+...


4

For continuous problems, minimizing a convex function on a convex domain is considered an easy problem, because there is only ever one local minimum, and a local minimum is the global minimum. Finding that minimum (when it exists) can be done by local search methods. On the other hand, maximizing a convex function on a convex domain is a hard problem, ...


4

A less-known example is $f(x):=x^2+\exp(-1/(100(x-1))^2)-1$ on the closed interval $[-2,2]$. It takes $-.0067419337989203 $ at $x = .996387676055289 $. See that discussion in MaplePrimes for more details.


4

Let us consider the closely related problem: maximize $EX^\alpha$ over all nonnegative random variables (r.v.'s) $X$ with $EX=\mu$. To avoid trivialities, assume that $\mu\in(0,\infty)$. Consider the following cases: Case 1: $\alpha>1$. Suppose that $P(X=x)=\mu/x=1-P(X=0)$ for some real $x>\mu$. Then $EX=\mu$, whereas $EX^\alpha=\mu x^{\alpha-1}\to\...


4

The said claim follows from the following general result on elementary symmetric polynomials, denoted $e_k$ below. $\newcommand{\vx}{\mathbf{x}}\newcommand{\vy}{\mathbf{y}}$ Theorem A (S. 2018). $\,$ Let $p\in (0,1)$ and $x \in \mathbb{R}_+^n$. The map \begin{equation*} \phi_{k,n}(x) := x \mapsto \left[\frac{e_k(x_1^p,\ldots,x_n^p)}{e_{k-1}(x_1^p,\...


4

Turns out kodlu's idea works in all dimensions, regardless of the existence of any Hadamard matrices. Consider all coordinate permutations of $$(1,...,1,-d)\in\Bbb R^{d+1}\quad\text{and}\quad (-1,...,-1,d)\in\Bbb R^{d+1}.$$ This gives $2d+2$ points in $\Bbb R^{d+1}$, but all these lie in the $d$-dimensional subspace orthogonal to $(1,...,1)$. The ...


4

Here is a simple direct argument. For $i=1,\ldots,n$, let $$C_i=\{z\in Z\mid d(z,x_i)\leq d(z,x_j), j=1,\ldots,n\}.$$ Clearly, each $C_i$ is closed and hence measurable. Let $M_i=C_i\setminus\bigcup_{l=1}^{i-1}C_l$. The nonempty sets of the form $M_i$ form a finite measurable partition of $Z$. Now let $S$ map each $M_i$ to $x_i$.


3

It may very well be that the evaluation of the analytical solution you are referring to poses some problems. An elementary example is an analytical formula for the solution of $Ax=y$ where $A$ is an arbitrary invertible matrix, i.e. $x = A^{-1}y$. It is a nice formula, but its numerical evaluation is a horrible idea. Quick googling for Horn's algorithm ...


3

As far as I can see, you'd like to find a global minimum of $F_0(x)=\sum_{k=1}^{M_0} f_k(x)^2$, where $x=(x_1,\dots,x_{12})$. Equivalently, the problem is to find maximal $\mu$ so that $F(\mu,x):=F_0(x)-\mu\geq 0$ for all $x_1,\dots,x_{12}$. Now, a sufficient condition for $F(\mu,x)\geq 0$ is that $F(\mu,x)=\sum_{k=1}^{M} g_k(\mu,x)^2$. The latter condition ...


3

Unfortunately, no. Here is an example for $n=1$ (1-dimension). For parameters $m>0$, $b\in\mathbb{R}$ define: $$f(x) = (m/2)(x-b)^2 $$ For any $b \in \mathbb{R}$, this function $f$ is strongly convex with modulus $m$. Now fix $\epsilon \in (0, 1/2)$ and define $b = 1/2 - \epsilon$. Then the minimizer of $f(x)$ over the integers is $x^*_{int} = 0$, and:...


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