# Questions tagged [semidefinite-programming]

This tag is for questions regarding semidefinite programming (SDP) which is a subfield of convex optimization concerned with the optimization of a linear objective function (an objective function is a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

375 questions
Filter by
Sorted by
Tagged with
21 views

### How to formulate nuclear norm minimisation (of a matrix) as an SDP?

It is pretty well-known that the minimisation of the nuclear norm (sum of all singular values) is closely related to semidefinite programming. However, I struggle to find a way to rewrite the problem &...
16 views

### The dual of this SDP with a simple nonconvex constraint

In this problem we're optimizing over variables $X\in \text{PSD}_n$ and $Y\in\mathbb R^{d\times n}$ for some $d\le n$. \begin{align} &\text{Maximize}&&\langle A_0, Z\rangle\\ &\...
19 views

16 views

60 views

### KKT Complementary Slackness with SDP constraint

I want to analyze the solutions (e.g., rank) that result from a given SDP program. One of the complementary conditions reads as follows $$\Phi \bullet X = 0$$ where $X \succeq 0$ is a decision ...
49 views

### What is the geometry of feasible region of vector program of MaxCut?

The relaxation of MaxCut can be formed as a vector program: $$\text{maximize} \quad \sum_{i,j}a_{ij}v_i^Tv_j \qquad \text{subject to} \quad u_i \in \mathbb{R}^n,\quad \|u_i\|_{L^2}=1$$ although we ...
1 vote
50 views

1 vote
32 views

### Optimization with rank constraint and a mask matrix

I've been struggling with this optimization problem using Matlab, I would really appreciate it if you could tell me how to solve it with Matlab, or at least which optimization method can solve it. \...
71 views

1 vote
60 views

### Rewriting quadratic optimization problem with negative definite matrix

Consider the following problem: Minimize $x(1-x) + y(1-y) + z(1-z)$ subject to: $$a. 0\leq x, y, z \leq 1$$ $$b. x+y+z = 1$$ If I plug in this problem in a standard quadratic optimizer, which ...
51 views

### Conversion of SDP relaxation of Travelling Salesman Problem (TSP) to standard SDP form

The standard SDP formulation is given as : \begin{equation} \begin{aligned} \min_{X\in H^{n}} \quad& \langle X,M_{0} \rangle\\ \textrm{s.t.} \quad& l_{s} \leq \langle X, M_{s} \rangle \leq ...
1 vote
15 views

### What are data matrices of a SDP problem?

I'm reading the paper 'New bounds for the max-$k$-cut and chromatic number of a graph' by van Dam and Sotirov. On page 221, it says: "It is well known that one can restrict optimization of a SDP ...
21 views

### Problems that semidefinit program(SDP) can solve while convex optimization cannot?

In this link I found that it(SDP) admits a new class of problem previously unsolvable by convex optimization techniques I wonder if there are some examples that convex optimization cannot solve ...
1 vote
94 views

### What algorithm does cvxpy actually use to solve SDP problems with the constraint form $\sum_i E_iXE_i^T \succ B$

Crossposted on Computational Science SE CVXPY is a famous software as a solver for optimization problems.Nowadays I use it to run a program presented in a paper,the Example 7.1,and the program runs ...
59 views

### Proving the sum of inner products between $N$ points ($N$ even) on the $k$-dimensional sphere $S^{k-1}$ is greater than or equal to $-N/2$

I've been going through an optimization problem, and found that the optimal solution has a certain value but now I'd like to prove its optimality. To solve it, I need to show the following inequality. ...
27 views

### Image of a $3 \times 3$ PSD cone under a linear transformation

Let $X \in \mathcal{S}_+^3$ be a $3 \times 3$ positive semidefinite matrix, and let $\mathcal{A}$ be a linear transformation from $\mathcal{S}^3 \rightarrow \mathbb{R}^3$ defined as follows: \begin{...
1 vote
167 views

### How does barrier function method for semidefinite programming avoid the case when even eigenvalues are negative?

Log-barrier function adds the expression $-\log(\det X)$ to the objective function to ensure that the matrix $X$ is positive definite.But when even eigenvalues of X is negative this expression is ...
Given Lemma 1, I want to prove the following corollary. lemma 1 (Rayleigh Quotient): Given matrix $A \succeq 0$, \begin{equation} \lambda_{\min} (A) = \min_{x \in \mathbb R^n}\frac{x^\top A x}{x^\...