Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it possible to have the following condition in a semidefinite programming as a constraint?

$ M= \left[ {\begin{array}{cc} a & \sqrt{u} \\ \sqrt{u} & b \\ \end{array} } \right] \geq 0$

where $\geq 0$ means positive semidefinite.

share|cite|improve this question

migrated from Feb 12 '13 at 23:45

This question came from our site for theoretical computer scientists and researchers in related fields.

Assuming that a, b, and u are real variables in your semidefinite program, the answer is negative.

The important fact here is that each constraint in a semidefinite program defines a convex set. Your condition cannot be written as a constraint in a semidefinite program because the set of points (a, b, u) ∈ ℝ3 that satisfy the condition is not convex. I suggest that you try to prove that this set is indeed not convex, but here is a proof (put the mouse cursor in the box below to show the proof):

Proof: (a, b, u) = (1, 1, 1) and (a, b, u) = (3, 3, 9) satisfy the condition, but their midpoint (a, b, u) = (2, 2, 5) does not satisfy the condition.

share|cite|improve this answer
However, if there are some constraints over $a$, $b$ and $u$ it can be, right? – Alex Grilo Feb 13 '13 at 19:44
@Alex Grilo: Clearly it all depends on what kind of constraints you are thinking of. For example, if one of a, b, and u is a constant, then the condition in the question can be easily written as a constraint in a semidefinite program, although this is a silly example. – Tsuyoshi Ito Feb 13 '13 at 20:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.