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

learn more… | top users | synonyms

26
votes
0answers
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
0answers
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
2answers
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
2answers
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
5answers
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
2answers
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
5answers
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
4answers
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
3answers
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
1answer
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
2answers
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
1answer
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
6answers
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
4answers
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
3answers
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
1answer
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
1answer
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
2answers
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
2answers
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
1answer
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
1answer
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
2answers
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
2answers
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
2answers
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
1answer
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
6answers
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
2answers
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
4answers
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
1answer
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
2answers
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
2answers
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
2answers
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
3answers
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
2answers
727 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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
4answers
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
1answer
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
1answer
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
5answers
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
5answers
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
2answers
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
3answers
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
3answers
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
2answers
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
1answer
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 ...