All Questions
1,544 questions
4
votes
1
answer
139
views
Characterization of convexity by connectedness of hyperplane sections
Let $S$ be a smooth closed connected embedded hypersurface in $\mathbb R^n$.
Is it true that $S$ is convex, i.e. is a boundary of a convex set, if and only if any section of $S$ by a hyperplane is ...
- 2,934
2
votes
1
answer
209
views
Prove inequality: $2\Big[ \sum_{k=0}^{n} (k+1) a_k \Big]^2 -\Big[1+ \sum_{k=0}^{n} a_k \Big]\Big[ \sum_{k=0}^{n} k(k+1)a_k \Big] \geq 0.$
Suppose $a_0\geq\dots \geq a_n \geq 0$ is a sequence of non-negative numbers, where $n+1\leq \sum_{k=0}^{n} a_k \leq n+2$. Then, I want to prove that the following statement is true,
$2\Big[ \sum_{k=0}...
- 23
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
1
vote
1
answer
88
views
Joint maximizer of a strongly concave function
I have a question that is arising in my research.
Suppose that $f : \mathbb{R}^ 2 \to \mathbb{R}$ is a strongly concave function, satisfying:
For every $x$, the function $y \to f(x, y)$ is maximized ...
- 11
3
votes
0
answers
208
views
Reference request: Carathéodory-type theorem for convex hulls of closed sets
I'm looking for a reference for the following theorem.
Theorem Let $X$ be a closed subset of $\mathbb{R}^N$, and let $a$ be a point of its convex hull $\operatorname{conv}(X)$. Then there exist ...
- 27.7k
0
votes
0
answers
43
views
For a convex body $K\subset R^n$, does the quantity $\min_{t>0} E[t^{-1} \|tg - \pi_K( t g)\|_2]$ have a name? Where has it been studied?
Consider a convex compact set $K\subset R^n$ (with non-empty interior if that helps).
Let $\Pi_K:R^n\to K$ be the projection onto $K$, defined as
$$
\Pi_K(x) = \operatorname{argmin}_{k\in K} \|k-x\|
$$...
- 1,724
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
2
votes
1
answer
383
views
Geometry in $\mathbb{R}^n$: angle between projections of a rectangle
Consider a hyper rectangle $R$ in $\mathbb{R}^n$ defined by $|x_i|\leq M_i$ for all $i\leq n$.
Consider a linear affine subspace $L$ of dimension $1\leq k <n$ such that $L\cap R\neq \emptyset$.
For ...
- 21
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 13.2k
0
votes
1
answer
172
views
Density of the set of convex polygons in the Banach-Mazur distance
Is the set of convex polygons dense in the set of convex domains in $\mathbb{R}^2$, for the Banach-Mazur distance?
Any insight for a negative or positive answer is very much welcome!
- 191
0
votes
0
answers
171
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
4
votes
1
answer
186
views
Convex hull of 3 points in Cartan-Hadamard manifolds
Can the convex hull of $3$ points in a Cartan-Hadamard manifold be smooth?
A Cartan-Hadamard manifold $M$ is a complete simply connected manifold with nonpositive curvature (so it includes the ...
- 7,149
2
votes
1
answer
107
views
To find the convex planar region minimizing diameter when area and perimeter are given
The basic question is to find that planar convex region for which diameter is a minimum when area and perimeter are specified.
A partial answer is given here: http://nandacumar.blogspot.com/2012/11/...
- 5,979
0
votes
1
answer
126
views
On 'special' points on uniform planar convex regions defined in terms of moment of inertia
The following can be easily proved using perpendicular axes theorem and intermediate value theorem:
Lemma: Given any uniform planar convex region $C$ and any point on it, $P$, there will be at least ...
- 5,979
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 129
2
votes
1
answer
159
views
Conic hull of a rectangle
I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...
- 275
2
votes
1
answer
138
views
On the moment of inertia of planar convex regions and possible special nature of circular disks
We consider uniform convex planar regions and lines through their center of mass and lying in the same plane as the region; each line is parametrized by an angle $\alpha$ it makes with some reference ...
- 5,979
1
vote
1
answer
96
views
If $|P|<\infty$ and $C=P\cap\partial(\textrm{Conv}(P))$, then $P\subset\textrm{Conv}(C)$?
That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$?
It seems true intuitively. In ...
1
vote
0
answers
22
views
Parabolic equations and nonconvex domains
Is there a (system of) parabolic equation(s) where qualitative properties depend on whether or not the (say, smooth and bounded) domain $\Omega$ is convex? I am aware of a few cases where a proof ...
- 313
19
votes
0
answers
550
views
Talagrand's "Creating convexity" conjecture
We say a subset $A$ of $\mathbb{R}^N$ is balanced if
\begin{equation}
x \in A, \lambda \in [-1,1] \implies \lambda x \in A.
\end{equation}
Given a subset $A$ of $\mathbb{R}^N$, we write
\begin{...
- 484
1
vote
0
answers
107
views
Planar sections of convex sets in Cartan-Hadamard manifolds
Let $X$ be a convex set in Euclidean space $\mathbf{R}^n$ and $p\in\mathbf{R}^n$ be a fixed point. Then any plane $\Pi$ passing through $p$ intersects $X$ in a convex set. Conversely, this property ...
- 7,149
2
votes
1
answer
136
views
On equal area planar sections of 3D convex bodies
This is an extension of On segments of equal area cut from planar convex regions by chords.
While the 3D analog of the above question would be about 3D pieces cut from a convex body $C$ by planes, ...
- 5,979
2
votes
1
answer
179
views
On segments of equal area cut from planar convex regions by chords
Consider a planar convex region $C$ of unit area and all chords of it that cut off a segment of area $\alpha$ from $C$. Obviously, if $C$ is a circular disk of unit area, all segments of area $\alpha$ ...
- 5,979
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 13.2k
1
vote
0
answers
122
views
Smooth action on cotangent space of the plane
Assuming that $S^1$ acts on $\mathbb{R}^2$ by smooth maps (which are diffeomorphisms), the induced action on the cotangent bundle given by
$$g\cdot(x,\xi)=(g\cdot x,\varphi^∗_{g^{−1}}\xi)$$
acts via ...
- 191
1
vote
0
answers
245
views
A sort of dual to nondegenerate random variables
I was motivated by this classical puzzle/1992 Putnam problem.
Suppose 4 points are independently and uniformly distributed on a sphere in 3d. What is the probability the tetrahedron they form contains ...
- 646
1
vote
0
answers
94
views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program
$\min c.x$
subject to $A.x \leq b ; x \geq 0.$
Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
11
votes
0
answers
717
views
John-type theorems: trading structure for accuracy?
Given two symmetric convex bodies $B, B'$ in ${\bf R}^d$, define the Banach-Mazur distance $d(B,B')$ between them to be the least constant $\tau \geq 1$ such that
$$ B \subset TB' \subset \tau B$$
for ...
- 114k
2
votes
0
answers
51
views
Estimating the Hausdorff distance of parallel facets of convex polytopes
Background
Let $\mathcal{K}_P^n$ denote the class of open, convex, $n$-dimensional polytopes in $\mathbb{R}^n$ containing the origin. For each $K\in \mathcal{K}_P^n$, its gauge function $f_*:\mathbb{R}...
- 21
0
votes
0
answers
56
views
Zero flux along lines
I am considering the $L^1$ ball in $\mathbb{R}^d$, and a conservative vector field $V$ on it, which arises as the gradient of a bounded, almost-everywhere Lipchitz-function. Denoting by $e_i$ as the i’...
- 232
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
3
votes
1
answer
42
views
A converse question about the polyhedrality under linear mapping
It is quite well known that for any polyhedral set $K$ and any linear mapping $A$, the set $AK$ is polyhedral and hence closed. I am more curious about the converse problem, namely:
Suppose $K$ is a ...
- 300
1
vote
1
answer
194
views
Reference request: Inequalities involving convex sets and Gaussian variables stated in a paper by Talagrand
I'm looking for references for two facts that are stated without proof in the paper:
Talagrand, M., Are all sets of
positive measure essentially convex?, Lindenstrauss, J. (ed.) et al.,
Geometric ...
- 484
1
vote
0
answers
68
views
On known links between convexity and fuzzy logic
The following are thoughts I had during a joint work with P. Olver on maps from spheres to the convex hull of finitely many points in some finite-dimensional vector space. I do not wish to discuss the ...
- 5,215
3
votes
1
answer
111
views
Does a matroid base polytope contain its circumcenter?
Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...
- 13.6k
3
votes
0
answers
94
views
On convex 3d bodies whose shadows are all of constant diameter [closed]
We add a bit to More on shadows of 3D convex bodies
By a shadow of a 3D body, we mean the orthogonal projection of it onto a 2D plane.
If all shadows of a convex 3D body have the same diameter, will ...
- 5,979
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
2
votes
1
answer
46
views
Complexity for determining whether a given metric space is hyperconvex?
Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?
Definition: A metric space is said to be hyperconvex if ...
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
2
votes
3
answers
197
views
Is there a way to parametrize the configuration space of all convex polyhedra of a given combinatorial type as a convex set?
I'm sure this is easy/known, but I'm not hitting an appropriate search term for finding the answer and the coffee hasn't kicked in enough to come up with it myself:
Let $T$ be a simplicial 2-complex ...
- 185
1
vote
0
answers
49
views
On points in the interior of planar convex regions and inscribed triangles
Given any planar convex region C, it is easy to show that every point in the interior C is the mid point of at least one chord of C. Likewise,
Question: Is every point in the interior of C the ...
- 5,979
1
vote
1
answer
75
views
When do the centers of mass of a uniform convex planar region as a whole and of its boundary alone coincide?
Given a uniform planar convex region C, let us consider 2 centers of mass - the center of mass of the region as a whole and the center of mass of its boundary alone (assuming its boundary to have ...
- 5,979
1
vote
1
answer
119
views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem
$$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$
where a minimum is ...
- 11
2
votes
1
answer
132
views
Planar convex region maximizing the difference in 'orientation' between its smallest containing rectangle and largest contained rectangle
We say a rectangle has orientation $\theta$ if the vector from its center to the middle of its shortest side (parallel to the longest side) has some angle $\theta$ with X axis.
Consider a planar ...
- 5,979
0
votes
1
answer
241
views
Norm functions induced by convex bodies
Given a centrally symmetric convex body $K$ in the plane (with smooth boundary), it is easy to see that there exists a norm function $g:\mathbb{R}^2\to \mathbb{R}_{\geq 0}$ for which $K$ is the unit ...
- 191