All Questions
1,593 questions
53
votes
5
answers
9k
views
Why do bees create hexagonal cells ? (Mathematical reasons)
Question 0 Are there any mathematical phenomena which are related to the form of honeycomb cells?
Question 1 Maybe hexagonal lattices satisfy certain optimality condition(s) which are related to it? ...
- 24.9k
51
votes
7
answers
23k
views
Is all non-convex optimization heuristic?
Convex Optimization is a mathematically rigorous and well-studied field. In linear programming a whole host of tractable methods give your global optimums in lightning fast times. Quadratic ...
- 2,383
38
votes
5
answers
6k
views
When does symmetry in an optimization problem imply that all variables are equal at optimality?
There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such ...
- 3,283
38
votes
2
answers
2k
views
Optimization problem arising from the study of zeta zeros
Motivation: The following problem arose in [1] while studying the vertical distribution of the zeros of the Riemann zeta-function. At the time, my collaborators and I were unable to solve it and I ...
- 5,037
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
34
votes
2
answers
4k
views
Functions whose gradient-descent paths are geodesics
Let $f(x,y)$ define a surface $S$
in $\mathbb{R}^3$ with a unique local minimum at $b \in S$.
Suppose gradient descent from any start point $a \in S$
follows a geodesic on $S$ from $a$ to $b$.
(Q1.)
...
- 151k
34
votes
3
answers
3k
views
What is the best way to peel fruit?
A mango made me wonder about this. (See also this question, which is in a similar spirit.)
Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset \mathbb{R}^3$...
- 15.4k
33
votes
1
answer
2k
views
$\mathbb{E}[X^4]=1$, $X,Y$ iid, what's the best upper bound of $\mathbb{E}[(X-Y)^4]$?
Let $X,Y$ be i.i.d. random variables, $\mathbb{E}[X^4]=1$, what's the best upper bound for $\mathbb{E}[(X-Y)^4]$ ?
A trivial upper bound is $16$, since $(X-Y)^4 \leq 8 (X^4+Y^4)$ then take ...
- 563
32
votes
0
answers
2k
views
A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
...
- 24.7k
30
votes
5
answers
14k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
- 303
29
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,383
29
votes
1
answer
1k
views
Can a real quartic polynomial in two variables have more than 4 isolated local minima?
This question: "Can a real quartic polynomial in two variables have at most 4 isolated local minima?" came up in this post on Math SE but with no answer so far.
Finding examples of 4 ...
- 431
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
28
votes
1
answer
2k
views
SOS polynomials with integer coefficients
A well known theorem of Polya and Szego says that every non-negative univariate polynomial $p(x)$ can be expressed as the sum of exactly two squares: $p(x) = (f(x))^2 + (g(x))^2$ for some $f, g$. ...
- 1,703
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
1
answer
995
views
The lion and the zebras
The lion plays a deadly game against a group of $N$ zebras that takes place in the steppe (= an infinite plane). The lion starts in the origin with coordinates $(0,0)$, while the $N$ zebras may ...
- 2,619
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
23
votes
2
answers
2k
views
Five Front Battle
Two generals are fighting a five front battle. Each general has 1 unit of army, which he divides into five separate armies that he sends to the five fronts. If one general sends more army to a front ...
- 8,688
22
votes
4
answers
5k
views
Is there an intuitive explanation for an extremal property of Chebyshev polynomials?
Consider the following optimization problem:
Problem: find a monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$.
The solution is given by Chebyshev polynomials:
Theorem:...
- 976
21
votes
4
answers
2k
views
Fairest way to choose gifts
Suppose that a parent brings home from a trip $2n$ gifts of roughly equal value for his/her two children. The children get to choose one at a time which gifts they want. What is the fairest way to ...
- 50.8k
21
votes
1
answer
3k
views
A circle packing conjecture
Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and ...
- 1,085
21
votes
2
answers
3k
views
How to optimally bet on a biased coin?
A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you.
You start with a total ...
- 6,155
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
19
votes
2
answers
2k
views
Higher or lower?
Consider the following game - I draw a number from $[0, 1]$ uniformly, and show it to you. I tell you I am going to draw another $1000$ numbers in sequence, independently and uniformly. Your task is ...
- 6,155
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
17
votes
4
answers
959
views
What is the minimum of this quantity on $S^{n-2}\times S^{n-2}$?
My question is to find the minimum of the following expression:
$$A(x,y) = \sum_{1\leq i<j\leq n} |x_i-x_j|\ |y_i-y_j|,$$
over the set of pairs of real vectors $x=(x_1,\dots,x_n),y=(y_1,\dots,y_n)$ ...
- 4,484
17
votes
10
answers
13k
views
How do I approach Optimal Control?
Other than learning basic calculus, I don't really have an advanced background. I was curious to learn about Optimal Control (the theory that involves, bang-bang, Potryagin's Maximum Principle etc.) ...
- 439
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
17
votes
1
answer
1k
views
What braking strategy is most fuel-efficient?
You notice a stop-light ahead of you and it is currently red. You can't run the red light, so you will have to brake, but braking wastes energy and you want to be as fuel efficient as possible. What ...
- 8,659
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
16
votes
4
answers
1k
views
Maximum of the Vandermonde determinant / minimum of the logarithmic energy
The problem is to find the asymptotics (as $n\to\infty$) of the maximum (say $M_n$) of the Vandermonde determinant
$$V_n:=\prod_{0\le i<j\le n-1}(a_j-a_i)
$$
over all $a_0,\dots,a_{n-1}$ such ...
- 128k
16
votes
2
answers
797
views
What tools should I use for this problem?
Suppose we have $d$ cylindrical metal bars, with radius $l$, attached orthogonal to a support in random places:
Now we have to attach bars with radius $k$ EVENLY SPACED, with distance $p$ between ...
- 480
16
votes
1
answer
508
views
Can solutions to Thomson's problem have pentagons?
Thomson's problem asks for the minimum-energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...
- 1,203
16
votes
2
answers
277
views
Finding a plane numerically
Suppose I have three large finite sets $\{x_i\}$, $\{y_i\}$ and $\{z_i\}$;
they are obtained by measuring coordinates of a collection of vectors in $\mathbb{R}^3$, but I do not know which triples ...
- 45k
16
votes
1
answer
928
views
A simple stochastic game
An individual, henceforth called the runner starts at the center of an open two dimensional square $\Omega$ of side length $r \geq 2$.
At each turn, a vector $x \in S^1$ is chosen uniformly at random, ...
- 6,155
15
votes
2
answers
779
views
How to characterize the regularity of a polygon?
In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their ...
- 161
15
votes
2
answers
974
views
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that:
(1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$;
(2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
- 373
15
votes
3
answers
1k
views
Optimal inspection path on a sphere
Suppose you would like to "inspect" every point of a unit-radius
sphere $S \subset \mathbb{R}^3$ by walking along a path $\gamma$
on $S$, but you can only see a distance $d$ from where you ...
- 151k
14
votes
2
answers
743
views
Is there a class of optimization problems more general than semidefinite programming?
I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there ...
- 141
14
votes
0
answers
261
views
Dividing a convex region to minimize average distances
Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
- 4,049
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
5
answers
4k
views
Application of polynomials with non-negative coefficients
Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...
13
votes
2
answers
1k
views
Optimal search puzzle
Consider the following puzzle: On the integer line from 1 to $t$ (top, let's say 1000 for this example), you have two operators: uniform random on 1 to $t$, and subtract 1. What is the optimal ...
- 265
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 19.2k
13
votes
4
answers
584
views
Minimal-length embeddings of braids into R^3 with fixed endpoints
(Apologies in advance for any imprecision in the following; I am a computer scientist and regret never having taken an actual course on topology.)
One way to define the pure braid group $P_n$ is as ...
user6979
13
votes
3
answers
835
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13
votes
2
answers
1k
views
Seeking proof for linear algebra constraint problem.
Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...
- 379