**26**

votes

**0**answers

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

**23**

votes

**0**answers

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

**22**

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

**2**answers

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

**20**

votes

**5**answers

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

**18**

votes

**5**answers

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

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

**3**answers

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

**13**

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

**13**

votes

**2**answers

907 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

**1**answer

682 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

**6**answers

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

**11**

votes

**4**answers

436 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

462 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

503 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

232 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

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

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

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

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

370 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

627 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

337 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

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

**7**

votes

**6**answers

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

**7**

votes

**2**answers

342 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

**1**answer

289 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

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

**7**

votes

**2**answers

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

**6**

votes

**2**answers

345 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

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

**2**answers

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

**6**

votes

**1**answer

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

**6**

votes

**1**answer

868 views

### Cross correlation detection in binary Hamming distance

Given two long binary strings of length N, it's easy to find the Hamming distance between them. If you're allowed to cyclically shift one of the strings, you'll get N different Hamming distances when ...

**6**

votes

**1**answer

362 views

### Eigenspace of Euclidean distance matrix.

What is the necessary and sufficient condition (if there is any) that $n$ orthonormal vectors $v_1,v_2,\cdots,v_n$ are eigenvectors of a Euclidean distance matrix. When $n=2$, the orthonormal ...

**6**

votes

**3**answers

399 views

### Sequences of evenly-distributed points in a product of intervals

Let φ be the golden ratio, (1+√5)/2. Taking the fractional parts of its integer multiples, we obtain a sequence of values in (0,1) which are in some sense "evenly distributed" in a way which ...

**6**

votes

**1**answer

260 views

### Constructing a hypersurface with given outer normals

Pick a point on each of the positive half-axes in $\mathbb{R}^n$. Put a (unit-norm?) vector at each of the n points.
(a) Is there a hypersurface in the orthant $\mathbb{R}^n_+$ going through these n ...

**6**

votes

**1**answer

315 views

### Stable orthogonalization procedure

At a high level, my question is the following: given a set of $k$ vectors in Euclidean space which are pairwise "almost orthogonal", can one find a set of $k$ orthogonal vectors which are pairwise ...

**6**

votes

**4**answers

1k views

### Robust black box function minimization with extremely expensive cost function

There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc.
But I still have not found a good ...

**6**

votes

**1**answer

333 views

### Degree constrained edge partitioning

I've come up with the following optimization problem in my research. Is this a known problem in graph-theory and/or combinatorial optimization? If not, which of the known problems are the most similar ...

**6**

votes

**1**answer

683 views

### Random, Linear, Homogeneous Difference Equations and Time Integration Methods for ODEs

Most methods (that I know of) of numerically approximating the solution of ODEs are "general linear methods". For this type of method, the so-called 'linear stability' is examined by applying the ...

**5**

votes

**5**answers

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

**5**

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

**5**

votes

**2**answers

409 views

### Maximize the intersection of a n-dimensional sphere and an ellipsoid.

I have the conjecture that the volume of the intersection between an $n$-dim sphere (of radius $r$) and an ellipsoid (with one semi-axis larger than $r$) is maximized when the two are concentric, but ...

**5**

votes

**3**answers

587 views

### How can I embed an N-points metric space to a hypercube with low distortion?

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...

**5**

votes

**3**answers

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

**5**

votes

**2**answers

498 views

### Gandhi's quote formalized [closed]

Hello,
I hope this question is appropriate for Mathoverflow. Gandhi said, "Be the change that you wish to see in the world". I don't understand anything in Game/optimization theory (I don't know ...

**5**

votes

**1**answer

842 views

### Non-negative quadratic maximization

For a given symmetric and positive semidefinite $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \ x\geq 0} x^T A x.$$
Here, $x\geq 0$ indicates that $x$ must be component-wise ...