All Questions
782 questions
1
vote
0
answers
121
views
Algorithm for the nilpotence of matrix polynomials
Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of ...
- 19
0
votes
0
answers
108
views
Solutions to matrix equations in the non-negative integers
For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...
- 101
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
- 13.9k
1
vote
0
answers
147
views
Convergence of infinite linear programming
Suppose we have the following linear program (LP1),
$$\min_{f \in \mathcal{C}} \int_{\mathbb{R}} f(t) \cos(2 \pi x_0 t) dt \\ \text{subject to } \int_{\mathbb{R}}f(t)dt = 1 \\\forall x\in [0,1]: \int_{...
- 53
34
votes
3
answers
6k
views
Why is uncomputability of the spectral decomposition not a problem?
Below, we compute with exact real numbers using a realistic / conservative model of computability like Type Two Effectivity.
Assume that there is an algorithm that, given a symmetric real matrix $M$, ...
- 4,943
-1
votes
1
answer
103
views
How to solve MILP problem on several linear subspaces
I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
- 39
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
1
answer
301
views
Best approximation with tensors of rank $\ge2$
Let $k\in\mathbb N$, $H_i$ be a (finite-dimensional, if necessary) $\mathbb R$-Hilbert space for $i\in I:=\{1,\ldots,k\}$, $H:=\bigotimes_{i\in I}H_i$ denote the tensor product$^1$ of $(H_i)_{i\in I}$ ...
- 167
1
vote
0
answers
82
views
What is the relation between different generalizations of linear programming?
Linear programming subsumed by each of
Semidefinite programming (SDP)
Convex programming (CXP)
SOS programming (SSP)
Is there any relation between each pair in the three?
Are all three equivalent in ...
- 1,826
1
vote
0
answers
78
views
Fast computation of linear equation with row and column removed
Given $A, x, b$ and a linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ is full rank. Denote $A_{\backslash i}$ as a $(n-1)\times(n-1)$ matrix where $A$ removes its $i^{th}$ column and row, ...
- 133
1
vote
1
answer
321
views
Solve linear system with bordered positive definite matrix
I want to solve the usual $A x = b$ system. In block form:
$$ \begin{bmatrix} B & c \\ c^{T} & 0 \end{bmatrix} \begin{bmatrix} x' \\ x_{n+1} \end{bmatrix} = \begin{bmatrix} b' \\ b_{n+1} \end{...
- 139
3
votes
2
answers
506
views
Updating the null space of a matrix
I am facing a problem where I have to find any (nontrivial) vector x such that Ax=0, where A is a rectangular nxm matrix with m>n, so the problem is underdetermined. I must find this x for A, but ...
- 33
1
vote
0
answers
78
views
Reference for the algorithm to find the intersection between a subspace and positive orthant
I came across this algorithm, in this question Algorithm for the intersection of a vector subspace with a cone of non-negative vectors ;
Is there any reference for the algorithm described in the ...
0
votes
1
answer
139
views
Linear programming with exponential inequalities and rational variables
If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
- 1,826
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 ...
1
vote
0
answers
67
views
What are the corners of this polytope?
Let $f$ be a non-negative function on the positive integers such that $f(s+t)\geq f(s) + f(t)$ for all $s,t\in\mathbb{Z}^+$. Consider the polytope consisting of all $x\in \mathbb{R}^n$ such that $$\...
- 11
1
vote
0
answers
175
views
Compute Frobenius inner product of two tensor-trains in terms of tensor contractions
Let $p\in\mathbb N$, $n\in\mathbb N^p$ and identify the Hilbert space tensor $\bigotimes_{k=1}^p\mathbb R^{n_k}$ with $\mathbb R^{n_1\times\cdots\times n_p}$ (equipped with the Euclidean inner product)...
- 167
1
vote
0
answers
27
views
Show that a tensor-train is contained in a recursive sequence of subspaces
Let
$p\in\mathbb N$;
$n_k\in\mathbb N$ and $\left(e^{(k)}_1,\ldots,e^{(k)}_{n_k}\right)$ denote the standard basis of $\mathbb R^{n_k}$ for $k\in\{1,\ldots,p\}$;
$u\in\bigotimes_{k=1}^p\mathbb R^{n_k}...
- 167
1
vote
1
answer
323
views
How can I find minimum and maximum eigenvalue of non-positive define matrix [closed]
There is a power iteration method, but it only returns the greatest(in absolute value) eigenvalue of matrix. So when we have negative eigenvalues it'll give wrong results.
Is there any method, which ...
- 11
0
votes
0
answers
159
views
How to solve a non-local self-consistent equation
I have been struggling lately with solving numerically an equation of the form:
$$ g(x\pm x_{0}) = F[ g(x) ] $$
where $g(x)$ is a matrix satisfying the condition $g(x\to\pm\infty)=0$. My question is ...
- 123
0
votes
1
answer
226
views
Fractional values in linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
0
votes
1
answer
320
views
Sub optimal algorithm for linear programming
Consider the linear programming problem
\begin{align}
f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1
\end{align}where $c$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ ...
- 1,421
1
vote
0
answers
34
views
One-sided Jacobi SVD and Divide&Conquer SVD stability and cost [closed]
I'm studying SVD, in particularly the Jacobi SVD and Divide&Conquer SVD algorithms. I can't find anything on the stability and error analysis on these methods. Also can someone show show me what's ...
- 139
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
0
votes
0
answers
127
views
ADMM for solving linear systems
I would like to use ADMM for solving $Mx=b$, where $M\in \mathbb{R}^{R\times R}$ is symmetric and positive definite. I know that a lot of methods will do for me in this case, but I'm specially ...
- 133
0
votes
1
answer
144
views
Maximize function on rotation matrices [closed]
Let $A$ be a fixed 3-by-3 matrix and $Q$ be a rotation matrix whose yaw, pitch, and roll angles are $\phi\in[0,\pi]$, $\theta\in[0,\pi]$, and $\psi\in[0,\pi/2]$, respectively:
\begin{equation}
Q=
\...
3
votes
1
answer
339
views
How to find the elliptical arc that corresponds to the cubic bezier curve
Let's assume I have a cubic bezier curve that is provided with A, B, C, D points, where
A is the start of the curve
B is the first control point
C is the second control point
D is the end of the ...
- 131
0
votes
0
answers
41
views
Orthogonality condition of symmetric matrix pencil
Let $P(\lambda)=\lambda M−L\in \mathbb{R}^{n \times n}$ be a matrix pencil with symmetric nonsingular matrix $M$ and $L$ is a weighted Laplacian matrix of a connected graph. Clearly $(0,1_n)$ is an ...
- 21
3
votes
0
answers
163
views
A new "adversarial" Wasserstein distance?
Let us consider $\mu_1, \mu_2$ and $\mu_3$ three probability measures living on $[0,1]^{k_1}, [0,1]^{k_2}$ and $[0,1]^k$respectively, with $k_1 +k_2=k$. Let us denote by $\Gamma(\mu,\nu)$ the set of ...
- 555
11
votes
2
answers
963
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
2
votes
1
answer
485
views
Odd cycle transversal
Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, ...
1
vote
2
answers
958
views
Integer linear programming (ILP) formulation of connectivity of induced subgraph
Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
2
votes
1
answer
871
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
237
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
0
votes
0
answers
43
views
Minimizing along independent directions, nonlinear programming
Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...
- 193
7
votes
1
answer
254
views
Numerical method for simultaneous computation of eigenvalues of a family of commuting matrices
I have a problem where I have $n$ commuting matrices $M_1,\dots,M_n$. It is a well-known fact that commuting matrices are simultaneously diagonalizable/triangularizable. I need to find the eigenvalues ...
7
votes
1
answer
427
views
Minimize spectral radius with orthogonal matrix
Let $A$ be a real square and invertible matrix. I would like to find
$$
s(A) = \min_U \rho(U A),
$$
Where $U$ is orthogoal, i.e. $U U^T = I$ and $\rho(A)$ is the spectral radius, i.e. the largest ...
- 909
8
votes
2
answers
404
views
How to obtain the rational solution of a linear system efficiently?
Suppose that I have a linear system $AX=b$ with $A\in\mathbb{Z}^{n\times m}$ and $b\in\mathbb{Z}^{n}$. Assume that $AX=b$ has exactly one rational solution. Then how can I obtain this solution ...
- 133
2
votes
1
answer
128
views
Matrix factorization for dimensional reduction similar to spectral decomposition/SVD
I have a graph clustering problem I'm working on and it basically involves finding a factorization of the adjacency matrix $A$ such that the following equations are (approximately) satisfied:
$$
A \...
- 123
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21
1
vote
1
answer
275
views
Action of square root of tridiagonal matrix product on vector
Assume nonsymmetric, tridiagonal matrices $A, B \in \mathbb{R}^{n\times n}$ (where $n$ is in the order of 1000) and $A, B, AB$ are diagonalizable and have positive eigenvalues.
How do you efficiently ...
- 213
1
vote
1
answer
168
views
Perturbation of the value of a general-sum game at a equilibirium
Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
- 1,127
1
vote
0
answers
282
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
2
votes
1
answer
556
views
How to solve a quadratic matrix equation with positive semidefinite constraint?
I have the following quadratic matrix equation:
$$ XAX+X = B $$
where both $A$ and $B$ are given positive definite matrices, and $X$ is a covariance matrix and, hence, positive definite.
When there is ...
- 101
1
vote
1
answer
130
views
find a PSD matrix that that verify matrices sum of equality
$A $, $ C$ $(n,n)$ are symmetric PSD matrices,
$B$ is PD symmetric matrix, and $H_i$ $\; $ $(i=[1,m])$ represent $ m $ complex matrices. $H_i$ are all one rank matrix
Our objectif is to find ...
- 377
2
votes
2
answers
421
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 461
0
votes
1
answer
405
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
- 133
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
3
votes
0
answers
95
views
Sparse perturbation
Let $x, x_0\in\mathbb{R}^n$ be two vectors satisfying $$\frac{\|x\|_1}{\|x\|_2}\leq\frac{\|x_0\|_1}{\|x_0\|_2}.$$
$\| \cdot\|_1$ and $\| \cdot\|_2$ are the $\ell_1$ and $\ell_2$ norm in $\mathbb{R}^n$,...
- 31