Skip to main content
9 votes
Accepted

Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix). However, this is not a real restriction. (We have two ...
Erwin Kalvelagen's user avatar
5 votes
Accepted

Conditions required for strong duality to hold for SDPs

The following is from Section 2.2 of Semidefinite Programming for Combinatorial Optimization by Christoph Helmberg. Let's define \begin{align*} p^* &= \inf\{\langle C,X\rangle\,:\,X\text{ primal ...
Thomas Kalinowski's user avatar
5 votes
Accepted

Augmented Lagrangian Function for Semidefinite Programming Problems

My way of reading it is $\langle X, \mathcal{A}^*(y)+S-C\rangle = \langle X, \mathcal{A}^*(y)-C\rangle + \langle X,S \rangle$. The first term is your standard inner product between dual variable and ...
Johan Löfberg's user avatar
4 votes

Augmented Lagrangian Function for Semidefinite Programming Problems

There's a good discussion of this in Convex Optimization by Stephen Boyd and Lieven Vandenberghe. See section 5.9. With an ordinary scalar inequality constraint: $f_{i}(x) \leq 0$, you'll have a term ...
Brian Borchers's user avatar
4 votes
Accepted

How is semidefinite programming a special case of convex programming?

The second of those is NOT equivalent to $x^2−1 \ge 0$. That second semidefinite constraint not only implies $x^2 -1 \ge 0$, it also implies the diagonal elements are nonnegative, i.e., $x \ge 0$. ...
Mark L. Stone's user avatar
2 votes
Accepted

How is this problem quasi-convex?

I won't prove the paper's claim that the optimization problem is quasiconvex. However, the problem is clearly a convex Linear SDP (LMI) for any fixed value of $\lambda$. That does not require $Z$ to ...
Mark L. Stone's user avatar
1 vote
Accepted

Does strong duality hold for this semidefinite program?

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$It turns out that strong duality holds for a slightly different but equivalent SDP. We prove this using the following three ...
mhdadk's user avatar
  • 629
1 vote

Solver for nonlinear semidefinite optimization

If you use Python, I have found calling the scs solver through cvxpy to be very effective for semidefinite programming. The <...
Robert Bassett's user avatar

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