Talk:Semidefinite programming: Difference between revisions
The objective function looks wrong |
m Signing comment by 129.74.154.207 - "The objective function looks wrong" |
||
| Line 48: | Line 48: | ||
== The objective function == |
== The objective function == |
||
I thought semidefinite programming optimized a linear function of the variable, as in c'x. Why is there a quadratic function of x in the objective in the article? |
I thought semidefinite programming optimized a linear function of the variable, as in c'x. Why is there a quadratic function of x in the objective in the article? <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/129.74.154.207|129.74.154.207]] ([[User talk:129.74.154.207|talk]]) 16:42, 20 August 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot--> |
||
Revision as of 16:43, 20 August 2013
 | Systems Start‑class Mid‑importance | ||||||||||||
| |||||||||||||
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
(@Hartwig) I found Polynomial SOS has its own wikipedia page now (or rather since 2008), so I will do some edits soon to incorporate it into this SDP page. Probably will start a separate section discussing the algebraic properties of SDP. BR, hattoriace March 2013
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)
See Barnum, Saks & Szegedy CCC 2003. This technique has been applied in particular to the ordered search problem. I have not added these references to the article because I feel the application to quantum computing, while significant, is still only a minor application. 99.236.146.26 (talk) 00:08, 20 January 2009 (UTC)
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 —Preceding unsigned comment added by 69.253.172.250 (talk) 13:04, 22 December 2008 (UTC)
Can the kernel trick be applied in this context to extend the method?
I recall hearing that in many instances where a dot product is used, one can use replace the dot product with a Mercer kernel (http://en.wikipedia.org/wiki/Mercer's_theorem)
Also see (http://en.wikipedia.org/wiki/Kernel_trick).
Furthermore, if this method can be extended with the kernel trick, can the problem still be solved in polynomial time? — Preceding unsigned comment added by 24.251.45.60 (talk) 01:37, 18 November 2012 (UTC)
The objective function
I thought semidefinite programming optimized a linear function of the variable, as in c'x. Why is there a quadratic function of x in the objective in the article? — Preceding unsigned comment added by 129.74.154.207 (talk) 16:42, 20 August 2013 (UTC)