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?
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.
References
http://www.purplemath.com/modules/linprog.htm
https://people.richland.edu/james/ictcm/2006/simplex.html
https://en.wikipedia.org/wiki/Simplex_algorithm
https://en.wikipedia.org/wiki/Linear_programming
