All Questions
80 questions
24
votes
3
answers
1k
views
Average measure of intersection of a convex region with its translate
Let $\lambda$ denote the Lebesgue-measure on $\mathbb{R}^n$, and let $C\subset\mathbb{R}^n$ be a convex region.
My question is about
$$f(C):=\int_{C} \lambda(C \cap (x + C) ) \mathrm{d} x.$$
How ...
- 343
18
votes
2
answers
1k
views
The Teichmüller space $T_g$ of a closed riemann surface $S_g$ of genus $g \geq 2$ can't be parametrized by $6g−6$ geodesic length functions
I asked this question almost a month ago on Math SE. After waiting three weeks for an answer or a comment, I opened a bounty on the question in hope that it might get an answer this way. The bounty ...
- 385
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
327
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
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
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
1
answer
1k
views
Second order differentiability of convex functions
Let $f:\mathbb{R}^n\to\mathbb{R}$ be a convex function. Then $f$ is locally Lipschitz and hence differentiable a.e. (Rademacher). Let $E\subset\mathbb{R}^n$ be the set of points where $f$ is ...
- 28k
13
votes
1
answer
1k
views
Aleksandrov's proof of the second order differentiability of convex functions
Aleksandrov [A], proved a remarkable property of convex functions.
Theorem. If $f:\mathbb{R}^n\to\mathbb{R}$ is convex, then for almost every $x\in\mathbb{R}^n$ there is $Df(x)\in\mathbb{R}^n$ and ...
- 28k
8
votes
0
answers
459
views
Are there any characterizations of $C^2$ convex functions?
There are several characterizations of convex functions with the Lipschitz continuous gradient. If we already know that the function is of class $C^1$, then we have the following equivalent conditions:...
- 28k
7
votes
3
answers
986
views
Mixtures of log-convex functions are log-convex: a reference
A referee of a submitted paper requested details on the statement that $\int_0^a e^{-tx^2}\,dx$ is log-convex in real $t$, for each $a>0$. While there are a number of ways to prove this statement, ...
- 128k
6
votes
2
answers
539
views
Conditions for including cones
Consider $N$ $n$-dimensional vectors, where the angle between any two vectors is acute and their starting point is at the origin. Can we rotate these vectors together so that the coordinate components ...
- 61
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 ...
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
4
votes
0
answers
220
views
improved regularization for $\lambda$-convex gradient flows
It is well-known that gradient-flows of convex functionals are "parabolic" in some vague sense, and accordingly solutions tend to regularize instataneously. In the abstract context of gradient flows ...
- 5,380
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
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
205
views
Conditions for Lipschitzness of boundary normal vector, almost everywhere
Let $C$ be a nonempty closed subset of $\mathbb R^n$. It is known that any such set satisfies the following condition
(Unique CPP a.e). For almost every $x \in \mathbb R^n$, there exists a unique ...
- 6,853
1
vote
1
answer
139
views
On the Lipschitz continuity of the unit-normal vector field of a polytope
Let $\mu$ be a probability measure on $\mathbb R^n$ and let $P$ be a compact polytope in $\mathbb R^n$. For any $x \in \mathbb R^n \setminus P$, let $p(x) \in P$ be (unique!) point in $P$ which is ...
- 6,853
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
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
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
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
0
answers
310
views
How large are the smallest-area projections of a high-dimensional convex body?
Let $B$ be a convex body in $\mathbb{R}^d$, equipped with its standard Euclidean form, and assume that
$$\intop_B x \, dx = 0$$
$$\frac{1}{|B|_d} \intop_B x_i x_j \, dx = \delta_{ij},$$
a ...
- 4,000
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
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
9
votes
1
answer
748
views
property of convex functions
I am able to give a proof to the following inequality for convex functions. Most likely this is well known, but I am unable to find a reference. I would appreciate if someone more knowledgeable in the ...
- 1,211
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
7
votes
2
answers
497
views
Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex
I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex.
I have managed to prove this by moving all ...
7
votes
2
answers
605
views
Gaussian and the convex hull of moment curves
Let $c_1,\dots, c_d$ be the first $d$ moments of the standard normal distribution. Does the point $(c_1,\dots, c_d)$ lie in the convex hull of the set $\{(t,t^2,\dots,t^d)\colon t\in[-b,b]\}$, for a ...
- 1,127
7
votes
1
answer
2k
views
Does midpoint-convex imply rationally convex?
Say that a function $f$ defined on $\mathbb{Q}^n$ is midpoint convex if $f((x+y)/2) \le (f(x) + f(y))/2$. Say that it is rationally convex if, for $\lambda \in \mathbb{Q} \cap [0,1]$ and $\bar \lambda ...
- 10.1k
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
6
votes
2
answers
341
views
For most directions does the supporting hyperplane meeting a bounded convex set meet it in one point?
Let $C\subseteq \mathbb R^n$ be non-empty, convex and compact. For $v\in S^{n-1}$, let $H_v$ be the supporting hyperplane in the direction of $v$ (i.e., $H_v$ is the boundary of the smallest closed ...
- 2,555
6
votes
2
answers
1k
views
Quantitative version of Jensen's inequality?
I've been looking at situations where Jensen's inequality is almost tight, and found myself proving a lemma that I'm nearly certain exists somewhere in the literature.
The specifics are as follows: ...
- 131
6
votes
2
answers
2k
views
Hausdorff dimension of convex set in ${\bf R}^n$
I want to know the smoothness of convex set in ${\bf R}^n$.
Recall the following definition.
Definition : $X$ is a bounded closed convex set in ${\bf R}^n$ if for $x$, $y\in X$, the any $d$-...
- 1,100
6
votes
2
answers
570
views
Why are $\Gamma_0$ functions called this
It is very common to indicate with $\Gamma_0(A)$ the set of lower semicontinuous convex functions from $A$ to $(-\infty,+\infty]$ with nonempty domain. An example of usage of this notation can be ...
- 71
5
votes
1
answer
392
views
Proving equivalence of two definitions of a convex-type Hamming distance
Update: If somebody can answer my question there, then I will be able to fully answer my question here.
Consider $n\in\mathbb N$ and a non-empty set $M\subset\{0,1\}^n$. I have the following ...
- 1,326
5
votes
1
answer
2k
views
When do convexity and lower semicontinuity imply continuity?
Let $X$ be a nonempty compact convex subset of a locally convex space. Say $X$ has the convex function property if every convex, lower semicontinuous $f:X\to\mathbb R$ is also continuous.
Question: ...
- 537
5
votes
2
answers
1k
views
Distance to a closed set. Is this result known?
Given a closed set $\varnothing\neq E\subset\mathbb{R}^n$, let $\operatorname{Unp}(E)$ be the set if points $x\in\mathbb{R}^n$ for which there is a unique point $y\in E$ nearest to $x$.
Clearly $E\...
- 28k
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41