Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

Why study the linear programming (LP) ?

LP has a lot of use cases, one of them is the SVM ( support vector machine). The SVM ‘s Lagrangian dual can give the lower bound of SVM,  this Lagrangian dual can be solved by quadratic programming. The KKT conditions of this quadratic programming can be solved by linear programming.

What is the linear programming?

normally it is something like:

find max or min of  z= 3x + 4y

with constraints like:   x + 2y <=14, 3x – y >= 0 , x -y <= 2

How to solve it?

graph of inequalities, with lines labelled and feasibility region shaded in


It has been proved  that the maximum and minimum values of the optimization equation will always be on the corners of the feasibility region ( extreme points), so generally we just need to find a possible extreme points first, then find the next possible points, …., until we reach the max or min. ( that is basic of simplex algorithm)


Dr. Salimina’s video explained the simplex algorithm very well. Please watch it if you really want to understand it.

notes: simplex algorithm is just one of the many algorithms to solve this.



Leave a Reply

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