Questions tagged [semidefinite-programming]
Semidefinite programming can be regarded as an extension of linear programming. In a semidefinite program, the goal is to optimize a linear function over the intersection of the cone of positive semidefinite matrices with some affine space.
86
questions
1
vote
1
answer
120
views
Perturbation of positive semidefinite matrix
Consider an $n\times n$ matrix $A$ that is positive semidefinite and has rank $n-1$, so there exists exactly one eigenvector $v$ such that $Av=0$. Let now $B$ be a symmetric matrix such that $v^TBv=0$....
- 459
3
votes
1
answer
103
views
Positive-definite block matrix with constant block sums
Given two natural numbers $n$ and $m$, suppose that $A$ is an $nm \times nm$ real nonnegative matrix. Seeing $A$ as a block matrix where each block has size $m\times m$, suppose that the sum of the ...
- 459
1
vote
0
answers
67
views
Fastest algorithm for finding the closest semi-definite matrix?
Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:
$$
X^* = \mathop{\text{...
- 703
0
votes
0
answers
56
views
Feasibility of a polynomial system of equalities and inequalities
Consider a system of the form $f_i(x) = 0$ and $g_j(x) \ge 0$ ,where $f_i,i=1,\dots,r$ and $g_j,j=1,\dots,s$ are polynomials in real unknowns $x_i,i=1,\dots,n$ with rational coefficients.
Is there a ...
- 1,305
1
vote
0
answers
67
views
If $\hat{D}$ minimizes trace over all $D+ B \succeq 0$, then is $\hat{D}_{ii} \leq \sum_{j} |B_{ij}|$ for each $i$?
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
Let $\hat{D}$ be a solution to the SDP that minimizes $tr(...
- 371
0
votes
0
answers
40
views
Minimizing a certain trace-product involving orthonormal vectors
Let $C$ be an $n \times n$ positive-semidefinite matrix. Fix and integer $1 \le m \le n$, and for orthonormal vectors $v_1,\ldots,v_m$ in $\mathbb R^n$, and set $V := (v_1,\ldots,v_m) \in \mathbb R^{m ...
- 6,466
6
votes
0
answers
102
views
Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...
- 371
1
vote
2
answers
57
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 ...
- 634
0
votes
0
answers
39
views
Linear transformation of intersection of SDP cone and polyhedral cone
Let $A$ be a linear transformation, let $\mathcal{S}^n_+$ be the cone of positive semidefinite matrices. Suppose $P$ is a polyhedral cone. We consider the image of the intersection of the two cones, i....
- 263
0
votes
0
answers
74
views
Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general
Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...
2
votes
1
answer
213
views
Solving linear programming without solving linear programming
Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...
- 9,260
2
votes
0
answers
87
views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...
- 133
0
votes
0
answers
138
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} & \...
2
votes
0
answers
54
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,554
0
votes
0
answers
96
views
On least-squares with positive semidefinite constraints
Given real symmetric matrix $\mathbf{R} \in \mathbb{S}^{n\times n}$ and matrices $\mathbf{X}_n, \mathbf{X}_{n-1} \in \mathbb{R}^{n \times m}$,
$$\begin{array}{ll} \underset{\mathbf{A} \in \mathbb{R}^{...
3
votes
1
answer
140
views
Relaxations for the spectral norm maximization problem
Optimizing the spectral norm of some positive semidefinite matrix $A(x) \in S^{n}$, w.r.t. a list of variables $x \in \mathbb{R}^d$ and semidefinite constraints is, in general, a nonconvex problem (...
- 33
2
votes
0
answers
152
views
Certificates of connectivity of basic semi-algebraic sets
Given real polynomials $p_1, \ldots, p_n \in {\mathbb R}[x_1, \ldots, x_d]$, consider the closed basic semi-algebraic set $S \subseteq {\mathbb R}^d$ given by $$S := \{x \in {\mathbb R}^d : p_i(x) \...
- 51
4
votes
3
answers
230
views
When does a finite metric induce a matrix norm?
If I have a metric $d(\cdot,\cdot)$ on the set $\{1,\dots,n\}$, are there well-known necessary or sufficient conditions for the existence of a matrix norm $Q$ that induces that metric on the unit ...
- 3,868
4
votes
1
answer
169
views
What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?
I'd like to know what is the convex cone generated by $\left\{ (h h^T, h) : h \in \Bbb R^{d\times1} \right\}$. It is known that $$\mathrm{cone} \left\{h h^T : h \in \Bbb R^{d \times1} \right\} = S_+^d$...
- 118
2
votes
0
answers
127
views
Three-constraint homogeneous QCQP
Consider the homogeneous quadratically constrained quadratic program,
$$\min_{u^T u =1} u^T A_1 u$$
$$\textrm{subject to}\quad u^T A_2 u = 0,\quad u^T A_3 u = 0$$
This problem is particularly studied ...
- 1,133
1
vote
0
answers
32
views
Solution to dynamic program-type recursion
I have the following dynamic programming principle-type problem.
Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
2
votes
1
answer
54
views
Convexity of a positive definite objective with min(x,y)-nonlinearity
I have derived an optimization objective of the form
$$
f(x) = \sum_{i,j} C_{ij}\min(x_i, x_j), s.t. g(x) \geq 0
$$
where $C \in \mathcal{R}^{N \times N}$ is a positive definite matrix, and $x \in \...
- 123
1
vote
0
answers
48
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 \...
- 31
0
votes
2
answers
976
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}}
& &...
- 345
3
votes
0
answers
106
views
Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$
Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
- 205
3
votes
0
answers
65
views
Non-negative bivariate polynomials in a rectangle
I have been working on non-negative univariate polynomials and I found the following equivalent relationship to check if a polynomial is non-negative or not:
The polynomial $g(x) = \sum_{r=0}^k y_rx^...
- 131
1
vote
0
answers
46
views
Minimum operator that exceeds others (in a PSD, linear matrix inequality, sense)
Given a collection of $n$ matrices $A_i$, we could ask for the $B$ such that:
$$\textrm{Minimize: }\quad \textrm{Tr}[B]$$
$$\textrm{Such that: }\forall_i\, B \succeq A_i$$
Here $\succeq$ is in the ...
- 1,133
1
vote
0
answers
65
views
SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?
the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs.
Another popular approach to obtain efficient ...
- 91
1
vote
0
answers
80
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,776
1
vote
0
answers
62
views
Reference request for linear matrix inequality with PSD matrices
In literature, people say a spectrahedron is the following set
$$\left\{x \in \mathbb{R}^d : x_1 A_1 + \cdots + x_d A_d \geq B \right\}$$
where $\geq$ is in the positive semidefinite sense. Is there a ...
- 11
2
votes
0
answers
141
views
Representations in Archimedean quadratic modules
Let $\mathbb R [X] = \mathbb R [X_1,\dots,X_n]$ and $\Sigma[X] = \big\{ \, f \in \mathbb R[X] \mid \exists r \in \mathbb N, \ g_i \in \mathbb R[X] \colon f = g_1^2 + \dots + g_r^2 \,\big\}$ denote ...
4
votes
1
answer
194
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\...
- 41
1
vote
0
answers
59
views
Linear algebra - For symmetric matrix X $\in S^n$, prove the $a^T X a$ = $\det X \det(X_{n-1})$ , where $a_i$ = $(-1)^i M_{in} $ [closed]
Suppose we have a symmetric matrix X$\in S^n$, and $X_k$ denotes the submatrix consists of first $k$ rows and columns of X. If $\det X < 0$, but $\det X_1, ..., \det X_{n-1} > 0$. Let $a_i=(-1)^...
- 33
1
vote
1
answer
1k
views
Matrix Completion SDP Relaxation and Duality
I am studying the matrix Completion problem, as well as its SDP relaxation. However, I am having trouble deriving the final SDP form of the matrix completion problem. I will give some background, ...
1
vote
0
answers
88
views
Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related?
I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy:
$$
\inf_{x\in\mathbb{R}^n}\quad p(x),
$$
where $p$ is a polynomial of even degree ...
- 607
2
votes
0
answers
125
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
5
votes
2
answers
326
views
Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)
Currently, what conditions are known to be sufficient for the SDP relaxation of Max-Cut to be exact?
- 51
3
votes
0
answers
142
views
Uniqueness of projection under spectral norm
I am considering
$$
\min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0,
$$
where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...
- 131
2
votes
1
answer
152
views
SDP representation of ideal polynomials for positivstellensatz refutations
If we want to certify the nonexistence of real solutions to a polynomial system of equations, i.e.
$$ S = \{ x\in \mathbb{R}^n \ | \ h_i (x) = 0, \ i=1,\dots,t \} = \emptyset, $$
we can produce a ...
- 21
4
votes
1
answer
187
views
Convex Hull of Outer Products of (Normalised) Nonnegative Vectors
If I define $\mathcal{A} = \{ xx^T : x \in \mathbb{R}^d, \| x \|_2 \leqslant 1 \}$, then (assuming I recall correctly) it is known that the convex hull of $\mathcal{A}$ is given by
\begin{align}
\...
- 634
2
votes
2
answers
158
views
Subspaces of real $n \times n$ matrices of dimension $O(n)$ [closed]
The set of real $n \times n$ matrices forms a vector space over the reals. Given any set $S$ of $n \times n$ matrices, there is a basis $S' \subseteq S$ of size at most $n^2$ such that any $x \in S \...
- 281
3
votes
1
answer
483
views
Advantages of hyperbolic programming over semidefinite programming?
What are the advantages of a hyperbolic program over a semi definite program? SDPs can be used to represent a wide variety of algebraic constraints. Are there constraints that can be represented in a ...
- 133
11
votes
2
answers
702
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$...
- 2,662
3
votes
0
answers
4k
views
About product of PSD matrices
In Theorem 3 in this paper, https://core.ac.uk/download/pdf/82822897.pdf, ``On a product of positive semidefinite matrices, A.R. Meenakshi, C. Rajian, Linear Algebra and its Applications, Volume 295, ...
- 2,136
6
votes
1
answer
2k
views
Solving system of bilinear equations
Consider a collection of $m$ matrices $A_i$ of size $n\times n$, and a vector $b$ of size $m$. I want to solve the bilinear system
$$\left\{ x^T A_i y = b_i : i = 1,\dots,m \right\}$$
in variables $x,...
- 2,459
3
votes
2
answers
1k
views
Strict complementary slackness for semidefinite programs with strong duality
By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...
- 11.7k
2
votes
2
answers
267
views
Is this parametrized semidefinite program convex?
I am considering an optimization problem of the form:
\begin{equation}
\begin{split}
f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\
&\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\
&\;\;\;\;\;\;\;\;\;\;\; \...
- 101
3
votes
0
answers
603
views
Can a quadratic matrix inequality constraint be convex?
I have an optimization problem with a semi-definiteness constraint:
$$
N \preceq 0
$$
where the entries $N^{AB}$ of the matrix $N$ are defined through
$$
N^{AB} = \sum_{i,j} x^i M_{ij}^{AB} x^j
$$
The ...
- 131
1
vote
1
answer
128
views
On Polynomial Characterization of Projection area of semidefinite matrices
Suppose $m,n$ are positive integers.
$D$ denotes the set of $n\times n$ complex semidefinite positive matrices with unit trace.
$A_1,\cdots,A_m$ are $n\times n$ Hermitians.
We are interested in the ...
- 1,463
4
votes
1
answer
472
views
Common lower bounds for positive semidefinite matrices
Suppose we are given positive semidefinite matrices $P_1, P_2, \dots, P_n \in \mathbb{C}^{m \times m}$.
How to characterize the set $S$ of their common lower bounds $$S = \{Q \mid 0 \leq Q\leq P_i, \...
- 1,463