**34**

votes

**1**answer

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 ...

**28**

votes

**3**answers

2k 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 ...

**28**

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$, ...

**25**

votes

**6**answers

12k 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 ...

**23**

votes

**2**answers

1k 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

**5**answers

2k 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 ...

**20**

votes

**2**answers

1k 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.)
...

**15**

votes

**3**answers

966 views

### “Entropy” proof of Brunn-Minkowski Inequality?

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.
The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then
$$ ...

**15**

votes

**3**answers

1k 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 do ...

**15**

votes

**1**answer

2k 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 ...

**14**

votes

**4**answers

2k 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:
...

**13**

votes

**6**answers

4k 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 ...

**13**

votes

**4**answers

375 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 ...

**13**

votes

**2**answers

936 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 ...

**13**

votes

**1**answer

738 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 ...

**11**

votes

**8**answers

2k 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.) ...

**11**

votes

**4**answers

467 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 ...

**11**

votes

**3**answers

506 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} ...

**10**

votes

**1**answer

537 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 ...

**10**

votes

**1**answer

275 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**10**

votes

**2**answers

418 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 stand.
...

**10**

votes

**2**answers

2k views

### Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix

Assume that we have a full-rank diagonally dominant matrix $A$, all the diagonal elements of which are positive, all the non-diagonal elements are negative, and the sum of the absolute values of the ...

**10**

votes

**0**answers

141 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 ...

**9**

votes

**1**answer

254 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 ...

**9**

votes

**2**answers

2k views

### An optimization problem for points on the sphere (master's dissertation)

First, by means of a disclaimer, some background. I am entering the fourth and final year of an undergraduate master's degree in maths, and a quarter of the maximum credit for this year will be for a ...

**9**

votes

**1**answer

3k views

### “You can't push a rope”

"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 ...

**8**

votes

**5**answers

3k views

### Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms

Just a new guy in optimization. Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms?

**8**

votes

**1**answer

2k views

### Universal definition of Fourier transform [closed]

Is there a category theoretic definition for the Fourier transform using only its universality properties? I am not looking for the most general definition -- one that works only in some special ...

**8**

votes

**2**answers

378 views

### Projecting the unit cube onto subspaces

Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max_{s \in S}\frac{\|Ps\|_2}{\|s\|_2}$ where $Ps$ is the orthogonal projection of $s$ onto $L.$
...

**8**

votes

**2**answers

684 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 ...

**8**

votes

**2**answers

225 views

### Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...

**8**

votes

**2**answers

344 views

### An extension of Gaussian Isoperimetry

The Gaussian isoperimetric inequality (Tsirelson,Sudakov, Borell) states that among all sets of given Gaussian measure in the n-dimensional Euclidean space, half-spaces have the minimal Gaussian ...

**8**

votes

**1**answer

211 views

### Algorithm for matching in the power set lattice

Suppose that we have two probability distributions, $f$ and $g$ on the subsets of a finite set $X$, i.e. $f, g: P(X) \to [0,1]$, with
$$
\sum_{A \subseteq X} f(A) = \sum_{A \subseteq X} g(A) = 1.
$$
...

**8**

votes

**0**answers

263 views

### Hasse-Weil Bound and Chebyshev Inequality

I was reading about the Hasse-Weil bound for the number of points in on a curve over the finite field $\mathbb{F}_q$.
$$ \big| |C(\mathbb{F}_q)| - (q+1) \big| \leq 2g \sqrt{q} $$
However, this ...

**8**

votes

**2**answers

347 views

### Entropy conjecture for distributions over $\mathbb{Z}_n$

Suppose we have two independent random variables $X$ (with distribution $p_X$) and $Y$ (with distribution $p_Y$) which take values in the cyclic group $\mathbb{Z}_n$. Let $Z = X +Y$, where the ...

**7**

votes

**2**answers

352 views

### More general form of inequality?

I have proved a simple Lemma that I need for a larger result, and I was wondering whether it is actually another more famous result in disguise.
The lemma says that for any set of vectors in ...

**7**

votes

**4**answers

1k views

### Is there a name for the matrix equation A X B + B X A + C X C = D?

I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...

**7**

votes

**3**answers

359 views

### The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...

**7**

votes

**1**answer

312 views

### Probability density that minimizes the sample range

Let $\mathcal{F}$ denote the set of all "concave probability distributions" on the unit interval, that is, all functions $f:[0,1]\to \mathbb{R}$ such that $f$ is concave, $f(x)\geq 0$ for all $x\in ...

**7**

votes

**2**answers

1k views

### Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...

**7**

votes

**2**answers

177 views

### Relativistic Control Theory

I am looking for literature that combines General relativity and control theory.
So far I found a video lecture on "Integrability meets Control Theory: Harmonic maps in GR", other than that not so ...

**7**

votes

**1**answer

381 views

### Nilpotent Lie algebras of vector fields

Let $L$ be a finite-dimensional nilpotent subalgebra of the Lie algebra $W_n$ of all vector fields in $n$ variables (I am interested both in polynomial and formal vector fields). Does there exist a ...

**7**

votes

**2**answers

442 views

### How to solve such an optimization problem

I encounter the following optimization problem, but I can't solve it.
Given $N$ variables satisfying $0 \leq x_1 \leq x_2 \leq x_3 \leq ... \leq x_N \leq 1$ and an integer $K$ no large than $N$, find ...

**7**

votes

**2**answers

409 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( ...

**6**

votes

**5**answers

1k 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 ...

**6**

votes

**2**answers

370 views

### The odd power of copositive matrix

If $A$ is copositive, what about $A^3$? Is it also copositive? More generally,
my question is whether the odd power of a copositive matrix is still copositive.
Any reference is appreciated

**6**

votes

**3**answers

630 views

### Some questions about Invexity

Recently, I am looking into a non-convex optimization problem whose points satisfying KKT conditions can be obtained. Then the problem becomes how to decide whether the KKT conditions are sufficient ...

**6**

votes

**3**answers

1k views

### minimize the sum of absolute eigenvalues

Hi,
We have a real symmetric matrix M with diagonal elements 0's, the eigenvalues and eigenvectors of M are computed.
Now we wish to change its diagonal elements arbitrarily to minimize the sum of ...

**6**

votes

**4**answers

830 views

### Simplex method for SDP?

I know the interior point method works both for Linear Programming (LP) and semidefinite programming (SDP). My question is, can the other popular method for solving LP, namely the simplex method, be ...

**6**

votes

**3**answers

748 views

### SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...