All Questions
783 questions
6
votes
1
answer
830
views
Dominant eigenvector of a real symmetric tridiagonal matrix
What is the most efficient way to calculate the dominant eigenvector of a real symmetric tridiagonal matrix? What's the corresponding time complexity bound?
Could someone give me a reference for ...
2
votes
1
answer
148
views
Fast algorithm for large-scale, asymmetric transportation linear program
I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
CommunityBot
- 1
1
vote
2
answers
83
views
Algorithm for a linear optimization problem
For the vectors $X=(x_1,\cdots, x_n),~ Y=(y_1,\cdots, y_n)$ and $\alpha=(\alpha_1,\cdots,\alpha_n),~ \beta=(\beta_1,\cdots, \beta_n)\in\mathbb R^n_+$ s.t. $\sum_{k=1}^n\alpha_k~~=~~\sum_{k=1}^n\beta_k~...
2
votes
0
answers
64
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
- 19.6k
1
vote
0
answers
78
views
Family of functions which satisfies $f(\boldsymbol{x}) = 0$ if $\nabla f(\boldsymbol{x})=0$? [closed]
I have a Lagrangian of which I want to find the supremum in the primal variable $\boldsymbol{x}$:
$\mathscr{L}(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})^T\boldsymbol{a} + \boldsymbol{\...
1
vote
0
answers
47
views
Linear programs [closed]
Can the optimal value of the primal problem of a linear program ever be less then zero?
An example is: minimize $C=2x_1 +3x_2$ Subject to: $3x_1+4x_2 \leq 5$. Obviously, $x_1$ and $x_2$ are free ...
- 993
3
votes
1
answer
4k
views
Is the square root of a matrix unique? [closed]
I know the answer is No, since you can put plus/minus on each eigenvalue. But how about putting a psd requirement? Like $A = S^2$, $S$ is psd, is $S$ unique?
I was worried about the case where if $\...
- 96.4k
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
3
votes
2
answers
1k
views
Equality constraints in mixed-integer optimization
Suppose I have a linear mixed-integer optimization problem of the form
$$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq ...
- 342
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
4
votes
1
answer
967
views
Solving for Hamiltonian path with constraints on allowable routes through vertices
Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
- 151k
0
votes
1
answer
79
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
- 13.6k
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 ...
CommunityBot
- 1
4
votes
1
answer
4k
views
Numerical trace of inverse matrix from Cholesky
This question was somewhat answered here: Fast trace of inverse of a square matrix. However, I feel like there was no complete answer wrt the Cholesky case.
I have the matrix $\Sigma=LL^T$. Is there ...
CommunityBot
- 1
2
votes
0
answers
1k
views
Condition number of the product of two matrices
Consider two matrices $A$ and $B$ that are non-square in general and may not be full rank. Assuming their shapes are such that the product $A\cdot B$ is well-defined, what is the relationship between ...
- 171
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
1
vote
1
answer
73
views
minimize number of unique elements in a vector
I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
- 14k
2
votes
2
answers
403
views
Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative
$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative.
What should $A$ satisfy to guarantee the equation set have only zero solution?
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 ...
- 43.2k
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 ...
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 ...
9
votes
1
answer
6k
views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
1
vote
1
answer
206
views
Show $0-1$ Knapsack is polynomially reducible to this problem
I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians:
Let $T=\{1,\cdots,n\}$ and consider the ...
CommunityBot
- 1
15
votes
9
answers
9k
views
Exponential of large matrices
I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...
1
vote
1
answer
113
views
Are convex combinations of 0-1 Pareto efficient vectors efficient?
Let $Y$ be any subset of $\{0,1\}^n$ for $n\geq3$. A vector $\alpha\in$ $Y$ is Pareto efficient if there is no $\beta\in$ $Y$ such that $\beta_i$ $\geq$ $\alpha_i$ for each $i\in\{1,...,n\}$ and $\...
- 1,502
6
votes
2
answers
1k
views
Linear programming is continuous
Consider an arbitrary linear program:
$$\max \vec c \cdot \vec x$$
subject to:
$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$
Assume that this program is feasible and bounded. ...
- 884
0
votes
1
answer
81
views
Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?
Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that:
1) $P\neq \varnothing$,
2) $\forall x\in P, |x| >1$,
3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
- 13.4k
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
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 - ...
- 11
1
vote
1
answer
142
views
error bound for least square minimization
Let $X = [x_1 \cdots x_N] \in \mathbb{R}^{d \times N}$ and $ T= [t_1 \cdots t_N] \in \mathbb{R}^{1 \times N}$. Define
$$
E(w) = \text{tr}(T - w^TX)(T - w^TX)^T
$$
as least square energy. When ...
- 883
1
vote
1
answer
184
views
Do doubly infeasible Linear Programming problems always have doubly infeasible bases?
Consider a Linear Programming problem in dictionary form,
$$\max\Big\{f^\pi+\!\!\!\sum_{j\in D(\pi)}\!\! d^\pi_jx_j~\Big|~\forall~i\!\in\!B(\pi)~~~ b^\pi_i+\!\!\!\sum_{j\in D(\pi)}\!\! G^\pi_{ij}x_j\...
CommunityBot
- 1
2
votes
1
answer
3k
views
max-flow at max-cost
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
CommunityBot
- 1
5
votes
3
answers
8k
views
Linear programming - uniqueness of optimal solution
Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution?
My general problem is to get any vertex of a polytope formed by a ...
- 367
0
votes
1
answer
110
views
How to show inconsistency of a linear system of equations? [closed]
Consider the (real) linear system of equations $A\mathbf{x}=\mathbf{c}$ of size $N$ as
$$
\begin{bmatrix} a_{N}-a_{2}& a_{2}& 0 &\dots& 0 & -a_{N} \\-a_{1} & a_{1}-a_{3}&a_{...
- 54.2k
1
vote
0
answers
173
views
Matrix exponential bounds
Let $A$ be a stochastic matrix, $q\in (0,1)$. How to bound $n$ such that $$q^n A^n e^A \leq e^A$$
Note that here $e^A$ is the matrix exponential, and $\leq$ is taken entrywise.
To be clear, what I ...
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\...
4
votes
2
answers
383
views
Question about preconditioning
I posted the following question on stackexchange but didn't get any replies; I'm hoping perhaps someone can help me here.
I understand that for many iterative methods, convergence rates can be shown ...
- 20.2k
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
3
votes
0
answers
71
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
- 1,835
9
votes
1
answer
492
views
When are two binary matrices simultaneously equivalent to their transpose?
For any real square matrix $A$ there is an invertible matrix $P$ such that $A^t = P^{-1}AP$. I have two binary ($0,1$) matrices $A$ and $B$. When does there exist a $P$ such that $A^t = P^{-1}AP$ and $...
CommunityBot
- 1
2
votes
1
answer
1k
views
Complementary slackness for approximately optimal Dual solution
Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
- 54.2k
12
votes
2
answers
4k
views
How can one construct a sparse null space basis using recursive LU decomposition?
Given an $m$ by $n$ matrix $A$ I'm familiar with the standard method to compute a basis for the null space of $A$ by computing a QR factorization of $A^T$. If $A$ is large and sparse, we can use ...
- 6,045
0
votes
0
answers
890
views
Maximum shortest path problem
I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path.
In ...
- 342
2
votes
0
answers
126
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
CommunityBot
- 1
4
votes
1
answer
444
views
minimizing the product of rayleigh quotient
The problem is:
$$\min_{\alpha}\frac{\alpha^T A \alpha}{\alpha^T\alpha}\frac{ \alpha^T B \alpha}{\alpha^T\alpha}$$
where $A$ and $B$ are symmetric and positive definite matrix.
I think the explicit ...
- 28.6k
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
CommunityBot
- 1
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: \...
- 1
4
votes
2
answers
722
views
Minimum number of rectangles in a polygon
Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.
Example:
Consider the following diagram:
I want to cover maximum shaded ...
- 13k
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
CommunityBot
- 1
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