Questions tagged [semidefinite-programming]
The semidefinite-programming tag has no usage guidance.
43
questions
1
vote
1
answer
94
views
Space complexity of a semidefinite program
What is the space complexity of a semidefinite program (SDP)?
What is the answer to the same question for convex optimization problems in general?
3
votes
1
answer
119
views
Rewriting quadratically-constrained optimization problem as a semidefinite program
Suppose $A,H$ are positive definite matrices and $\alpha,t$ are scalars. Is there a way to massage the following problem into a form suitable for a specialized solver?
$$\begin{array}{ll} \underset{\...
- 1,789
1
vote
1
answer
156
views
What algorithm does CVXPY actually use to solve semidefinite programs with the constraints of the form $\sum\limits_i E_iXE_i^T \succ B$?
Crossposted on Mathematics 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 as ...
- 113
2
votes
0
answers
158
views
How to solve the following SDP with cvxpy in Python?
The SDP problem is
$$
\min_{Z \in S^{n},Y \in S^{m}} {\rm trace}(Z) +{\rm trace}(Y)\\
{\rm s.t.} \begin{bmatrix}
Y & X\\
X^T & Z
\end{bmatrix} \succeq 0\\
X \in C
$$
Where $C$ is a convex set....
- 21
0
votes
1
answer
90
views
Efficiently solving SDP relaxation of an integer quadratic program
I have an integer quadratic program of the form,
\begin{align}
\underset{x}{\max}&\;\;\|Ax-b\|_2^2\\
\text{subject to}&\;\;x\in{\bf Z}\geq0
\end{align}
I'm currently using the (admittedly ...
- 443
0
votes
0
answers
31
views
How to write a dynamic SDP using CVX?
Consider the following SDP
$$
\begin{aligned}
\min\quad&\text{tr}(CX)\\
\text{s.t.}\quad&\text{tr}(A_iX)=b_i,\quad i=1,\cdots,p\\
&X\succeq0
\end{aligned}
$$
where $C$ and $A_i$ are given ...
- 131
3
votes
1
answer
459
views
Questions regarding the result of the CVXPY
I want to optimize the function
$$\min_{X \in \mathbb{S}^{n}_{+}} \mbox{tr} \left( C^T X \right) + \mbox{tr} \left( X^{-1} \right),$$
of which I optimize the equivalent problem
$$\min \mbox{tr}\left(C^...
- 133
2
votes
1
answer
2k
views
How to solve the following SDP with Python?
Supposing that $\{B_{ij}\}_{i,j}$ are all Hermitian matrices and $\{c_{ijk}\}_{i,j,k}$ are all real numbers, the corresponding SDP(Semidefinite Programming) problem is as follows:
$$
\begin{aligned}
&...
- 131
3
votes
1
answer
94
views
Find $x$ that satisfy $(I-A^*A)+x(\frac{A+A^*}{2})\prec0$ using LMI or SDP on Matlab
Given $A\in\mathbb{C}^{n\times n}$, I want to use LMI or SDP to find feasibility of $x>0$ in the following inequality:
$$(I-A^*A)+x(\frac{A+A^*}{2})\prec0,$$
where $D\prec0$ means that $D$ is ...
- 183
0
votes
1
answer
82
views
Variable equality constraints in SDP Problem
I'm quite new to SDP programming, hence I might not have been able to use the right search terms to find a solution.
I try to reformulate an SDP problem to the original form. However a side constraint ...
- 13
3
votes
1
answer
166
views
Log-Determinant constraints in SDP
This is a belated follow up to my question here, because I didn't want to tack questions onto questions.
According to the Mosek documentation here, one possibility for expressing $t \leq log(det(X))$, ...
- 131
1
vote
1
answer
386
views
How to optimize nuclear norm subject to positive semidefinite constraints?
For finite dimensional symmetric positive semidefinite matrices $A$ and $B$, I would like to solve
\begin{align}&\min |X - A|_1 \\
&\text{subject to}\\
&X \preceq B \\
&0 \preceq X\...
- 113
5
votes
2
answers
961
views
log(det(X)) in Semidefinite Programming
I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
- 131
4
votes
1
answer
215
views
Underdetermined Minimum Volume Enclosing Ellipsoid
Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
- 131
-1
votes
1
answer
27
views
Semi-Definite relaxation of non-linear constraint?
I am implementing an optimization problem using semi-definite approach. One of my constraints is of following form
$ trace(A∗X)−(k∗trace(A∗X))+(k∗\sqrt {(trace(B∗X)} )==0$
where k is a constant, A ...
3
votes
0
answers
162
views
First order methods for a large scale semidefinite program
I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...
- 31
2
votes
0
answers
70
views
Looking for a version of DSDP that is less prone to integer overflows than the original
I am working on a problem that involves semidefinite programming (constrained optimization of fairly large positive definite matrices). The software is written in C++ and calls DSDP 5.8 to solve the ...
- 321
3
votes
1
answer
536
views
What is the fastest way to solve Ax=b (subject to constraints and an absolute term)
I am trying to solve/optimize $Ax=b$ in the least squares sense subject to
box constraints;
a few (less than 5) equality/inequality constraints; and
an absolute function penalty (or some other ...
- 133
4
votes
0
answers
65
views
Obtainting KKT for QSDP for the trace inequality constraint
I am working on developing my own solver(for implementation on hardware), based on IPM for following problem:
\begin{equation}
\begin{split}
\min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\
\text{...
4
votes
1
answer
457
views
Imposing special structure on Positive Semi-Definite matrix
I am trying to implement the algorithm described in reference 1 using cvxpy. However I am struggling to constrain the matrix $Z_j$ as described in equations (33-35)....
- 45
3
votes
1
answer
467
views
Translating a nuclear norm constraint to an LMI constraint
I'm attempting to solve a convex optimization problem where one of the constraints is
$$\|M\|_* \leq a$$
where $\|M\|_*$ denotes the nuclear norm of matrix $M$. I'm using CVXOPT in Python to solve ...
- 131
1
vote
1
answer
417
views
How to deal with quadratic constrain in semidefinite programming
I am using CVX to solve an optimization problem. One of my constraints in the problem is
$$M \succeq \eta {\eta}^T$$
where $M$ is a square matrix and $\eta$ is a column vector (both $M$ and $\eta$ ...
- 113
0
votes
1
answer
203
views
Express SDP problem in CSDP
I am trying to use CSDP and am struggling with this.
Consider for example the SDP problem proposed by prof. Borchers here. Namely:
$$\max_{A,z} \sum_{i} z_{i}\quad\text{subject to}\quad\mbox{tr}(P_{...
- 437
4
votes
2
answers
195
views
Maximization variant of semidefinite programming (SDP)
Consider the following program:
$$\max_{\pmb a} \sum_i z_i\\
u.c. \pmb a \pmb P_i\pmb a^\top\geq z_i$$
where $\pmb a \in\mathbb{R}^p$ and the $\pmb P_i$ are all symmetric positive semidefinite ...
- 143
1
vote
1
answer
45
views
How to compute $\mathrm{proj}_{SDP}(C\odot X)./C$ without numerical problems?
I have a matrix, $X$, it is symmetric. I project $C \odot X$ and $D\odot X$ to semidefinite cone. $C$ is a Gramian matrix with some elements near zero and of course semidefinite, with one row and ...
- 221
0
votes
1
answer
68
views
Express the $\gamma_{2}^{\epsilon}$ SemiDefinite program in a form that is acceptable by SDPT3
I'm trying to express the following semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$,
\begin{align}
&\gamma_{2}^{\epsilon}(A):= \min\,t\\
&\text{...
- 103
0
votes
1
answer
511
views
Storage complexity of SDP solver SCS
This is a follow up question to this question.
Consider the following SDP in standard form:
\begin{align}
&\min_{X\in S^n, X>0} \operatorname{tr}(AX)\\
&\mbox{subject to}\; \operatorname{...
- 101
6
votes
1
answer
567
views
Best platform for complex SDPs with n and m around 5-15K?
I am looking to solve a class of SDPs with complex entries, with the semi-definite cone $S^n$, $n$ around 5000 to 15000. Also, $m$, the number of equality/inequality constraints is close to $n$.
I ...
- 61
4
votes
1
answer
232
views
Rank constrained SDP
I would like to optimize a function of the following form:
\begin{equation}
\sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j,
\end{equation}
where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible ...
- 93
5
votes
1
answer
1k
views
Fast projection onto semidefinite cone
Lots of algorithms for semidefinite programming make use of the Frobenius projection onto the cone of semidefinite matrices:
$$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$$
Let's ...
- 1,341
5
votes
1
answer
802
views
Semidefinite Programming Using CVX in Matlab
I have the following optimization problem
$$\begin{align}
&\min_{ X_{1}, \dots,X_{k} } \max_{ \theta, \phi } \left|P_{d}(\theta,\phi) - \sum_{k=1}^K \operatorname{Tr}(a_{k}(\theta,\phi)a_{k}^{H}...
- 53
0
votes
1
answer
364
views
How to write Goemans-Williamson MAX-CUT relaxation as SDP
Let W be a graph Laplacian (symmetric diagonally dominant, and thus PSD), and X the matrix variable.
Let $<A,B>=Tr(A^TB)$.
$$\text{Maximize}\;\; \displaystyle\sum_{i,j} w_{ij}(x^{(i)}\cdot x^{(...
- 443
2
votes
2
answers
2k
views
Solve large dense positive-definite linear system
Which method should I choose to solve a large (~20 000 variables) dense symmetric positive-definite, possibly ill-conditioned, system of linear equations?
The system will be solved for two vectors. I'...
- 21
7
votes
3
answers
2k
views
Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm
So I have a symmetric matrix $A$ and I would like to solve the optimization problem,
$$\hspace{2.5mm}\text{Minimize}\;\; \|A-S\|_2$$
$$\hspace{-5mm}\text{Subject to}\;\; S\geq0.$$
$A$ is given and $S$ ...
- 443
10
votes
3
answers
2k
views
Do they use semidefinite programming in industry?
I can't see any mention of it in job listings. I've seen mentioned integer programming, MIP, mixed-integer nonlinear programming, LP, dynamic programming etc., but no SDP.
Is it much trendier in the ...
- 201
0
votes
1
answer
582
views
Fastest linear solver for sparse positive semidefinite, striclty diagonally dominant matrix
What is the state of the art for fastest linear solver for sparse, positive semi definite and strictly diagonally dominant matrix with N varies from ~700 to ~3000, and about a 1/16 of the matrix is ...
- 83
2
votes
1
answer
151
views
How can I convert this SDP constraint?
I have the following SDP problem:
max: $Tr(CX)$
subject to: $X \geq 0, I - X \geq 0$.
I want to convert it into the standard form specified by CSDP (I'm using the callable C interface), which is:
...
- 23
2
votes
1
answer
821
views
Efficient formulation of an SDP involving L1 norm
I am trying to reformulate the following problem to be solved efficiently (by MOSEK)
$$
\min_{X} \text{Tr}(CX)+\lambda\sum_{i,j}|x_{i,j}| \\
\text{s.t.} \quad ||X||_F\le1 \quad \text{and} \quad X\ge 0 ...
- 23
2
votes
2
answers
970
views
How to put following SDP probllem into an equality standard form
I have the following semi-definite programming problem that I want to put in a standard form in order to estimate its order of complexity.
The problem is:
$$
\max_{x_{i,j}}\sum_{i \in \mathbf{F} }^{...
- 31
5
votes
1
answer
584
views
How to transform such an SDP to standard form
I plans to use CSDP to solve the following semi-definite problem:
$$\min_{B, \beta}\operatorname{trace}(CB) \\
\text{s.t.} \ \operatorname{trace}(AB)=1 \\
\beta\geqslant 0 \\
\begin{bmatrix}
1 & \...
- 317
1
vote
0
answers
230
views
Sign or cardinality constraint when solving for sparse signal
I'm currently learning about using linear and semidefinite programming to find sparse solutions to problems. In particular, finding sparse solutions where the sampling functions are sinusoidal (...
- 335
4
votes
3
answers
486
views
How to implement this trigonometric polynomial maximum finding semidefinite program
Hi All, I posted this on the math.se site, but this may be a better location.
I need a method of finding the maximum of a real valued trigonometric polynomial where I can trade accuracy for speed. ...
- 335
4
votes
1
answer
727
views
What is a vector programming problem?
In a note:
semi-definite programming is equivalent to vector programming.
...
A Vector Program is a Linear Program over dot products.
In Boyd's Convex Optimization, a vector optimization ...
- 1,291