All Questions
608 questions
9
votes
2
answers
321
views
Is a polytope that has in-spheres for faces of all dimensions already regular?
Let $P\subset\Bbb R^d$ be a convex polytope (convex hull of finitely many points).
A $k$-in-sphere of $P$ is a sphere centered at the origin to which each $k$-face of $P$ is tangent. So a 0-in-sphere ...
- 12.4k
5
votes
1
answer
361
views
What is known about the duals of cyclic polytopes?
What is known about the duals of cyclic polytopes, in particular, their facets (or equivalently, the vertex-figures of cyclic polytopes)?
In even dimensions, all facets of the dual are ...
3
votes
1
answer
111
views
Reference for "every 5-dimensional polytope has a 3-gonal or 4-gonal face"
It seems to be folklore that every 5-dimensional convex polytope has a 3-gonal or 4-gonal face of dimension two. I was not able to track down a source for that claim.
Alternatively, I would be ...
- 35.5k
2
votes
0
answers
103
views
Polytopes with large dihedral angles
The regular $d$-simplex has dihedral angle $\arccos(1/d)<90^\circ$, and the $d$-cube has dihedral angle exactly $90^\circ$.
The maximal dihedral angle of a prism over a $(d-1)$-simplex is also $90^\...
- 13.6k
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
CommunityBot
- 1
4
votes
0
answers
82
views
If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?
This question on MSE has not received a satisfying answer. It can be summarized as follows:
Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces ...
- 13.6k
0
votes
1
answer
226
views
Fractional values in linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 63.9k
0
votes
2
answers
4k
views
Linear programming piecewise linear objective
I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:
max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$
$s.t. $
$|\...
2
votes
1
answer
871
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
- 1,216
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 63.9k
0
votes
1
answer
144
views
Maximize function on rotation matrices [closed]
Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively:
\begin{equation}
Q=
\...
- 20.2k
2
votes
0
answers
2k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
CommunityBot
- 1
3
votes
0
answers
163
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
- 555
11
votes
2
answers
964
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 16.8k
1
vote
2
answers
958
views
Integer linear programming (ILP) formulation of connectivity of induced subgraph
Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
2
votes
1
answer
237
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
- 96.4k
0
votes
0
answers
43
views
Minimizing along independent directions, nonlinear programming
Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...
- 63.9k
5
votes
1
answer
280
views
Classification of vertex-transitive zonotopes
Zonotopes are convex polytopes that can be defined in several equivalent ways:
parallel projections of cubes,
Minkowsi sums of line segments,
only centrally symmetric faces,
...
I wonder whether ...
- 13.6k
1
vote
1
answer
151
views
The Fano plane, stericated 6-simplex, and pentallated 6-simplex
According to this link:
https://en.wikipedia.org/wiki/Stericated_6-simplexes
the stericated 5-simplex "scal" has 105 vertices defined as permutations of (0,0,1,1,1,1,2).
In the course of my team's ...
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21
6
votes
1
answer
779
views
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
- 1,517
1
vote
1
answer
130
views
find a PSD matrix that that verify matrices sum of equality
$A $, $ C$ $(n,n)$ are symmetric PSD matrices,
$B$ is PD symmetric matrix, and $H_i$ $\; $ $(i=[1,m])$ represent $ m $ complex matrices. $H_i$ are all one rank matrix
Our objectif is to find ...
- 1,517
4
votes
2
answers
173
views
4-polytopes with only one kind of regular facet
Is there a neat way to show (or a reference that already proves) that
the 4-cube is the only convex 4-polytope in which all facets are regular 3-cubes?
the 24-cell is the only convex 4-polytope in ...
1
vote
1
answer
168
views
Perturbation of the value of a general-sum game at a equilibirium
Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
- 745
5
votes
4
answers
836
views
Who knows this convex polytope?
I hope this is not too trivial for this forum. I was wondering if someone has come across this polytope.
You start with the rhombic dodecahedron, subdivide it into four parallellepipeds,
and then ...
2
votes
1
answer
282
views
Polytopes generated as the convex hull of the orbit of a finite reflection group acting on a given vector
Consider a finite reflection group acting on $\mathbb{R}^N$. Pick a vector $x \in \mathbb{R}^N$ and look at the convex hull of its orbit. This is a polytope.
There are some interesting particular ...
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
2
votes
2
answers
422
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 47.1k
0
votes
0
answers
50
views
Every point in a regular polytope has its own antipodal point or antipodal face
I apologize for using non-common language. When this problem comes to my mind, it seems quite easy but It's not.
Maybe It can be rewritten as,
There exists a unique facet containing the most far ...
- 285
0
votes
1
answer
456
views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
- 1,826
3
votes
1
answer
152
views
Are there any more polytopes whose 2-faces are identical 4-gons?
What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds
$P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and
all 2-faces of $P$ are ...
- 13.6k
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
0
votes
1
answer
99
views
Finding dual of a scheduling LP formulation
Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...
- 5,429
0
votes
1
answer
113
views
How do I solve this integer programming problem with non convex constraints?
I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...
- 5,429
2
votes
0
answers
159
views
The topological complexity of polytopes
Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be ...
CommunityBot
- 1
0
votes
0
answers
101
views
How can we analytically solve this max-sum-min problem?
Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
- 167
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 5,429
2
votes
0
answers
148
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
CommunityBot
- 1
0
votes
0
answers
35
views
Converting a vector in a cone statement to inequality constraints
I would like to convert the following condition for $x$
\begin{align}
x = N \lambda, \lambda \geq 0
\end{align}
to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$
\begin{...
- 356
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
6
votes
1
answer
861
views
Is Binary Integer Linear Programming solvable in polynomial time?
The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
- 151k
3
votes
1
answer
1k
views
Finding the closest special orthogonal matrix in Frobenius norm sense
Given a $3\times3$ matrix $M$, if we would like to get the closest $\mathrm{SO}(3)$ matrix $R$ that minimizes
\begin{equation}
\|R-M\|_F
\end{equation}
then $R$ = $UV^{T}$ where $U$ and $V^{T}$ are ...
- 33
1
vote
0
answers
49
views
Realizing 0/1-polytopes with shortest possible edge lengths
Has there been something written about the following question?
Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope.
The ...
- 13.6k
3
votes
0
answers
63
views
Matroids which are transitive on minimal basis exchanges
I am looking for matroids in which all minimal basis exchanges look the same, that is, the matroid is transitive on these. Let me explain what I mean by that.
Consider a finite matroid $M$. Define a ...
- 13.6k
3
votes
1
answer
244
views
What importance does the Hirsch conjecture have to Simplex Complexity?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
- 24.7k
5
votes
1
answer
315
views
On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights
Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...
- 4,878
3
votes
1
answer
275
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 3,209
1
vote
0
answers
177
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...
- 1,183
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
CommunityBot
- 1
3
votes
2
answers
331
views
Program to solve Optimization Problem
I have an optimization problem, this problem has linear constraints and nonlinear constraints. I solved the linear part by MATLAB but the nonlinear constraints I could not solve it. I downloaded ...
- 1,517