Questions tagged [oc.optimization-and-control]
Operations research, linear programming, control theory, systems theory, optimal control, game theory
1,142
questions
52
votes
5
answers
8k
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? ...
50
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 ...
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 ...
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 ...
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$...
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 ...
33
votes
2
answers
3k
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.)
...
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$,
...
30
votes
5
answers
13k
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?
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 ...
28
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 ...
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$. ...
27
votes
1
answer
979
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 ...
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 ...
21
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:
...
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 ...
20
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 ...
20
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 ...
17
votes
4
answers
950
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)$ ...
17
votes
10
answers
12k
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.) ...
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 ...
16
votes
2
answers
781
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 ...
16
votes
1
answer
476
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/...
16
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 ...
16
votes
2
answers
275
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 ...
16
votes
1
answer
865
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, ...
15
votes
2
answers
883
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 ...
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 ...
14
votes
2
answers
656
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 ...
14
votes
0
answers
248
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 ...
13
votes
5
answers
3k
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 ...
13
votes
2
answers
715
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 ...
13
votes
2
answers
660
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 ...
13
votes
4
answers
576
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 ...
13
votes
3
answers
815
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 ...
12
votes
3
answers
792
views
finding the most-isolated point in a high-dimensional cube
I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find
$\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} \|\...
12
votes
2
answers
728
views
Geometric applications of Ekeland's variational principle
I'm looking for geometric applications of Ekeland's variational principle in order to see it at work in a context I'm familiar with. Let me recall the principle itself:
Definition. Let $(X,d)$ be a ...
12
votes
3
answers
996
views
Eigencircles of n x n matrices?
An eigenvalue of a 2 x 2 matrix satisfies the equation
$$ \left(\begin{array}{cc} a & b \\ c & d \end{array} \right)\left( \begin{array}{c} x \\ y \end{array}\right) = \lambda \left( \...
12
votes
1
answer
356
views
An averaging game on finite multisets of integers
The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...
12
votes
1
answer
202
views
The angles subtended in a TSP tour
If I sample a large number of uniform points in the unit square and take a traveling salesman tour of them, is there anything at all that can be said/is known about the distribution of angles at each ...
11
votes
4
answers
10k
views
"You can't push a rope" [closed]
"You can't push a rope" is a wisdom saying that some engineering teachers pass along to their students. Since I'm not an engineer, I can only guess at what they mean, but it sounds to me like code ...
11
votes
2
answers
792
views
A generalization of Chebyshev polynomials
What is the monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$? The answer is the Chebyshev polynomial, and its largest value on $[-1,1]$ is $1/2^{n-1}$.
Now suppose ...
11
votes
1
answer
2k
views
Sard's Theorem For Banach Spaces
Given a smooth map from $\phi: B \rightarrow M$ where $B$ is a Banach Space and $M$ is a finite dimensional smooth manifold (for example, the end point map for a control system), what is the strongest ...
11
votes
5
answers
8k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
11
votes
2
answers
339
views
A (reverse)-Minkowski type inequality for symmetric sums
Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true?
\begin{align*}
\left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...
11
votes
2
answers
867
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
11
votes
2
answers
752
views
A (linear) optimization problem subject to (linear) matrix inequality constraints
Let $A \in \mathbb{R}^{n \times n}$ be a Hurwitz matrix, i.e. $A$ satisfies $\mathrm{Re}\,\lambda_i< 0$, where $\{\lambda_i\}_{i=1}^n$ is the set of eigenvalues of $A$. Suppose that the trace of $A$...
11
votes
0
answers
748
views
Hamilton-Jacobi equations: Method of characteristics
In Cannarsa-Sinestrari's book 'Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control' there is a proof, via the Method of Characteristics, of global-in-time existence of classical ...