3
$\begingroup$

In this image from Wikipedia, semidefinite programming is presented as a special case of convex programming. I do not see how this can be. Consider the following two constraints (where $\succeq$ means positive-semidefinite):

$$ \left( \begin{matrix} 1 & x \\ x & 1 \end{matrix} \right) \succeq 0 , ~~~~~~~~~~~~~~~~ \left( \begin{matrix} x & 1 \\ 1 & x \end{matrix} \right) \succeq 0 $$

The first is equivalent to $1-x^2\geq 0$, which is a convex constraint; but the second is equivalent to $x^2-1\geq 0$, which is not a convex constraint. I am probably misunderstanding something very basic here; but what?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$. Together, they are equivalent to $x \ge 1$, which is convex.

The Wikipedia claim about Semidefintie Programs being convex is not really true either. That Wikipedia article makes the implicit assumption that the SDP is linear (affine), in which case the statement is true. However, Semidefinite Programs can also be Bilinear (Bilinear Matrix Inequality, a.k.a., BMI), or more general Nonlinear Semidefinte Programs.

In summary, Linear SDP (SDP in which variables appear only affinely) is convex. Nonlinear SDP (Bilinear and general nonlinear) is non-convex, and generally not so easy to solve to global optimality if the dimension is not very small.

$\endgroup$
1
  • 1
    $\begingroup$ SDP basically refers to the extension (of some mathematical programming base) allowing the set of positive semidefinite matrices (a convex conic set) to be used as a variable domain. All other forms can be seen as syntactic sugar. The historically first mathematical programming base for SDP, the simplest base for SDP, and the most common base for SDP are all LP -- hence the implicit assumption. I agree with Mark, however, that SDP does find use in other contexts and -- if there is any potential for misunderstanding -- it should be clarified. $\endgroup$ Commented Jan 2 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.