All Questions
115 questions
0
votes
0
answers
68
views
A seemingly easy integer programming question
Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
- 501
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
3
votes
1
answer
634
views
Properties of one dimensional null space
Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition).
Let $S: \...
- 31
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
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 7,182
4
votes
1
answer
345
views
Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints
Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints:
...
- 49
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
1
vote
1
answer
390
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695
1
vote
0
answers
85
views
Smallest sum of original column entries in 2d matrix [closed]
I have an interesting optimization problem I am trying to solve now and I thought I'd share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:
...
- 111
1
vote
1
answer
2k
views
Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm
I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105
Unfortunately I am struggling to make the algorithm work on ...
- 11
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
- 321
8
votes
2
answers
246
views
Are sums of 0-1 Pareto efficient vectors Pareto efficient?
Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...
- 388
6
votes
1
answer
1k
views
Speed up Linear programming
I have a linear programming problem like this:
minimize $c^t X$
under the constraint that $AX \ge b$.
I will need to solve this linear programming problem online many times. I need it to be as fast ...
- 83
2
votes
1
answer
143
views
Find base of kernel with as many 0 as possible
I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...
- 83
2
votes
2
answers
219
views
Boundedness of ratio of linear functions
Consider the function
\begin{eqnarray}
f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i},
\end{eqnarray}
over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
- 23
0
votes
1
answer
546
views
Solution of infinite dimension linear system
Suppose that ${a_n}$ and $b_n$ is decreasing sequence such that $a_0=A$, $lim_{n->\infty}a_n=0$ and $b_0=B$, $lim_{n->\infty}b_n=0$.
For fix n,
we can construct n dimension linear equation ...
- 111
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
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
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}...
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
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
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
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
0
votes
1
answer
2k
views
eigen-decomposition solution? is it unique?
Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
- 1
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) = ( ...
1
vote
1
answer
296
views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
- 185
2
votes
1
answer
227
views
Arrangements of hyperplanes
Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...
- 3,274
9
votes
1
answer
3k
views
Inverse of a totally unimodular matrix
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
- 93
0
votes
1
answer
2k
views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
- 340
3
votes
1
answer
4k
views
Schur complement and negative definite matrices
Hello,
My question regards to the Schur complement lemma. Consider the matrix $M=\left( \begin{array}{cc}
A & B\\\
B^T & C \end{array}\right)
$.
According to the lemma $M\geq0$ iff $C>0$ ...
- 155
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829
0
votes
1
answer
2k
views
Finding linearly independent columns of a large sparse rectangular matrix
I have a problem that necessitates solving a large non-negative least-squares
problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols)
and nearly binary. However, A is not ...
- 103
5
votes
2
answers
2k
views
Bounding the minimal maximum norm of a solution of a linear system.
I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
- 191
3
votes
1
answer
533
views
Solving a system of linear inequalities
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without ...
- 221
2
votes
0
answers
230
views
Consistency of a system of linear equations
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
- 221
1
vote
0
answers
628
views
Totally unimodular Matrices
A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
- 11
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
1
vote
1
answer
2k
views
Can one efficiently optimize over the inverse of matrix?
Hello,
I have the following problem:
Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
- 53
0
votes
1
answer
409
views
Need help to find an efficient algorithm for the following problem!
Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.
Given $A_{n\times n}$ is the covariance matrix of $x$.
$u$ is a given n-dimensional vector of real ...
- 131
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151