# 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.

56
questions

**2**

votes

**0**answers

36 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 ...

**2**

votes

**1**answer

58 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\...

**1**

vote

**0**answers

54 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)^...

**1**

vote

**1**answer

111 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

62 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 ...

**2**

votes

**0**answers

92 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 ...

**4**

votes

**2**answers

138 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?

**3**

votes

**0**answers

73 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 ...

**2**

votes

**1**answer

87 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 ...

**4**

votes

**1**answer

89 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}
\...

**2**

votes

**2**answers

146 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 \...

**2**

votes

**1**answer

248 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 ...

**10**

votes

**2**answers

456 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**

votes

**0**answers

1k 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, ...

**5**

votes

**1**answer

674 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 $\{x^T A_i y=b_i:i=1,\dots,m\}$ in variables $x,y$. Is there an ...

**2**

votes

**2**answers

423 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 ...

**1**

vote

**1**answer

205 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, \\
&\;\;\;\;\;\;\;\;\;\;\; \...

**3**

votes

**0**answers

352 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 ...

**1**

vote

**1**answer

122 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 ...

**4**

votes

**1**answer

250 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, \...

**3**

votes

**2**answers

300 views

### Standard solution to semidefinite program [closed]

I have an optimization problem of the following form
$$\text{minimize} \,\|Qa-b\|_2 \quad \text{ subject to } Q \succeq 0$$
where $a,b \in \mathbb{R}^n$ are given and the $n \times n$ square matrix ...

**2**

votes

**0**answers

141 views

### Lovasz theta and circulant graphs

Let $\theta(G)$ denote Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be Lovasz upper bound for $\theta(G)$.
Let $C_{2n+1}$ denote cycle graph with $2n+1$ nodes.
We know following two ...

**2**

votes

**1**answer

926 views

### Full rank submatrices of positive semidefinite matrix

Suppose $A$ is symmetric, positive semidefinite and all its diagonal entries are strictly positive (real coefficients - even integer if it helps). Suppose that the first $r$ rows of $A$ are linearly ...

**5**

votes

**1**answer

280 views

### Maximize the determinant of Boolean combinations of positive definite matrices

I have the following optimization problem.
$$\begin{array}{ll} \text{maximize} & \det \left(\sum^n_{i=1}z_i W_i \right)\\ \text{subject to} & \sum_{i=1}^n z_i = N\\ & z_i
\in \{0,1\}\end{...

**1**

vote

**0**answers

62 views

### Soft: Lagrange Multiplier and Intersection of Thickened Sets

Suppose I have an optimization problem of the form
$$
\inf_{\{x \in \mathbb{R}^d: g(x)=0\}} f(x),
$$
for some convex function $f$ and non-convex l.s.c. function $g$.
Can we reinterpret the ...

**1**

vote

**0**answers

450 views

### Why are SDP generally slow?

This is more of a conceptual question. Don't expect a highly mathematical question. Nonetheless, the questions I pose here often arise in my field (not mathematics).
Usually Semidefinite Programs (...

**3**

votes

**2**answers

885 views

### SDP relaxation vs LP relaxation

I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...

**4**

votes

**0**answers

106 views

### Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)

I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program
\begin{align}
\max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~...

**1**

vote

**0**answers

84 views

### determine the existence of positive semi-definite matrix

Given a $d\times d$ complex matrix subspace $S$, we are asking whether there is some finite integer $n$ such that there exists a non-zero positive semi-definite matrix is orthogonal to $S^{\otimes n}$....

**5**

votes

**1**answer

611 views

### Structure of a real 3x3 positive-semidefinite matrix whose eigenvalues verify the triangle inequalities

It is known that a 3 by 3 real symmetric matrix $A$ has an eigendecomposition
$$ A = Q E Q^T $$
where $Q$ is an orthogonal matrix and $E$ is a diagonal matrix whose elements, $E_{11}$, $E_{22}$ and $...

**1**

vote

**0**answers

186 views

### SDP based heuristics for graph coloring

This is a question about semidefinite programming heuristics for graph vertex coloring based on the Lovasz theta number such as "Approximate Graph Coloring" by Karger, Motwani and Sudan or "A ...

**4**

votes

**2**answers

345 views

### About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form or ...

**1**

vote

**0**answers

133 views

### About hyperplane separation theorem

I read in Lovasz's notes about semidefinite programs and combinatoric optimization.
If $x_1A_1 + ... + x_nA_n\succ 0$ has no solution, then the linear subspace $L = x_1A_1 + ... + x_nA_n$ is ...

**6**

votes

**2**answers

2k views

### Minimize Frobenius norm

My question is the following:
Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...

**3**

votes

**1**answer

115 views

### Finding a semigroup that maximizes the trace of a sum of matrices

Let $H$ be a finite semigroup containing $n$ elements from a compact group $G$. I am trying to solve
$$\max_{h_i,\ h_j\ \in\ H} \operatorname{tr} \sum_{i,\ j\ \leq\ n} \rho(h_i^{-1} h_j)(A_j A_i^T)$$...

**6**

votes

**1**answer

208 views

### when does elementwise-log preserve positive-semidefiniteness?

Let $Z$ be a positive semidefinite matrix with nonnegative entries, and define $X=\log(1+Z)$, where the $\log$ is taken entrywise, i.e., $X_{ij}=\log(1+Z_{ij})$. Are there some simple sufficient ...

**1**

vote

**1**answer

223 views

### how to determine a biquadratic form is positive-definite

A biquadratic form $\sum_{i,j,k,l}b_{i,j,k,l}x_{i}x_{j}y_{k}y_{l}$，
how to determine whether it is positive-definite？
A necessary and sufficient condition？
In fact, I have a matrix $B=\sum_{1\leq i,...

**-1**

votes

**1**answer

680 views

### How to show the square root function of a positive semidefinite matrix is differentiable? [closed]

How to show the square root function of a positive semidefinite matrix is differentiable?
In this context PSD means symmetric PSD.

**1**

vote

**0**answers

197 views

### Is there an improvement for the Schur-Horn inequalities for positive semi-definite matrices?

By the Schur-Horn inequality I am thinking of the statement that for any Hermitian matrix $H$ its diagonal n-tuple $(H_{11},H_{22},..,H_{nn})$ for any choice of basis lies in the convex hull of the $n!...

**6**

votes

**1**answer

470 views

### On the positivity of matrices

For given $n$, the following $n\times n$ real matrix $M=M^{T}$ is called positive, if
$x^{T}M x\geq 0$
holds for all non-negative real $x_1,x_2,\cdots,x_n$,
where $x=(x_1,x_2,\cdots,x_n)^T$.
...

**2**

votes

**1**answer

112 views

### mixed semi definite and second order programming complexity order

Consider the following mixed semi definite and second order programming:
$\begin{array}{l}
\mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\
{\rm{s}}{\rm{.t:}}\, & {\rm{...

**0**

votes

**1**answer

295 views

### Positive Semidefinite matrix [closed]

Let $A$ be an $n\times n$ symmetrix matrix, if $\forall i$,
$a_{ii}\geq |a_{ij}|,\forall j$
satisfies, can we say that $A$ is a positive semidefinite matrix? I tried to find a counter example, but ...

**1**

vote

**0**answers

259 views

### dual problem of SDP [closed]

suppose we have the following optimization problem:
\begin{array}{l}
\mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\,Tr\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\
s.t:\,\,\,\,\left[ {\...

**2**

votes

**1**answer

169 views

### Optimization problem whose cardinality never exceeds 7 for some reason

I am working on a problem in which I have a collection of $n$ points, $x_1,\dots,x_n$, in the plane, as well as a positive definite matrix $\Sigma$ and another point $\mu$ in the plane. I am trying ...

**1**

vote

**0**answers

200 views

### An optimization problem on the sphere

Let $S$ be a sphere centered at origin in $\Bbb R^{2n}$ of radius $\sqrt{2n}$. Let $D$ be a diagonal matrix. Let $U$ be an orthogonal matrix. Let $r\in\Bbb Z_+$ be a fixed integer.
Let vector $v\in\...

**0**

votes

**1**answer

162 views

### On the upper bound of Hermitian matrices

Suppose we are given a Hermitian matrix $A$, how to describe the following set of Hermitian
$S=\{X:X\geq \pm A\}$, where $Y\geq B$ is $Y-B$ is semidefinite matrix.
This is of course a convex set, and ...

**6**

votes

**1**answer

2k views

### SDP formulation of noisy low rank matrix completion

Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...

**1**

vote

**1**answer

882 views

### Lagrange multiplier and semidefinite programming

suppose we have a primal semidefinite programming. for finding its dual we use Lagrange multiplier $w_i$ for each semidefinite constraint. If the Lagrange multiplier be zero for one constraint what we ...

**2**

votes

**1**answer

284 views

### positive semidefinite matrix condition

There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted ...

**31**

votes

**4**answers

3k views

### Why are optimization problems often called “programs”?

Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...