**0**

votes

**0**answers

162 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

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

**0**

votes

**0**answers

47 views

### About identifying a few diagrams

Please have a look at these beautiful seminar slides,
https://math.berkeley.edu/~bernd/coimbra1.pdf
Can someone kindly identify the algebraic description of the spectrahedron that is drawn on slide ...

**1**

vote

**0**answers

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

**5**

votes

**1**answer

265 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

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

**0**

votes

**0**answers

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

**5**

votes

**1**answer

83 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

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

**-1**

votes

**1**answer

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

**0**

votes

**0**answers

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

**6**

votes

**1**answer

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

**1**

vote

**1**answer

80 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:}}\, & ...

**0**

votes

**1**answer

191 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

117 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

152 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

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

**0**

votes

**1**answer

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

**3**

votes

**1**answer

564 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

274 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

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

**1**

vote

**0**answers

90 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

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

**3**

votes

**1**answer

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