Linear Programming Problem

We describe the ideas and applications of Linear Programming; our presentation is heavily influenced, Methods of Mathematical Economics. We strongly recommend to anyone interested in a very readable presentation, replete with examples and references. Linear Programming is a generalization of Linear Algebra (Desai et. al., 2012. Abbasi-Yadkori, 2012. Bazaraa et. al., 2004. Ben-Tal, Nemirovski, 2002). The reason for this great versatility is the ease at which constraints can be incorporated into the model. To see this, in the following section we describe a specific problem in great detail, and in §3 we discuss how some quadratic (or higher order) constraints can be handled as well. A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to linear constraints (Marsden and Tromba, 2003. Sutton et. al., 2009. Calafiore and Campi, 2005. Bertsekas, 2007). The constraints may be equalities or inequalities. Here is a simple example Find numbers x1 and x2 that maximize the sum x1 + x2 subject to the constraints x1 ≥ 0, x2 ≥ 0, and In this problem there are two unknowns, and five constraints. All the constraints are inequalities and they are all linear in the sense that each involves an inequality in some linear function of the variables (Campi and Garatti, 2008. Maei et. al., 2010. Winston, 2003). The first two constraints, x1 ≥ 0 and x2 ≥ 0, are special. These are called no negativity constraints and are often found in linear programming problems. The other constraints are then called the main constraints. The function to be maximized (or minimized) is called the objective function. Here, the objective function is x1 + x2. Since there are only two variables, we can solve this problem by graphing the set of points in the plane that satisfies all the constraints (called the constraint set) and then finding which point of this set maximizes the value of the objective function (Farias and Van Roy, 2006). Each inequality constraint is satisfied by a half-plane of points, and the constraint set is the intersection of all the half-planes. In the present example, the constraint set is the five sided figure shaded in Figure 1. We seek the point (x1, x2), that achieves the maximum of x1 + x2 as (x1, x2) ranges over this constraint set. The function x1 + x2 is constant on lines with slope −1, for example the line x1 + x2 = 1, and as we move this line further from the origin up and to the right, the value of x1 + x2 increases (Pena et. al., 2009). Therefore, we seek the line of slope −1 that is farthest from the origin and still touches the constraint set. This occurs at the intersection of the lines x1 + 2x2 = 4 and 4x1 + 2x2 = 12, namely, (x1, x2) = (8/3, 2/3). The value of the objective function there is (8/3) + (2/3) = 10/3. minimum) value at a corner point of the constraint set, provided the constraint set is bounded. Occasionally, the maximum occurs along an entire edge or face of the constraint set, but then the maximum occurs at a corner point as well. Not all linear programming problems are so easily solved (Petrik and Zilberstein, 2009).There may be many variables and many constraints. Some variables may be constrained to be nonnegative and others unconstrained. Some of the main constraints may be equalities and others inequalities.

However, two classes of problems, called here the standard maximum problem and the standard minimum problem, (Veatch, 2013). play a special role. In these problems, all variables are constrained to be nonnegative, and all main constraints are inequalities. We are given an m-vector,, an n-vector, , and an m × n matrix, of real numbers. The Standard Maximum Problem: Find an n-vector, x = (x1,...,xn)T, to maximize

And, The Standard Minimum Problem: Find an m-vector, y = (y1,...,ym), to minimize And, Note that the main constraints are written as ≤ for the standard maximum problem and ≥ for the standard minimum problem. The introductory example is a standard maximum problem.

Recall the Linear Programming problem may be assumed to be in the following form: 1. Variables x = (x1. . . xN ) ≥ 0; 2. Linear constraints Ax = b, with b = (b1. . . bM); 3. Minimize the linear function Definition: (Dual Problem). Given a canonical Linear Programming problem, the Dual Problem is defined by 1. Variables 2. Linear constraints 3. Maximize the linear function. Exercise: Prove the Dual Problem of the Dual Problem is the original Linear Programming problem. We give a simple example of how the Dual Problem can provide information about the original problem. Assume y is a feasible solution of the Dual Problem. Thus. We immediately find that, if x is a

And Thus, And any feasible solution of the Dual Problem gives a lower bound for the linear function we are trying to maximize in the canonical Linear Programming problem. This leads to the following test for optimality: Consider a canonical Linear Programming problem with a feasible solution, and its Dual Problem with a feasible solution then is also an optimal solution. Proof: Let x be any feasible solution to our Linear Programming problem. we know that however, by assumption we have, which implies that for x any feasible solution to our Linear Programming problem. Thus is an optimal solution, minimizing our linear function.

Let x be a feasible solution for the canonical Linear Programming problem with constraints Ax = b. While all the coordinates of x are non-negative, some may be zero. Let denote the coordinates of x that are positive. If the corresponding columns are linearly independent, then we say that x is a basic solution1 to the Linear Programming problem. The following simple observation is crucial to efficiently solving Linear Programming problems. There are only finitely many basic solutions to a canonical Linear Programming problem. Proof: Let A have M rows and N columns. There are only finitely many subsets of columns (in fact, there are non-empty subsets of k columns of Consider one such subset; let denote a set of k linearly independent columns of A. We are reduced to showing that there are only finitely many (with each coordinate positive) such that There is at most one such solution. Where has M rows and k columns. Note because if M < k then the k columns cannot be linearly independent. We would like to say however, A0 is not necessarily a square matrix (and if it is not a square matrix, it cannot be invertible). We remedy this by multiplying both sides by , obtaining For example, if Then we may take to be the first two columns, and we find Prove that if has M rows and k columns, with is invertible. The above arguments show that there are only finitely many basic solutions to a canonical Linear Programming problem.

This paper describes Linear Programming, an important simplification of Linear Algebra. Linear Programming is used to successfully model numerous actual world situations, ranging from scheduling airline routes to shipping oil from refineries to cities to finding inexpensive diets capable of meeting the minimum daily requirements. In many of these problems, the numeral of variables and constraints are so big that it is not enough too simply to know there is solution; we require some way of finding it (or at least a close approximation to it) in a rational amount of time. We explain the types of problems Linear Programming can handle and show how we can solve them using the simple method. It is significant to examine the cost of linear how to do and solve Linear Programming problems, it is attractive to convert other problems to Linear Programming problems. While this will be a reasonable solution in many situations, there are additional techniques that are better able to handle many of these problems.

A. Ben-Tal and A. Nemirovski (2002). Robust optimization – Linear programming, Math. Program. Ser. B 92. D. P. Bertsekas (2007). Dynamic and Linear programming Control. Athena Scientific. D. P. de Farias and B. Van Roy (2006). A cost-shaping linear program for average-cost approximate dynamic programming with performance guarantees. Mathematics of Operations Research, 31. G. Calafiore and M. C. Campi (2005). Uncertain convex programs: randomized solutions and confidence levels. Mathematical Linear Programming, 102(1): pp. 25–46. H. R. Maei, Cs. Szepesvari, S. Bhatnagar, and R. S. Sutton (2010). Toward off-policy of Mathematics linear learning control with function approximation. In ICML. J. E. Marsden and A. Tromba (2003). Vector calculus, 5 ed., W. H. Freeman. M. C. Campi and S. Garatti (2008). The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3): pp. 1211–1230. M. H. Veatch (2013). Approximate linear programming for average cost mdps. Mathematics of Operations Research, 38 (3). M. Petrik and S. Zilberstein (2009). Constraint relaxation in approximate Mathematics of linear programs. In ICML. Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali (2004). Linear programming, Wiley-Interscience. R. S. Sutton, Cs. Szepesvari, and H. R. Maei (2009). A convergent ´O (n) algorithm for off-policy temporal-difference learning with linear function approximation. In NIPS. V. H. de la Pena, T. L. Lai, and Q-M. Shao (2009). Self-normalized processes: Limit theory and Statistical Applications. Springer. smoothed linear program. Operations Research, 60(3): pp. 655–674. Wayne L. Winston (2003). Operations Research: Applications and Algorithms of Mathematics. Duxbury Press, fourth edition. Y. Abbasi-Yadkori (2012). Linear programming Control Problems. PhD thesis, University of Alberta.