Why in quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear

Question

I found in wikipedia that...

Quadratic programming is particularly simple when there are only equality constraints; specifically, the problem is linear

font: Quadratic Programming

What I can't understand is why. I didn't find any reference about this affirmation. This indicates that the computational cost is also smaller?

Answer 1

If the problem is linear and only has equality constraints, then the optimal solution occurs on the vertices of the shape given by the intersection of the inequality constraints. So if there are $n$ equality constraints, then there are less than $n$ points that are candidates for the optimal solution (i.e. Yes the computational cost shrinks).

I'm not sure why the problem becomes linear, but the wiki page you linked seems to suggest that with equality constraints, the problem can be equivalently written as a linear program (under section Equality constraints).

Dantzig shows in his book Linear Programming (volume 2) that each extreme point in a linear programming problem with only equality constraints is a basic feasible solution (Thm 1.5, p.16). It then remains to show that $x$ is a basic feasible solution if and only if $x$ is a vertex of the constraint set $C=\{x:Ax=0\}$, where $x$ is a vertex means there does not exist nonzero $y$ so that $x+y\in C$ and $x-y\in C$.