All Questions
739 questions
1
vote
1
answer
624
views
a closed form lower bound solution for linear programming
Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it?
to clearly express the problem assume that
$$
z(\mathbf{a,B,c})=\mathop {\inf} ...
- 275
28
votes
5
answers
2k
views
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
3
votes
1
answer
340
views
Name search for special Linear Integer Program
I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
$...
- 31
2
votes
1
answer
191
views
Optimization problem whose cardinality never exceeds 7 for some reason
I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...
0
votes
1
answer
451
views
Large scale least squares of non symmetric and non square problems
Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$).
There is a large amount of algorithms for symmetric ...
- 125
13
votes
0
answers
406
views
Surface area of convex hull [duplicate]
Let Q be the convex hull of a non-convex polyhedron P. Is it true that the surface area of Q is not greater than the surface area of P?
- 131
1
vote
1
answer
70
views
Heuristic for choosing n-vectors from n-sets
my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
- 11
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 151
3
votes
3
answers
349
views
Sensitivity analysis in conic optimization
I have a conic optimization of the form:
$$\min_x \langle c, x \rangle,\ \text{s.t.}\ Ax = b,\ x \in K.$$
where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a ...
- 143
3
votes
2
answers
64
views
Enumerating Tri-vertex transitive polyhedra n > 3 faces
How many unique vertex transitive polyhedra exist where each vertex has 3 incident edges
for polyhedra with n (= # faces) > 3 ?
- 31
2
votes
0
answers
91
views
Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings
In one paper from 1980 I found a note that there are no known algorithms for solving
homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring.
(The non-...
1
vote
2
answers
172
views
Linear Programm with matrix [closed]
Is there a name for problems like this
min norm(Cx)
Ax = b
where C is a matrix and norm is the maximum norm.
This is kind of like a linear Programm. Could this be rewritten as linear programm? Or Any ...
- 11
0
votes
0
answers
917
views
Inverse problem with a rank-1 update
I hope you can help me out with this. I have to find the solution x to an inverse system
$$
x=A^{-1}b
$$
This inverse problem is basically a least square problem with a rank-1 update.
$$
x=[uv^{T}...
13
votes
2
answers
680
views
What was the Question that led Euler to his Investigations on Polyhedra?
The question that led Euler to his investigations on graphs is the well-known question related to the seven bridges of Königsberg, and that story is a must in every introduction to graph theory.
...
- 13.2k
4
votes
1
answer
750
views
submatrix of a given size with maximum frobenius norm
Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
- 859
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
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
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
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
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 $\...
- 987
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, ...
- 243
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
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$...
- 4,757
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 ...
- 151k
1
vote
1
answer
4k
views
Maximizing linear objective function with absolute values
This has be asked on other forums, though couldn't
find authoritative answer.
I have a linear program over the reals and don't
want to introduce integer or binary variables.
The objective function ...
- 25.4k
2
votes
2
answers
840
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 ...
user24451
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
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
- 591
0
votes
1
answer
99
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 ...
- 109
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
32
votes
3
answers
4k
views
Did ancient mathematicians know Euler's characteristic for convex polyhedra?
The formula $V-E+F=2$ is so simple that I can't believe that it was really Euler (or perhaps Descartes) who first observed it (I mean the formula itself in some generality, not necessarily a valid ...
- 16.4k
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 ...
- 1,509
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 |) ...
- 141
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 ...
- 99
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 ...
- 41
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 ...
- 61
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
7
votes
2
answers
392
views
Convex deltahedra in higher dimensions
There are eight convex polyhedra whose faces are equilateral triangles, so-called
deltahedra:
(Image from here)
Q. Have the equivalent higher-dimensional ...
- 151k
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
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},.....
- 45
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. ...
- 329
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
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 ...
- 41
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$.
...
- 29
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
34
votes
4
answers
2k
views
About the ratio of the areas of a convex pentagon and the inner pentagon made by the five diagonals
Question : Letting $S{^\prime}$ be the area of the inner pentagon made by the five diagonals of a convex pentagon whose area is $S$, then find the max of $\frac{S^\prime}{S}$.
...
- 4,757
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 ...
- 31
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