# Tag Info

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 ...
• 2,242
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 ...
• 18.8k
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$.
• 1,848
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 ...
• 18.8k
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: ...
• 2,242
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 ...
• 1,848

### 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 ...
• 131

### 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 ...
• 1,848

### 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 ...
• 31

### 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: ...
• 55.9k
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$
• 1,848
Accepted

• 18.8k

### 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 ...
• 121
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 ...
• 2,242
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 ...
• 126
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 ...
• 1,848
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 ...
• 2,242
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 ...
• 57

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