All Questions
Tagged with matrices oc.optimization-and-control
107 questions
4
votes
1
answer
228
views
A question on eigenvalue of parametric matrix
Is there a way to efficiently check if all matrices in the following set are Hurwitz stable (eigenvalues strictly in the left-hand plane)?$$\left\{ A \in \Bbb R^{n \times n} : \ell_{i,j}\leq A_{i,j} \...
CommunityBot
- 1
1
vote
1
answer
67
views
Low rank matrices which preserve maximizers of quadratic form
Suppose $x, y \in \{0,1\}^d$ are binary vectors. For a matrix $M$ consider the quadratic form,
\begin{align}
x^T M y + (\mathbb{1} - x)^T M (\mathbb{1} - y)
\end{align}
Does there exist an $M$ such ...
CommunityBot
- 1
1
vote
1
answer
519
views
Optimal transport between two matrices
I'm investigating the use of optimal transport to define a distance between non-negative matrices that satisfy the condition $\mathbf e^\top\mathbf M\mathbf e = 1$ (i.e., the sum of all elements in ...
CommunityBot
- 1
3
votes
1
answer
255
views
Minimizing quadratic objective under orthogonality constraints
The following problem is motivated from Generalized Procrustes Analysis. I am wondering if it is possible to obtain a closed form minimizer (which may involve SVD or some other decomposition of a ...
CommunityBot
- 1
12
votes
2
answers
800
views
A (linear) optimization problem subject to (linear) matrix inequality constraints
Let $A \in \mathbb{R}^{n \times n}$ be a Hurwitz matrix, i.e. $A$ satisfies $\mathrm{Re}\,\lambda_i< 0$, where $\{\lambda_i\}_{i=1}^n$ is the set of eigenvalues of $A$. Suppose that the trace of $A$...
CommunityBot
- 1
1
vote
0
answers
63
views
The rank of a matrix expression
I'm studying discrete-time LTI systems and state estimators for them. Recently, I studied this paper. I am facing a matrix rank calculation problem and having trouble solving it. I will provide more ...
- 4,484
0
votes
0
answers
53
views
Relations between the optimal solutions of two related SDPs
In system theory, we often encounter Semi-Definite Programs (SDPs) with Linear Matrix Inequality (LMI) constraints, such as those presented in this paper. I have introduced new variables based on the ...
- 4,484
2
votes
0
answers
72
views
Gradient descent over the set of complex symmetric matrices
In the course of my research (somewhat related to compressive sensing), I am trying to determine a complex, symmetric matrix $L$ (i.e. $L = L^T$) through the following optimization formulation:
$$ \...
- 63.9k
4
votes
1
answer
7k
views
Matrix optimization problem
This is (probably) an easy one:
Given a positive definite matrix $M$, find the positive definite matrix $X$, which minimizes $\textrm{tr}(X M)$ subject to $\det(X) = 1$.
Looking for how to find X, ...
- 1,446
0
votes
1
answer
134
views
Existence of cyclic subspace decompositions for pairs of commuting matrices
Let $\mathbb{K}$ be an arbitrary field (possibly finite). Let $V$ be a finite-dimensional vector space over $\mathbb{K}$, and let $A,B$ be two linear endomorphisms of $V$ which commute.
For $v\in V$, ...
- 16.2k
5
votes
2
answers
343
views
Maximal eigenvalue of a correlation matrix with some entries fixed as zeros
Let $A$ be real a positive semidefinite matrix of dimension $n$ and with $1$s on the diagonal. Those matrices are sometimes referred to as correlation matrices. From the positivity of the minors, we ...
5
votes
1
answer
261
views
Bounds on number of "non-metric" entries in matrices
Question:
what upper bounds are known on the number of non-metric entries of finite dimensional square matrices $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ with strictly positive off-diagonal elements $...
CommunityBot
- 1
3
votes
1
answer
730
views
Computational complexity of low rank SDP
Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{...
1
vote
0
answers
221
views
Nonunique low-rank matrix completion from a few entries
Suppose we want to have a good approximation for the following NP-hard problem
$$\min_{\bf X} \operatorname{rank}({\bf X}) \text{ s.t. } \mathcal{A}({\bf X}) = {\bf b}, {\bf X} \succeq 0$$
where ${\bf ...
1
vote
2
answers
69
views
Monotonicity of kernel matrices with respect to hyperparameters
Let $\mathcal{X}$ be some nice space, let $\Phi$ be some ordered space, and let $K :\mathcal{X} \times \mathcal{X} \times \Phi \to \mathbf{R}$ be a positive-semidefinite kernel indexed by a ...
- 3,979
6
votes
1
answer
1k
views
Solve equation with matrix variable
I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1,\ldots,K$ are known, and are positive definite matrices. $\Omega$ also has to ...
- 6,357
1
vote
0
answers
49
views
Bounds on Eigenvalues After Skew-Symmetric Perturbation
Consider two matrices $\mathbf{J} \in \mathbb{R}^{n \times n}$ and $\mathbf{L} = -\mathbf{L}^T \in \mathbb{R}^{n \times n}$. I am trying to upper bound the eigenvalues of their sum:
$$\mathbf{A} = \...
- 11
1
vote
3
answers
345
views
How to optimize for the best fit nonuniform-scale-rotation to a given 3×3 matrix?
Given a matrix $L\in \mathbb{R}^{3 \times 3}$, I'm looking for a method to find the closest (in a least squares sense) product of a non-uniform scaling matrix and a rotation matrix:
$$
\min_{s\in\...
- 61.9k
3
votes
1
answer
3k
views
How do I optimize over (or take derivative wrt) a square diagonal matrix?
I would like to solve the following optimization problem in $k$-vector $w_i$
$$ \min_{w_i} \quad \left\|P_i - X \mbox{diag} (w_i) Y^T \right\|_F^2 $$
where $P_i$ is a $6 \times 6$ matrix, $X$ and $Y$ ...
3
votes
2
answers
246
views
$\min(\det(\mathbf{A}))$ for special matrix $\mathbf{A}$
(The construction of matrix $\mathbf{A}$ is not difficult to be understood. You can first jump to A Toy Example to take a glance. Any idea or suggestion would be appealing for me.)
The Original ...
1
vote
2
answers
307
views
How to solve this system of Matrix equations? (Coupled riccati equations?)
I am trying to solve for K in the following problem:
$ 3I = A_1 + A_2 + A_3$
$ A_1 K A_1 = K_1 $
$ A_2 K A_2 = K_2 $
$ A_3 K A_3 = K_3 $
Where $I$ is the identity, $K, K_1, K_2, K_3, A_1, A_2, ...
- 1,216
0
votes
0
answers
159
views
Double summation of matrices as constraints in convex optimization in CVX
I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53:
\begin{align}
\text{minimize} &\qquad s\\
\text{subject to} & \...
- 63.9k
8
votes
2
answers
380
views
Projecting onto space of matrices with spectral radius less than one
Consider the space
$$ S = \left\{ A \in \mathbb{R}^{n \times n} : \mathrm{SpectralRadius}(|A|) \leq 1 \right\}$$
where $|A|$ is the entry-wise absolute value. Given a matrix $M \in \mathbb{R}^{n\times ...
- 20.2k
4
votes
2
answers
1k
views
Optimizing over matrices with spectral radius <1?
Suppose $F(x)$ is a convex objective function on $n\times n$ matrices, and I need to numerically optimize $F$ with the condition that $x$ has spectral radius less than $1$. This might be too hard, so ...
4
votes
1
answer
254
views
Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices
For a given Hermitian matrix $A$ (i.e. complex matrix with $A_{ij}^{\ast}=A_{ji}$) find its max-norm projection onto the set of complex positive semi-definite matrices:
$$\Pi(A)=\mathrm{argmin}_{M\...
CommunityBot
- 1
7
votes
2
answers
486
views
The odd power of copositive matrix
If $A$ is copositive, what about $A^3$? Is it also copositive? More generally,
my question is whether the odd power of a copositive matrix is still copositive.
Any reference is appreciated
- 19.6k
0
votes
0
answers
46
views
Lipschitz solutions to linear complementarity problems (LCP)
Let $M\in\mathbb{R}^{n\times n}$.
For $q\in\mathbb{R}^n$, define the set:
$$S_M(q)=\{y\in\mathbb{R}^n|y\ge 0,q+My\ge 0, y^\top (q+My)=0\}.$$
This is the set of solutions to the LCP $(q,M)$.
We say $...
- 183
1
vote
1
answer
1k
views
Prove that absolute value of eigenvalue is smaller than 1 [closed]
I want to prove that the absolute value of the eigenvalues of a matrix A are smaller than 1 for $$A=\left(\begin{array}{cc}
0 & -H_{11}^{-1} H_{12} \\
-H_{22}^{-1} H_{21} & 0
\end{array}\right)...
- 52.3k
0
votes
0
answers
193
views
Rewriting Kronecker product
im considering a pole placement problem in control theory and my controler has a specific form:
$$R=I_n\otimes q$$
where $I_n$ is the identitiy matrix of size $n$ and $q\in\Re^k$ is a vector of the ...
- 188k
1
vote
0
answers
78
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 \...
0
votes
2
answers
1k
views
Matrix norm minimization and matrix inner product
One of the famous problem in SDP is the matrix norm minimization (see S. Boyd, Convex Optimization, p. 170).
Consider:
\begin{equation}\label{eq:Lasse}
\begin{aligned}
&\min_{\mathbf{x}}
& &...
- 3,065
0
votes
0
answers
113
views
Reference for matrix Lyapunov function / matrix dynamic system / stability
We usually consider $\dot{x} = f(x)$, where $x$ is a vector.
Now, I want to consider $$\dot{X}=f(X,U),$$ where $X$ is a square matrix $\mathbb{R}^{n\times n}$ state, $U$ is a square matrix variable $\...
- 2,821
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
1
vote
2
answers
87
views
Stability of linear controller in the presence of a lag
Consider the following equation:
$\ddot{x} = -a x - b \dot{x}$
which we interpret as saying that we are trying to control $x$ by setting $\ddot{x}$.
We can rewrite this with $X = \begin{bmatrix}
...
- 61.9k
1
vote
0
answers
514
views
Minimizing the Frobenius norm of a quadratic matrix expression
Given matrices $R \in \mathbb R^{m \times n}$ and $Y \in \mathbb R^{p \times n}$, where $R$ is full rank, how can I solve the following optimization problems?
$$\min_{X \in \mathbb R^{p \times m}} \| ...
- 11
0
votes
1
answer
194
views
Optimization problem involving matrix
I am struggling to solve an optimization problem of the following form:
$$\begin{array}{ll} \underset{A}{\text{maximize}} & \log \det (A) \\ \text{subject to} & a^T A^{-1} a \le b\end{array}$$
...
- 1,517
8
votes
1
answer
2k
views
Symplectic block-diagonalization of a real symmetric Hamiltonian matrix
Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal?
Being ...
- 20.2k
2
votes
1
answer
2k
views
Finding permutation matrix $P$ that minimizes the trace of $P C P^T D$
I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case...
thanks for your help in advance
I want to find permutation ...
0
votes
0
answers
95
views
How to maximum L1 norm problem?
I have met a problem these days.
\begin{equation}
\underset{\omega}{\max} \quad \Vert \text{diag}(\mathbf{h}^H)\mathbf{G}^H\mathbf{\omega}\Vert_1 \\
s.t.\quad\mathbf{\omega}^H\mathbf{G}\mathbf{G}^H\...
- 171
2
votes
1
answer
536
views
Minimize matrix norm over the unitary matrices
Suppose $C_1$ and $C_2$ are some fixed $n \times n$ matrices. Define the norm $\| M \| = \sum_{i = 1}^n \max_j |M_{ij}|$. What is $\min_U \|C_1 U C_2 \|$? Here $U$ ranges over the $n \times n$ unitary ...
- 6,351
1
vote
0
answers
152
views
solving a non-linear Matrix equation
I am working on a problem of optimization of wireless sensor networks in order to achieve the optimal power allocation in the network. I find an equality matrix problem that can be written as ...
- 377
5
votes
1
answer
335
views
Projecting a symmetric matrix onto the space of linear operators with a particular eigenvalue
Specifically, I am interested in the case where one eigenvalue is exactly $0$. Given an $n \times n$ symmetric matrix, I would like to find the closest $n\times n$ symmetric matrix that has one ...
1
vote
1
answer
877
views
Minimization problem involving the inverse of an affine matrix function
I want to minimize $v^T (A+I+UQU^*)^{-1} v$, subject to $Q$ and $A$ being positive semi-definite and ${\rm trace}(Q)<1$. Here, $v$ is a given vector with unit norm, that is, $\|v\|_2=1$.
- 377
2
votes
1
answer
497
views
Does the Perron vector maximize $x^TAx$ in the simplex?
Let $\mathbf{A}$ be any $n\times n$ symmetric positive matrix ($A_{ij}>0$). It is easy to show that the solution to the following optimization problem
\begin{align}
\max_{\mathbf{x}}~~\mathbf{x^...
3
votes
0
answers
111
views
Approximate inverse of large sparse matrix
Given a large sparse matrix $M$, how to determine the existence of a good preconditioner? In other words, does there exist a sparse matrix $X$ such that $X M$ is close to the identity with respect to ...
5
votes
3
answers
3k
views
A nice necessary and sufficient condition on positive semi-definiteness of a matrix with a special structure
Let
$$
A =
\begin{pmatrix}
\sum_{j\ne 1}a_{1j} & -a_{12} & \cdots & -a_{1n}\\
-a_{21} & \sum_{j\ne 2}a_{2j} & \cdots & -a_{2n}\\
\vdots & \vdots & \ddots & \...
- 63.9k
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 20.2k
1
vote
2
answers
143
views
Controllability Gramian asymptotics for small times
Set-up. Consider the following linear controlled system
$$
\dot{y}(t) = A y(t) + B u (t), \ \ t \in [0,T], \ \ \ \ \ \ \ \ \ \ (1)
$$
where $y$ is the state of the system, $y(t) \in R ^n$, $A \in R ...
- 3,223
0
votes
1
answer
135
views
Solving Problem: LMIs and block matrices
I have been reading through this paper (https://ieeexplore.ieee.org/document/7995739) where I am stuck with this particular LMI. If you are familiar with control theory, the author is trying to find ...
- 63.9k
4
votes
0
answers
249
views
Is every stable matrix orthogonally similar to a $D$-skew-symmetric matrix?
Let $\mathrm{diag}(A)$ denote the diagonal matrix with diagonal entries of $A\in\mathbb{R}^{n\times n}$ and let $\succeq$ denote the standard partial order in the cone of (symmetric) positive definite ...
- 2,712