Talk:Quadratic programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Conversion to LP[edit]

the first section states that if Q = 0, then the problem is an LP. However, the article on LPs defines every element of x being > 0. The QP is not defined in this manner. — Preceding unsigned comment added by 72.208.4.159 (talk) 05:31, 12 October 2011 (UTC)

Only Equality[edit]

The article states: "If there are only equality constraints, then the QP can be solved by a linear system". This can't be right, as you could easily convert inequality constraints to equality. Can somebody explain where this claim comes from? 130.149.13.91 (talk) 13:47, 29 May 2009 (UTC)

I think it should be simple to explain the claim. Following the article, if we have only inequality constraints (and we assume c = 0 for simplicity), then the dual problem is
maximize  -\tfrac{1}{2}\lambda^{T}AQ^{-1}A^{T}\lambda - b^{T}\lambda
subject to \lambda \geqslant 0
Now, suppose we had only equality constraints and no inequality constraints. This only changes the dual problem in the sense that there is now no constraint on \lambda (and, for clarity, we'll use a new variable name for \lambda, for example \nu). So the dual is now the unconstrained problem
maximize  -\tfrac{1}{2}\nu^{T}EQ^{-1}E^{T}\nu - b^{T}\nu
Since it is unconstrained, and since it is differentiable, the solution can be found by setting the gradient equal to zero (recall that Q is symmetric):
 0 = - EQ^{-1}E^{T}\nu - b
so the solution is found by solving a linear system.
Now, to address your point that we can convert inequality constraints to equality constraints. This is only partially correct. You're probably thinking of slack variables. If we want to convert the inequalities
 Ax \le b
we can write down the following equivalent statement
 Ax + s = b,\quad s \ge 0
so we have introduced the slack variables  s to eliminate the inequality constraint on x, but at the cost of introducing an inequality constraint on s. So, there's no "easy-way-out". However, the converse is true: we can convert an equality to two inequalities, as shown below
 E x = d
is equivalent to
 E x \le d,\quad -Ex \le -d
Hope that clarifies. Lavaka (talk) 23:31, 18 August 2009 (UTC)

Help please[edit]

This is a very good article if you already know what quadratic programming is. For those of us who had to look it up, this is not particularly helpful.—Preceding unsigned comment added by 165.124.165.113 (talkcontribs) 06:00, October 20, 2006 (UTC)

Two years later, the problem hasn't gone away. A simple practical example is needed! --New Thought (talk) 14:26, 13 November 2008 (UTC)
It would probably be helpful to contrast it with linear programming. But I agree with above comment. —Preceding unsigned comment added by 128.101.34.35 (talkcontribs) 20:14, March 31, 2006 (UTC)
Have added a short comment on the LP case. —Preceding unsigned comment added by 88.111.53.221 (talkcontribs) 11:56, July 7, 2006 (UTC)
Should a section "Applications of Quadratic Programming" be added, e.g. portfolio optimization? —Preceding unsigned comment added by Kem wiki (talkcontribs) 11:34, 24 November 2009 (UTC)
I agree. I didn't get much out of skimming this article. --mgarde (talk) 22:01, 8 December 2011 (UTC)

Complexity[edit]

Why does it say "Even if Q has only one negative eigenvalue..." but that's covered by the statement preceeding about indefinite Q. So it seems silly and confusing to have a 2nd special-case statement here. —Preceding unsigned comment added by 71.197.232.50 (talk) 04:44, 7 January 2010 (UTC)

I'm not so sure about the comments in the complexity section - why should Q need to be positive definite in order to obtain a polynomial time solution? Perhaps the article should say "If Q is postive semidefinite (including Q = 0), then a solution can be found in polynomial time".

I'm also not convinced about the ellipsoidal method reference - the associated article claims that ellipsoid method is for LPs. Perhaps a reference to an interior point text or to a general convex optimization book is more appropriate. —Preceding unsigned comment added by 88.111.53.221 (talkcontribs) 11:56, July 7, 2006 (UTC)

Transpose[edit]

In my opinion it can be confusing to use 2 different things to note a matrix' transpose on the same page by writing v' and vT alike. —Preceding unsigned comment added by 213.44.221.86 (talkcontribs) 14:05, June 7, 2007 (UTC)

Please define your terms[edit]

Can the article please explain what the symbol \preceq means? I have a Ph.D. in maths and I don't know! --Dr Greg 12:36, 13 September 2007 (UTC)

Done. It's only because I know what it should mean that I could explain it; the symbol is not in wide use. -- Jitse Niesen (talk) 13:22, 13 September 2007 (UTC)
The symbol is in wide use in the optimization community, so I think it's fine to have it (but I do agree that it should be defined) Lavaka (talk) 23:13, 18 August 2009 (UTC)

Definition[edit]

This edit claims that the constraints in a Quadratic Programming problem can be quadratic. However, the rest of the article assumes that they are linear. Also, the definition in the book of Nocedal and Wright (p. 449, at the start of Chapter 16, in the second edition) states that the constraints in quadratic programming are linear, as does the QP page in the NEOS Guide. I would be very interested in references to the literature stating that the constraints can be quadratic as this goes against everything I have seen. For the moment, the definition with linear constraint is the only one supported by the references, so I reverted again. -- Jitse Niesen (talk) 09:41, 11 June 2008 (UTC)

If also the constraints are quadratic it is called a quadratically constrained quadratic program (QCQP). Reference: Boyd & Vandenberghe : Convex Optimization. --Petter (talk) 16:50, 16 July 2009 (UTC)

page title is undescriptive/misleading[edit]

As an experienced programmer with a solid background in math, I find the title very undescriptive if not misleading. I am suggesting that the title should be replaced by "Quadratic Optimization" and, "quadratic programming" should be the title of a redirection page pointing this article. — Preceding unsigned comment added by Condmatstrel (talkcontribs) 09:52, 16 December 2012 (UTC)