Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

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) .



Leave a Reply

Your email address will not be published. Required fields are marked *