Questions tagged [oc.optimization-and-control]

Operations research, linear programming, control theory, systems theory, optimal control, game theory

Filter by
Sorted by
Tagged with
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? ...
Alexander Chervov's user avatar
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 ...
DoubleJay's user avatar
  • 2,353
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 ...
Mike Spivey's user avatar
  • 3,253
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 ...
Micah Milinovich's user avatar
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$...
Steve Huntsman's user avatar
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 ...
Chen Dan's user avatar
  • 563
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.) ...
Joseph O'Rourke's user avatar
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$, ...
Gil Kalai's user avatar
  • 24.2k
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?
Optimizationguy's user avatar
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 ...
Jap88's user avatar
  • 431
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 ...
DoubleJay's user avatar
  • 2,353
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$. ...
Gautam's user avatar
  • 1,693
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 ...
Eric's user avatar
  • 2,601
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 ...
zeb's user avatar
  • 8,533
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: ...
alex's user avatar
  • 956
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 ...
Richard Stanley's user avatar
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 ...
Veit Elser's user avatar
  • 1,045
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 ...
Nate River's user avatar
  • 4,822
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)$ ...
Mostafa's user avatar
  • 4,454
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.) ...
Legend's user avatar
  • 429
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 ...
Iosif Pinelis's user avatar
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 ...
Diego Santos's user avatar
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/...
Alex Meiburg's user avatar
  • 1,193
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 ...
David Spivak's user avatar
  • 8,549
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 ...
Anton Petrunin's user avatar
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, ...
Nate River's user avatar
  • 4,822
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 ...
X. Li's user avatar
  • 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 ...
Joseph O'Rourke's user avatar
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 ...
Caio Tomás's user avatar
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
Miroslav Korbelar's user avatar
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 ...
jackisquizzical's user avatar
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 ...
Anthony Esparza's user avatar
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 ...
JSE's user avatar
  • 19.1k
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 ...
user avatar
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 ...
Jeremy 's user avatar
  • 379
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} \|\...
Jeff's user avatar
  • 500
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 ...
alvarezpaiva's user avatar
  • 13.2k
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( \...
john mangual's user avatar
  • 22.6k
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 ...
Richard Stanley's user avatar
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
Mike Cook's user avatar
  • 113
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 ...
Benjamin's user avatar
  • 2,069
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 ...
Hellen's user avatar
  • 111
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} + \...
VSJ's user avatar
  • 1,024
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 ...
Louigi Addario-Berry's user avatar
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$...
Ludwig's user avatar
  • 2,682
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 ...
TØS's user avatar
  • 101

1
2 3 4 5
23