Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
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$...
frgoe's user avatar
  • 31
0 votes
0 answers
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, ...
Junsukim's user avatar
0 votes
0 answers
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 ...
calculus_crusader's user avatar
3 votes
0 answers
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}$: ...
Gro-Tsen's user avatar
  • 5,631
1 vote
1 answer
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 ...
Cedric Martens's user avatar
0 votes
0 answers
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:...
happyman's user avatar
1 vote
0 answers
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 ...
GoemanWilliamson's user avatar
0 votes
0 answers
17 views

What is the computational complexity of a second-order cone with linear matrix inequality (LMI)?

I am trying to compute the complexity of solving the following problem. The goal is to design the parameter $(t,\textbf{x})$ where $\textbf{x}\in \mathbb{R}^n$ and the formulated problem is $\min_{t,\...
PDDMM's user avatar
  • 1
0 votes
1 answer
52 views

Is this SDP analytically solvable?

I am studying the following semi-definite problem: $$\begin{array}{rl} \textrm{Given:} & W \in \mathbb{R}^{n \times n} \\ \textrm{Minimize:} & u_1 + u_2 + \ldots + u_n \\ \textrm{Subject to:} &...
ConMan's user avatar
  • 25.6k
0 votes
0 answers
66 views

How to capture low-rankness of a symmetric matrix using its components (not eigenvalues)?

Suppose I have an optimization model (P1) which its decision variable is a symmetric matrix $W$ (but not necessarily negative/positive semidefinite). In my case, this model can be converted to a ...
Sam's user avatar
  • 366
1 vote
1 answer
76 views

Minimizing symmetric convex functions of eigenvalues

I am stuck with the following problem. Prove that the optimal value to the SDP \begin{align} \text{minimize} \quad &\operatorname{tr}(V) \end{align} \begin{align} \text{subject to} \quad &\...
Ryukendo Dey's user avatar
1 vote
1 answer
28 views

Equivalence of $R^m$ and $l^2$(square-summable sequence) in the proof of Grothendieck's inequality

This is from High dimensional probability by Vershynin. In the proof of Grothendieck's inequality, for $u,v \in \mathbb{R}^n$, we find functions $\phi, \varphi \colon \mathbb{R} \to l^2$ such that $\...
Phil's user avatar
  • 1,710
1 vote
0 answers
50 views

LMI robustness to small perturbations

Let $P\in\mathbb{R}^{n\times n}$ be a positive semidefinite matrix, i.e., $P=P^\top$ and $\langle Px,x\rangle\geq0$ for all $x\in\mathbb{R}^n$. Assume that, for a certain $A\in\mathbb{R}^{n\times n}$ ...
ofir_13's user avatar
  • 584
0 votes
0 answers
59 views

Semidefinite program matrix

We consider the following semidefinite program where the variables are semidefinite matrices, i.e., their set is $S_n^+$.We want to solve the following problem $$\inf_{X \in M_3(\mathbb{R})} X_{3,3} + ...
user1240705's user avatar
0 votes
1 answer
34 views

Semidefinite programming over infinite dimensional space

During my calculations I've encountered a semidefinite program, e.g. $$\max\{ \lVert X \rVert : \lVert X \circ M \rVert \le 1 \}$$ where $\circ$ denotes the entry-wise multiplication (this is called ...
NYG's user avatar
  • 321
0 votes
0 answers
71 views

Eigenvalue decomposition for $A^TA$ for sparse A?

I have a sparse matrix $A \in \mathbb{R}^{n \times l^{2}}$, and I want to calculate the eigenvalue decomposition of $A^{\top}A$. Since $A^{\top}A$ is positive semidefinite, all the eigenvalues are non-...
wsz_fantasy's user avatar
  • 1,732
4 votes
0 answers
63 views

Solving $\operatorname{argmin}_\alpha \|I-\alpha \operatorname{diag} h + 2 \alpha^2 \operatorname{diag} h^2 +\alpha^2 h\otimes h\|$

Suppose $h^*=\left(1,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{d}\right)$ and $h=h^*/\|h^*\|_1$. Can someone see a way to approximate the following quantity for $d\approx 10^6$? The problem is to ...
Yaroslav Bulatov's user avatar
0 votes
0 answers
34 views

How to recover solution of SDP relaxation to maxcut problem given the solution matrix

I have found the solution to an SDP relaxation of the maxcut problem and I have the solution matrix $Y$. I have found that the SDP relaxation was exact because all the eigenvalues of the matrix Y are ...
hunterlineage's user avatar
0 votes
0 answers
82 views

How to add Linear Matrix Inequality (LMI) constraints to a Semidefinite program (SDP) in standard form

Given an SDP problem with $m$ equality constraints and one Linear Matrix Inequality (LMI) in standard form: $$ \begin{align} \min \quad & \mathbf{F}_0 \bullet \mathbf{Y} \\ \text{s.t.} \...
abc's user avatar
  • 121
0 votes
1 answer
95 views

Lower bound arccos

How can I derive the following lower bound for $\arccos(x)$ for $x\in [-1, +1]$ $$\frac{\text{arccos}(x)}{\pi} ≥ \frac{0.8785(1-x)}{2}$$ I can see it from the plot that it holds, but how would one ...
v.tralala's user avatar
  • 299
0 votes
1 answer
55 views

SDP relaxation of mixed-integer nonlinear program

I am having trouble understanding the semidefinite programming (SDP) relaxation of a mixed-integer nonlinear program (MINLP) from section 3 of this paper. The optimization problem in MINLP form is \...
Physics Penguin's user avatar
0 votes
0 answers
54 views

Write an inequality form SDP as an conic form problem in inequality form

I understand that semidefinite programming (SDP) is a subset of conic programming (CP). According to Boyd's Convex Optimization book section 4.6.1, the conic problem in inequality form is written as $$...
Nick's user avatar
  • 11
0 votes
0 answers
66 views

Transforming rank constraints over positive semidefinite matrices

For $A, B \in S_{n\times n}$, $i$.$e$. symmetric matrices. Consider the following program $$ \begin{align} \underset{ Y \in S_{n \times n} }{ \text{Find} } \quad & Y \succeq 0 \\ s.t. \quad & \...
wsz_fantasy's user avatar
  • 1,732
0 votes
0 answers
51 views

Rank Constraints in dual program

I am interested in verifying that the feasibility of the following program: For $A, B \in S_{n\times n}$, $i$.$e$. symmetric matrices. $$ \begin{align} \underset{ Y \in S_{n \times n} }{ \text{Find} } ...
wsz_fantasy's user avatar
  • 1,732
2 votes
1 answer
133 views

Using Schur's Complement to Reformulate Semidefinite Programming Constraint

I am currently reading Boyd & Vandenberghe's Convex Optimization and encountered (at least twice) reformulations of matrix inequalities that confuses me a lot. I will try to clarify my question ...
HansEtherious's user avatar
0 votes
0 answers
295 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 &...
Ma Joad's user avatar
  • 7,534
0 votes
0 answers
30 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\\ &\...
Blake's user avatar
  • 86
0 votes
0 answers
21 views

How to derive the dual for Parabolic Relaxation for QCQPs

I'm reading this paper (EQ 11/15/16) on a way to relax QCQPs. They state the dual of their program, but I can't quite figure out how they got there. We're minimizing over variables: $X$ (PSD $n\times ...
Blake's user avatar
  • 86
2 votes
0 answers
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 ...
Audrey's user avatar
  • 95
0 votes
0 answers
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 ...
12345's user avatar
  • 187
0 votes
0 answers
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 ...
Zhouyou Gu's user avatar
0 votes
0 answers
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 ...
Blake's user avatar
  • 86
1 vote
0 answers
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....
wsz_fantasy's user avatar
  • 1,732
1 vote
1 answer
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-...
Pranav's user avatar
  • 90
0 votes
3 answers
165 views

Span of positive (semi)definite matrices

In this answer, Ben Grossmann said that $\operatorname{span}\{P:P \succ 0\} = \{A:A = A^T\} =: \mathcal S$. I am not sure, however, why this is true. Also, I guess $\operatorname{span}\{ P:P\succeq 0 \...
wsz_fantasy's user avatar
  • 1,732
0 votes
0 answers
45 views

Dual of the SDP relaxation in Yinyu Ye's paper

I was stuck in computing the dual problem in a paper by Yinyu Ye which raises an SDP relaxation such that $$ \min_{Z \in \mathcal{K}} \left\{ h(Z) := \sqrt{\sum_{(i, j) \in \mathcal{E}} \gamma_{ij}^2 (...
ENTONG HE's user avatar
1 vote
1 answer
387 views

How to approximate a rank-1 solution after exploiting semidefinite relaxation method?

For my problem, I try to optimize the vector $\mathbf{w}\in\mathbb{C}^{N}$ at first. After exploiting semidefinite relaxation (SDR) method, the variable becomes $\mathbf{W} = \mathbf{ww}^H$ and the ...
tyrela's user avatar
  • 363
2 votes
1 answer
199 views

Grothendieck's inequality guarantee of relaxation for Semidefinite problem

I am struggling to understand a proof of theorem 3.5.6 in Roman Vershynin's High-Dimensional Probability Theorem: $$\text{INT}(A) = \max_{x_i = \pm 1 \text{ for } i = 1,\ldots,n} \sum_{i,j=1}^{n} A_{...
Lose' CKi's user avatar
3 votes
2 answers
143 views

Is $ \left\{ A P + P A^{T} \mid P \succ 0 \right\} $ open?

Consider an $n$ by $n$ matrix $A$, and the set $$ \left\{ A P + P A^{T} \mid P \succ 0 \right\} $$ Is this set open under the standard metric (the one induced by Frobenius norm) in the space of all ...
wsz_fantasy's user avatar
  • 1,732
5 votes
1 answer
348 views

Optimization problem involving the inverse matrix

I have a question related to optimization. Given natural numbers $n$ and $\ell$, matrices ${\bf K}_1, \dots, {\bf K}_\ell \in \Bbb R^{n \times n}$ and a vector ${\bf y} \in \Bbb R^n$, define $${\bf K} ...
박희인's user avatar
  • 131
0 votes
1 answer
100 views

Definition of a dual program to a feasibility problem

I was asked (not as a homework problem), to find the dual program of the following feasibility program. $$ \text{find } P \succ 0 $$ $$ \text{subject to } A_{i}P + PA_{i}^{T} \prec 0 \text{ for all i}...
wsz_fantasy's user avatar
  • 1,732
2 votes
0 answers
66 views

Translating SDP into SDPA format

I'm experimenting with the semi-definite optimisation problem given as Program 5.2 in the paper "Optimizing Linear Counting QueriesUnder Differential Privacy", which is as follows: Given: $\...
ConMan's user avatar
  • 25.6k
4 votes
0 answers
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}$ ...
beyondzk's user avatar
1 vote
0 answers
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$,...
qmww987's user avatar
  • 925
1 vote
0 answers
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 ...
MisterWalter's user avatar
0 votes
1 answer
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 = ...
Morcus's user avatar
  • 585
0 votes
1 answer
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 ...
chloe's user avatar
  • 1,052
1 vote
1 answer
112 views

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

We are given the problem \begin{equation}\label{primal} \begin{aligned} & \underset{x}{\text{minimize}} & & x^TA_0x+2b_0^Tx+c_0 \\ & \text{subject to} & &...
manav's user avatar
  • 253
1 vote
0 answers
104 views

Simplifying low-rank matrix completion using SDP

I understand that a Low-Rank Matrix Completion (LRMC) problem of the form: $$ \min_{\mathbf{X}} \mathrm{rank}(\mathbf{X}) \\ \text{s.t.:} \quad \mathbf{X}_{i,j} = \mathbf{M}_{i,j} \quad \forall (i,j) \...
Audrey's user avatar
  • 95
0 votes
0 answers
238 views

Quadratic-fractional or linear-fractional programming through SDP relaxation

I have an optimization problem as follows. $$ \text{maximize}_{\mathbf{x}\in \mathbb{R}^{n}} \sum_{i=1}^{P} \frac{(\mathbf{x}^{T} H_{p} \mathbf{x})}{(\mathbf{x}^{T} C_{p} \mathbf{x})}$$ $$s.t. A\...
StandTall's user avatar
  • 176

1
2 3 4 5
8