All Questions
552 questions with no upvoted or accepted answers
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
- 41.8k
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
- 1,151
1
vote
0
answers
82
views
Relations between conjugate ℓₚ unit ball surface areas
I understand that little is known on the surface area of the unit ball in $\ell_p$, excepting the cases $p=1,2,\infty$, but can anything be said on the relation between the surface areas for $p$ and ...
- 2,545
1
vote
0
answers
53
views
Projecting two convex polyhedra onto their intersection
Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$.
For the orthogonal ...
- 337
1
vote
0
answers
34
views
Limiting law of quadratic functions of sample averages
Let $X_1,\cdots,X_n$ be independent centered univariate random variables. Let also $\{w_{ij}\}_{i,j=1}^{k,n}$ be a set of deterministic scalar weights, where $k\ll n$. Define sample averages
$$
\...
- 373
1
vote
0
answers
43
views
Quantitative error control in Minkowski-Stein formula
Let $K\subseteq\mathbb R^d$ be a compact convex body with non-empty interior, and $E$ be a $(d-1)$-dimensional linear subspace of $\mathbb R^d$. Let $\theta\in\mathbb R^d$ be the unit vector such that ...
- 373
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
1
vote
0
answers
56
views
Distance from a hyperplane (determined by the cut of a convex cone with the unit sphere) to the origin
The setting is a convex cone $C$ in $\mathbb{R}^d$ with the property that if you cut it with $S^d$ the volume of the cut is greater than or equal to $\operatorname{Vol}(S^d)/d+1$. That is, the volume ...
1
vote
0
answers
131
views
Maximum of the Dirichlet eigenvalue of Monge-Ampere equation arrived at regular simplex
There is a article http://pages.iu.edu/~nqle/MA_EVP.pdf of NAM Q.LE state a conjecture of when the eigenvalue of Monge-Ampere equation will arrive the maximum.
It divide into two part:
Conjecture ...
- 697
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 31
1
vote
0
answers
74
views
Existence of circumscribing simplex in infinite dimensional space
It is well known that every compact convex set with non-empty interior $K\in\mathbb{R}^{n}$ has (many) circumscribing regular simplices. That is, there exists at least a simplex $\Delta$ such that $K\...
- 11
1
vote
0
answers
126
views
What is an umbilic point of a convex polyhedron?
An umbilic point of a smooth ($C^2$) convex surface in Euclidean 3-space is a point where the principal curvatures are equal. Is there some good way to generalize this notion to convex polyhedra? See ...
- 7,149
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
1
vote
0
answers
122
views
Does the convex-hull of a set contain zero (II)?
Let $(\lambda_1, \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Suppose we have $k$ non-zero vectors $\alpha^{(j)} = (\alpha^{(j)}_1, \cdots , \alpha^{(j)}_d) \in \mathbb{Z}^d$, ...
- 500
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
- 13.2k
1
vote
0
answers
31
views
Extending the projective action of several positive linear maps to a complex neighbourhood
I am currently reading a paper which, somewhat indirectly, asserts the following result:
Lemma: Let $\Delta \subset \mathbb{R}^d$ denote the simplex $\{(x_1,\ldots,x_d):\sum_{i=1}^d x_i=1\}$, let $...
- 6,206
1
vote
0
answers
218
views
volume of the region above a simplex in a spherical cap
Consider the $n$-dimensional unit ball $B$ centered at the origin and a hyperplane $H$ that intersects $B$. Suppose that there is a simplex $S$ inscribed in $B\cap H$, so that the vertices of $S$ lie ...
- 216
1
vote
0
answers
34
views
Realizing set systems in real space
Let $\mathcal{S} = \{S_i\}$ be a collection of subsets of the same size $s$, all drawn from the universe $[n]$, with the property that $|S_i \cap S_j| \le 1$ for all $ i \ne j$. Let us say that $\...
- 1,389
1
vote
0
answers
53
views
Is it possible that a convex cone and its closure both induce vector lattices?
Given a convex cone $P\subset X$ where $X$ is a $K$-vector space, $K=\mathbb{R}\text{ or }\mathbb{C}$ is a field.
Suppose that $P$ satisfies positive element stipulations.
(1) $X=P-P$.
(2) $P\cap-P=...
- 8,071
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
1
vote
0
answers
385
views
About hyperplanes cutting the discrete hypercube
Given $\{-1,1\}^n$ we randomly choose a hyperplane in $\mathbb{R}^n$. Now given an integer $p \in [1,n]$ and a number $\epsilon \in [0,1]$, I want to ask, "How likely is it that at least one of the $p-...
- 2,246
1
vote
0
answers
62
views
Sampling in a polyhedral complex
Assume one is given a polyhedral complex $P$ in $\mathbb{R}^n$. Now consider picking uniformly at random a $D \subseteq \{0,1\}^n$. Is there way to upper bound the probability that $D$ (a subset of ...
- 2,246
1
vote
0
answers
125
views
Estimating $\ell^p$ and $\ell^q$ norms on a convex cone
For $1 \le p \le q \le \infty$, I need an inequality bounding the $\ell_q$ norm from above by the $\ell_p$ norm on $\mathbb{R}^n$: finding a $\lambda$ so that
$$
\Vert v \Vert_q \le \lambda \Vert v \...
- 10.1k
1
vote
0
answers
53
views
Given a fixed convex domain $\Omega$ in 3D, for what value $c$ the function $f(c) := \int_{\partial \Omega} |x-c| d \sigma_x$ gets its minimum?
Let $\Omega$ be a bounded smooth convex domain in $\mathbb{R}^3$, then consider the following minimization problem:
$$\inf_{c \in \overline{\Omega}} f(c), \quad f(c) := \int_{\partial \Omega} |x-c| ...
- 1,350
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
1
vote
0
answers
168
views
Projecting on a a special polyhedron
Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron
$$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$
Notice that $\mathcal P_X$ is symmetric about the origin.
...
- 6,853
1
vote
0
answers
77
views
Projecting on a convex compact polytope with special form
Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
- 6,853
1
vote
0
answers
162
views
Affine-regular hexagon in convex body
An affine-regular $n$-gon is a non-degenerate affine image of the regular $n$-gon. It seems to be a standard fact in combinatorial geometry that inside every convex compact set $K\subseteq \mathbb R^2$...
- 111
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
1
vote
0
answers
40
views
Perimeters of the cells of a convex tessellation
Let $C$ be a compact, convex region in $\mathbb{R}^2$, and say we have scalars $a_i, b_i, c_i$ for $i\in\{1,\dots,n\}$. Consider the tessellation $R_1,\dots,R_n$ of $C$ defined by letting $$R_{i}=\{(...
- 4,049
1
vote
0
answers
117
views
Inscribed polytopal approximation to a convex body
This question is on the continuation of the post
Approximation of convex body by polytopes
The central problem I am interested is an explicit construction of inscribed polytope with at most $n$ ...
- 599
1
vote
0
answers
93
views
Bounds on the spherical measure of sub-level sets of quadratic forms
I'm wondering if there are any bounds on the spherical measure of sets of the form
$$
\mu_n\left(\{y\in S^{n-1} : \frac{y_1^2}{y_2^2} < \alpha\}\right) \leq f(\alpha)
$$
where $\alpha$ is some ...
- 205
1
vote
0
answers
50
views
Projection of a ray onto a random polytope
Suppose $P$ is a polytope formed by $p$ (general) random planes in $\mathbb{R}^n$. We assume $p \asymp n$ and $P$ has a diameter $O(\sqrt{n})$. For any $x \in \mathbb{R}^n$, denote by $\operatorname{...
- 773
1
vote
0
answers
82
views
Averaging a log-concave centrally-symmetric function over convex bodies
the question is the following: given a log-concave isotropic function $f$ defined on $\mathbb{R}^n$ and two compact 0-symmetric convex bodies $C_1, C_2$, where $C_1 \subset C_2$. Is it true that
$$
...
1
vote
0
answers
495
views
About the $C^{1,1} $regularity of the boundary of a set
I am studying a paper that uses the following property :
Consider $U$ and $V$ open, bounded and convex domains in $R^n$ with $U \supset \overline{V}$ and suppose that $min_{y \in V} |x - y| = \lambda ...
- 269
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
1
vote
0
answers
91
views
Tubular neighbourhood which is nowhere piecewise linear
I recently asked this question.
I think, if the following were true, then I would solve my problem.
Let $E\subset\{(x_1,\dots,x_n)\in\mathbb R^n\;|\;x_i\geq 0\, \&\, \sum_ix_i=1\}$ be a convex ...
- 11
1
vote
0
answers
75
views
Are there any known bounds on the value of solutions of linear integer programming?
Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...
- 111
1
vote
0
answers
413
views
Extreme points of a set related to semidefinite cone
Let $X \in \mathbb{R}^{n \times n}$ be symmetric matrix. Consider the following set
$$
\mathcal{C} = \{ X: X \succeq 0, \quad 0 \le X_{ij} \le 1, \forall i,j\}
$$
What are the extreme points of this ...
- 1,731
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
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
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
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
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829