As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [semidefinite-programming]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
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
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
572 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
1k 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 ...
806 views

• 317
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
198 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
487 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
729 views

### What is a vector programming problem?

In a note: semi-deﬁnite 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
475 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
232 views

### Rank constrained SDP

I would like to optimize a function of the following form: $$\sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j,$$ where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible ...
• 93
217 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 ...
67 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{split} \min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\ \text{...
123 views

• 133
169 views

### First order methods for a large scale semidefinite program

I am interested in solving the following semidefinite optimization problem: \begin{split} \underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\ &-\mathbb{I} \le X \le \...
• 31
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
975 views

• 131
832 views

• 437
69 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
368 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
100 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
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 ...