All Questions
552 questions with no upvoted or accepted answers
1
vote
0
answers
57
views
Shadows and planar sections of polyhedra – 2
This post continues Shadows and planar sections of polyhedra and On planar sections of 3D convex bodies
Shadows and planar sections of polyhedra gives an example demonstrating that shadows (orthogonal ...
- 5,979
1
vote
0
answers
83
views
Weird transportation polytope
I'm looking to compute extremal points of a weird polytope. This polytope contains all matrices with positive entries $A \in \mathcal M_{n,m}\left(\mathbb R_+\right)$ such that:
every row sum except ...
- 686
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
1
vote
0
answers
45
views
Analytic lower-bound for minimal value of $\|x\|^2$ such that $\|Cx-b\|^2 \le c^2$ (a hyperellipsoid)
Let $C$ be an $n \times p$ matrix and $b$ be a column vector of length $n$, and $c>0$. Let $E := \{x \in \mathbb R^p \mid \|Cx-b\| \le c\}$, a hyperellipsoid in nonstandard position.
Question 1. ...
- 6,853
1
vote
0
answers
52
views
ratio between the volume of a section of the cube and a section of the ball
Let $H\subset \mathbb{R}^n$ be a $k$-dimensional affine space and suppose $vol_k(H\cap [-\frac{1}{2},+\frac{1}{2}]^n)>0$ then can one upper bound the ratio $$\frac{vol_k(H\cap [-\frac{1}{2},+\frac{...
- 21
1
vote
0
answers
122
views
Integrality of polyhedra
Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral?
Given two polyhedra in $H$ representation $P_1:Ax\...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
124
views
Number of lattice points in a structural symmetric convex body
Let $f$ is a convex symmetric function on the interval $[-a,a]$, i.e., $f(-x)=f(x)$ for $\forall \, x\in [-a,a]$. Then we consider a $n$-dimensional convex body in Euclidean space
\begin{equation}
\...
- 550
1
vote
0
answers
160
views
Angles between simple, closed geodesics on convex surface
It is known that there are at least three simple, closed geodesics on
the surface of any smooth convex body $K$ in $\mathbb{R}^3$, the
Lusternik-Schnirelmann Theorem (see links below for references).
...
- 151k
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
59
views
Can convex programming capture affine curves or surfaces?
A friend of mine asked me a question that relates to algebraic geometry and convex programming.
The question was "What is the minimal size of a program that capture (the intended object is not ...
- 13.9k
1
vote
0
answers
41
views
If the volume-ratio of an inscribed convex set to the circumscribing convex set is rational, can anything of consequence be further deduced?
Say, one has two $n$-dimensional convex sets $A$ and $B$, with $B$ being inscribed in the strictly larger set $A$. ($A$ and $B$ have at least one boundary point in common. $B$ “fits snugly” in $A$ ...
- 723
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
83
views
Given a large random matrix, how to prove that every large submatrix whose range contains a large ball?
Context. Studing a problem in machine-learning, I'm led to consider the following problem in RMT...
Definition. Given positive integers $m$ and $n$ and positive real numbers $c_1$ and $c_2$, let's ...
- 6,853
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
102
views
Given a finite set of points, does there exist a linear function pass through a point and strictly below the other points for all the points?
I guess my question is a follow up question of this one: usul, Existence of a strictly convex function interpolating given gradients and values, version: 2019-04-13.
In usul's question, the answer ...
- 29
1
vote
1
answer
227
views
On comparing planar convex regions of equal perimeter and area
Definitions:
The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set.
Given two planar convex regions $C_1$ ...
- 5,979
1
vote
0
answers
135
views
Linearly independent support vectors of a convex set
Let $\Omega\subset\mathbb{R}^n$ a compact strictly convex set containing $0$ in its interior and let $k\leq n$.
Given a vector $x\neq 0$ in $\mathbb{R}^n$ a supporting vector $\xi_x$ in the ...
- 11
1
vote
0
answers
35
views
Convex combination of semi-algebraic sets
Suppose we are given two semi-algebraic sets $S_1$ and $S_2$. Define
$$
S=\{s=ps_1+(1-p)s_2: s_1\in S_1, s_2\in S_2, 0\leq p\leq 1.\}
$$
$S$ is semi-algebraic.
Can we bound the degree of $S$?
If we ...
- 1,503
1
vote
0
answers
54
views
Essential rays in fan structure
Let $|\Sigma|$ be the underlying set of some fan $\Sigma$ in $\mathbb{R}^n$. It is well known that in general there is no coarsest fan structure on $|\Sigma|$. However, there may be some special rays ...
- 2,788
1
vote
0
answers
283
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
248
views
Gaussian mean width of normal random cones
Suppose $1 \leq n < m < \infty$ are integers. For $g \sim \mathcal N(0, I_n)$ define the gaussian mean width of a non-empty set $T \subseteq \mathbb R^n$ by
$$
w(T) := \mathbb E \sup_{x \in T} \...
- 119
1
vote
0
answers
99
views
Inheriting quasiconvexity from convex function after re-parametrisation of space into the Stiefel manifold
Consider a function $f(S): \mathcal{S} \to \mathbb{R}$, where $\mathcal{S}$ is the convex cone of all positive semidefinite complex $M\times M$ Hermitian matrices.
The function $f(\cdot )$ is concave ...
1
vote
0
answers
171
views
Minimum volume of intersection between two high-dim $\ell^1$-balls
Let $B_1$ and $B_2$ be two balls with the same radius, in $\mathbb R^n$ with the $\ell^1$ norm. The distance between the centers of $B_1$ and $B_2$ is $d(B_1, B_2)$. Is there any deterministic method ...
- 11
1
vote
0
answers
94
views
Family of polytopes whose measure respects multiplication?
Is there a family $\mathcal{P}$ of integral polytopes and a polytope product $\star$ such that for every $n\in\mathbb N_{>1}$ $\exists p\in\mathcal{P}:vol(p)=n$ and
$\forall q\in\mathcal{P}\...
- 13.9k
1
vote
0
answers
120
views
John's ellipsoid of a polytope
Suppose that $X$ is $\mathbb R^n$ with some polyhedral norm, that is, the unit ball of $X$ is an $n$-dimensional polytope. Assume that the John ellipsoid of $X$ is an Euclidean ball that touches every ...
- 113
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
99
views
Finding a point on a convex set
Given a compact bounded convex set $\mathcal C\subseteq\mathbb R^n$ given by $t$ hyperplane inequalities I want to find a point $u\in\mathcal C$ such that for all $v\in\mathcal C$
a convex relation $...
- 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
68
views
Curvature of projection function onto a smooth curve
Suppose we have a smooth curve $C$ lying in $\mathbb{R}^2$, and let us consider the orthogonal projection function $P_C(x)$ onto the curve, described by
$$P_C(x) = argmin_{y \in C} \Vert x - y \Vert$$...
- 141
1
vote
0
answers
68
views
Volume of caps of a polytope
Let $K$ be a polytope in $\mathbb R^d$, blow it up by a factor $\lambda>0$. For a unit vector $u \in \mathbb S^{d-1}$, $\lambda K$ has 2 support hyperplanes $H_1$ and $H_2$ with corresponding ...
- 13
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
1
answer
266
views
Relative interior of a normal cone at a face of a convex polytope?
Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
- 159
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