All Questions
1,544 questions
4
votes
0
answers
195
views
Happy ending problem - why not a proof by induction? (cont)
After sharing ideas on this post, I have been thinking for some time on the problem, and I think that a possible way to prove the Erdös-Szekeres conjecture could be structured as follows:
Consider ...
- 189
2
votes
1
answer
308
views
Intersection of the simplex with a linear subspace of codimension $2$
The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...
- 449
1
vote
0
answers
111
views
Maximizing the minimum curvature of a convex shape with a given volume in higher dimensions
Given any $d$-dimensional convex shape $S$ in the Euclidean space with $d\gg 1$, let $K_{\min}(S)$ be the minimum value of the Gaussian curvature of its boundary.
Question: What is the maximum value $...
- 1,677
2
votes
0
answers
33
views
Decreasing magnitude of spherical centroid (simplex version)
Let $\sigma$ be the uniform measure on $\mathbb{S}^{d-1}\subset \mathbb{R}^d$. For any region $R\subset \mathbb{S}^{d-1}$, let $X_R$ be a random variable which is uniformly distributed across $R$. We ...
9
votes
1
answer
209
views
Reduction to convex case in Brunn - Minkowski
Is there a direct way to reduct the general case of Brunn - Minkowski inequality $|A+B|^{1/n}\geqslant |A|^{1/n}+|B|^{1/n}$ for non-empty compact sets $A, B\subset \mathbb{R}^n$ (here $|\cdot|$ ...
- 109k
3
votes
1
answer
292
views
Continuity of Legendre transform
Let $I \subset \mathbb{R}$ be an interval, and $f_n, f: I \rightarrow \mathbb{R}$ a convex function; then its Legendre transform is the function $f^{\ast}: I^{\ast} \rightarrow \mathbb{R}$ defined by
$...
- 1,043
23
votes
1
answer
713
views
Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks
Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...
- 7,149
0
votes
1
answer
143
views
$\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem
Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...
- 13.2k
5
votes
1
answer
385
views
Contact points for John's ellipsoid
Suppose $K$ is a centrally symmetric convex body in $\mathbb{R}^n$ and $E$ is the John's ellipsoid, the ellipsoid of maximal volume inside $K$.
If $E$ and $K$ have exactly $2n$ contact points, say $(\...
- 1,361
1
vote
1
answer
181
views
Linear programming with "nice" matrices
Consider the following linear programming problem
\begin{array}{ll}
\text{minimize} & \mathrm 1^{\top} \mathrm x\\
\text{subject to} & v\le \mathrm A \mathrm x \le u\\
& \mathrm x \geq ...
- 650
3
votes
0
answers
67
views
Atomicity and BF-ness in monoids of integer points of a polyhedral cone of $\mathbb R^n$
Fix an integer $n \ge 2$ and let $H$ be the (additive) monoid of integer points of a polyhedral cone of the Euclidean space $\mathbb R^n$ with the additional property that $H \setminus \{0_n\}$ is ...
- 10.5k
2
votes
1
answer
108
views
Is the polar dual of a semi-algebraic convex body also semi-algebraic?
Call a convex body $C\subset\Bbb R^n$ semi-algebraic if it can be written as
$$(*)\quad C=\bigcap_{i\in I}\, \{x\in \Bbb R^n\mid p_i(x)\le 0\}$$
with polynomials $p_i\in\Bbb R[X_1,...,X_n]$ and a ...
- 13.6k
0
votes
0
answers
118
views
Polynomial-time algorithm for exact projection to polyhedral cone
Given $c \in \mathbb{R}^d$ and $A \in \mathbb{R}^{n \times d}$, project $c$ to the polyhedral cone $\{x \in \mathbb{R}^d \mid A x \leq 0\}$. Is there an algorithm that outputs an exact solution to ...
- 2,203
1
vote
1
answer
212
views
Lipschitz aspect of a projection on the boundary of a convex
Let $C$ be a closed convex set of $\mathbb{R}^n$ $(n\geq 1)$, with asymptotic cone $C^{as}$ having for interior $\text{Int}\big(C^{as}\big)$. Let $u\in\mathbb{R}^n\setminus\{0\}$ such that
\begin{...
- 449
2
votes
0
answers
133
views
Norm of the Lipschitz-Killing differential forms
I am currently learning about the theory of Normal Cycles which makes use of the language of currents and differential forms. They are defined in the following way
The Lipschitz-Killing curvature form ...
- 93
2
votes
1
answer
875
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171
4
votes
2
answers
394
views
Is this projection on the boundary of a convex Lipschitz?
Let $C$ be a closed convex set of $\mathbb{R}^n$ $(n\geq 1)$, and $u\in\mathbb{R}^n\setminus\{0\}$ such that $u$ does not belong to the asymptotic cone of $C$ and is nowhere tangent to $\partial C$. ...
- 449
0
votes
1
answer
115
views
Invariance of Minkowski sum of sets
Given an euclidean space $E$, two sets $A,B\subset E$ and the action on $E$ of two groups $G_A,G_B$ such that $G_A A=A$ and $G_B B=B$, it is possible to generate a group that leaves invariant $A\oplus ...
0
votes
1
answer
64
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
0
votes
0
answers
71
views
Non-proper orthant automorphisms
Given a real vector space $V$ of dimension $d$, it is known that the automorphism Lie group of the nonnegative orthant $\mathcal{O}^+_d$ can be described just as $$\mathrm{Aut}(\mathcal{O}^+_d)=\...
1
vote
1
answer
119
views
Volume ratio of polytopes with few vertices
The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...
- 245
2
votes
1
answer
227
views
Solving linear programming without solving linear programming
Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
- 9,501
6
votes
2
answers
377
views
Convex surfaces with minimal total curvature in Cartan-Hadamard 3-space
A Cartan-Hadamard 3-space $M$ is a complete simply connected 3-dimensional Riemannian manifold with nonpositive sectional curvature. A (smooth) convex surface $\Gamma\subset M$ is an embedded ...
- 7,149
1
vote
1
answer
87
views
Can upper bounds on totally monotone functions be taken (WLOG) to be themselves totally monotone?
Consider the following: fix a function $\bar{b} : \mathbf{R}_+ \to [0, \infty]$, and define
\begin{align}
\mathcal{S} \left( \bar{b} \right) := \left\{ b : \mathbf{R}_+ \to [0, \infty] \, \text{s.t.} \...
- 801
5
votes
1
answer
354
views
Are the polyhedral cones the only examples of cones that remains closed when they are added to vector subspaces?
Let $C \subset \mathbb{R}^{n}$ be a closed convex cone. If one wants to know whether the linear map $T:\mathbb{R}^{n} \to\mathbb{R}^m$ sends the closed set $C$ to another closed one, $T(C)$, it is ...
- 225
1
vote
1
answer
113
views
Measurable sets of $\mathbb R^n$ forming unique absolutely continuous convex combinations?
If we consider a finite set $A\subset\mathbb R^n$, uniqueness of the convex decomposition of points in $A$ is equivalent to the absence of $\mu\neq0$ signed measure supported on $A$ such that $\mu(\...
- 13
1
vote
0
answers
32
views
Adjacent vertices of a permutohedron which is the orbit of a point $x$ with repeated coordinates
Question: Let $x=(x_1, ..., x_n) \in \mathbb{R}^n$, and let $P$ be the convex hull of the points formed by permuting the coordinates of $x$. Given a vertex $y$ of $P$, what is a general rule for ...
- 637
2
votes
1
answer
372
views
Who called Farkas' fundamental theorem a lemma?
Farkas proved his famous result (which, nowadays, is fundamental in optimization theory) in 1902 and called it Grundsatz der einfachen Ungleichung which may be translated as fundamental theorem of ...
- 16.4k
4
votes
0
answers
68
views
Good resources that talk about geodesically convex sets for riemannian manifolds?
Are there any good resources that talk about geodesically convex sets, and in particular convex hulls, for riemannian manifolds? I’ve been wanting to learn more about them, their geometry and ...
- 518
1
vote
1
answer
124
views
A neighborhood $Y$ of a set $X$ such that the line segment connecting any point in $Y$ and its projection to $X$ is contained in $Y$
A direct line from a point $p$ to a set $X$ is a line segment with one endpoint at $p$ and one endpoint in $X$, which is as short as any other line segment from $p$ to $X$. Given a closed set $X$ and ...
- 637
1
vote
0
answers
37
views
Reference for a general theory of spaces of one-directional rays?
There is a lot of work done on projective spaces, over real, complex numbers or over an abstract field. But I do not find a reference for similar theory where the vectors are projected to the same &...
- 330
5
votes
2
answers
672
views
Secondary polytope
Given a polytope $P$, what do the points of the secondary polytope correspond to?
I know that the vertices of the secondary polytope correspond to regular triangulations of $P$.
But what do the ...
- 43.2k
1
vote
0
answers
47
views
Support functions for subset and superset
I have an ellipse $\mathcal{E} = \{x^TAx = 1\}$, and I have a connected subset of an ellipse $U\subset \mathcal{E}$
For a given $\theta$ let $x_U^*(\theta) = \arg \sup\{\langle x,\theta\rangle, x\in ...
- 215
1
vote
0
answers
113
views
Maximizing a parametric integral over the unit sphere
I am trying to compute the nonnegative quantity
$$
\underset{y\in\mathbb{S}^{d-1}}{\sup}\int_{0}^{t}(\Vert A(\tau)y\Vert_{1}- \Vert A(\tau)y\Vert_{q})d\tau, \quad 1 < q < \infty
$$
where $\...
- 1,538
1
vote
1
answer
331
views
Finding a special solution in a solution set over F2
Given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...
- 51
0
votes
1
answer
396
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
- 1
2
votes
0
answers
191
views
Approximation of zonoids
I have a question regarding the papers on approximating zonoids with zonotopes. I'll first write down the approximation problem and then state what my question is.
Problem of Approximating Zonoids. ...
- 640
1
vote
0
answers
71
views
Is there any previous study on the relationship between convexity and the order of points in the general position?
Let's assume $V =(v_1,v_2,v_3,… ,v_n)$ is a set points in a general-position. For each point $v_i$, let's list the points in the order we encounter as we rotate around a certain direction (say ...
- 11
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
0
votes
1
answer
319
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
1
vote
0
answers
61
views
Linear programming robustness to input perturbations
I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
- 11
0
votes
0
answers
121
views
Sharp, salient and opposite cones
I have been reading about star shaped sets and support cones from this article.
Can anyone please help me with examples the difference between a sharp and dull cone.
How come a salient cone has a ...
- 27
0
votes
0
answers
202
views
Regarding definition of convex cone and apex
I have been reading about star shaped sets and support cones from this article. I am wondering about the definition of the cone as to why is it defined this way? Why is it $C-a$? I am familiar with ...
- 27
2
votes
1
answer
644
views
How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]
I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
2
votes
2
answers
164
views
Angle between a point in a convex polytope and the nearest point of a face
Let $P \subset \mathbb{R}^d$ be a convex polytope, and let $F$ be a face of $P$ (of co-dimension 1, let's say). Now let $x \in P \setminus F$ and let $y \in F$ be the nearest point of $F$ to $x$. Then ...
- 153
1
vote
1
answer
231
views
For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?
Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the ...
- 6,853
2
votes
2
answers
261
views
Distribution of the support function of convex bodies: beyond mean width
Let $K$ be a symmetric convex body in $\mathbb{R}^n$ (that is the unit ball of a norm). Let $h_K$ be its support function, that is $h_K(u) = \sup_{x \in K}\langle x,u \rangle$. The quantity $w(K) = \...
- 245
2
votes
1
answer
66
views
Optimal unions of planar convex regions
This post continues Optimal intersections between planar convex regions.
Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
- 5,979
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 385
0
votes
0
answers
74
views
Diameter of inner parallel body
Let's say I have a convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with non-empty interior.
Let $\mathcal{P}=\bigcap_{i=1}^mH_i$ for some halfspaces $H_i$ and let $d=diam(\mathcal{P})=\sup\{\|x-y\|:...
- 93