All Questions
783 questions
0
votes
1
answer
320
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
1
vote
0
answers
198
views
Complexity of singular value decomposition using matrix multiplication oracles
Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. ...
- 63.9k
0
votes
1
answer
118
views
Proving maximum value of a determinant of $I - B$, where $B$ is nonnegative matrix
I have the following setting:
Let $0 \leq r < 1$ and let $\{z_i\}_{i=1}^k$ be $k$ complex numbers such that $|z_i| \leq r$ for all $i$.
Moreover, $r + \sum_{i=1}^k 2Re(z_i) \geq 0$
I am interested ...
- 128k
3
votes
2
answers
2k
views
Iterative methods for linear system with non-diagonally dominant matrix
I have a linear system
\begin{align*}
\left[\begin{array}{cccc}
1 & 2 & 1 & -1 \\
3 & 2 & 4 & 4 \\
4 & 4 & 3 & 4 \\
2 & 0 &...
- 20.2k
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 5,429
1
vote
0
answers
61
views
Linear programming robustness to input perturbations
I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
- 11
2
votes
1
answer
644
views
How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]
I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
- 162
1
vote
1
answer
223
views
Does Wilkinson's shift need to be discontinuous?
Given a symmetric Hessenberg matrix $A = \left[\begin{matrix}\ddots& \vdots & \vdots\\\dotsb & a & b\\\dotsb& b & c\end{matrix}\right]$, the Wilkinson shift $\mu$ employed in ...
- 4,943
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 63.9k
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 63.9k
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
5
votes
1
answer
251
views
Smooth, non-analytic functions of non-normal matrices
My apologies if this isn't a well-enough-posed question, I think I'm partly unsure of what exact question to even ask.
There are many different ways in which we can take a function of a matrix.
We ...
- 52.3k
1
vote
0
answers
35
views
How to chose the start vector for the MTZ variables
In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
- 4,713
2
votes
1
answer
421
views
Is it possible to obtain orthogonal (but not normalized) vectors after QR factorization?
After QR decomposition of a matrix, $M$, the columns of Q are orthonormal. Is it possible after obtaining Q, we recover unnormalized column vectors from $Q$? For example, the matrix M has the ...
- 879
1
vote
0
answers
200
views
Drawing a 3D object in a 3D environment, and converting to math [closed]
So I have been granted a free time and I want to work on a project but first I had to research.
As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...
- 11
0
votes
0
answers
109
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
3
votes
0
answers
147
views
Convolution integral and its matrix representation
My background is chemistry and I was exploring some one dimensional deconvolution problems i.e., resolution of two or more overlapping peaks. A lot of excellent work was done in the 1970-80s. However, ...
- 879
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
1
vote
1
answer
82
views
Do we really need degree constraints for ILP formulations of TSP problems
The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
- 5,429
0
votes
1
answer
266
views
Using QR or SVD to sum up finite number of matrices
Problem
I was wondering if there are any theoretical results that tackle the following problem:
Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\...
CommunityBot
- 1
1
vote
0
answers
58
views
Second-order envelope theorem for linear programming
Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...
- 373
1
vote
1
answer
475
views
Sufficient conditions for a system of linear inequalities to admit a solution
I am looking for sufficient conditions such that a system of linear inequalities of the type $A x >0$ admits a non-negative solution $x \in \mathbb{R}^n_+$. I know a few properties of the $m \times ...
1
vote
0
answers
37
views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
2
votes
1
answer
91
views
Where has the necessary and sufficient condition for the convergence of the unshifted QR algorithm been stated?
I've obtained a necessary and sufficient condition for the unshifted QR algorithm to converge. The condition for the algorithm to converge for a square matrix $M$ is:
For any two eigenvalues $\lambda$...
- 188k
2
votes
0
answers
194
views
Maximize the product of Hadamard matrix and a vector
Let $X$ be an $n \times n$ Hadamard matrix (i.e. entries are in $\{-1,1\}$ and rows are orthogonal). For my application, we can assume $n=2^k$.
Given a vector $\bf{w} \in R^n$, I want to find the $X^*$...
- 21
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 32.1k
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
- 32.1k
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 32.1k
5
votes
1
answer
124
views
Is Sun's spectral variation bound for normal matrices optimal?
In On the variation of the spectrum of a normal matrix, Sun proves the following result (Corollary 1.2):
Let $A$ be an $n$-square normal matrix and $B$ an arbitrary $n$-square matrix. Then $$ \min_{\...
CommunityBot
- 1
6
votes
2
answers
2k
views
Complexity of rectangular matrix multiplication
I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$.
From [Le Gall and Urrotia], I know that:
if $A$ and $B$ are square-matrices of size $n$, then this can ...
- 562
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
0
votes
0
answers
165
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
0
votes
0
answers
137
views
Any technique for linearization, or linear approximation?
Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...
0
votes
3
answers
7k
views
Find an $N$-dimensional vector orthogonal to a given vector
I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only ...
- 1
0
votes
0
answers
227
views
Decomposition of symmetric block matrix
I came across this question and got really interested about it. There, the OP asks whether is possible to decompose a $2n \times 2n$ block matrix:
$$ \begin{pmatrix}
X & I \\
I & Y
\end{...
0
votes
1
answer
131
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
- 63.9k
2
votes
0
answers
75
views
Dense matrix vs sparse matrix, when they have same number of nonzero elements
I came across a new way in the literature to solve PDE problems numerically, which is called 'Patch Reconstruction'. One example paper is: Li, R., Sun, Z., Yang, F., & Yang, Z. (2019). A finite ...
- 12.9k
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
0
votes
1
answer
214
views
How do you call a linear programming problem when the solution should be "constrained" to a norm?
(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...
- 1,714
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 14k
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
11
votes
2
answers
1k
views
Existence of sparse LU decomposition of sparse matrix
Let $A$ be a sparse matrix over some field. I would like to know about the existence of LU decompositions so that $L,U$ are both sparse.
More precisely, let $A$ be an $N$-by-$N$ matrix. Suppose each ...
- 3,741
0
votes
1
answer
116
views
Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
- 5,429
3
votes
1
answer
439
views
Derivative of eigenvalues of a symmetric tridiagonal matrix built via the Lanczos-Arnoldi scheme
Suppose $\mathbf{A}(\mu)$ being a symmetric positive definite matrix of dimension $n$ where its elements depend parametrically on the real parameter $\mu$.
Suppose now to build the orthonormal basis ...
- 188k
2
votes
3
answers
753
views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
- 13.2k
2
votes
1
answer
164
views
The "best way" to order unknowns in linear systems
Start with a linear system of the form
\begin{equation*}
Ax + Bt + C = 0,
\end{equation*}
where $x = (x_1, \dots, x_n) \in \mathbb R^n$ is the vector of unknowns, $t \in \mathbb R^m$ is a vector of ...
- 20.2k
2
votes
1
answer
591
views
Intersection of a vector subspace with a cone
Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
- 6,962
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k