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
1 vote
0 answers
86 views

Interpreting positive semidefinite matrix as a graph

Given any symmetric matrix $S \in \mathbb{R}^{n \times n}$, if $S \succeq 0$, is there a way to encode $S$ into a graph such that it takes into account the positive semidefinite constraint, and ...
wsz_fantasy's user avatar
1 vote
1 answer
75 views

Norm bound in simultaneous stability to semidefinite program

In the context of robust control, I remember hearing that the two following problems are equivalent. Find $P \succ 0$, such that $A P + P A^{\top} \prec 0$ for all $A \in \mathscr{A}$ where $$\...
wsz_fantasy's user avatar
0 votes
0 answers
17 views

Dual semi-definite programming formulation of the quantum adversary method

I'm reading about the quantum adversary method and its semi-definite program formulation. It is not clear to me how to arrive to the dual SDP problem as usually found (e.g. here page 101). Given a ...
NYG's user avatar
  • 119
1 vote
1 answer
162 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$....
GaussJordan's user avatar
3 votes
1 answer
161 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 ...
GaussJordan's user avatar
1 vote
0 answers
146 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{...
Alec Jacobson's user avatar
0 votes
0 answers
65 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 ...
giulio bullsaver's user avatar
1 vote
0 answers
69 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(...
user135520's user avatar
6 votes
0 answers
115 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 ...
user135520's user avatar
1 vote
2 answers
59 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 ...
πr8's user avatar
  • 688
0 votes
0 answers
99 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 ...
Shih-Chi Liao's user avatar
2 votes
1 answer
222 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 ...
LeechLattice's user avatar
  • 9,411
2 votes
0 answers
102 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}...
Richard Border's user avatar
0 votes
0 answers
149 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} & \...
Spring Breeze's user avatar
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 ...
alesia's user avatar
  • 2,572
0 votes
0 answers
117 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}^{...
Universal_Bulin's user avatar
3 votes
1 answer
164 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 (...
ccln's user avatar
  • 33
2 votes
0 answers
165 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) \...
opti's user avatar
  • 51
4 votes
3 answers
242 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 ...
Tom Solberg's user avatar
  • 3,910
4 votes
1 answer
179 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$...
DASON's user avatar
  • 118
2 votes
0 answers
141 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 ...
Alex Meiburg's user avatar
  • 1,193
1 vote
0 answers
35 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 \...
John_Algorithm's user avatar
2 votes
1 answer
57 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 \...
koo's user avatar
  • 123
1 vote
0 answers
58 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 \...
henrikr's user avatar
  • 31
0 votes
2 answers
1k 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}} & &...
sleeve chen's user avatar
3 votes
0 answers
109 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 ...
zxzx179's user avatar
  • 205
3 votes
0 answers
66 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^...
user326159's user avatar
1 vote
0 answers
49 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 ...
Alex Meiburg's user avatar
  • 1,193
1 vote
0 answers
68 views

Fundamental regions in convex programming

In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
73 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 ...
user134977's user avatar
1 vote
0 answers
81 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 ...
VS.'s user avatar
  • 1,816
1 vote
0 answers
70 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 ...
wwjohnsmith's user avatar
2 votes
0 answers
158 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 ...
Baldi Lorenzo's user avatar
4 votes
1 answer
221 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\...
user157498's user avatar
1 vote
0 answers
62 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)^...
RayyyyySun's user avatar
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, ...
alternate direction's user avatar
1 vote
0 answers
92 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 ...
guigux's user avatar
  • 607
2 votes
0 answers
133 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 ...
Frederik vom Ende's user avatar
5 votes
2 answers
431 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?
SGC's user avatar
  • 51
3 votes
0 answers
164 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 ...
Doris's user avatar
  • 131
2 votes
1 answer
166 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 ...
Andrea Olivo's user avatar
4 votes
1 answer
210 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} \...
πr8's user avatar
  • 688
2 votes
2 answers
162 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 \...
Bart Jansen's user avatar
3 votes
1 answer
507 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 ...
codehippo's user avatar
  • 133
11 votes
2 answers
751 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$...
Ludwig's user avatar
  • 2,682
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, ...
gradstudent's user avatar
  • 2,136
7 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,...
grok's user avatar
  • 2,489
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 ...
M. Winter's user avatar
  • 12.5k
2 votes
2 answers
271 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, \\ &\;\;\;\;\;\;\;\;\;\;\; \...
Marc's user avatar
  • 101
3 votes
0 answers
620 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 ...
fanfare's user avatar
  • 131