Talk:Quadratic programming

Conversion to LP

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)

Every QP with Q = 0 is an LP. This is supported by standard texts like Boyd & Vandenberghe : Convex Optimization. When Q = 0, then one has an LP in general form. Any LP in general form can be converted to an LP in standard form by an appropriate reformulation - see Section 4.3 of Boyd & Vandenberghe : Convex Optimization. The linear programming page poses an LP in standard form. So there is no contradiction.

I guess the line in the quadratic programming page mentioning the Q=0 case has since been removed. StygEng (talk) 13:40, 5 January 2024 (UTC)

Only Equality

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\leq b$

we can write down the following equivalent statement

$Ax+s=b,\quad s\geq 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

$Ex=d$

is equivalent to

$Ex\leq d,\quad -Ex\leq -d$

Hope that clarifies. Lavaka (talk) 23:31, 18 August 2009 (UTC)

Help please

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 (talk • contribs) 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 (talk • contribs) 20:14, March 31, 2006 (UTC)

Have added a short comment on the LP case. —Preceding unsigned comment added by 88.111.53.221 (talk • contribs) 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 (talk • contribs) 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

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 (talk • contribs) 11:56, July 7, 2006 (UTC)

Transpose

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 v^T alike. —Preceding unsigned comment added by 213.44.221.86 (talk • contribs) 14:05, June 7, 2007 (UTC)

Please define your terms

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

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

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 (talk • contribs) 09:52, 16 December 2012 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Quadratic programming. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://web.archive.org/web/20110201043008/http://openopt.org:80/QP to http://openopt.org/QP

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 12:09, 21 July 2016 (UTC)

XPRESS =>XPRESS (newspaper)

There is link to XPRESS (newspaper)... What connection has XPRESS Solver to XPRESS (newspaper)? Jumpow (talk) 17:36, 3 March 2017 (UTC)