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
0
votes
0
answers
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 &...
- 7,071
0
votes
0
answers
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\\
&\...
- 66
0
votes
0
answers
19
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 ...
- 66
2
votes
0
answers
37
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 ...
- 81
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 ...
- 177
0
votes
0
answers
19
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 ...
0
votes
0
answers
20
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 ...
- 66
1
vote
0
answers
94
views
Reducing an SDP to an SOCP
Consider a linear estimation setting where we have measurements of the following form.
$$ {\bf y} = {\bf H} {\bf x} + {\bf v} $$
where ${\bf y}, {\bf v} \in \mathbb{R}^m$, ${\bf x} \in \mathbb{R}^n$ ...
- 11
1
vote
0
answers
41
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,106
1
vote
1
answer
47
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-...
- 58
0
votes
0
answers
31
views
Hessian positive semidefinite for a matrix variable function?
I am currently reading a paper, and a proof (see below) in the paper talks about the hessian being positive semidefinite for a matrix variable function $g:\mathbb{R}^{n\times k} \to \mathbb{R}$, and ...
- 1,106
0
votes
3
answers
64
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 \...
- 1,106
0
votes
0
answers
16
views
Matrix completion with Pfaffians constrain
Perform matrix completion of a real $2n \times 2n$ matrix $\mathbf{C}$ (i.e., we have only a few entries of the matrix $C$ and want to fill in the remaining ones) with the constraints that:
$\mathbf{...
0
votes
0
answers
36
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 (...
0
votes
1
answer
93
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 ...
- 21
2
votes
1
answer
101
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_{...
- 75
0
votes
0
answers
21
views
Minimization of p-norm of diagonal
As I am rather unfamiliar with optimization and convex programming my question might be a bit naive.
Let's start with a very simple semidefinite program
$$\min \, \, tr(X)$$
$$ s.t.\, X \succeq 0 \...
- 11
3
votes
2
answers
135
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 ...
- 1,106
5
votes
1
answer
117
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} ...
- 121
0
votes
1
answer
31
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}...
- 1,106
2
votes
0
answers
45
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: $\...
- 21.4k
4
votes
0
answers
84
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
0
votes
0
answers
19
views
How to solve a Euclidean projector to map a matrix to a valid Laplacian?
We define the vaild Laplacian matrix space $$\mathcal{L}=\{\mathbf{L}\in\mathbb{R}^{n\times n}|\mathbf{L}_{ij}=\mathbf{L}_{ji}\leq0,\forall i\neq j;\mathbf{L}\cdot\mathbf{1}=\mathbf{0};\mathrm{tr}(\...
- 11
0
votes
0
answers
48
views
Semidefinite programming: flat directions and "not numerically HPD"
My question involves semidefinite programming (SDP) in the sense of attempting to find some vector $\alpha^{\mu}$ that satisfies the following conditions:
Normalisation: $\alpha^{\mu}n_{\mu} = 1$
...
1
vote
0
answers
58
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$,...
- 797
0
votes
0
answers
33
views
Greatest predecessor of a PSD matrix
Suppose I have a rank-$k$ orthonormal basis $Q$ of $d$-dimensional space (summarized by a $d\times k$ matrix of the same name).
Then, provided some $W\in\mathbb{R}^{d\times m}$, I'm interested in ...
- 1,973
0
votes
0
answers
19
views
Finding largest centered (n-1)-ball in a n-dimensional union polyhedral complex
Given a polyhedral complex $S$ in $\mathbf{R}^n$ composed of $\left\{P_1, \ldots, P_k\right\}$
$$
S:=\bigcup_{i=1}^k P_i
$$
and a point $x \in S$, I am interested in finding the largest (n-1)-...
- 111
1
vote
0
answers
37
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 ...
- 78
0
votes
1
answer
91
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 = ...
- 581
0
votes
0
answers
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 ...
- 698
0
votes
1
answer
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 ...
- 294
1
vote
0
answers
50
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) \...
- 81
0
votes
0
answers
149
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\...
- 170
1
vote
0
answers
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
0
votes
0
answers
71
views
How do I go about proving the feasibility of this LMI?
I have the given Linear matrix inequality
$$ {X^T}{\left( {{P^{ - 1}} - {\gamma ^{ - 2}}}I \right)^{ - 1}}X \succeq {\left( {X - C} \right)^T}{\left( {{T^{ - 1}} - {\gamma ^{ - 2}}}I \right)^{ - 1}}\...
- 57
3
votes
1
answer
94
views
Find $\alpha$ that minimizes $\|(I-\alpha H)^2 A\|$
Suppose $A,H$ are positive definite matrices. How do I find $\alpha$ which minimizes the following?
$$\|(I-\alpha H) A(I-\alpha H)^T\|_\text{op}$$
It can be written as minimizing linear function with ...
- 4,739
1
vote
0
answers
65
views
Semidefinite program with equality constraints expressed as matrix product
Consider a semi-definite program with equality constraints where the variable $X$ is a block matrix. Denoting the different blocks of $X$ by $X_j$ where $j$ is an index, the standard form of the ...
- 111
1
vote
1
answer
58
views
Maximizing $2\text{Tr}(AX) - \|AX\|_F^2$ for p.s.d X?
For a positive semi-definite $A$, I need to find positive semi-definite $X$ which maximizes the following
$$2\text{Tr}(AX) - \|AX\|_F^2$$
Is there a geometric or statistical interpretation of this ...
- 4,739
1
vote
1
answer
111
views
Matrix Logarithm for cvx package of optimization [closed]
I have a convex optimization problem with the Hermitian semi-definite matrix variable. The problem is in fact a matrix entropy maximization with some other constraints which I don't mention for ...
2
votes
2
answers
127
views
How to derive the dual of a conic programming problem, $\min_{x\in L}\{c^T x: \,\, Ax-b\in K\}$?
I'm trying to get a better understanding of the derivation of the dual problem associated with a given conic problem.
From these notes (pdf alert), a conic problem is written (see page 5) as
$$\min_x ...
- 6,503
1
vote
0
answers
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 ...
- 71
0
votes
0
answers
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
0
answers
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 ...
0
votes
1
answer
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 ...
- 87
1
vote
0
answers
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 ...
- 797
2
votes
1
answer
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. ...
0
votes
1
answer
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{...
- 643
1
vote
1
answer
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 ...
- 797
3
votes
1
answer
47
views
Eigenvalue of PSD matrices by constrained SDP program
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^\...
- 33
0
votes
0
answers
85
views
How do you convert the following optimization problem with LMI constraints from the standard form given to the Semi Definite Programming(SDP) form?
We are currently working on an engineering project involving convex optimization. The project relates to a low earth orbit spacecraft rendezvous. In the course of this project, we are required to ...
