All Questions
Tagged with convex-optimization mg.metric-geometry
20 questions
1
vote
0
answers
95
views
Distance between two convex sets
Setting
If $A$ an $B$ are two symmetric matrices, we denote by $A >B$ when the matrice $A-B$ is definite positive.
In $\left(\mathbb{R}^{*}_{+} \right)^4$, consider the convex set $$ \Lambda = \...
- 125
3
votes
0
answers
87
views
Instances of c-concavity outside of optimal transport?
Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \...
- 232
1
vote
0
answers
61
views
Fitting a convex polytope with 𝑛 facets between two nested spheres
This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
1
vote
0
answers
121
views
John and Lowner ellipsoid
I am looking at a proof to show that Lowner ellipsoids are unique for centrally symmetric convex body $K$. I want to show basically that
$$
\DeclareMathOperator{\Vol}{Vol}\DeclareMathOperator{\Low}{...
- 11
0
votes
1
answer
101
views
Estimation via projecting onto a convex body
Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
- 773
4
votes
2
answers
415
views
Selecting vertices in a convex polygon
Given $n$ vertices of a convex polygon in $\mathbb{R}^2$, selecting two points that are furthest apart is done by finding the diameter in a convex polygon. But how can one select three vertices such ...
- 51
0
votes
0
answers
44
views
Let $A,B,C$ be centrally-symmetric convex bodies. What is this function $G(x,y) := \sup_{b \in B}\inf_{a \in A} a^T x - b^T y + \|a-b\|_C$?
Let $A$, $B$, and $C$ be centrally-symmeric convex bodies in $\mathbb R^n$. Note that any such set can such set induces a norm $\|\cdot\|_C$ on $\mathbb R^n$ defined by $\|x\|_C := \sup_{c \in C}c^\...
- 6,853
6
votes
1
answer
176
views
Subsets of a ball/sphere with the largest sum of distances
$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$Let $B_d$ and $S_{d-1}$ denote, respectively, the closed unit ball and the unit sphere in $\R^d$. Let us say that a finite subset $F$ of $B_d$ is ...
- 128k
4
votes
0
answers
229
views
How to find the dimension of the polar cone of a convex cone generated by some given vectors
Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
- 461
5
votes
0
answers
135
views
Conv A = Dual B
I have two cones $A$ and $B$ in a Euclidean space.
I want to show that $\mathrm{Conv}\,A=\mathrm{Dual}\,B$; that is, $a\in\mathrm{Conv}\,A$ if and only if $\langle a,b\rangle\ge 0$ for any $b\in B$.
...
- 45k
3
votes
0
answers
240
views
Optimization with parametric constraints: solution maps
For constrained optimization problems
$$ \begin{array}{ll} \min\limits_{x \in \mathbb R^n} & f(p, x) \\
\text{s.t.} & x \in C \end{array} $$
where $p \in \mathbb R$ is a parameter, we can ...
- 791
4
votes
1
answer
255
views
Inequality $\frac{C}{d_{max}} \le \pi $ relating perimeter and diameter of planar convex body
Let $C$ is a perimeter of a convex hull (plane geometry) and $d_{max}$ is the largest distance of two arbitrary points in the convex hull. I am looking for a proof that:
$$\frac{C}{d_{max}} \le \pi ...
- 1,776
11
votes
2
answers
414
views
Sum of squared nearest-neighbor distances between points in a square
Let $\square_2=\{(x,y): 0\leq x, y\leq1\}$ be the unit square in $\mathbb{R}^2$. Take $n>1$ points $P_1, \dots, P_n\in\square_2$.
Denote the distances $d_j=\min\{\Vert P_k-P_j\Vert: k\neq j\}$, ...
- 43.2k
7
votes
2
answers
460
views
Gaussian Surface Area of Positive Semidefinite Cone
Let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e.g., one that has smooth boundary or is convex. We define the $\epsilon$-neighbor of $A$ in the ...
- 1,127
9
votes
0
answers
1k
views
Existence of barycenter
Let $(X,d)$ be a metric space. A barycenter of a Borel probability measure $\mu$ on $X$ is a minimizer of the function
\begin{equation}
\begin{split}
f \colon X & \to \mathbb{R}\\
x &\mapsto \...
- 1,347
1
vote
0
answers
80
views
A version of isotone projection cones
We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
- 773
10
votes
4
answers
904
views
The distribution of the shortest path through $n$ points
In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...
- 121
3
votes
1
answer
966
views
Continuity of minimizers to distance function from point to convex set
Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$):
$\min_{x\in U}\|x-y\|$.
I believe the minimizer $x_{U}^{*}$ is ...
- 81
5
votes
1
answer
704
views
What it is the volume of the unit ball section of the cone of positive definite matrices?
Let $PD_{n}$ be the cone of positive definite $n \times n$ real matrices and let $B$ be the unit sphere in $n \times n$ dimensions. What is the volume of $PD_{n} \cap B$?
EDIT: Let's assume that $B$ ...
- 6,962
2
votes
1
answer
250
views
Circumscribed ellipsoid of minimum Hilbert-Schmidt norm
Let $K\subseteq \mathbb{R}^n$ be a full-dumensional convex body. The Löwner ellipsoid of $K$ is the unique ellipsoid of smallest volume containing $K$. My question is about a related object: the ...
- 757