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

392 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Optimization of eigenvalue of matrix with discrete variables

Suppose we have a matrix $H$ like this, where $H_{ii}$ is a discrete variable (for example out of $[1,2,3]$) and $H_{ij}$ is a value that depends on the two adjacent values ($H_{ii}$ and $H_{jj}$). $H$...
• 31
52 views

### Off -diagonal perturbations of a positive semi-difinite matrix

Does the following statement hold? For a positive semi-definite(PSD) matrix X, if $rank(X) \ge 2$, there exists a nonzero off-diagonal matrix D that both X+D, X-D are also PSD. If it doesn't work, ...
• 39
24 views

### Minimize $\mathrm{tr}((FK + G)^TQ(FK + G) + K^TRK)$ over block lower-triangular matrices $K$

I want to solve the minimization problem $$\inf_{K\in\mathcal{K}}\mathrm{tr}\left(\left((FK + G)^TQ(FK + G) + K^TRK\right)\Sigma\right)$$ where $\mathcal{K}$ is the set of block lower triangular ...
68 views

### Bounds of Pearson correlation coefficients for (X,Z) knowing those for (X,Y) and (Y,Z)

Assume $X,Y,Z$ are three variables over a set of data (say, a finite set of data to avoid discussions of convergence). Suppose we know the Pearson correlation coefficient $r_{X,Y}$ and $r_{Y,Z}$: ...
• 5,631
1 vote
21 views

### Elliptic curve from a spectrahedron, why is semipositiveness equivalent to the following conditions?

$$(x,y) \in \mathbb{R}^2 \; A(x,y) := \begin{bmatrix} x+1 & 0 & y\\ 0 & 2 & -x-1 \\ y & -x-1 & 2 \end{bmatrix} \succeq 0$$ In the book from Blekherman (2012) ex 2.7: To ...
• 1,312
15 views

### Question on the Necessity of $Q_U Q^\top _U$ in Norm Calculation (from a semidefinite optimization).

I've been reading a paper titled "S. Bhojanapalli, A. Kyrillidis, and S. Sanghavi, Dropping convexity for faster semi-definite optimization, in Proc. Conf. Learn. Theory, 2016, pp. 530–582 (https:...
• 15
1 vote
45 views

### Duality Results for Convex SDP Programming

Suppose we have an SDP program with a convex (but nonlinear) objective $f(X)$, where $X$ is a positive semidefinite matrix. All other constraints are linear. Does there exist a dual program for such a ...
17 views

• 86
53 views

### Question on Candès-Tao's near-optimal matrix completion theorem

I have a question about the key result from this paper : Candès, Emmanuel J.; Tao, Terence, The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory 56, No. 5, 2053-2080 ...
• 95
13 views

### Checking whether matrix is PD vs computing PD completion

Let $E$ be a subset of entries of a real symmetric $n \times n$ matrix. We want to find a positive-definite matrix $X$ such that $X_{i,j}=M_{i,j}$ for all $(i,j) \in E$ for a fixed positive ...
• 187
26 views

### Rounding of semidefinite programms using simplex

Suppose we have two unit vectors, $\mathbf{a}_1$ and $\mathbf{a}_2$, where $\mathbf{a}_1,\mathbf{a}_2\in\mathbb{R}^N$ and $\|\mathbf{a}_1\|_2 = \|\mathbf{a}_2\|_2 =1$. Also, we have their inner ...
22 views

### Is there a Schur-like theorem for proving $B^TB\succeq A$?

This is in the context of semidefinite programs, and $A\in\mathbb R^{n\times n},~B\in\mathbb R^{k\times n}$ are variables. If want to show that $A-B^TB\succeq 0$ and I know $A\succeq 0$, then I can ...
• 86
1 vote
45 views

### Transforming determining $\exists x \in \mathbb{R}^m, A(x) \succ 0$ into least squares possible?

Consider a linear operator $A: \mathbb{R}^{m} \to S^{n \times n}$, where $S^{n\times n}$ are the symmetric n by matrix. Can we turn the problem of determining if there exists $x \in \mathbb{R}^{m}$ s....
• 1,732
1 vote
123 views

### Decomposition of nonnegative polynomial on interval into sum of squares

My professor went over the following theorem Consider a univariate polynomial $p(x)$. Then, If $p(x)$ has degree $2d$, then $p(x)$ is nonnegative on $[-1,1]$ if and only if there exists sum-of-...
• 90
165 views

• 25.6k
130 views

### Finding the optimal adjacency matrix [closed]

Notation: Let $\mathbf{A} \in \{0,1\}^{n \times n}$ be the adjacency matrix of an undirected graph. Let $\mathbf{D}$ be the degree matrix of this graph and let $\mathbf{L} = \mathbf{D} - \mathbf{A}$ ...
• 41
1 vote
62 views

### Can $\mbox{tr}(AX) \leq \frac{\mbox{tr}(\Omega BXB)}{\mbox{tr}(BXB)}$ be reduced to known programs?

Assume all the matrices mentioned below are in $\mathbb{R}^{n\times n}$ and symmetric. Also, below, $M \preceq N$ denotes that all eigenvalues of $N-M$ are non-negative. Given $0\preceq A, B\preceq I$,...
• 925
1 vote
44 views

### Indefinite log determinant constraint optimization problem

Looking at the following optimization problem $\min_{A \in S_{++}} \operatorname{tr}(MA)- \log(|A|)$ where $S_{++}$ denotes the space of positive definite matrices and $|\cdot|$ denotes the ...
127 views

### negative semidefinite matrices

Can someone point me to a paper, or show here, why symmetric matrices have orthogonal eigenvectors? In particular, I'd like to see proof that for a symmetric matrix $A$ there exists decomposition \$A = ...
• 585
53 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,052
1 vote
112 views

### Strong duality result for non-convex problem with two quadratic functions

We are given the problem \label{primal} \begin{aligned} & \underset{x}{\text{minimize}} & & x^TA_0x+2b_0^Tx+c_0 \\ & \text{subject to} & &...
• 253
1 vote