Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
2answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
4answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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 ...