All Questions
331 questions with no upvoted or accepted answers
1
vote
0
answers
183
views
Using Bertini software to determine whether or not a variety is empty
I have a system of polynomials $f_1,\dots, f_n \in \mathbb{C}[x_1,\dots, x_m]$, and I would like to determine whether the set of solutions to the system $f_1(x)=\dots=f_n(x)=0$ is empty or not. Since ...
- 980
1
vote
0
answers
242
views
How to estimate the probability of an edge appearing in the minimum spanning tree of a graph?
I've been running into this problem recently and I've been stuck on it for a while.
I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ vertices (which would also ...
- 11
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
147
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
1
vote
0
answers
34
views
How do I find the portion of a cell/voxel lying within a defined surface?
We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$.
A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
- 111
1
vote
0
answers
62
views
fast V representation update of polytope
Say that I have both the V and the H representation of a (possibly unbounded) polytope $P$. I want to append a some rows to the H representation, how can I quickly update the V representation to ...
- 155
1
vote
0
answers
27
views
Complexity of tour-expansion heuristic for the planar Euclidean TSP
This is a followup question to this one: Computational Geometric Aspects of Greedy Tour Expansion.
Assume that the candidate point, whose insertion into current incurs the least tour-length increase, ...
- 13.2k
1
vote
1
answer
149
views
Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities
Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows:
$V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...
- 1,875
1
vote
0
answers
282
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
1
vote
0
answers
43
views
Vertex enumeration for polytope with a sparse halfplane description?
Say I have a (bounded convex) polytope $P\subset\mathbb R^d$ with description $Ax\le b$, where $A$ is sparse in the sense that there are at most $k$ nonzero entries in each row or column, where $k$ is ...
- 523
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
1
vote
0
answers
48
views
Efficient scissors congruence between efficiently describable convex polytopes and simplex?
Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
- 1,826
1
vote
0
answers
65
views
Covering a simplex efficiently by efficiently describable polytopes?
Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...
- 1,826
1
vote
0
answers
64
views
Polytopes that can be efficiently described and efficiently covered by cubes or simplices?
Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
- 1,826
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
- 13.9k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
- 13.2k
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
117
views
The upper bound of the number of points of a convex hull formed by external co-tangents of circles
Consider the following problem: Given a rope to surround some circles, and minimize the length of the rope.
In order to solve the problem, we shall calculate all external co-tangents of these circles, ...
- 601
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
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
99
views
Geometry of a $(d-1)$-dimensional lattice
Let $\mathbf u\in\mathbb Z^d$ be a primitive vector (i.e. $\gcd(u_i)=1$) and let $\Pi_{\mathbf u^\perp}$ be the orthogonal projection perpendicular to $\mathbf u$. I want to understand the geometry of ...
- 23.2k
1
vote
0
answers
63
views
Congruency check for set of points in 3D using inertia tensor
You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...
- 1,171
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
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
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
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
368
views
Convex hull of the intersection of nonconvex sets
I have a set $D$ in $\mathbb{R}^{d+1}$ which is the intersection of $d$ domains $D_i$ given by $f(x_{i}) \leq x_{i+1} \leq g(x_{i})$ for two functions $f$ and $g$.
I want to find the convex hull of $...
- 31
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
104
views
connectedness of semi algebraic sets
We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...
- 53
1
vote
0
answers
126
views
cohomology ring of compact submanifolds of Euclidean spaces
Suppose we have a compact $m$-dimensional submanifold $M$ of $\mathbb{R}^N$ and we want to know the cohomology ring $H^*(M;\mathbb{Z})$.
Let $\epsilon>0$ and a $m$-dimensional finite simplicial ...
- 1,990
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
1
answer
242
views
Finding generators of symmetric cones
I have a bunch of vectors $\mathbf v_i$ in $\mathbb R^n$. I would like to consider the cone $C$ spanned by these vectors, together with all the other vectors that can be obtained by permuting the ...
user47305
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
537
views
Epsilon-net of operator norm ball around Identity
Suppose I look at the set of matrices which are invertible and satisfy
$$
\left\|A-Id\right\|_{op}<r
$$
for some $r<1$, where $Id$ is the $n\times n$ identity matrix. An $\epsilon$-net of such ...
- 205