All Questions
1,547 questions
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
- 591
0
votes
1
answer
100
views
generalization from linear programming solution [closed]
I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
- 109
3
votes
1
answer
178
views
Generalizations of Directly Similar Theorem?
There is an attractive theorem that says that if two plane figures
are directly similar, then so is any convex combination of them.
Below, $P_1$ and $P_2$ are directly similar polygons: they have
the ...
- 151k
7
votes
1
answer
819
views
Has this generalization of a determinant (assigning multiplicities to the rows) been studied?
I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:
Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
- 1,509
3
votes
2
answers
668
views
The epigraph of a semi-convex function has positive reach
I've been trying to prove the following theorem for several hours with no result so far.
Claim. Let $f:\mathbb{R} \to \mathbb{R}$ be a semi-convex function, i.e. there exists a constant $C > 0$ ...
- 31
7
votes
1
answer
412
views
Shortest curve with given convex hull
Suppose $S\subset\mathbb{R}^2$ is compact and convex. Suppose $\Gamma:[0,1]\to S$ is a continuous curve that passes through every extreme point of $S$, i.e., the convex hull of $\Gamma([0,1])$ is $S$. ...
- 363
3
votes
1
answer
247
views
Map from a convex polygon that increases distance
At the risk of asking an extremely stupid question, suppose that $P\subset\mathbb{R}^2$ is a convex polygon with area $1$ that contains the origin, and let $r$ denote the farthest distance between the ...
- 33
4
votes
1
answer
288
views
Equivalent method for maximum likelihood estimation of covariance parameters
My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...
- 141
1
vote
1
answer
3k
views
Minimizing sum of absolute deviations
Suppose we want to find coefficients $b$ in $\underset{b}{\operatorname{argmin}} \displaystyle\sum\limits_{i=1}^n | y_{i}-b_{1}x_{i}-b_{0}\mid$.
If we rewrite this problem in terms of linear ...
- 99
6
votes
1
answer
185
views
Maximizing ratio volume/diameter^n by an affinity
Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant $\...
- 5,053
2
votes
0
answers
154
views
Maximizing an integral over a convex region
Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
- 21
0
votes
1
answer
158
views
2-neighborhood of a simplex
Let $\Delta$ be an $n-1$-simplex in ${\mathbb R}^{n-1}$. For each vertex $v$ of $\Delta$ let $H_v$ be the hyperplane through $v$ and parallel to the opposite facet. By 2-neighborhood of a simplex I ...
- 65
13
votes
1
answer
442
views
Choquet theory and Hilbert's fourth problem
The following text is an attempt to see Hilbert's fourth problem in a new light.
Definition. A pseudometric $d$ on $\mathbb{R}^n$ is called projective if whenever a point $z$ belongs to a line ...
- 13.5k
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
14
votes
2
answers
882
views
Lattice points and convex bodies
Given are two convex bodies $K, L \subset \mathbb{R}^n$ that contain the origin as an interior point. Assume the number of integer points contained in $\lambda K$ equals the number of integer points ...
- 13.5k
6
votes
0
answers
317
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
0
votes
1
answer
452
views
Relative interior and dense subsets
(This is a cross-post from here.) Let $A,B\subseteq \mathbb R^d$ be non-empty, such that $B\subseteq \overline A.$ For $S\subseteq\mathbb R^d$ define the relative interior of $S$ by $$\text{ri}(S)=\{s\...
- 215
0
votes
1
answer
241
views
Volume in tropical geometry as compared to volume in convex geometry
In tropical geometry, is there a notion of volume. Maybe one with some of the properties as found in classical convex geometry? If so, is there a good reference that elaborates on this question.
I ...
- 329
3
votes
0
answers
635
views
Wasserstein distance, convex polytopes and extreme points
Let us consider convex polytopes with $K$ extreme points in $\mathbb{R}^d$. Let $\mathbf{P}$ be such polytope, and let $\text{ext}(\mathbf{P})$ denote its set of extreme points, so that $\mathbf{P} = \...
- 1,731
1
vote
1
answer
246
views
Eigenvalue problem with quadratic constraints
$\circ$ Consider the following eigenvalue problem : $$Ax=\lambda x \hspace{0.5cm} (1)$$
where matrice $A \in \mathbb{R}_{n \times n}$ is a positive semi-definite with eigenvectors $x = (x_{1},x_{2},.....
- 45
9
votes
3
answers
7k
views
Set of Positive Definite matrices with determinant > 1 forms a convex set
While reading a paper An Arithmetic Proof of John’s Ellipsoid Theorem by Gruber and Schuster, I have a question on their proof.
Consider an $n\times n$ real symmetric and positive definite matrix $\...
6
votes
0
answers
189
views
Variations on a problem of S. Mazur
In problem 76 of the Scottish Book Mazur asked
Given a convex body $K$ in three-dimensional space and a point $o$ in its interior, consider the surface $S$ formed by all points $p$ such that the ...
- 13.5k
2
votes
0
answers
283
views
Distance function from the origin to the boundary of a convex polytope
Let $K\subseteq \mathbb R^n$, $n\ge 3$ be a convex bounded polytope containing the origin in its interior. Consider the unit sphere with geodesic distance $(\mathcal S^{n-1},d)$ and define the ...
- 21
3
votes
1
answer
391
views
Algorithmic Version of John's Decomposition of Convex Body
While reading textbooks on convex geometry, I heard about Fritz John's theorem on convex body, which is known as John's Theorem or John's Decomposition.
(I know that there are many variants, but this ...
2
votes
2
answers
798
views
Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method
If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...
- 329
1
vote
0
answers
262
views
Is the size of $\varepsilon$-nets of the Euclidean ball exponential for large $\varepsilon$
Let $X$ be the unit ball of $(\mathbb{R}^n,\|\cdot\|_2)$. A finite set $N=N(\varepsilon)$ is a $\varepsilon$-net of $X$ if every point in $X$ is at most a distance $\varepsilon$ from a point from $N$.
...
- 980
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
0
votes
1
answer
85
views
About the suboptimality of linear estimators
Let $X$ be a random variable and $N$ a Gaussian noise independent from $X$. We observe $Y=X+N$ and want to estimate $X$ based on $Y$ to minimize the mean square error $mmse(X|Y):=E(\hat X(Y)-X)^2$.
...
- 29
5
votes
0
answers
194
views
A linear optimization problem on a graph
Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
- 2,288
3
votes
1
answer
1k
views
For interior point methods of linear programming, what is the "L" in the computational complexity $\mathcal{O}(n^3 L)$?
My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
- 31
15
votes
2
answers
2k
views
Intuitive explanation of Dvoretzky's theorem
I am wondering if anyone has an enlightening explanation of why Dvoretzky's theorem (which says that a high-dimensional convex body has an almost round central section) is true -- there are a number ...
- 96.4k
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
1
vote
1
answer
308
views
A question about rational convex cone
Edit: Fix a lattice $N = \mathbb{Z}^n$ and let $N_{\mathbb{R}} = N \otimes \mathbb{R}$.
Let $C(S)$ be a strongly convex rational cone in $N_{\mathbb{R}}$ generated by a finite set $S \subset N$, with ...
- 75
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
4
votes
3
answers
428
views
Can the intersection of the boundaries of compact and convex sets be a single element?
Let $H_1,H_2,\dots,H_n$ be compact and convex sets in $\mathbb{R}^n$ such that $\bigcap_{j=1}^n H_j$ has non-empty interior and for each $i=1,2,\dots,n$ there exist at least one element $x \in H_i$ ...
- 43
0
votes
1
answer
2k
views
eigen-decomposition solution? is it unique?
Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
- 1
9
votes
1
answer
370
views
Largest convex hull of a unit length path
What is the largest area possible for the convex hull of a path of unit length lying on a plane? For what paths is that largest area attained?
- 851
3
votes
2
answers
1k
views
Extensions of Urysohn's inequality
A version of Urysohn's inequality states that for a symmetric convex body $K \subset \mathbb{R}^n$, one has
$$
\left(\frac{\text{vol}(K)}{\text{vol}(B_2)} \right)^{1/n} \le \frac{1}{\sqrt{n}} E
\; \| ...
- 1,731
4
votes
1
answer
333
views
n-simplex in an intersection of n balls
Consider any $n$-simplex, $n \geq 2$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ in the simplex. The question: ...
- 195
6
votes
2
answers
994
views
Minkowski successive minima inequality for a lattice base?
Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors.
The Minkowski successive minima inequality says ...
- 403
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 1,318
4
votes
0
answers
162
views
Hilbert metric of a sum of cones
Suppose that $K_{1}$ and $K_{2}$ are pointed closed cones in a finite-dimensional space $V$ whose Hilbert metrics $d_{1},d_{2}$ are known. Is there a way to express the Hilbert metric of $K_{1}+K_{2}$ ...
- 6,962
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
- 111
8
votes
2
answers
566
views
Two cubes in unit cube
A cube of side one contains two cubes of sides a and b having non-overlapping interiors. How to prove the inequality $a+b \le 1$? The same question in higher dimensions. It was asked, but not answered ...
- 3,486
16
votes
1
answer
589
views
(A question about)${}^3$ 3-dimensional convex bodies
Related to the questions mathoverflow.net question No. 137850 and mathoverflow.net question No. 39127, is there a 3-dimensional convex body other than a ball whose perpendicular projections in all ...
- 7,276
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
1
vote
1
answer
163
views
A question concerning convex functions
Consider points $a,b,c$ (not on a line) and $x_1,...,x_n$ in $\Bbb{R}^2$. I am looking for a necessary and sufficient condition in terms of the geometric configuration of these points such that for ...
user37834
7
votes
2
answers
390
views
A question about a question about 3-dimensional convex bodies
For each positive integer n let E(n) denote n-dimensional Euclidean space and let the term "n-dimensional convex body" mean a compact convex subset of E(n) whose interior (with respect to E(n)) is non-...
- 6,215