Skip to main content
7 votes
Accepted

Imposing special structure on Positive Semi-Definite matrix

The whole point is that you do NOT include the constraint $U = uu^T$ . That constraint is non-convex. Instead you include the constraint that $Z_j$ is (positive) semi-definite. This constraint is ...
Mark L. Stone's user avatar
7 votes
Accepted

Maximization variant of semidefinite programming (SDP)

You can obtain a semidefinite relaxation of your problem that will provide a bound on the optimal value of your problem, but it will not be an exact semidefinite formulation of your problem. Start ...
Brian Borchers's user avatar
6 votes
Accepted

Rewriting quadratically-constrained optimization problem as a semidefinite program

With a factorization such as $HAH = R^TR$ you can apply a Schur complement and use $\begin{pmatrix}tI+\alpha (AH+HA)-A & \alpha R^T\\\alpha R & I\end{pmatrix} \succeq 0$.
Johan Löfberg's user avatar
4 votes
Accepted

Space complexity of a semidefinite program

For a problem with $m$ linear equality constraints and a $n$ by $n$ matrix variable, the problem data $A$, $b$, $C$ requires $O(mn^{2})$ storage for $A$, $O(m)$ storage for $b$, and $O(n^{2})$ storage ...
Brian Borchers's user avatar
4 votes
Accepted

How to optimize nuclear norm subject to positive semidefinite constraints?

This is easy to formulate in CVX, under MATLAB. A CVXPY solution, under Python, is similar. CVX code: ...
Mark L. Stone's user avatar
4 votes
Accepted

Variable equality constraints in SDP Problem

First, a standard semidefinite program (in primal form) would be $$\underset{X}{\text{min }} \langle W, X \rangle, \\ X\succeq 0,~\mathbf{A}(X) = b$$ where $\mathbf{A}(X) = b$ denotes the primal ...
Johan Löfberg's user avatar
3 votes

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$?

I assume your question is "which optimizer did cvxpy choose for my problem", as cvxpy can use a number of optimizers that it selects based on the problem, and indeed the output doesn't ...
Marses's user avatar
  • 131
3 votes

Log-Determinant constraints in SDP

You simply put zeros on the required positions, i.e. parameterize $Z$ using the required triangular basis. You never explicitly work with any factorization, that's just for proving that the ...
Johan Löfberg's user avatar
3 votes

Nearest positive semidefinite matrix to a symmetric matrix in the spectral norm

According to the paper Nicholas J. Higham, MR 943997 Computing a nearest symmetric positive semidefinite matrix, Linear Algebra Appl. 103 (1988), 103--118, one of the solution is in the following ...
Kai's user avatar
  • 31
3 votes

log(det(X)) in Semidefinite Programming

The determinant is the product of all eigenvalues $\lambda_i(A)$, so its logarithm is the sum of the logarithms of the eigenvalues. As a consequence, you can write the objective function as follows: $$...
Wolfgang Bangerth's user avatar
3 votes
Accepted

How to deal with quadratic constrain in semidefinite programming

Apply a Schur complement on the constraint $\begin{pmatrix} M & \eta\\\eta^T & 1\end{pmatrix} \succeq 0$
Johan Löfberg's user avatar
3 votes
Accepted

What is the fastest way to solve Ax=b (subject to constraints and an absolute term)

This problem can be formulated as a standard positive semidefinite QP with bounded variables. First, deal with the absolute value terms in the objective by letting $x=u-v$, where $u\geq 0$ and $v \...
Brian Borchers's user avatar
3 votes
Accepted

How to solve the following SDP with Python?

Edit: I looked at the paper you linked in the comment. I'm no expert in quantum computing, but it seems like a hot mess. The notation is certainly not clear to me, but if you can clear it up then I'll ...
Robert Bassett's user avatar
2 votes

How to formulate a convex expression to minimize the difference between Frobenius norm of a positive semidefinite matrix and a positive value

One solution to the problem is to choose $P$ as the diagonal matrix with diagonal entries equal to $J/\sqrt{n}$. Its Frobenius norm is $J$ and it is symmetric and positive definite.
Wolfgang Bangerth's user avatar
2 votes
Accepted

Find $x$ that satisfy $(I-A^*A)+x(\frac{A+A^*}{2})\prec0$ using LMI or SDP on Matlab

Here is the correct answer: ...
Lee's user avatar
  • 183
2 votes
Accepted

Express SDP problem in CSDP

Inequality constraints in an SDP can be turned into equality constraints by introducing non-negative slack variables. If your original problem is $\max \Sigma_{i=1}^{n} z_{i}$ subject to $\mbox{...
Brian Borchers's user avatar
2 votes

Maximization variant of semidefinite programming (SDP)

It's possible I'm misunderstanding something (and please let me know if I am), but here's another approach: Based on your formulation, it looks like your first group of inequality constraints will ...
AJ Friend's user avatar
  • 121
2 votes
Accepted

log(det(X)) in Semidefinite Programming

First of all, move the objective to the constraints by using the epigraph formulation max t subject to log_det(A) $\ge$ t plus your other constraints. Section 6.2.3 of the Mosek Modeling ...
Mark L. Stone's user avatar
1 vote
Accepted

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$?

Cvxpy cannot solve SDPs by it itself. It feeds the problem into an optimizer such as Mosek. Therefore, you should consult the documentation of the optimizer you are using. Btw it is trivial to convert ...
ErlingMOSEK's user avatar
1 vote

Efficiently solving SDP relaxation of an integer quadratic program

As a follow up to my comment, where I say that the model has to be interpreted from the primal model side, here it implements the model for $n=1000$ and then tells the modelling layer YALMIP that it ...
Johan Löfberg's user avatar
1 vote
Accepted

Questions regarding the result of the CVXPY

The "equivalent" problem is equivalent (by Schur Complement of the "equivalent" formulation). But $A$ is not positive semidefinite. Therefore, $A$ does not satisfy the constraint ...
Mark L. Stone's user avatar
1 vote

Underdetermined Minimum Volume Enclosing Ellipsoid

You don't need SDP for an easy task like this. $X$ are your points. Do a PCA on $Y Y', Y = X - \operatorname{mean}(X)$, reduce dimension to 2-dimensions (others dimensions are zeros). 3 points on the ...
sharl's user avatar
  • 57

Only top scored, non community-wiki answers of a minimum length are eligible