# Tag Info

## Hot answers tagged global-optimization

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