Talk:Semidefinite programming

Systems: Operations research Start‑class Mid‑importance

	Systems science portal This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.SystemsWikipedia:WikiProject SystemsTemplate:WikiProject SystemsSystems
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-importance on the project's importance scale.
	This article is within the field of Operations research.

Hello,

welcome to the article on semidefinite programming.
So far (May 3rd 2006) it is only a stub and definitely needs more input.
I prepared a skeleton and some first exterior links.

There is a lot to do on this article, and for its "environment" (e.g. theorem on primal-dual gap, etc).
In addition to the obvious (definition, duality, solvers etc.) it would be nice to have some formulations for interesting SDPs.
Moreover, it would be good to document the links to polynomial optimization and sums of squares (of polynomials).
But: it seems there are no articles for these as well.

Hopefully we get this article (and its environment) up and running fast.
Best, Hartwig

I added a "citation needed" tag to the reference to quantum computing, mostly because I would like to know more about this connection. Can someone give an in-depth reference for that?

Thanks! —Preceding unsigned comment added by 128.135.214.108 (talk) 01:57, 3 February 2008 (UTC)[reply]

Hello, The reduction from LP with (x^2/y) form objectives to semi-definite program is simply a relaxation or approximation. It is not exact.

The key step is when you are reducing from a constraint det(D) >= 0 to D \succeq 0 (SDP inequality). The implication is strictly one way. For instance, a 2x2 negative semi-definite matrix can also have a positive determinant. It is rather misleading, please consider revising the note.

SS