Questions tagged [semidefinite-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 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 ...
user avatar
  • 13
2 votes
0 answers
42 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....
user avatar
  • 21
0 votes
1 answer
61 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 ...
user avatar
  • 443
0 votes
0 answers
21 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 ...
user avatar
3 votes
1 answer
158 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^...
user avatar
  • 133
0 votes
0 answers
40 views

Eliminating Variables in Semidefinite Programs Using Equality Constraints

Suppose I have an SDP $$\min_{X \in \mathbb{S}^{n}_{+}} f(X)$$ $$\text{s.t.} \quad X_{i,j} = c_{i,j} \quad \forall (i,j) \in I,$$ where $I \subseteq [n] \times [n]$ and $f$ is convex on the set of ...
user avatar
2 votes
1 answer
622 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} &...
user avatar
3 votes
1 answer
88 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 ...
user avatar
  • 183
0 votes
1 answer
61 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 ...
user avatar
  • 13
3 votes
1 answer
117 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))$, ...
user avatar
1 vote
1 answer
229 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\...
user avatar
5 votes
2 answers
755 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 ...
user avatar
4 votes
1 answer
212 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 ...
user avatar
-1 votes
1 answer
25 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 ...
user avatar
3 votes
0 answers
142 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 \...
user avatar
  • 31
2 votes
0 answers
65 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 ...
user avatar
3 votes
1 answer
414 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 ...
user avatar
  • 133
4 votes
0 answers
59 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{...
user avatar
4 votes
1 answer
415 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)....
user avatar
3 votes
1 answer
427 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 ...
user avatar
  • 131
1 vote
1 answer
339 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$ ...
user avatar
  • 113
0 votes
1 answer
177 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_{...
user avatar
4 votes
2 answers
176 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 ...
user avatar
  • 143
1 vote
1 answer
44 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 ...
user avatar
  • 221
0 votes
1 answer
67 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{...
user avatar
  • 103
0 votes
1 answer
477 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{...
user avatar
  • 101
6 votes
1 answer
541 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 ...
user avatar
4 votes
1 answer
213 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 ...
user avatar
  • 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 ...
user avatar
5 votes
1 answer
757 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}...
user avatar
0 votes
1 answer
360 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^{(...
user avatar
  • 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'...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
0 votes
1 answer
552 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 ...
user avatar
  • 83
2 votes
1 answer
132 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: ...
user avatar
  • 23
2 votes
1 answer
760 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 ...
user avatar
  • 23
2 votes
2 answers
926 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} }^{...
user avatar
  • 31
5 votes
1 answer
545 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 & \...
user avatar
  • 317
1 vote
0 answers
229 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 (...
user avatar
4 votes
3 answers
466 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. ...
user avatar
4 votes
1 answer
706 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 ...
user avatar
  • 1,241