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

86
questions

1
vote

1
answer

120
views

### Perturbation of positive semidefinite matrix

Consider an $n\times n$ matrix $A$ that is positive semidefinite and has rank $n-1$, so there exists exactly one eigenvector $v$ such that $Av=0$. Let now $B$ be a symmetric matrix such that $v^TBv=0$....

3
votes

1
answer

103
views

### Positive-definite block matrix with constant block sums

Given two natural numbers $n$ and $m$, suppose that $A$ is an $nm \times nm$ real nonnegative matrix. Seeing $A$ as a block matrix where each block has size $m\times m$, suppose that the sum of the ...

1
vote

0
answers

67
views

### Fastest algorithm for finding the closest semi-definite matrix?

Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:
$$
X^* = \mathop{\text{...

0
votes

0
answers

56
views

### Feasibility of a polynomial system of equalities and inequalities

Consider a system of the form $f_i(x) = 0$ and $g_j(x) \ge 0$ ,where $f_i,i=1,\dots,r$ and $g_j,j=1,\dots,s$ are polynomials in real unknowns $x_i,i=1,\dots,n$ with rational coefficients.
Is there a ...

1
vote

0
answers

67
views

### If $\hat{D}$ minimizes trace over all $D+ B \succeq 0$, then is $\hat{D}_{ii} \leq \sum_{j} |B_{ij}|$ for each $i$?

Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
Let $\hat{D}$ be a solution to the SDP that minimizes $tr(...

0
votes

0
answers

40
views

### Minimizing a certain trace-product involving orthonormal vectors

Let $C$ be an $n \times n$ positive-semidefinite matrix. Fix and integer $1 \le m \le n$, and for orthonormal vectors $v_1,\ldots,v_m$ in $\mathbb R^n$, and set $V := (v_1,\ldots,v_m) \in \mathbb R^{m ...

6
votes

0
answers

102
views

### Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$

Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...

1
vote

2
answers

57
views

### Monotonicity of kernel matrices with respect to hyperparameters

Let $\mathcal{X}$ be some nice space, let $\Phi$ be some ordered space, and let $K :\mathcal{X} \times \mathcal{X} \times \Phi \to \mathbf{R}$ be a positive-semidefinite kernel indexed by a ...

0
votes

0
answers

39
views

### Linear transformation of intersection of SDP cone and polyhedral cone

Let $A$ be a linear transformation, let $\mathcal{S}^n_+$ be the cone of positive semidefinite matrices. Suppose $P$ is a polyhedral cone. We consider the image of the intersection of the two cones, i....

0
votes

0
answers

74
views

### Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general

Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...

2
votes

1
answer

213
views

### Solving linear programming without solving linear programming

Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with ...

2
votes

0
answers

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

0
votes

0
answers

138
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} & \...

2
votes

0
answers

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

0
votes

0
answers

96
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}^{...

3
votes

1
answer

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

2
votes

0
answers

152
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) \...

4
votes

3
answers

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

4
votes

1
answer

169
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 $\left\{ (h h^T, h) : h \in \Bbb R^{d\times1} \right\}$. It is known that $$\mathrm{cone} \left\{h h^T : h \in \Bbb R^{d \times1} \right\} = S_+^d$...

2
votes

0
answers

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

1
vote

0
answers

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

2
votes

1
answer

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

1
vote

0
answers

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

0
votes

2
answers

976
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}}
& &...

3
votes

0
answers

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

3
votes

0
answers

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

1
vote

0
answers

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

1
vote

0
answers

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

1
vote

0
answers

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

1
vote

0
answers

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

2
votes

0
answers

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

4
votes

1
answer

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

1
vote

0
answers

59
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)^...

1
vote

1
answer

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

1
vote

0
answers

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

2
votes

0
answers

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

5
votes

2
answers

326
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?

3
votes

0
answers

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

2
votes

1
answer

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

4
votes

1
answer

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

2
votes

2
answers

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

3
votes

1
answer

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

11
votes

2
answers

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

3
votes

0
answers

4k
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, ...

6
votes

1
answer

2k
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,...

3
votes

2
answers

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

2
votes

2
answers

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

3
votes

0
answers

603
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

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

4
votes

1
answer

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