Questions tagged [convex-geometry]

Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.

Filter by
Sorted by
Tagged with
-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{...

1
2 3 4 5
16