# Linear Programming - [Handwritten note](https://notability.com/n/2roI3TS8K5xeTcz7q_WEhQ) - Definition - Minimize _objective function_ $c_1x_1 + c_2x_2 + \dots + c_nx_n$. - Subject to _constraints_ $a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le b_n$, .... - Optimization under linear constraints! ## Solution - A solution with feasible region - Form _feasible region_ - In convex cases, we know that the solution must be on the endpoints. We may simply find out all the values and compare. - Or, probe at one of the endpoint, and binary search to find the minimum. - Another solution without feasible region, similar to [[prune-and-search]] - Pair constraints (half-plane boundaries) in arbitrary manner. - Probe anywhere, the local slope tells us where the minimum is at, this allows us to eliminate half of the half-planes. - Repeat the process. - Similarly for the upper convex hull.