Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
410 questions
0
votes
0answers
23 views
Is there any kind of trigonometry analog for solids?
I'm looking for a general method of calculating angles in convex tetrahedra, a 3-dimensional analog of trigonometry. Have someone established such system in a formal way?
3
votes
1answer
34 views
How to approximate a 3x3 linear inequality constraint
Let $M$ be a $3\times3$ symmetric matrix (6 independent variables).
The following constraint:
$$M \succeq 0$$
is a convex linear matrix inequality (LMI), meaning that M is positive semidefinite.
I'...
0
votes
0answers
15 views
Strongly convex with respect to norm of Ellipsoid
In $\mathbb R^n$ with Euclidean norm $\|\cdot\|$, a convex set $\Omega$ is set to be strongly convex with respect to the norm $\|\cdot\|$ if there exists $\alpha>0$ such that for any $x,y\in \Omega$...
0
votes
0answers
27 views
the sum of many polytopes has round shape.?
I generate 1000 polytopes $P_1, \ldots, P_{1000}$ in $\mathbb R^{n}$, each of them has $m$ vertices that are $m$ rows of an $m\times n$ matrix
$A_i={\sf rand(m,n)}$. Then I take their sum $P=P_1+\...
0
votes
0answers
37 views
Show that a ball is contained in at least one overlapping convex set
Consider a convex domain $\Omega\subset\mathbb R^n$ and a collection of convex sets $A_i\in\Omega$, $i=1,2,...,N$, whose union contains $\Omega$. Define the $i$-th overlap $\kappa_i$ as the largest ...
0
votes
0answers
8 views
Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra
Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...
0
votes
0answers
22 views
Properties of Splitting Convex Sets
Say I have a convex set of $n$ dimensional polynomials that satisfy certain properties $P$.
I then want to split $P$ into two disjoint sets $P_U, P_S$ such that $P_S\cup P_U = P$ and $P_S \cap P_U = ...
1
vote
1answer
28 views
Alternating Projection Convergence Proof
Following the Convergence proof (on page 3) from Alternative Projection paper: https://web.stanford.edu/class/ee392o/alt_proj.pdf
I know intuitively how to show that both sequences {$ \left\lVert y_k ...
1
vote
0answers
37 views
Prove that a cone is convex if and only if it is closed under addition.
Let $K \subset \mathbb{R}^n$ be a cone.
A cone is defined as: $(\forall x\in K) \wedge (\forall \lambda>0) \Longrightarrow \lambda x\in K$.
Prove that: $K$ is convex $\Longleftrightarrow K$ is ...
0
votes
1answer
30 views
Boundedness of sublevelsets of strongly convex functions implies boundedness of second-order gradient
In page 460 of Stephen Boyd's "Convex Optimization", he described a property of strongly convex functions:
"The inequality (9.8) (i.e. $f(y) \geq f(x) + \nabla f(x)^T (y - x) + \frac{m}{2} \|y - x\|...
2
votes
1answer
143 views
+100
Stable strict local minimum implies local convexity
Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function.
We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is ...
3
votes
4answers
483 views
how to draw the space of such linear combinations?
We have the linear combination
$$ {2 \choose 1 } x_1 + {1 \choose 2} x_2 + {1 \choose -2} x_3 + {1 \choose 1} x_4 + {-1 \choose 0 } x_5 + {0 \choose -1 }x_6 $$
As $x_i \geq 0 $ is given, according ...
0
votes
0answers
42 views
a compact set with nonempty convex sections
Let $X = [0,1]^d$ be the unit cube in the $d$-dimensional Euclidean space.
For every $x \in X$ and every coordinate $i=1,2,\ldots,d$ denote by $x_{-i} := (x_j)_{j \neq i}$.
Given a set $Y \subseteq X$ ...
1
vote
2answers
25 views
Using Alternative Projection Algorithm to solve linear systems
We can find $x^*$ which converges to the intersection point of convex sets using Alternative projection algorithm.
A linear system $$Ax=b$$ can be considered as a set of hyperplanes $H_i := \{x \in ...
0
votes
2answers
29 views
Writing the equation of hyperplane separates a point and a convex set
Consider a point, $v$ outside a closed convex set $C$ and $\omega \in C$. Let $v^*$ be the orthogonol projection of $v$ onto $C$. Can I write the equation of the hyperplane goes through the projection ...
0
votes
1answer
33 views
Orthogonal projection of a vector onto convex set
What is the meaning of an orthogonal projection of a vector onto a convex set? I am familiar with orthogonal projection of a vector onto a vector space but I cannot ...
0
votes
2answers
56 views
Counterexample: Convex set which is NOT the intersection of half-spaces
half-space: either an open half-space, a closed half-space, or a set $H$ s.t. $$ H^{o} \subsetneq H \subsetneq \bar{H} \,,$$ where the relative interior $H^o$ is an open half-space and the relative ...
0
votes
1answer
23 views
Distance between the boundaries of a convex set and its shrunk version
Let $S$ be a compact convex set and $S'=\{x\in S: d(x, \partial S)\ge \delta\}$, where $d$ is the Euclidean distance and $\partial S$ is the boundary of $S$. Assume that we choose $\delta>0$ such ...
0
votes
0answers
7 views
Ratio volume convex body and smallest box containing that body
Let $V\subset \mathbb R^d$ be a convex compact set of positive volume. Write $C$ for the unit cube. Does there exist an $r>0$, depending only on $d$ and not on $V$, such that there exists an affine ...
0
votes
1answer
39 views
An Impossibility Theorem in $\mathbb{R}^3$
It's a trivial though verbose to note, that in $\mathbb{R}^2$ if you have a point $p$ contained between parallel lines $l_1, l_2$ and if $p$ is formed by the intersection of 2 rays $r_1, r_2$ (...
2
votes
0answers
84 views
Understanding whether a set of vectors is convex
I have a set $\Theta$ of vectors $\theta$ and I want to find whether $\Theta$ is convex. The difficulty that I have is related to some "peculiar" constraints that I impose on some components of $\...
1
vote
2answers
26 views
Algorithm for Finding a Conic Combination Giving the Zero Vector
Suppose I have a set of vectors $\{\mathbf s_1, \dots, \mathbf s_N\} \subset \mathbb Z^n$, and I want to find all conic combinations that give the zero vector. In other words, I want to find all ...
1
vote
1answer
21 views
How to conclude $ \left\lVert x_k - \bar x \right\rVert_2 \le \left\lVert x_0 - \bar x \right\rVert_2$
There are 2 intersecting convex sets and I am discussing about alternating algorithm related to those convex sets.
I obtain the following results
$ \left\lVert y_k - \bar x \right\rVert_2^2 \le \...
2
votes
0answers
40 views
The set of vectors whose coordinates are non-negative and sum to a number less than $1$
Let $n \in \{1,2,\dots\}$.
Consider the convex set consisting of all $(x_1,\dots,x_n) \in \mathbb{R}^n$ satisfying:
$x_i \geq 0$, $i \in \{1,\dots,n\}$
$x_1 + \cdots + x_n \leq 1$
Does this set ...
3
votes
0answers
44 views
What is known about these “transparent” polytopes?
I am looking for the name (if there is one), simple properties and possible literature for the following class of polytopes (by polytope I mean the convex hull of finitely man points in $\Bbb R^n,n\ge ...
1
vote
0answers
17 views
Valuation Property for mean width
For some polyhedron, $P$, define the mean width function,
$$H(P)=\sum_{e\in E} L_e(\pi - \delta_e)/(4\pi)$$
Where $E$ is the set of all edges of the polyhedron, $L_e$ is the length of edge $e$ and $\...
0
votes
0answers
15 views
The dual of a regular polyhedral cone is regular
A rational polyhedral cone in $\mathbb{R}^n$ is a set of the form
$$\sigma=\{\lambda_1x_1+\dots+\lambda_kx_k\in \mathbb{R}^n\mid \lambda_i\in \mathbb{R}_{\geq 0} \; \;\forall \, 1\leq i\leq k\}$$
for ...
3
votes
1answer
54 views
Estimate the volume of Voronoi cell
Let given a ball of radius $\alpha$ centered in point $u$ in $d$-dimensional space. Let given a sample of $n$ uniformly distributed vectors $x_i$ ($i = 1,\dots,n$) inside the ball. For each vector $...
0
votes
1answer
22 views
Interpreting strong convexity geometrically
According to the definition, function $f$ is strongly convex if and only if for all $x$ and $y$ where $t>0$,
$$ f(x) \geq f(y) + \langle\nabla f(y), x-y\rangle + \frac{\gamma}{2}\Vert x-y\Vert^...
0
votes
0answers
34 views
Convex Hulls and maximizing volume
I thought of a function (recreational mathematics) and wonder if there is any existing math about it. Google searching did not turn anything up.
Let $n\in \mathbb{N}$ be the dimension, and $x\in \...
1
vote
1answer
29 views
Polytope in Minkowski sum
Is the following statement true?
Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=\{a+b: a\in A, b\in B\}$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Q\...
0
votes
0answers
31 views
Minimal/Small convex partition of a set of points
Given a set of $n$ point tuples $(x_1, y_1), \ldots, (x_n, y_n)$ with $x_i, y_i \in \mathbb{R}^m$. I am interested in a partition of a hypercube the points $x_1, \ldots, x_n, y_1, \ldots, y_n$ are ...
0
votes
1answer
62 views
Lower bound for the number of edges in a Minkowski sum
I was wondering whether the following statement about a Minkowski sum of two polytopes is true:
Let $P=P_1 + P_2$ be the Minkowski sum of two polytopes $P_1$ and $P_2$ in $\Bbb R^n$, i.e. $P=\{p_1+...
1
vote
1answer
32 views
Why recession cone of a set $C$ is indeed a cone?
The recession cone of a set $C$, i.e., $R_C$ is defined as the set of all vectors $y$ such that for each $x \in C$, $x-ty \in C$ for all $t\geq 0$.
On the other hand, a set $S$ is called a cone, if ...
0
votes
1answer
28 views
Does the following set of polynomials non-negative on the interval $[0,1]^2$ positively span all non-negative polynomials on the interval?
Given the following set of polynomials that are non-negative on the interval $[0,1]^2$
$$
B = \{x, 1-x, y,1-y,xy,x-xy,y-xy,1-x-y+xy\} = \{b_1,b_2,...,b_8\}
$$
Can we definitively say that all ...
2
votes
1answer
124 views
Convex side of a spherical mirror
A convex set has the property that if you take any two points in the
set and draw the line segment connecting those two points, that line
segment lies entirely in the set.
My textbook says that ...
0
votes
1answer
36 views
About theory of convex cones
Working with positive semidefinite matrices I discovered the concept of convex cone. That is, a subset $C$ of a vector space $V$ that is closed under positive linear combinations. I had never read ...
1
vote
0answers
29 views
Is the dual of a cone can be defined by the dual of the closure of its convex hull?
Let $K$ be a nonempty cone in $\mathbb{R}^n$. We denote the dual of a cone $K$ as $K^*$. Show that $$K^*=(\mathop{\boldsymbol{cl}} \mathop{\boldsymbol{conv}}K)^*$$
How can we describe the closure of ...
1
vote
0answers
22 views
Intuition of convex set separation hyper-plane
According to the hyperplane separation theorem
Let A and B be two disjoint nonempty convex subsets of Rn. Then there exists a non-zero vector v and a real number c such that
$$ <x,v> \le c $$ ...
1
vote
0answers
16 views
Is the volume of the largest hyperrectangle inscribed in a convex polytope always larger than some fixed proportion of the polytopes volume?
Fix a positive integer $n$. For any convex polytope $\mathcal{P}$ of dimension $n$, let $V_\mathcal{P}$ denote its volume and let $K_{\mathcal{P}}$ denote the maximum possible volume of an $n$-...
0
votes
1answer
33 views
Does there exist a basis of a Convex Cone
We are given a set $C \subset V$, where $V$ is a vector space. $C$ is a convex cone, so it has the following properties
$$
0 \in C
$$
$$
C+C \in C
$$
$$
x\cdot C\in C\mid x\in\mathbb{R} \land x\...
0
votes
0answers
22 views
Lower-bounding Gaussian inner products with high probability
Suppose that $K\subseteq \mathbb R^n$ is a proper convex set with piecewise smooth boundary and that $0 \in K$. Assume that $x \in K$ and let $z \sim \mathcal{N}(0, I_n)$ be a Gaussian random vector. ...
3
votes
0answers
47 views
An inequality relation of convex decreasing function
Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be convex decreasing function. I read from somewhere that we have the following inequality:
For any $x\leq y$ and $t\geq 0$, $f(x+t) - f(x) \leq f(y +t) -f(...
3
votes
1answer
28 views
Separation of subsets of $\mathbb{R}^n$ with the graph of a convex function
Let $A, B \subset \mathbb{R}^n$ be compact and disjoint sets. Assume that there exists a $(n-1)$-dimensional surface $S$ such that separates the $A$ and $B$, i.e. there exists $C \subset \mathbb{R}^n$...
0
votes
0answers
31 views
Analogue of subcontractive property of Hilbert space projections for general Banach spaces
Let $ X $ be a Banach space over the reals with norm $ \| \cdot \| $. Let $ C $ be a nonempty closed convex subset of $ X $. Suppose $ a \notin C $. Is it true that there exists $ b \in C $ such that $...
4
votes
1answer
36 views
Convexity of a convex set minus points close to its frontier.
Let $d\geq 1$. Let $K\subset\Bbb{R}^d$ be a convex set, $\varepsilon>0$, and $K(\varepsilon)\subset K$ the points of $K$ whose distance to $\partial K$ is less than $\varepsilon$.
Is $K\setminus K(...
0
votes
0answers
7 views
What separates a cyclic polytope from a projective polytope?
I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries.
The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
0
votes
1answer
21 views
Inexistence of norm in $\mathbb{R}^2$
Prove that there is no norm in $\mathbb{R}^2$ such that the balls are six-pointed stars.
I'm aware this has to do with connexity, but not sure how to procced... If the star has empty interior then it'...
0
votes
0answers
49 views
Area calculation in a convex quadrilateral
I´ve some problem with the area calculation in a convex quadrilateral. My problem looks like this:
Let $ABCD$ be a convex quadrilateral with points $X$ and $Y$ on side $AB$ so that $AX = XY = YB$, ...
2
votes
1answer
44 views
Convex hull of set of points inside a half-space
We place ourselves in $\Bbb{R}^d$, for $d\geq 1$. Let $\mathcal{h}$ a hyperplane, and let $S$ be a finite set of points that all lie in one of the (closed) half-spaces limited by $h$.
Let $C$ denote ...
