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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
70 views

Modified quadratic assignment problem

Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that $$\left\Vert Y^{T}...
user avatar
0 votes
0 answers
53 views

Double summation of matrices as constraints in convex optimization in CVX

I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53: \begin{align} \text{minimize} &\qquad s\\ \text{subject to} & \...
user avatar
2 votes
0 answers
44 views

A variant of the elliptope relaxation

Given a p.s.d. matrix $A$, one may want to find: $$ \max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}. $$ This hard problem has a well known relaxation based on the so called ...
user avatar
  • 1,931
0 votes
0 answers
66 views

On least-squares with positive semidefinite constraints

Given real symmetric matrix $\mathbf{R} \in \mathbb{S}^{n\times n}$ and matrices $\mathbf{X}_n, \mathbf{X}_{n-1} \in \mathbb{R}^{n \times m}$, $$\begin{array}{ll} \underset{\mathbf{A} \in \mathbb{R}^{...
user avatar
2 votes
1 answer
50 views

Relaxations for the spectral norm maximization problem

Optimizing the spectral norm of some positive semidefinite matrix $A(x) \in S^{n}$, w.r.t. a list of variables $x \in \mathbb{R}^d$ and semidefinite constraints is, in general, a nonconvex problem (...
user avatar
  • 23
2 votes
0 answers
142 views

Certificates of connectivity of basic semi-algebraic sets

Given real polynomials $p_1, \ldots, p_n \in {\mathbb R}[x_1, \ldots, x_d]$, consider the closed basic semi-algebraic set $S \subseteq {\mathbb R}^d$ given by $$S := \{x \in {\mathbb R}^d : p_i(x) \...
user avatar
  • 51
4 votes
3 answers
215 views

When does a finite metric induce a matrix norm?

If I have a metric $d(\cdot,\cdot)$ on the set $\{1,\dots,n\}$, are there well-known necessary or sufficient conditions for the existence of a matrix norm $Q$ that induces that metric on the unit ...
user avatar
  • 3,668
3 votes
1 answer
76 views

What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?

I'd like to know what is the convex cone generated by $\{ (h h^T, h), h\in R^{d\times1}\}$. It is known that $\mathrm{cone}\{h h^T, h\in R^{d\times1}\}=S_+^d$, and $\mathrm{cone}\{h, h\in R^{d\times1}\...
user avatar
  • 108
2 votes
0 answers
79 views

Three-constraint homogeneous QCQP

Consider the homogeneous quadratically constrained quadratic program, $$\min_{u^T u =1} u^T A_1 u$$ $$\textrm{subject to}\quad u^T A_2 u = 0,\quad u^T A_3 u = 0$$ This problem is particularly studied ...
user avatar
  • 1,033
1 vote
0 answers
28 views

Solution to dynamic program-type recursion

I have the following dynamic programming principle-type problem. Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
user avatar
2 votes
1 answer
48 views

Convexity of a positive definite objective with min(x,y)-nonlinearity

I have derived an optimization objective of the form $$ f(x) = \sum_{i,j} C_{ij}\min(x_i, x_j), s.t. g(x) \geq 0 $$ where $C \in \mathcal{R}^{N \times N}$ is a positive definite matrix, and $x \in \...
user avatar
  • 123
1 vote
0 answers
37 views

Is there an efficient way to do semidefinite programming with a Lyapunov equation constraint?

I am trying to numerically solve semidefinite programs of the form $$\begin{array}{ll} \underset{X,Y}{\text{minimize}} & \operatorname{tr}(AX)\\ \text{subject to} & BY + YB = X\\ & X, Y \...
user avatar
  • 31
0 votes
2 answers
440 views

Matrix norm minimization and matrix inner product

One of the famous problem in SDP is the matrix norm minimization (see S. Boyd, Convex Optimization, p. 170). Consider: \begin{equation}\label{eq:Lasse} \begin{aligned} &\min_{\mathbf{x}} & &...
user avatar
3 votes
0 answers
93 views

Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix). Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
user avatar
  • 205
3 votes
0 answers
55 views

Non-negative bivariate polynomials in a rectangle

I have been working on non-negative univariate polynomials and I found the following equivalent relationship to check if a polynomial is non-negative or not: The polynomial $g(x) = \sum_{r=0}^k y_rx^...
user avatar
1 vote
0 answers
39 views

Minimum operator that exceeds others (in a PSD, linear matrix inequality, sense)

Given a collection of $n$ matrices $A_i$, we could ask for the $B$ such that: $$\textrm{Minimize: }\quad \textrm{Tr}[B]$$ $$\textrm{Such that: }\forall_i\, B \succeq A_i$$ Here $\succeq$ is in the ...
user avatar
  • 1,033
1 vote
0 answers
48 views

SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?

the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs. Another popular approach to obtain efficient ...
user avatar
1 vote
0 answers
75 views

What is the relation between different generalizations of linear programming?

Linear programming subsumed by each of Semidefinite programming (SDP) Convex programming (CXP) SOS programming (SSP) Is there any relation between each pair in the three? Are all three equivalent in ...
user avatar
  • 1,708
1 vote
0 answers
59 views

Reference request for linear matrix inequality with PSD matrices

In literature, people say a spectrahedron is the following set $$\left\{x \in \mathbb{R}^d : x_1 A_1 + \cdots + x_d A_d \geq B \right\}$$ where $\geq$ is in the positive semidefinite sense. Is there a ...
user avatar
2 votes
0 answers
106 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 ...
user avatar
4 votes
1 answer
167 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\...
user avatar
  • 41
1 vote
0 answers
57 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)^...
user avatar
1 vote
1 answer
750 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, ...
user avatar
1 vote
0 answers
70 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 ...
user avatar
  • 547
2 votes
0 answers
110 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 ...
user avatar
5 votes
2 answers
245 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?
user avatar
  • 51
3 votes
0 answers
106 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 ...
user avatar
  • 131
2 votes
1 answer
133 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 ...
user avatar
4 votes
1 answer
146 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} \...
user avatar
  • 267
2 votes
2 answers
156 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 \...
user avatar
3 votes
1 answer
400 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 ...
user avatar
  • 133
11 votes
2 answers
599 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$...
user avatar
  • 2,610
3 votes
0 answers
3k 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, ...
user avatar
  • 2,016
6 votes
1 answer
1k 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 $$\left\{ x^T A_i y = b_i : i = 1,\dots,m \right\}$$ in variables $x,...
user avatar
  • 2,287
2 votes
2 answers
848 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 ...
user avatar
  • 9,471
2 votes
2 answers
260 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, \\ &\;\;\;\;\;\;\;\;\;\;\; \...
user avatar
  • 101
3 votes
0 answers
557 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 ...
user avatar
  • 121
1 vote
1 answer
125 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 ...
user avatar
  • 1,265
4 votes
1 answer
338 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, \...
user avatar
  • 1,265
3 votes
2 answers
330 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 ...
user avatar
3 votes
1 answer
352 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 ...
user avatar
  • 12.8k
2 votes
1 answer
1k 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 ...
user avatar
  • 185
5 votes
1 answer
350 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{...
user avatar
  • 71
1 vote
0 answers
65 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 ...
user avatar
1 vote
0 answers
508 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 (...
user avatar
3 votes
2 answers
1k 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{...
user avatar
  • 332
4 votes
0 answers
115 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}~...
user avatar
  • 1,095
1 vote
0 answers
86 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}$....
user avatar
  • 1,265
5 votes
1 answer
1k 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 $...
user avatar
1 vote
0 answers
200 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 ...
user avatar
  • 91