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

**2**

votes

**2**answers

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

**0**

votes

**0**answers

17 views

### Projection constrain of SDP

Suppose $\Phi$ maps $m+d$ dimensional Hermitian matrices to $n$ dimensional Hermitian matrices. We have the following SDP constrain on $m$ dimensional Hermitian matrix $X$ and $d$ dimensional ...

**2**

votes

**1**answer

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

**7**

votes

**2**answers

254 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

158 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

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

**0**

votes

**1**answer

157 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

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

**2**

votes

**0**answers

196 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

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

**0**

votes

**0**answers

48 views

### semidefinite optimization with quadratic functionals

I'm not an expert on non-linear optimization, and I'm wondering if the following problem is related to standard optimization algorithms, such as semidefinite programming.
I have to maximize $$ a^T z,...

**0**

votes

**0**answers

100 views

### bounding minimum eigenvalue of a block matrix

Let $C=[C_{i,j}]$ be a $dk\times dk$ positive semidefinite (PSD) matrix with PSD $k\times k$ blocks $C_{i,j}$. Diagonal blocks are identity matrices. Is there a way to bound the minimum eigenvalue of $...

**4**

votes

**1**answer

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

**2**

votes

**2**answers

240 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

94 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

515 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

241 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

313 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

644 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

91 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

81 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

392 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

178 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

206 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

114 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

**1**answer

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

113 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)$$...

**0**

votes

**0**answers

123 views

### How to use the property of Frobenius norm in this proof?

Let $A \in \mathcal{S}^{n}$($\mathcal{S}^{n}$ is the $n \times n$ symmetric matrix space), $P,Q \in\mathbb R^{n \times n}$, and $\rho \geq 0$ be given. Show that:
$$A \succeq P^{T}ZQ+Q^{T}Z^{T}P$$
for ...

**6**

votes

**1**answer

167 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

162 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

493 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

182 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

431 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

106 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

267 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

226 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

164 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

198 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

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

**5**

votes

**1**answer

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

763 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

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

**30**

votes

**4**answers

2k views

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

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

**1**

vote

**0**answers

132 views

### Checking feasibility with eigenvalue and linear constraints

Is there an efficient algorithm to check the simultaneous feasibility of linear and eigenvalue constraints? For example, given $ \lambda_1 \ge \lambda_2 \ge 0$, is the following problem efficiently ...

**1**

vote

**1**answer

932 views

### Bounding the positive semi-definite matrix with its block diagonal matrix [closed]

Can we bound $\mathbf{A}$ with $\mathbf{A^*}$ as ${\bf{A}} \preceq {{\bf{A}}^*}$ where
\begin{equation}
{\bf{A}} = \left[ {\begin{array}{*{20}{c}}
{{{\bf{A}}_{11}}}&{...}&{{{\bf{A}}_{1N}}}\\
...

**1**

vote

**1**answer

387 views

### Semidefinite relaxation for a quadratic feasibility problem using CVX

The following decides the feasibility of a semidefinite program (SDP)
\begin{align}
\max_{\mathbf{Z}}~0 \\\
\mathrm{trace}(\mathbf{Z})\leq \rho \\\
\mathrm{trace}(\mathbf{S}_1\mathbf{Z}) \geq \alpha \...

**4**

votes

**1**answer

215 views

### Explicit formula for an LMI solution

Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):
$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$
(The notation $X \succeq Y$ means that $X-...

**1**

vote

**1**answer

580 views

### A non-convex quadratically constrained quadratic program

$$\begin{array}{ll} \text{minimize} & \beta^{T} A \beta\\ \text{subject to} & \beta^{T} C \beta=1\\ & \beta \geqslant 0\end{array}$$
where $A, C\in \mathbb{R}^{M\times M}$ and $\beta \in ...

**2**

votes

**1**answer

863 views

### Can one maximize the spectral norm of a matrix via semidefinite programming?

Consider the following optimization problem:
Maximize $\|X\|_2$, subject to $X$ being Hermitian (or symmetric) and a bunch of semidefinite constraints on $X$. Here, $\|X\|_2$ is the spectral norm of ...