# 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
Filter by
Sorted by
Tagged with
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 ...
58 views

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 ...
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 ...
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 ...
280 views

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 ...
223 views

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$. ...
112 views

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