Questions tagged [convex-geometry]
Use this tag when posting questions related to the concept of convexity and geometry. For example, for convex polygons.
1
vote
0answers
27 views
Convex piecewise linear functions - partitioned vs max representation
I know that convex piecewise linear function $f$ can be defined in two closely related ways -
There exist $Q \subseteq P(X)$ s.t. $\bigcup Q = X$ and on every $A \in Q$ the function is linear (...
3
votes
1answer
41 views
Why can't a vertex of a $d$-dimensional polytope be in fewer than $d$ edges?
This is motivated by the definition of simple polytopes: if all vertices of a $d$-dimensional convex polytope $P$ are in exactly $d$ edges (i.e. $1$-dimensional faces of $P$), then $P$ is simple.
I ...
2
votes
0answers
37 views
Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \mathbb{R}^n$where $K$ is a cone in $\mathbb{R}^n$.
Let $K$ be a closed convex set in $\mathbb{R}^n$, $K^*$ be the dual cone of $K$, and $\prod_K(x)$ denote the Euclidean projection onto $K$.
Show that $\prod_K(x)+\prod_{-K^*}(x)=x$ $\forall x \in \...
1
vote
1answer
25 views
Show minimum distance to a convex set is a convex function.
Show that
$$
g(x)=\inf_{z \in C}\|x-z\|
$$
where $g:\mathbb{R}^n \rightarrow \mathbb{R}$, $C$ is a convex set in $\mathbb{R}^n$ (nor close neither bounded), and $\|\cdot\|$ is a norm on $\mathbb{R}^...
0
votes
0answers
28 views
Do $|f'|$ and $f$ have the same minimisers for strictly convex functions?
Call the differentiable function $f: \mathbb K \to \mathbb R$ on some compact convex $K \subset \mathbb R^n$strictly convex to mean $f(\lambda x + (1- \lambda)y) < \lambda f(x) + (1-\lambda)f(y)$ ...
0
votes
0answers
11 views
$A_1(B)+A_2(B)=(A_1+A_2)(B)$
Let $B=B_1(0)$ be the unit ball in $R^n$, $A_1$ and $A_2$ be two invertible matrixes, when will $A_1(B)+A_2(B)=(A_1+A_2)(B)$ if we add some conditions on $A_1$ and $A_2$?
Obviously that the inclusion ...
2
votes
0answers
17 views
Can a Jordan convex curve be rewritten as the image of 4 monotone real functions?
Is it true that a smooth Jordan curve $C \subseteq \mathbb{R}^2$ that is convex (in the sense that the region bounded by this curve is convex) can be rewritten as the union of the image sets of 4 ...
0
votes
0answers
17 views
Why cones are represented by matrices
I see there are multiple definitions of cones:
1) Cone $K$ is defines as a set of vertices $[x_1, x_2, x_3, ...]$ with $[0]$ as the base (starting point)
2) Cone $K$ is defined as intersection of ...
1
vote
0answers
11 views
How to maintain concavity while normalising a set of samples?
I have a set of 2D samples that approximate a geometric shape that I am trying to construct. Due to measuring errors some samples are slightly off, generating "jaggy" artifacts in the surface of the ...
4
votes
0answers
28 views
For two polytopes $A$ and $B$, when can we find $C$ such that $A=B+C$?
$A\subset\mathbb{R}^d$ is a polytope if $A$ equals the convex hull of some finite set.
For any two sets $B$ and $C$, $B+C\equiv\{x+y:x\in B,y\in C\}$.
My question:
Let $A$ and $B$ be polytopes in $\...
3
votes
2answers
61 views
Why is $\alpha^n\beta^m+\alpha^m\beta^n\le\alpha^s\beta^t+\alpha^t\beta^s$ if $(n,m)\preceq(s,t)$?
I've recently come across the following statement:
$$\alpha^n\beta^m+\alpha^m\beta^n\le\alpha^s\beta^t+\alpha^t\beta^s$$
for $\alpha,\beta\ge0$, $n,m,s,t\in\mathbb N_+$, $n+m=s+t$, and $(n,m)\preceq(s,...
1
vote
1answer
14 views
Prove that the normal cone $N_{\text{gph}(f)}$ of the graph of the affine function $f$ has the given form.
GIVEN
Let $f : \mathbb{R}^n \longrightarrow \mathbb{R}^m$ be the affine function defined by $f(x) = Mx + b$ where $M$ is an $m \times n$ matrix and $b$ is a vector in $\mathbb{R}^m$. Prove that for $(...
0
votes
2answers
40 views
Find the convex subdifferential $\partial d_K$ of the distance function $d_K$ associated to a convex set $K$ at in-set points $x_0 \in K$.
GIVEN
Let $K \subset \mathbb{R}^n$ be a nonempty, closed and convex set. The associated distance function is $d_K$. Find the subdifferential $\partial d_K(x_0)$ for all $x_0 \in K$.
USEFUL ...
1
vote
0answers
29 views
Determine the normal and tangent cones $N_C (x)$ and $T_C (x)$ for all $x \in C$.
GIVEN
Let $C = \{ x \in \mathbb{R}^n : Ax=b \}$, where $A$ is an $m \times n$ matrix and $b \in \mathbb{R}^m$.
Determine the normal cone $N_C(x)$ and $T_C(x)$ for all $x \in C$.
USEFUL ...
1
vote
1answer
32 views
Show that support function of a set $S$ and support function of the closure of that set $\bar{S}$ are equal.
Let $S\subseteq \mathbb{R}^n$.
The support function of set $S$ is defined as the following
$$
\sigma_S(x)=\sup_{y \in S} x^Ty
$$
where $x \in \mathbb{R}^n$.
Show that $\sigma_S(x)=\sigma_{\bar{S}}(...
1
vote
0answers
57 views
Proof of Caratheodory's Theorem
I am trying to understand the proof of Carathoeodory theorem, I am following the one given by wikipedia.
This is what I have understood so far :
First we are taking any point then saying it can be ...
0
votes
0answers
12 views
Caratheodory's theorem applied to a disk
Here's the statement that was given in my class.
Caratheorody's theorem: Let M $\subset$ $\mathbb R^n$. Then conv$(M)$ is the set of all convex combinations of at most n+1 points from M.
Am I ...
0
votes
0answers
57 views
A both strictly quasi-concave and quasi-convex function in $R^{2}_{+}$?
Is there an example of both strictly quasi-concave and strictly quasi-convex function in $R^{2}_{+}$? Thanks so much.
0
votes
0answers
15 views
Why support function describes the (signed) distances of supporting hyperplanes of A from the origin?
The support function of a set $A \in \mathbb{R}^n$ is defined as the following
$$
S_A(x)=\sup_{y \in A} x^Ty
$$
where $x \in \mathbb{R}^n$.
In Wikipedia:
Support function it says support function ...
0
votes
0answers
21 views
Is this a convex set?
Is set A convex when set A = the union of all points on a circle and all points in the interior of the circle, minus point R?
1
vote
1answer
59 views
Show that every point is an extreme point of the given convex set
Show that for any $a,b \in \mathbb{R}$ every point
$p=\begin{pmatrix} s\\ t \end{pmatrix}$ with property
$\frac{s^2}{a^2}+\frac{t^2}{b^2}=1$ is an extreme point of the convex
set $E(a,b)=...
1
vote
0answers
22 views
Are there convex surfaces with negative Gaussian curvature?
I've just started reading about convex surfaces and there are a few things which are breaking my intuition. According to this page: "Minkowski proved the existence of a closed convex surface with ...
1
vote
0answers
27 views
A bound for the radius of a convex set of diameter $d$ in $\mathbb{R}^p$?
Given $C$ the convex hull of the points $Y_1,\ldots,Y_K$ in $\mathbb{R}^p$. Call $d$, the diameter of $C$. Suppose without loss of generality that $\|Y_1-Y_2\|=d$. Take $Y_0=(Y_1+Y_2)/2$. I need an ...
6
votes
1answer
46 views
Generalized convex combination using matrices
A convex combination between two points $x_1$ and $x_2$ in $\mathbb{R}^N$ is defined as:
$$ x(\lambda) = \lambda x_1 + (1-\lambda)x_2, \qquad \lambda \in [0,1].$$
Here $x(0) = x_2$, $x(1) = x_1$, ...
0
votes
1answer
39 views
write a point in the plane as a convex combination
Suppose we have a polyhedron with vertices (extreme points) $e_1 = (4,5)$, $e_2 = (0,3)$ , $e_3=(1,2)$, $e_4=(6,0)$ and extreme direction $d_1 = (1,0)$. I want to write the vector $(10,1)$ as convex ...
1
vote
1answer
47 views
Convergence of subgradients
Let $C$ be a compact, convex subset of a Hilbert space $\mathcal{H}$ and $g:\mathcal{H}\to\mathbb{R}\cup\infty$ an extended valued, proper, lower semicontinuous, convex function. Also, assume that $C\...
0
votes
0answers
22 views
Mean width distance and containment of ball
Let $B_n$ denote the Euclidean unit ball in $\Bbb R^n$, and let $P\subset B_n$ be a polytope such that $w(B_n)-w(P) \leq \epsilon$, where $w(K)=2\int_{\Bbb S^{n-1}} h_K(u)\,d\sigma(u)$ is the mean ...
0
votes
0answers
35 views
Generalized inequality (preservation under limits)
I know this question may seem too broad or primarily opinion based but please bear with me. I have an ambiguity on my exercise context. I'm asked to prove that Generalized Inequality is preserved ...
0
votes
1answer
18 views
Why does a d-polytope being k-neighborly for 1 <= k <= d imply the polytope is neighborly for all k' such that 1 <= k' <= k?
I'm reading Grunbaum's Convex Polytopes where he cites the following theorem in a proof by contradiction for a larger theorem:
"If $P$ is a $k$-neighborly $d$-polytope, and if $1 \le k' \le k$, ...
1
vote
1answer
52 views
Convexity of trace$(X^{-1})$
Prove that the function $$ f(X) = \operatorname{trace}(X^{−1}) $$ is convex on the domain $S^n_{++}$.
I was given the hint to try using line restriction. So I am trying to prove that $$ g(t) = f(x+ty)...
0
votes
0answers
28 views
Number of intersection points of an ellipse and a circle
I am taught that there will be maximum 4 intersection points between an ellipse and a circle, as it is described here
http://mathworld.wolfram.com/Circle-EllipseIntersection.html
Is there a way to ...
2
votes
0answers
18 views
Convert a vector of distances to a normalized vector of similarities
I'm struggling to find a way to solve this problem.
I have derived a $m \times n$ matrix containing in each row the Mahalanobis distance from a certain centroid. So at the end I have $m$ rows each ...
0
votes
1answer
25 views
How to find coordinates of non intersecting areas between two intersecting polygons?
I have two polygons that have some intersection. Then there are some areas which belong to either Polygon1 or Polygon2.
How can I find the coordinates of those areas?
Is there any algorithm to do ...
1
vote
0answers
67 views
Parallelogram containing symmetric, compact, convex set
Assume that $V=\mathbb{R}^2$ has a norm $\|\ \|$. So $V$ is a metric space $d(x,y)=\| x-y\|$. Assume that there is unique path attaining distance $d$ between any two points. And assume that $C$ is $\|\...
0
votes
1answer
19 views
Is there a unique minimizing geodesic to a geodesically convex set?
Let $(\mathcal M,g)$ be a geodesically complete Riemannian manifold, and $\mathcal X\subset \mathcal M$ be a compact, geodesically convex subset.
It is trivial that for any point $x\in\mathcal M$, ...
0
votes
0answers
29 views
Whether a Convex function is a semi-algebraic function, a convex set is a semi-algebraic set?
Definition: A semi-algebraic set is a subset described by equality and inequality of polynomials. For example: $\left\lbrace x \;|\; f(x)>0, \;g(x)=0, \ldots \right\rbrace$.
Graph $(x,f(x))$ of a ...
0
votes
1answer
40 views
What is the inverse of this transformation from a rectangle to a quadrilateral?
Given the following rectangles:
one can map any point $(x, y)$ from the rectangle to a point $P$ on the quadrilateral using the following steps:
Define linear interpolation as $l(p0, p1, t) = p0 + t(...
0
votes
0answers
26 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
46 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
25 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
32 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
42 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
12 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,...
1
vote
1answer
31 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
81 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
35 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\|...
9
votes
2answers
450 views
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
525 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
46 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
28 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 ...
