All Questions
108 questions
30
votes
5
answers
14k
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?
- 303
2
votes
2
answers
293
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
- 835
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 ...
- 431
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
3
votes
1
answer
328
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
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$...
- 15.4k
34
votes
2
answers
4k
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.)
...
- 151k
29
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 ...
- 2,383
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
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 ...
- 50.8k
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
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 ...
- 151k
12
votes
1
answer
361
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 ...
- 50.8k
8
votes
1
answer
2k
views
Symplectic block-diagonalization of a real symmetric Hamiltonian matrix
Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal?
Being ...
- 315
7
votes
2
answers
3k
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 ...
- 96.4k
5
votes
2
answers
1k
views
Minimum of squared sum minus sum of squares
I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...
- 205
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
Countably Infinite
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
3
votes
2
answers
402
views
Generalized Moore Graphs
A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore ...
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
2
votes
0
answers
111
views
Maximization of an integral functional over a closed convex set
I want to maximize $$F(w):=\sum_{1\le i,\:j\le2}\int\lambda^{\otimes2}({\rm d}(x,y))\left(w_i(x)f_j(x,y)\wedge w_j(y)f_i(y,x)\right)g_{ij}(x,y)$$ over the closed convex set $$S:=\left\{w\in{\mathcal L^...
- 167
1
vote
1
answer
148
views
How can we calculate the generalized gradient of $L^2\ni x\mapsto a\min(x(s),by(t))$?
Let $(T,\mathcal T,\tau)$ be a measure space, $a,b\ge0$, $s,t\in T$ and $$f(x):=a\min(x(s),bx(t))\;\;\;\text{for }x\in L^2(\tau).$$
How can we calculate the generalized gradient $\partial_Cf(x)$ of ...
- 167
13
votes
5
answers
4k
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 ...
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 ...
- 3,283
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
27
votes
1
answer
995
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 ...
- 2,619
22
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:
Theorem:...
- 976
21
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 ...
- 6,155
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
17
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 ...
- 8,659
16
votes
1
answer
928
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, ...
- 6,155
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
14
votes
2
answers
743
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 ...
- 141
13
votes
4
answers
584
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 ...
user6979
10
votes
1
answer
308
views
In what area of study does one encounter this principle in timetabling?
A while ago I saw an image like the one below in a lecture, which was supposed to represent a rail network in a (square) city:
The circles represent trains that are moving either North/South or East/...
- 4,049
10
votes
1
answer
411
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 ...
- 37.7k
10
votes
2
answers
9k
views
When do maximum and expectation commute?
Hi, I'm looking for conditions on $G(t,x)$ such that
$$
\sup\limits_{t\in [0,1]}E[G(t,X)]=E[\sup\limits_{t\in [0,1]}G(t,X)]
$$
where $X$ is a random variable (it's easy to see that $\sup\limits_{t\in [...
- 111
10
votes
4
answers
904
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 ...
- 121
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 381
8
votes
3
answers
296
views
Shrinking subset and product
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|...
- 1,209
8
votes
2
answers
955
views
Applications of Topological Complexity of configuration space
I'm starting to work on topological complexity of configuration spaces.
Articles say that this field has applications in robotic and control theory. One of the important articles belongs to Michael ...
- 283
8
votes
0
answers
232
views
Decay of orthogonal contributions in a random set of vectors
Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$:
$$\frac{v_1}{\|v_1\|},\...
- 2,442
7
votes
1
answer
403
views
Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?
"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...
- 24.9k