All Questions
740 questions
2
votes
0
answers
120
views
integrality of a linear program -- binary equality constaints
Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...
- 127
4
votes
0
answers
2k
views
Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes
One can intersect a dodecahedron with a plane and
obtain an equilateral triangle, a square, a regular pentagon,
a regular hexagon, and a regular decagon:
&...
- 151k
4
votes
2
answers
212
views
combinatorial and linear duality
Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
- 24.8k
2
votes
1
answer
134
views
Integer point in a non-empty polytope
I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
- 3,979
11
votes
0
answers
726
views
Making a convex polyhedron with two sheets of paper
Suppose that we have two sheets of paper $S,T$ and that each of $S,T$ is in the shape of a convex quadrilateral. Also, suppose that the length of the perimeter of $S$ equals that of $T$. (Note that $S$...
CommunityBot
- 1
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
4
votes
1
answer
320
views
Seeking criteria for "threadable" pairs of centrosymmetric polyhedra
Let $A$ and $B$ be origin-centered centrosymmetric polyhedra in $\mathbb{R}^3$:
"for every point $(x, y, z)$ [...] there is an indistinguishable point $(-x, -y, -z)$."
Say that $A$ and $B$ are ...
- 1,016
2
votes
2
answers
841
views
Finding the maximum of a multivariate polynomial of degree one
I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...
CommunityBot
- 1
10
votes
1
answer
426
views
Complexity of the union of randomly rotated unit cubes
It is a remarkable fact that the union of congrent cubes
has only at most near-quadratic combinatorial complexity,
$O^*(n^2)$ for $n$ cubes, known to be almost tight.
This contrasts with the union of ...
CommunityBot
- 1
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(\...
CommunityBot
- 1
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 ...
- 3,934
3
votes
0
answers
133
views
Convex polyhedra jammed in $k$ disjoint holes
For a given convex polyhedron $P \subset \mathbb{R}^3$,
I was imagining finding the optimal "fixing" of $P$ in holes (or jamming them in "mud"),
which led to the following question.
First, scale $P$ ...
- 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 ...
CommunityBot
- 1
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
CommunityBot
- 1
4
votes
3
answers
3k
views
Intersection of Polyhedra
I'm writing a collision detection algorithm, and so far I've been using Joseph O'Rourke's book "Computational Geometry in C" as reference. It outlines an algorithm to determine whether a point is ...
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 |) ...
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 ...
- 1,107
4
votes
1
answer
143
views
Polyhedra with minimal edge length
Given a fixed volume and fixed surface area I would like to construct polyhedra that minimize the total length of the edges. This seems like a straight-forward problem to solve by brute force for ...
- 6,210
18
votes
2
answers
986
views
"Derived" polyhedra and polytopes
The notion of derived polygon is natural and leads to remarkable convergence.
Start with a polygon, and replace it by locating a point on every edge
a fraction $\alpha$ between the two endpoints. For ...
- 151k
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 ...
- 19.6k
0
votes
2
answers
340
views
positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix
Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem.
$$
\...
- 3,741
6
votes
0
answers
114
views
Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces
Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
- 161
5
votes
2
answers
888
views
relation between solution of a linear program and its perturbation
I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$:
$$
\max_j c' x_j
$$
Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
- 177
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},.....
- 188k
2
votes
2
answers
129
views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
CommunityBot
- 1
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. ...
- 151k
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 ...
- 1,107
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$.
...
- 7,514
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
5
votes
2
answers
584
views
Continuous Transportation Problem
Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
- 12.7k
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 ...
- 6,694
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
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 747
1
vote
1
answer
240
views
Conditions for differentiability of minima and minimizers of linear functionals?
Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C :...
- 60.5k
1
vote
0
answers
1k
views
Robust optimization in matlab using fmincon [closed]
I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...
CommunityBot
- 1
10
votes
0
answers
333
views
Bi-spherical polyhedra
Bicentric polygons have been studied: a polygon all of whose vertices lie on its
circumcirle, and whose incircle is tangent to every edge:
I have not been able to find a comparable literature ...
- 151k
4
votes
4
answers
703
views
efficient way to compute the inversion of the following matrix
Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
- 2,205
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 ...
- 12.3k
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 ...
CommunityBot
- 1
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 ...
- 6,210
3
votes
1
answer
233
views
Equiprojective polyhedra
Seeing Garabed Gulbenkian's question (which was inspired by Joel Hamkins' question), reminds me of an analogous problem which I believe remains open,
and which some might find intriguing.
Define an ...
CommunityBot
- 1
10
votes
2
answers
326
views
Do maximal polyhedra have algebraic volume?
Is it possible to prove that for every $n > 3$ the maximal possible volume of a convex polyhedron having $n$ vertices inscribed in a sphere of unit radius is an algebraic number?
Update: What can ...
- 6,819
7
votes
1
answer
559
views
Standard (special) spines and hyperbolic structure on 3-manifolds
My question relates to constructing angled triangulations or hyperbolic triangulations for $3$--manifolds. Briefly, an angle triangulation can be considered as an assignment of a real number (called ...
CommunityBot
- 1
2
votes
1
answer
689
views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
- 46
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
1
vote
2
answers
306
views
Name of operations on two vectors
Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...
CommunityBot
- 1
2
votes
0
answers
107
views
Criteria to decide whether a subset of the boundary complex of a polyhedron is a manifold?
Let $\mathcal{P} \subseteq \mathbb{R}^d$ be a convex polyhedron. Let $K$ be a subset of the boundary complex of $\mathcal{P}$. (Perhaps $K$ could be defined in terms of a system of linear inequalities....
- 170
8
votes
2
answers
385
views
Volumes of convex vs non-convex polyhedra with prescribed facets areas
It is known that given a set of Areas $A_f$ and normals $\vec{n}_f$ if $\sum_f A_f \vec{n}_f=0$ exist a unique convex polyhedron with given face areas and normals. (Minkowski theorem - See Alexandrov ...
- 66
0
votes
2
answers
244
views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
- 3,934