Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
751
questions
-1
votes
1answer
35 views
convex sets in convex optimization
How to prove that the following set is not convex?
$$M = \left\{ \mathbb{R}^{3}: x_{1}x_{2}x_{3}\le 1,x_{1}+x_{3}\ge 2,x_{1} \ge 0 \right\}$$
Thanks for any help.
I tried to write it down as ...
0
votes
2answers
47 views
Convex hulls of a set and its subsets
Suppose that $P$ is a set of $k>3$ points in $\mathbb{R}^2$. Let $\mathrm{Conv}(P)$ be the convex hull of $P$.
I think that the following claim is true (I know how to prove it geometrically) :
$\...
1
vote
1answer
29 views
Convex hull and supporting hyperplanes
Let $S \subseteq \mathbb{R}^n$ be a nonempty set and $p \in S$ be a point. A (closed) halfspace $H\subseteq \mathbb{R}^n$ is said to support $S$ at $p$ if $S \subseteq H$ and $p \in \partial H$. For ...
1
vote
0answers
10 views
Convex geometric realizability of abstract polyhedron with congruent isosceles obtuse triangular faces
Take an isosceles obtuse triangle of the form
with $\alpha = \frac{n-1}{n}\pi$ for some $n \geq 3$ ($\beta=\frac{\pi}{2n}$)
If you look at the class of convex polyhedra such that each face is ...
0
votes
0answers
6 views
find planar dominating permutation with positive basis.
Given a basis/ordered set $X = (x_1, x_2, \cdots x_n), x_i \in \mathbf{R}^2_+$. where no any two elements is co-linear.
We can apply a permutation $p_j$ of $n$ elements. $p_j(X) = (x_2, x_1, \cdots, ...
3
votes
1answer
40 views
Do convex combinations of projection matrices majorize the probability vector, i.e. $\sum_k p_k P_k\succeq \boldsymbol p$?
Consider a convex combination of normal projection matrices with positive coefficients: $$C\equiv \sum_k p_k P_k,$$
where $p_k>0$, $\sum_k p_k=1$, and $P_k=P_k^\dagger=P_k^2$.
If the $P_k$ are ...
0
votes
1answer
16 views
Fixed area polygon maximize the area of its convex hull
For a fixed area, what kind of polygon that would obtain the maximum area of its convex hull.
For e.g. area 1 square, since it’s already convex, so the convex hull having area 1 too. Would there be ...
1
vote
1answer
25 views
How does strong convexity behave under Minkowski sums?
Suppose we have two convex sets $A,B$. It is straightforward to show the sum $A+B = \{a+b:a \in A,b\in B\}$ is convex. For take any $c=a+b$ and $c'=a'+b'$ and consider the convex combination
$$xc+(1-x)...
1
vote
2answers
44 views
If for every $\alpha$ the set $A_{\alpha}= \{x : f(x) < \alpha\}$ is convex, then $f$ is convex. Is it true?
I was asked to prove or disprove this statement:
If for every $\alpha$ the set $A_{\alpha} = \{x : f(x) < \alpha\}$ is convex, then $f$ is convex.
I tried by definition to solve it, but I got ...
0
votes
0answers
19 views
convex hull of partition of monotonic polygonal chain
Given A ordered set of vectors $X = (x_1, x_2, \cdots, x_n), x_i \in \mathbb R^2_+$.
The prefix sum of $X$ is $S = (x_1, x_1+x_2, \cdots, \sum_{i=1}^n x_i)$.
Connect the consecutive elements of $S$ ...
1
vote
0answers
29 views
Maximize area spanned by convex hull of a permutation
Given an ordered set $X = (x_1, x_2, \dots, x_n), x_i \in \Bbb R^2$ and a permutation $P$ defined on $X$ and that shuffles the order of the elements in $X$,
$$P(X) := (p_1, p_2, \dots, p_n)$$
and we ...
1
vote
1answer
48 views
Given convex differentiable function $h: R^m \to R$, what is geometric interpretation of $h(x)/\|\nabla h(x)\|$ vis à vis the level-set $h=0$?
Let $h:\mathbb R^m \to \mathbb R$ be a convex diifferentiable function and define $C_h := \{x \in \mathbb R^m \mid h(x) = 0\}$, assumed to be non-empty.
Question. Given $x \in \mathbb R^m$ such that $...
3
votes
0answers
19 views
Extreme points of prefix sum and prefix sum of subsets.
Given an ordered set of points $P = (p_1, p_2, \cdots, p_n)$, where $p_i \in R^d$.
The prefix sum set $S$ of $P$ is defined as
$$
S = (p_1, p_1+p_2, p_1+p_2+p_3, \cdots, \sum_{i=1}^n p_i)
$$
And there ...
0
votes
1answer
34 views
Can a part of the spherical surface be convex? [closed]
In my opinion, the line between two arbitrary points on the surface of a sphere is never part of the surface (the line is inside of the sphere). Hence a part of the spherical surface can't be convex.
...
0
votes
0answers
26 views
Normal vector of a separating or supporting hyperplane
I would like to ask how to find a normal vector $\gamma$ for a separating or supporting hyperplane for the following sets $A$ and points $d$:
$1.\quad A=\{(x,y):x\ge 0,y \ge 0\}$ and $d=(-1,-1)$
$2.\...
0
votes
1answer
33 views
How to find convex hull of functions?
How does one go about finding convex hulls of functions.
For example the equation $x_{1}^{2} + x_{2}^{2} = 1$.
How I attempted to solve this problem was I selected the extreme points $(1,0)$; $(0,1)$; ...
0
votes
1answer
56 views
Proof that feasible region of linear program is exactly one convex region
I have the following linear program:
$$\text{max b}\\\ \text{subject to} \quad \vec{x} \cdot \vec{r}_j \geq b \quad \forall j \quad \text{with} \quad x_i \in \mathbb{R}, \sum_{i=1}^N x_i=1,$$
where $\...
1
vote
1answer
30 views
Caratheodory's theorem for vectors in a cone
I am studying the book "matching theory" by Lovasz and Plummer, and I found the following statement (page 257):
Comparing it with Caratheodory's theorem in Wikipedia reveals two differences:...
0
votes
2answers
37 views
Conditions necessary to ensure unique minimizer of $\min_x \frac{1}{2} ‖Ax−b‖^2 $?
I'm doing a few exercises of convex optimization using notes for a previous course offering, and one of them asks for conditions necessary to ensure unique minimizer. I looked at the solution, but I ...
3
votes
1answer
58 views
Fenchel conjugate of convex combination of two norms
Let $\tau \in [0,1]$. Let us define the norm $\Omega(x)=\tau\|x\|_1+(1-\tau)\|x\|_{1,2}$; where
$$
\|x\|_{1,2}=\sqrt{\sum_{g \in \mathcal{G}} \left(\sum_{i \in g} |x_i|\right)^2}
$$
is the exclusive ...
0
votes
1answer
29 views
Finding a Lower Envelope of a Compact Convex Set in $R^2$
Consider the compact convex set $S$ in $\mathbb{R}^2$ with three extreme points $(0, 0)$, $(1, 1)$, and $(0, 1)$, i.e., $S$ is a triangle. To find the lower convex envelope $f(t)$ of $S$, where $t\in[...
2
votes
1answer
84 views
How to find the closest line from a convex hull to an arbitrary point
I'm stuck into a control system problem with geometrical interpretation.
I have a set of linear equations $Ax\leq b$ which form a convex hull (more precisely a parallelogram), where $A \in \mathbb{R}^{...
0
votes
1answer
27 views
Convex curve, asymptote
How can a convex increasing curve have an horizontal asymptote?
I read that in a paper, but I just can't see how this is possible.
The situation is the the following: $a,b$ are some constants, we have ...
0
votes
1answer
27 views
Projection onto a closed convex set in a general Hilbert space
Let $E$ denote a real Hilbert space and suppose $G \subset E$ is a nonempty closed convex set. I know that in this case, there is a unique nearest point in $G$ to each $x \in E$. Call this point $P_G(...
0
votes
0answers
25 views
first order condition for quasiconvex functions
I need to prove the following statement. Let $ f:\mathbb{R}^{n}\to \mathbb{R}$ be a differentiable function. If $\forall x,y\in$ dom$(f)$, $f(y)\le f(x)\Rightarrow \nabla f(x)^{T}(y-x)\le 0$, then $f$...
0
votes
0answers
26 views
On Erdös-Szekeres convex polygons lower bound
I have problems with the construction of $2^{n-2}$ points that contain no n-gon, particulary, the proof of the book "Open Problems in Mathematics".
The proof sais that:
For $i = 0, ..., n-2$ ...
0
votes
0answers
21 views
A question about the curvature of a clifford torus - convex and concave
I am a complete novice at math--actually an artist by trade but interested in topology and geometry. I have a weird question about the clifford torus. I ask you to please answer in as simple ...
0
votes
1answer
26 views
Understanding Helly's theorem
The following is part of the inductive step in Wiki's proof for Helly's theorem. Why is it true?
...
1
vote
0answers
22 views
Does Radon's theorem assume distinct $d+2$ points?
I'm reading Wikipedia's proof for Radon's theorem and wondering whether it still holds in case $x_1, x_2, \ldots, x_{d+2}$ aren't distinct.
2
votes
1answer
25 views
3 chords inclined at $\pi/3$ of a convex closed curve that intersect at their midpoint always exist
In "The penguin dictionary of curious and interesting geometry" David Wells mentions the following property of closed convex curves without a reference nor a proof.
"Given any closed ...
0
votes
0answers
13 views
Explicit tail bound for coordinates of uniform random vector on euclidean ball in high-dimensions
Let $X$ be drawn uniformly at random from a euclidean ball in $\mathbb R^n$ (the dimensionality $n$ is large!) around the origin and of finite radius, and let $M$ be the median of $|X_1|$. In Super-...
3
votes
1answer
44 views
Would any two consecutive extreme points on a convex hull can be linearly projected still being extreme?
Given two extreme points on a convex hull, if the straight line connects them is on the boundary , they are consecutive. Would there always exits a linear projection into lower dimension such that ...
2
votes
1answer
84 views
Showing triangulation of equilateral triangle is non-regular
I am trying to show that this triangulation is non-regular (sometimes called non-convex I think). By regular I mean there exists a convex function from the triangulation to $\mathbb{R}$ such that the ...
8
votes
1answer
69 views
Biggest convex set inside a concave unit ball
Denote the unit ball for the $p$-norm in $\mathbb{R}^N$ with $p \in (0,1]$, $$S_p^N = \Big \{ x \in \mathbb{R}^N,\ \Big(\sum \limits_{i=1}^N |x_i|^p\Big)^{1/p} \le 1 \Big\}$$
We want to find a convex ...
0
votes
2answers
23 views
Is the function convex?
Let's have the following function $f:\mathbb{R}^{2}\to\mathbb{R}$ defined by $|x+y|$, is it convex?
We have $\lambda\in (0,1),x,y\in$ dom$(f)$, so $|\lambda x+(1-\lambda)y|\le \lambda |x| + (1-\lambda)...
0
votes
0answers
17 views
Convex hull in different coordinate system
Given a set of points $X \subset R^n$, points are the row of $X$. We can find it's Convex hull $CH(X)$. And assuming the $X$ here are in cartesian coordinate.
There are many other coordinate systems, ...
2
votes
2answers
25 views
proving an inequality involving projections
Let $S \subset \mathbb{R}^n$ be a convex and closed set. Show that, given $x, y \in \mathbb{R}^n$:
$$\|\operatorname{proj}_S(x) - \operatorname{proj}_S(y)\| \leq \|x - y\|$$
This questions seems to be ...
0
votes
0answers
14 views
Minimize Maximal Angle at Vertex of 3d Convex Hull
I am looking for some results about three dimensional geometry.
I have a three dimensional convex hull.
Now, pick one vertex of the convex hull and find a vector that points from this vertex towards ...
0
votes
0answers
47 views
Proving that a set is convex
Is the following set $A=\{x\in\mathbb R^{n}:||x-z||\le||x-y||,\forall y\in K, K\subset\mathbb R^{n} \}$ convex? I need to prove it according to definition.
We have $x_{1},x_{2}\in A, \lambda\in (0,1)...
1
vote
2answers
35 views
Is it a convex set?
I have the following set
$$A = \{ (x,y) \in \Bbb R^{2} : \log x + y^{2}\ge 1, x \ge 1, y \ge 0 \}$$
and I need to know if it's convex or not. I tried to have a look at this function $-\log x-y^{2}$, ...
1
vote
2answers
67 views
Does convexity around a point imply the function is above the tangent at that point?
Let $\phi:\mathbb [0,\infty) \to [0,\infty)$ be a $C^2$ function, and let $c>0$ be a constant.
Suppose that for any $x_1,x_2>0, \alpha \in [0,1]$ satisfying $\alpha x_1 + (1- \alpha)x_2 =c$, we ...
1
vote
2answers
25 views
What’s the name for component constraint for compact convex set Cartesian products? And is the subset still convex?
Given one compact convex set $ X \subset \mathbf{R}^n$.
The cartesian product $Y = X \times X \subset \mathbf{R}^{2n} = \{(x_1, x_2)|x_1 \in X \text{ and } x_2\in X \}$ is going to be compact convex ...
1
vote
1answer
40 views
How do dihedral angles grow with number of edges in Euclidean polyhedra?
Consider a convex polyhedron $\mathcal{P}$ in $\mathbb{E}^3$ with $n$ edges. By convex polyhedron, I mean the convex hull of a finite set of points in $\mathbb{E}^3$ whose affine hull is all of $\...
2
votes
0answers
33 views
Can the convex hull be characterised as an intersection of half-spaces?
The convex hull $[X]$ of a set $X \subset \mathbb R^d$ is the set of all convex combinations $$[X] = \left\{a_1 x_1 + \ldots + a_n x_n: x_i \in X, a_i \ge 0, \sum_{i=1}^n a_i=1\right\}$$ of elements ...
0
votes
2answers
23 views
Is Inverse Cartesian product of convex set still convex?
Given two compact convex set $X \subset \mathbf{R}^2, Y \subset \mathbf{R}^2 $.
The Cartesian product $Z := X \times Y \subset \mathbf{R}^4$ Is again a convex subset.
Is the low dimension projection ...
1
vote
2answers
25 views
lift of the boundary of the projection of a convex body
Let $M\subset\mathbb{R}^3$ be a (compact) convex body and denote $\pi:(x, y, z)\to(x,y)$ the projection to the $xy$-plane. The image $\pi(M)$ is a convex shape on $\mathbb{R}^2$, and has a boundary $B=...
0
votes
0answers
77 views
How to build a linear map between vectors in $\mathbb{R}^n$ and a convex cone in $\mathbb{S}^n$
Let $x_a, x_b, x_c\in\mathbb{R}^n$, I'm looking for a linear transformation between the two vectors $x_a, x_b$, and the cone $K_c$ whose axis passes by $x_c$. I initially had the convex conbination $...
1
vote
1answer
21 views
'Shrunken Version' of a convex set is also convex
I'm trying to show that for a convex set $K$ in $\mathbb{R}^n $ (possibly bounded, if that makes things easier), the set $K_{\epsilon}:= \{x\in K: \text{dist}(x,\partial K)>\epsilon\}$ is also ...
0
votes
1answer
26 views
If a convex combination of conformal matrices is conformal, are they all proportional?
$\newcommand{\CO}{\text{CO}}$
$\newcommand{\SO}{\text{SO}}$
$\newcommand{\dist}{\text{dist}}$
Let
$\CO(2) =\{\lambda R : R \in \SO(2)\, | \, \lambda > 0\} $ be the set of $2 \times 2$ conformal ...
0
votes
0answers
15 views
Optimization function jointly over continue variable and discrete set
I want to minimize function $\underset{T,\alpha }{\mathop{\min }}\,F\left( T,\alpha \right)$, where T is continue variable and $\alpha$ is a subset of $\beta$ with constant c members, i.e.
$\begin{...
