All Questions
783 questions
0
votes
1
answer
112
views
Is there a specific name for this optimization problem?
Let $A$ be an $n\times n$ symmetric positive definite matrix with eigenvalues and eigenvectors $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n>0$ and $v_1,v_2,\cdots,v_n$ respectively.
We know that the ...
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
1
answer
98
views
Optimality gap between a joint linear program and decoupled sub programs
Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...
- 5,429
1
vote
0
answers
79
views
Is there an efficient way to do semidefinite programming with a Lyapunov equation constraint?
I am trying to numerically solve semidefinite programs of the form
$$\begin{array}{ll} \underset{X,Y}{\text{minimize}} & \operatorname{tr}(AX)\\ \text{subject to} & BY + YB = X\\ & X, Y \...
2
votes
0
answers
47
views
Transforming a symmetric matrix into pentadiagonal form
Given a symmetric matrix $A$, which has complex values in the diagonal, but whose all other entries are real, I am interested in finding an orthonormal transformation $Q$ such that $Q^tAQ$ is a ...
- 251
1
vote
0
answers
81
views
Algorithm for deciding feasibility of linear programs [closed]
Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...
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 ...
CommunityBot
- 1
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
1
vote
0
answers
192
views
What is the solution of the matrix equation $A X + X A' + B X B' + C = 0$ for $X$?
I know that the matrix equation $A X + X A' + C = 0$ is in the form of the time-continuous Lyapunov equation, so solving for $X$ is pretty trivial since the solution already and numeric solvers ...
- 111
3
votes
2
answers
246
views
A problem about determinant and matrix
Suppose $a_{0},a_{1},a_{2}\in\mathbb{Q}$, such that the following determinant is zero, i.e.
$
\left |\begin{array}{cccc}\\
a_{0} &a_{1} & a_{2} \\
\\
a_{2} &a_{0}+a_{1} & a_{1}+a_{...
- 56.9k
5
votes
1
answer
837
views
Row-based iterative algorithms for computing the kernel of a matrix
Suppose $A$ is an $m \times n$ matrix in the form
$$A=\begin{pmatrix} — a_1 —\\ — a_2 —\\ \vdots \\ — a_m — \end{pmatrix}$$
where $a_i \in R^n$ is the $i$-th row of $A$. I know that it is possible ...
CommunityBot
- 1
0
votes
1
answer
535
views
Conditions to solve linear system with matrix blocks
How to verify if a linear system of symmetrical matrix blocks has solution?
I have the matrix:
$\left[M\right]_{p \times p}$, symmetrical
$\left[G\right]_{p \times q}$
and then, I would like to ...
0
votes
0
answers
57
views
Numerically finding matrix approximation by lower-dimensional "pseudo-similar" matrix
Consider an $N\times N$ (real or complex) matrix $A$, and some $n<N$. Is there a good numerical algorithm that finds the set consisting of an $n\times n$ matrix $B$, an $n\times N$ matrix $I$, and ...
- 3,001
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 3,065
4
votes
1
answer
747
views
Condition number for matrix of eigenvectors of a diagonalizable matrix
Let $A$ be a diagonalizable matrix, i.e., $A=SDS^{−1}$. For any matrix $A$, condition number is defined as $\kappa(A)=\|A\| \|A\|^{-1}$.
For $A$ being a diagonalizable matrix, define $G_A=\{{S: S^{-1} ...
- 41
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 5,971
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
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 ...
- 35.5k
1
vote
1
answer
157
views
Constructing representations of probability revision functions
Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\...
- 631
3
votes
1
answer
202
views
Does there exist an O(n^3) algorithm for deciding whether PAP^T = LDU is solvable given some square matrix A?
Let $A$ be an arbitrary real square matrix. Does there exist an $\mathcal O(n^3)$ algorithm for deciding whether there exists a permutation matrix $P$, lower unit triangular matrix $L$, upper unit ...
CommunityBot
- 1
0
votes
1
answer
230
views
Solution of complex linear system
In Brubeck, Nakatsukasa, and Trefethen - Vandermonde with Arnoldi (example 3) they solve the following linear system:
$$\operatorname{Re}\left(\begin{array}{ccc}1 & \cdots & z_{1}^{n} \\ 1 &...
- 45
6
votes
1
answer
763
views
What is the big-O complexity of solving the sparse Laplace equation in the plane?
In MATLAB, you can get a 2d Laplacian via A = delsq(numgrid('S',N)); yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized ...
- 981
21
votes
3
answers
51k
views
What is the time complexity of truncated SVD?
Full SVD, on an $m \times n$ matrix $A$, [U,S,V] = svd(A), would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest ...
- 6,367
1
vote
1
answer
628
views
Allowing an "OR" option between equations in a linear program
I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...
- 34.3k
1
vote
1
answer
146
views
Norm of a matrix with clustered eigenvalues
On page 271 of Trefethen and Bau's Numerical Linear Algebra, it is constructed a matrix
$$A=2I_{m\times m}+0.5\cdot\frac{\text{rand}(m)}{\sqrt{m}}$$
for $m=200$, where rand(m) is an array with $m\...
7
votes
0
answers
116
views
Are there attempts to numerically finding algebraic structures over finite-dimensional vector spaces?
By "algebraic structure" I mean a finite set of linear operators between tensor products of copies of one (or more) finite-dimensional (complex or real) vector spaces, fulfilling a set of ...
- 3,001
2
votes
1
answer
139
views
linear programming with $n$ choose $r$ variables
Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is ...
CommunityBot
- 1
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
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$ ...
CommunityBot
- 1
1
vote
1
answer
326
views
For the purposes of solving linear equations, is there a fast decomposition that works for all Hermitian matrices?
Let $A$ be an arbitrary Hermitian matrix. Is there a way of efficiently factorizing $A$ for the purposes of solving $Ax = b$ for arbitrary $b$?
There are two decompositions I'm aware of that nearly ...
- 4,943
2
votes
2
answers
107
views
Solution to a matrix optimisation problem with a particular structure
Does a matrix of the form $A_{ij} = v_i + v_j$ for some arbitrary vector $v$ have a particular name?
I am attempting to find the closed form solution (if it exists, although it looks like it might) ...
- 31
0
votes
0
answers
68
views
Convex optimization under asymmetric loss in infinite dimensional space
The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...
- 45
1
vote
1
answer
144
views
Complexity of solving $\sum_i A_i X B_i = C$
Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation?
$$\sum_i^n A_i X B_i = C$$
With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature ...
- 3,065
9
votes
1
answer
472
views
$M = AA^t$ where $A$ has unit norm columns
Let $M \in \mathbb{R}^{k\times k}$ positive definite with $\operatorname{tr} M = m$, where $m$ is an integer such that $m \geq k$. I have found a way (using this answer) to decompose $M = AA^t$ with $...
- 185
6
votes
1
answer
222
views
Computing $(AA\otimes BB + AB \otimes BA)^{-1}$
Can anyone suggest a way to numerically compute the following matrix vector product?
$$u=A^{-1}b=(AA\otimes BB + AB \otimes BA)^{-1}\operatorname{vec}(C)$$
Here $AA,BB,AB,BA$ and $C$ are $d\times d$ ...
- 3,065
2
votes
1
answer
763
views
Integer solution of optimal transport
Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
- 12.7k
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
4
votes
2
answers
948
views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
- 384
1
vote
0
answers
92
views
Approximating matrix multiplication with integer arithmetic
The following question is inspired with approximation of matrix multiplication computations occurring in numerical simulations and machine learning algorithms with a use of efficient integer ...
- 3,065
1
vote
1
answer
3k
views
How to minimize l1-norm constrained by "infinity norm"
Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems:
P.1.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\
\text{s.t. } \| x \...
- 13
9
votes
1
answer
559
views
What is the Lipschitz constant of the differential of the matrix exponential $\mathfrak{so}(3)\to \mathrm{SO}(3)$
I'm interested in numerical methods on $\mathrm{SO}(3)$ manifold, and working on a particular problem using the exponential coordinates:
$$
R(u) := \exp(u_\times)
$$
with $u\in \mathbb{R}^3$ and where ...
- 111
16
votes
3
answers
15k
views
Interesting relationships between Cholesky decomposition and diagonalization
Let $\Sigma$ be a hermitian positive definite matrix and $L$ be its Cholesky decomposition so that $LL^\ast=\Sigma$. Furthermore, let's diagonalize $\Sigma$ as $\Sigma = P\Lambda P^\ast$. $\Lambda$ is ...
- 1,902
1
vote
1
answer
279
views
Splines linearly independent
Let $N_1:=\chi_{[0,1]}$ be defined as this characteristic function and $N_n:=N_{n-1}*N_1$ then this leads to polynomials with support $[0,n]$. These splines are well-studied click for wikipedia My ...
- 3,065
0
votes
1
answer
126
views
An otherwise linear matrix equation with the presence of a signum function : reference request
Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$
$\pmb{c}$ is a $n\times1$ matrix.
$G$ is a $n\times n$ matrix which is also positive definite.
matrices $G$ and $c$ are real.
$L$ is a $n\...
- 5,429
2
votes
0
answers
617
views
block diagonal approximation of (SPD) matrix
I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
- 3,065
3
votes
0
answers
122
views
Convex optimization upper bound for a non-linear optimization
Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem?
\begin{align}
\max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
- 63.9k
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 ...
- 3,574
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
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