Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [semidefinite-programming]

The tag has no usage guidance.

-1
votes
1answer
22 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
0answers
58 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 \...
0
votes
0answers
61 views

Clarifying a dual problem solution

I’m referring to this question on MathSE about the sum of $k$ largest eigenvalues of a symmetric matrix as an SDP-problem. I want to solve the maximization problem. As the dual problem is always ...
2
votes
0answers
48 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 ...
2
votes
1answer
93 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 ...
4
votes
0answers
36 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{...
3
votes
1answer
186 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)....
4
votes
1answer
214 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 ...
1
vote
1answer
171 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$ ...
0
votes
1answer
83 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_{...
4
votes
2answers
123 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 ...
1
vote
1answer
41 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 ...
0
votes
1answer
39 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{...
0
votes
1answer
290 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{...
4
votes
1answer
291 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 ...
4
votes
1answer
119 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 ...
4
votes
1answer
601 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 ...
5
votes
1answer
532 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}...
0
votes
1answer
197 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^{(...
1
vote
2answers
1k 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'...
6
votes
3answers
670 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: $$\text{Minimize}\;\; ||A-S||_2$$ $$\hspace{-5mm}\text{Subject to}\;\; S\geq0$$ $A$ is given and $S$ is the ...
8
votes
3answers
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 ...
0
votes
1answer
383 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 ...
2
votes
1answer
101 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: ...
2
votes
1answer
511 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 ...
2
votes
2answers
772 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} }^{...
5
votes
1answer
313 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 & \...
1
vote
0answers
209 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 (...
4
votes
3answers
399 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. ...
4
votes
1answer
447 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 ...