Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...