Member-only story
Linear Programming — The Corner Point Method
I haven’t written anything on here since June 2020. I had originally planned to write some more about linear algebra and I’m not sure what happened. In college I briefly did some research on using linear programming to help reduce noise in signals. At that point I don’t think I had much of an understanding of optimization. Over the past few months I spent some time learning about linear programming. This article will just be about interpreting simplistic problems and using basic tools to solve them.
Background
I’ll note that I know there have been several other posts about this topic on Medium but I feel like they’re all over the places. Some go into much more formal detail and others just seek to use an optimization library. Linear programming is a technique that was developed in the 1940’s by several mathematicians to look at certain optimization problems.
What makes linear programming unique is the combination of the objective function and the system of inequalities. There had been techniques developed for systems of equations before this by mathematicians in the 1800s but they don’t work for these problems. Generally these problems look like the following
The problem is constructed from three parts. You need an objective function, constraints and decision variables. It may be more useful to see it in this form which makes it clear that we have n variables and m constraints which together make a matrix. The m r,ows of the matrix are subject to the…