Introduction to Linear Optimization

Linear optimization is the branch of optimization that deals with problems in which the target function and the constraints are linear. The field that studies the algorithms and techniques that exploit the linearity of optimization problems is called linear programming.

Linear optimization

What do we mean by linear? A linear function $f$ has the following form:

$$f(x_1, x_2, ..., x_n) = a_1x_1 + a_2x_2 + ... + a_nx_n + b$$

A linear function is a polynomial function of degree zero or one. That means that the exponent of each variable is either zero or one. For cases in which the function only has one variable, its graph is a straight line. In the general case of $n$ variables (as in the example above), the graph of the function is what is known in math as a hyperplane.

In the example above, $a_1, a_2, ..., a_n$ ...