The big picture is: a quadratic programming problem can be reduced to be a linear programming problem.
Here is how:
(1) KTT conditions
For any non-linear programming:
max: f(x), s.t: g(x) <=0
It has been proved that it needs to meet Karush–Kuhn–Tucker (KKT) conditions provided that some regularity conditions are satisfied
how it is being proved? it is something like using Lagrange multiplier: f(x) – Lamda * ( g(x) + slack ) then do some smart deductions, we can get those conditions.
One example of KTT is:
Lamda >=0
Delta f(x) – Lamda Delta g(x) = 0 ( Delta is derivertive)
Lamda g(x) = 0
g(x) <=0
(2) Quadratic Programming
Quadratic programming belongs to non-linear programming, so KKT conditions applies here.
The general quadratic programming can be expressed as:
Max: cx + c^T D x
s.t: Ax <= b, x>=0
by applying (1)’s KTT, in short we can get some linear questions with some constraints.
Then we introduce +A in the linear equations, then try to minimize sum(A) with those constraints,
now the problem become a linear programming issue (with minimized target to be 0) .
References:
https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
http://www.comrite.com/wp/linear-programming-in-plain-english/
