Lecture notes Linear Programming

how linear programming helps in decision making and what is linear programming and how is it used in the real world pdf free downlaod
ImogenCameron Profile Pic
ImogenCameron,France,Teacher
Published Date:14-07-2017
Your Website URL(Optional)
Comment
Institute of Applied Mathematics Middle East Technical University LECTURE NOTES SERIES 1 NUMERICAL OPTIMIZATION Constrained Optimization Bülent Karasözen Gerhard-Wilhelm Weber Design & Layout:Ömür UgurPreface These are lecture notes o ered to the students of the course Numerical Op- timization at the Institute of Applied Mathematics (IAM) of Middle East Technical University (METU) in Summer Semester 2003. In these months, this course was held for the rst time at our new and for Turkey pioneering institute which was founded in Autumn 2002. There has been the institute teacher's conviction that optimization theory is an important key technology in many modern elds of application from science, engineering, operational research and economy and, forthcoming, even in social sciences. To be more precise, these lecture notes are prepared on the course's sec- ond part which treated the case of constrained continuous optimization from the numerical viewpoint. Here, we pay attention to both the cases of lin- ear and nonlinear optimization (or: programming). In future, extensions of these notes are considered, especially in direction of unconstrained optimiza- tion. Herewith, our lecture notes are much more a service for the students than a complete book. They essentially are a selection and a composition of three textbooks' elaborations: There are the works \Lineare und Netzwerkop- timierung. Linear and Network Optimization. Ein bilinguales Lehrbuch" by H. Hamacher and K. Klamroth (2000) used in the parts about linear pro- gramming, \Linear and Nonlinear Programming" by S.G. Nash and A. Sofer (1996) and \Numerical Optimization" by J. Nocedal and S.J. Wright (1999) used for the parts about foundations and nonlinear programming. During Summer Semester 2003, these lecture notes were given to the students in the handwritten form of a manuscript. We express our deep  gratitude to Dr. Omur  U gur from IAM of METU for having prepared this A LT X-typed version with so much care and devotion. Indeed, we are looking E forward that in future many of students of IAM will really enjoy these notes and bene t from them a lot. Moreover, we thank the scienti c and institu- tional partners of IAM very much for the nancial support which has made the lecture notes in the present form possible. With friendly regards and best wishes, Bulen  t Karas ozen and Gerhard-Wilhelm Weber, Ankara, in October 2003iiContents 1 Introduction 1 1.1 Some Preparations . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Linear Programming: Foundations and Simplex Method 9 3 Linear Programming: Interior-Point Methods 31 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Primal-Dual Methods . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 A Practical Primal-Dual Algorithm . . . . . . . . . . . . . . . 40 4 Nonlinear Programming: Feasible-Point Methods 45 4.1 Linear Equality Constraints . . . . . . . . . . . . . . . . . . . 45 4.2 Computing the Lagrange Multipliers  . . . . . . . . . . . . . 52 4.3 Linear Inequality Constraints . . . . . . . . . . . . . . . . . . 57 4.4 Sequential Quadratic Programming . . . . . . . . . . . . . . . 67 4.5 Reduced-Gradient Methods . . . . . . . . . . . . . . . . . . . 74 5 Nonlinear Programming: Penalty and Barrier Methods 81 5.1 Classical Penalty and Barrier Methods . . . . . . . . . . . . . 82iv CONTENTSList of Tables 2.1 Chocolate production. . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Corner points and values. . . . . . . . . . . . . . . . . . . . . 12 4.1 SQP method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 Reduced-gradient method. . . . . . . . . . . . . . . . . . . . . 78 5.1 Barrier function minimizers. . . . . . . . . . . . . . . . . . . . 87vi LIST OF TABLESList of Figures 2.1 Simplex algorithm, feasible region. . . . . . . . . . . . . . . . . 11 2.2 Simplex algorithm. . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Feasible region. . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Basis change. . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1 Central path, projected intox-space, showing a typical neigh- bourhoodN. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Iterates of Algorithm IPM2 plotted in (x;s)-space. . . . . . . . 40 3.3 Central pathC, and a trajectoryH from the current (noncen- tral) point (x;y;s) to the solution set . . . . . . . . . . . . . 41 4.1 Sequence of movements in an active-set method. . . . . . . . . 61 4.2 Illustration of active-set algorithm. . . . . . . . . . . . . . . . 66 4.3 Zigzagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.1 E ect of barrier term. . . . . . . . . . . . . . . . . . . . . . . 84 5.2 Contours of the logarithmic barrier function. . . . . . . . . . . 90viii LIST OF FIGURESChapter 1 Introduction In this chapter with its various aspects of consideration, we take into account constraints additionally to our problem of minimizing an objective function f. Actually, we become concerned with the problem 8 minimize f(x) subject to (P) h (x) = 0 8i2I :=f1; 2;:::;mg; i : g (x) 0 8j2J :=f1; 2;:::;sg: j n Here,f;h andg are supposed to be smooth real-valued function on R . By i j smooth, we usually think of being one- or two-times continuously di eren- tiable. The rst group of constraints, where we demand ::: = 0, are called equality constraints. The second group of constraints, where we ask ::: 0, are called inequality constraints. Denoting the feasible set, where we restrict the objective function f on, by  n M := x 2 R h (x) = 0 (i2I); g (x) 0 (j2J) ; i j our constrained optimization problem can be written as follows: (P) minimize f(x) subject to x2M or equivalently, (P) minf(x): x2M2 CHAPTER 1. INTRODUCTION Depending on the context, namely on the various assumptions onf;h;g;I and J we make, we shall sometimes denote the functions, the problem and its feasible set a bit di erently or speci c. For example, this will be the case when f;h;g are linear (to be more precise: linearly ane). In fact, we are going to distinguish the linear and the nonlinear case, speak about linear optimization and nonlinear optimization. As in our course, the practical character and aspect of optimization is more emphasized than the analytical or topological ones, we also talk about (non-)linear programming. This may remind us of both the motivation of optimization by concrete applications, and the numerical solution algorithms. Because of the priority we gave to the numerical-algorithmical aspect, we make the following introductory Section not so long. 1.1 Some Preparations By the following de nition we extend corresponding notions from uncon- strained optimization almost straightforwardly:  n De nition 1.1. Let a vector (or, point) x 2 R be given.   (i) We call x a local solution of (P), if x 2M and there is a neighbour-   hoodN(x ) of x such that   f(x )f(x) 8x2M\N(x ):   (ii) We call x a strict local solution of (P), x 2 M and there is a neigh-   bourhoodN(x ) of x such that     f(x )f(x) 8x2 M\N(x ) nfx g:   (iii) We call x an isolated local solution of (P), x 2 M and there is a    neighbourhood N(x ) of x such that x is the only local solution of  (P) in M\N(x ). Sometimes, we also say (strict or isolated) local minimizer for a (strict or local) local solution. Do you understand and geometrically distinguish these three conditions? We shall deepen our understanding in the exercises and in the following sections.1.1. SOME PREPARATIONS 3 Example 1.1. Let us consider the problem   minimize f(x) := x +x 1 2  (P) 2 2 2 2 subject to x +x 2 = 0 i.e., h(x) :=x +x 2 ; 1 2 1 2 Here,jIj =f1g (h =h) and J =;. We see by inspection that the feasible 1 p set M is the circle of radius 2 centered at the origin (just the boundary  of the corresponding disc, not its interior). The solution x is obviously T (1;1) , this is the global solution of (P): From any other point on the circle, it is easy to nd a way to move that stays feasible (i.e., remains on the p T circle) while decreasingf. For instance, from the point ( 2; 0) any move in the clockwise direction around the circle has the desired e ect. Would you please illustrate this and the following graphically? Indeed, we see that at    x , the gradientrh(x ) is parallel to the gradientrf(x ):   1    ( = ) rf(x ) = rh(x ) 1 1   where  = = . 1 2  The condition found in the previous example to be necessary for a (local) minimizer (or, local minimum) can be expressed as follows:   r L(x ; ) = 0; x n m where L : R  R R is de ned by L(x;) := f(x)h(x) and called   the Lagrange function. The value is called the Lagrange multiplier (atx ). This Lagrange multiplier rule is a rst-order necessary optimality condition 1 (NOC) which can be extended to cases where I is of some other cardi- nality m  n. in fact, provided that the Linear Independence Constraint  Quali cation (a regularity condition) holds at x , saying that the gradients    rh (x );rh (x );:::;rh (x ); 1 2 m regarded as a family (i.e., counted by multiplicity), are linearly independent,    then there exist so-called Lagrange multipliers  ; ;:::; such that 1 2 m m X    rf(x ) =  rh(x ): i i=1 1 In the next sections, we also consider feasibility to be a part of it.4 CHAPTER 1. INTRODUCTION The latter equation is just   r L(x ; ) = 0; x n m where L : R  R R is the so-called Lagrange function L(x;) := T T T f(x) h(x), with  := ( ; ;:::; ) and h := (h ;h ;:::;h ) . 1 2 m 1 2 m Next, we slightly modify Example 1.1. We replace the equality constraint by an inequality. Example 1.2. Let us consider the problem   minimize f(x) := x +x 1 2  (P) 2 2 2 2 subject to 2x x  0 i.e., g(x) := 2x x ; 1 2 1 2 here, I = ; and jJj = 1 (g = g ). The feasible set consists of the cir- 1 cle considered in Example 1.1 and its interior. We note that the gradient T rg(x) = (2x ;2x ) points from the circle in direction of the interior. 1 2 p p T T For example, inserting the point x = ( 2; 0) gives rg(x) = (2 2; 0) , pointing in the direction of the negative x axis, i.e., inwardly (regarded 1  T fromx). By inspection, we see that the solution of (P) is stillx = (1;1) , and we have now   rf(x ) = rg(x); 1   where  = =  0. 1 2 Again, we can write our necessary equation by using a Lagrange function, namely, L(x;) :=f(x)g(x):    r L(x ; ) = 0; where   0: x Again, our necessary optimality condition can be generalized by admitting another nite cardinalitys ofJ, andm =jIj possibly to be positive (mn). For this purpose, we need a regularity condition (constraint quali cation) at  our local minimizer x , once again. In the presence of both equality and inequality constraints, we can again formulate LICQ. For this purpose, we introduce the set of active inequality constraints at some feasible point x:  J (x) := j2J g (x) = 0 : 0 j  Then, LICQ at x means the linear independence of the vectors (together regarded as a family)1.1. SOME PREPARATIONS 5     rh (x ) (i2I); rg (x ) j2J (x ) i j 0 (so that the gradients of the active inequalities are taken into account to the gradients of the equality constraints, additionally). Another famous regular- ity condition is somewhat weaker than LICQ and called MFCQ (Mangasarian- Fromovitz Constraint Quali cation). The geometrical meaning of MFCQ is the following: At each point ofM we have an inwardly pointing direction (rel- ative to the surface given by the zero set ofh). In the sequel, we refer to LICQ for simplicity. Now, our rst-order necessary optimality conditions (NOC)    T are called Karush-Kuhn-Tucker conditions: There exist  = ( ;:::; ) 1 m    and  =  such that j  j2J (x ) 0 8 m X X      rf(x ) =  rh (x ) +  rg (x ); i j i j  i=1 j2J (x ) 0 :     0 8j2J (x ): 0 j   The second ones of the Lagrange multipliers, namely  (j2J (x )), neces- 0 j sarily are nonnegative. Here, we may interpret this as by the existence of (rel- atively) inwardly pointing direction along which f does not decrease, when  starting from our local minimizer x . Let us summarize our consideration T T by referring to the Lagrange function L(x;;) :=f(x) h(x) g(x),    where  is lled up by additional parameters  (j 62 J (x )) (at  j 0 j j2J (x ) 0    x =x , we have  = 0;j62J (x )). 0 j  Theorem 1.1. Suppose that x is a local solution of (P), and that LICQ   holds at x . Then, there uniquely exist Lagrange multiplier vectors  2 m  s R ; 2 R , such that the following conditions are satis ed: 8    r L(x ; ; ) = 0; x  h(x ) = 0;  (NOC) g(x )  0;    0; :    g (x ) = 08j2J: j j The latter multiplicative conditions are local complementarity conditions. To which case study do they give rise? Proof. See Nocedal, Wright (1999); the proof of uniqueness is left to the reader. 6 CHAPTER 1. INTRODUCTION Often, the compact form of (NOC), where we do not explicitly refer to  the active inequalitiesj2J (x ), is more convenient. In other times, a direct 0  reference to J (x ) is better for us. We note that our rst-order necessary 0 optimality conditions are not the only ones. In the subsequent sections and in the presentation given in lectures, we shall brie y indicate them sometimes. These conditions are, more or less, generalization of the condition (taught to us in the unconstrained case) that the gradient vanishes at a local solution:  rf(x ) = 0, if I = J = ;. Provided that all the de ning functions are twice continuously di erentiable, then we know the second-order optimality condition saying that the Hessian matrix has to be positive semi-de nite: T 2  n  r f(x ) 0 82 R : xx But how does this condition look like in our case of constrained optimization?  Let us de ne the tangent space of M at x as follows:  n T  T   T  := 2 R r h (x ) = 08i2I; r g (x ) = 08j2J (x ) : x i j 0 Then, our second-order condition states that the Hessian of the Lagrange   function L at x is positive semi-de nite over T . Here, we take the vectors x n 2 R for left- or right-multiplication from T . This can also be expressed x as the positive semi-de niteness of this Hessian, when rstly left- and right- T n multiplied byB andB, respectively, over R . Here,B is any matrix whose  columns constitute a basis of the linear space T . Herewith, we can express x  our second-order optimality condition so, where nb =nmb, mb =jJ (x )j: 0 T T 2    n b (NOC)  B r L(x ; ; )B  0 8 2 R : s:o: xx In literature, we also nd some re ned condition, where in the statement  of positive-de niteness the reference space T  is replaced by the set C  x x  which is a (tangent) cone. Namely,C  comes from substituting the gradient x conditions on the active inequalities by T    r g (x ) = 0 8j2J (x ) with  0; j 0 j T    r g (x ) 0 8j2J (x ) with  = 0: j 0 j1.1. SOME PREPARATIONS 7  Theorem 1.2. Suppose that x is a local solution of (P), and that LICQ    is satis ed at x . Let  and  be the corresponding Lagrange multiplier vectors so that (NOC) is (necessarily) ful lled. 2    Then, the Hessian r L(x ; ; ) is positive semi-de nite over T , or x xx  (re ned version) over C . x Proof. See, e.g., Nash, Sofer (1996) and Nocedal, Wright (1999).  This theorem plays an important role for detecting that some found or   submitted stationary point x (i.e., x ful lls our rst-order necessary opti- mality conditions) is not a local solution, but a local minimizer or a saddle point. How can we use Theorem 1.2 for this purpose? A saddle point is in between of a local minimizer and a local maximizer: there are feasible direc- tions of both an increasing and a decreasing behaviour off. But how can we detect that a stationary point, i.e., a candidate for being a local minimizer really is such a one? what we know from the unconstrained case gives rise to   assume that we should turn from positive semi-de niteness (overT orC ) x x  to positive de niteness (over T nf0g or C nf0g). In fact, by this sharp-  x x ening of (NOC) we obtain a condition which together with our rst-order s:o:  (NOC) is sucient forx to become a local solution. In particular, we arrive at T T 2    n b (SOC)  B r L(x ; ; )B 0 8 2 R nf0g: s:o: xx We state the following theorem on second-order sucient optimality condi- tions:  Theorem 1.3. Suppose that for some pointx 2M there are Lagrange mul-   tiplier vectors ; such that the conditions (NOC) (of rst-order) are satis-   2    ed and  0 (j2J (x )). Suppose also that the Hessianr L(x ; ; ) 0 j xx   is positive de nite over T , or over C (i.e., over T nf0g, or C nf0g).   x x x x  Then, x is a strict local solution for (P). Proof. See, e.g., Nash, Sofer (1996) and Nocedal, Wright (1999).  In our exercises, we shall consider a few examples on nding local or global solutions for nonlinear optimization problem, where the utilization of numerical-algorithmical methods is still not necessary. Let us also conclude our Section 1.1 with another such example. Example 1.3. Let us consider the problem (P) from Example 1.2:8 CHAPTER 1. INTRODUCTION   minimize f(x) := x +x 1 2  (P) 2 2 2 2 subject to 2x x  0 i.e., g(x) := 2x x : 1 2 1 2 We want to check the second-order conditions. The Lagrangian is L(x;) := (x +x )(2x x ); 1 2 1 2 and it is easy to show that the Karush-Kuhn-Tucker conditions (NOC) are  T  1 satis ed by x = (1;1) , with  = . The Hessian ofL (with respect to 2 x) is      2 0 1 0 2   r L(x ; ) = = : xx  0 2 0 1 T 2   This matrix is positive de nite, i.e., it satis es  r L(x ; ) 0 for all xx n    2 R nf0g (in particular, for all elements of T ;C , except 0). So, it  x x certainly satis es the conditions of Theorem 1.3.  T We conclude thatx = (1;1) is a strict local solution for (P). Let us  remark thatx is a even a global solution, since (P) is a convex programming problem.  In this course, we do not pay much attention to stability aspects which, however, can be well analyzed by LICQ and (SOC) . Next, we concentrate s:o of the linear case of (P).Chapter 2 Linear Programming: Foundations and Simplex Method In this chapter, based on the book of Hamacher, Klamroth (2000), we con- sider easy examples which lead to optimization (\programming") problems: Linear programs play a central role in modelling of optimization problems. Example 2.1. The manufacturer \Chocolate & Co." is in the process of reorganizing its production. Several chocolate products which have been produced up to now are taken out o production and are replaced by two new products. The rst product P1 is ne cocoa, and the second one P2 is dark chocolate. The company uses three production facilities F1, F2, and F3 for the production of the two products. In the central facility F1 the cocoa beans are cleaned, roasted and cracked. In F2, the ne cocoa and in F3 the dark chocolate are produced from the preprocessed cocoa beans. Since the chocolate products of the company are known for their high quality, it can be assumed that the complete output of the company can be sold on the market. The pro t per sold production unit of P1 (50kg of cocoa) is 3 (¤), whereas it is 5 per sold production unit of P2 (100kg of chocolate). However, the capacities of F1F3 are limited as speci ed in Table 2.1. (For example, the row corresponding to F1 implies that the per unit P1 and P2, 3% and 2%, respectively, of the daily capacity of production facility F1 are needed, and that 18% of the daily capacity of F1 is available for the production of P1 and P2.) The problem to be solved is to nd out how many units x of products 1 P1 and x of product P2 should be produced per day in order to maximize 2CHAPTER 2. LINEAR PROGRAMMING: FOUNDATIONS AND 10 SIMPLEX METHOD P1 P2 available capacity (in % of the daily capacity) F1 3 2 18 F2 1 0 4 F3 0 2 12 Table 2.1: Chocolate production. the pro t (while satisfying the capacity constraints.) This problem can be formulated as a linear program (LP): 8 T maximize 3x + 5x =:c x 1 2 subject to the constraints 3x + 2x  18 (I) 1 2 (LP) x  4 (II) 1 2x  12 (III) 2 : x ; x  0 (IV), (V) 1 2 T The functionc x is the (linear) objective function of the LP. The constraints are partitioned into functional constraints ((I)(III)) and nonnegativity con- straints ((IV),(V)). Each x which satis es all the constraints, is called a fea- T sible solution of the LP and c x is its objective (function) value. Instead of maximizing the function, it is often minimized. In this case, the coecients c of the objective function can be interpreted as unit costs. The functional i constraints can also be equations (\=") or inequalities with \". Let us continue by introducing a graphical procedure for the solution of (LP). In a rst step, we draw the set of feasible solutions (the feasible region P) of (LP), that is the set of all points (vectors) (x ;x ), in matrix notation: 1 2   x 1 , satisfying all the constraints; see Figure 2.1. x 2 i i If Axb is one of the constraints (e.g., A = (3; 2); b = 18) we draw the i 1 line corresponding to the equation i Ax =b: i 2 This space separates the space R into two half-spaces i i Axb; and Axb i i i The set P of feasible solutions is a subset of the half-space Ax  b . We i obtain P by taking the intersection of all these half-spaces including the half-11 Figure 2.1: Simplex algorithm, feasible region. 2 spaces x  0 and x  0. A set of points in R , which is obtained in such a 1 2 way is called a convex polyhedron. T In a second step, we draw the objective function z := c x = 3x + 5x . 1 2 For any given value of z we obtain a line, and for any two di erent values of z we obtain two parallel lines for which z is as large as possible. The following Figure 2.2 shows the feasible region P and, additionally, the line corresponding to the objective function 3x +5x , i.e., the line corresponding 1 2 to the objective valuez = 15. The arrow perpendicular to this line indicates, in which direction the line should be shifted in order to increase z. Figure 2.2: Simplex algorithm. T The intersection of any line c x = z with P in some x2 P corresponds   x 1 to a feasible solution x = with objective value z. Hence, in order to x 2 maximize the objective function, the line is shifted parallel as far as possible without violating the condition

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.