Heath - Scientific Computing (523150), страница 56
Текст из файла (страница 56)
6.7. The necessary condition for optimality requires thatthe negative gradient of the objective function line up with the gradient of the constraint,and that the point lie on the line x1 − x2 = 1. The only point satisfying both requirementsis the solution we computed, indicated by a bullet in the diagram.1.0contours of 0.5x21 + 2.5x22−1.5constraint x1 − x2 = 1................................................................................................................................................................................ .............................................................................................. .........................................................................................................................................................................................................................................................
........................................ ...................................................................................................................................................................... ............................................................................................................... .................................... .. ....
...................................... ............................................................................................... ........ ........... .............. ............................................ ............ ............................................... ............. ...........................................................................................................................................
.. ........................................... ...................................................... ...... ......... . .....................................................................................................................................................................................................................................................................................................................................................................................................•−1.0Figure 6.7: Solution to constrained optimization problem.1.56.5. CONSTRAINED OPTIMIZATION6.5.1205Linear ProgrammingOne of the most important and commonly occurring constrained optimization problems islinear programming.
One standard form for such problems ismin f (x) = cT xxsubject to Ax = b and x ≥ o,where c is an n-vector, A is an m × n matrix, m < n, and b is an m-vector.The feasible region for such a problem is a convex polyhedron in n-dimensional space,and the minimum must occur at one of its vertices. The standard method for solving linearprogramming problems, called the simplex method , systematically examines a sequence ofvertices to find the one yielding the minimum.A detailed description of the simplex method is beyond the scope of this book; but themain procedures, sketched here, make use of a number of tools we have already seen.
Phase1 of the simplex method is to find a vertex of the feasible region. A vertex of the feasibleregion is a point where all of the constraints are satisfied, and n − m of the inequalityconstraints are binding (i.e., xi = 0). If we choose any subset of n − m variables, callednonbasic variables, and set them to zero, then we can use the equality constraints to solvefor the m remaining basic variables. If the resulting values for the basic variables arenonnegative, then we have found a feasible vertex.
Otherwise, we must choose a differentset of nonbasic variables and try again. There are systematic procedures, which involveadding new artificial variables and constraints, to ensure that a feasible vertex is foundrapidly and efficiently.Phase 2 of the simplex method moves systematically from vertex to vertex until theminimum point is found. Starting from the feasible vertex found in Phase 1, a neighboringvertex that has a smaller value for the objective function is selected.
The specific newvertex chosen is obtained by exchanging one of the current nonbasic variables for the basicvariable that produces the greatest reduction in the value of the objective function, subjectto remaining feasible. This process is then repeated until no vertex has a lower functionvalue than the current point, which must therefore be optimal.The linear system solutions required at each step of the simplex method use matrixfactorization and updating techniques similar to those in Chapter 2.
In particular, much ofthe efficiency of the method depends on updating the factorization at each step as variablesare added or deleted one at a time.In this brief sketch of the simplex method, we have glossed over many details, such asthe various degeneracies that can arise, the detection of infeasible or unbounded problems,the updating of the factorization, and the optimality test. Suffice it to say that all of thesecan be addressed effectively, so that the method is very reliable and efficient in practice,able to solve problems having thousands of variables and constraints.The efficiency of the simplex method in practice is somewhat surprising, since the number of vertices that must potentially be examined is n!n=,mm! (n − m)!which is enormous for problems of realistic size. Yet in practice, the number of iterationsrequired is usually only a small multiple of the number of constraints m, essentially inde-206CHAPTER 6. OPTIMIZATIONpendent of the number of variables n (the value of n affects the cost per iteration, but notthe number of iterations).Although the simplex method is extremely effective in practice, in theory it can require in the worst case a solution time that is exponential in the size of the problem, andthere are contrived examples for which such behavior actually occurs.
In recent years, newmethods for linear programming have been developed, such as those of Khachiyan and ofKarmarkar, whose worst-case solution time is polynomial in the size of the problem. Thesemethods move through the interior of the feasible region, not restricting themselves to investigating only its vertices.
Although interior point methods are having significant practicalimpact, the simplex method is still the predominant method in standard packages for linearprogramming, and its effectiveness in practice is excellent.Example 6.11 Linear Programming. To illustrate linear programming we consider agraphical solution of the problemmin f (x) = cT x = −8x1 − 11x2xsubject to the linear inequality constraints5x1 + 4x2 ≤ 40,−x1 + 3x2 ≤ 12,x1 ≥ 0,x2 ≥ 0.The feasible region, which is bounded by the coordinate axes and the other two straight lines,is shaded in Fig.
6.8. Contour lines of the objective function are drawn, with correspondingvalues of the objective function shown along the bottom of the graph. The minimum valuenecessarily occurs at one of the vertices of the feasible region, in this case the point x1 = 3.79,x2 = 5.26, where the objective function has the value −88.2.x2..........................................................2.... 1....................................................................................................... ......................
............................. .............................. ............................. ..............................12................................................................................................................................ .......................... . ........................... . . . . . . . .......................... .
. . . . ... .................................... . . . ................. . . . . . . . ............................. ..... . . . . . ...... . . . . . .. ................ . ................. . . . . . . . . . ................ . . . . . . ........ ..................... . . .
........... . . . . . . . . . . . .......... . . . . . . ................................ . .. . .. . .. . ................... . .. . .. . .. . .. . .................. . .. . .. ....................... . . . . . ........ . . . . . . ....... . . ................... . . . . . ....... . . . . . ....... .
..................... . . . . . . . . . . . ......... . . . . . . . . . . ........... . . ............. . ............. . . . . . . . . . . .............. . . . . . . . . . ............. . ....................... . . . . ............. . . . . . . . . . .............. . . . . .
. . . . . ............. ......................... . . . . . . . ........... . . . . . . . . . ......... . . . . . . . . . . . ........... ...................... . . . . . . . . . . ........... . . . . . . . . ............ . . . . . . . . . . . .................................... . . .
. . . . . . . . . . ............. . . . . . . . . . ............ . . . . . . . . . . ........................... . . . . . . . . ......... . . . . . ......... . . . . . .......................................................................... ..............1........................................ ......................................... .............................5x + 4x = 40−x + 3x = 12x0−27−46−66−88.2Figure 6.8: Linear programming problem from Example 6.11.6.6.
SOFTWARE FOR OPTIMIZATION6.6207Software for OptimizationTable 6.1 is a list of some of the software available for solving one-dimensional and unconstrained optimization problems. In the multidimensional case, we distinguish betweenroutines that do or do not require the user to supply derivatives for the functions, althoughin some cases the routines mentioned offer both options.Table 6.1: Software for one-dimensional and unconstrained optimizationOne-dimensionalMultidimensionalSourceNo derivativesNo derivativesDerivativesBrent [23]localminpraxisFMMfminHSLvd01/vd04va04/va08/va09 va06/va10/va13IMSLuvmifuminfumiahKMNfminuncminMATLABfminfminsNAGe04abfe04jafe04lafNAPACKcgNRbrentpowelldfpminNUMALmininpraxisflemin/rnk1minPORTmnfmngSchnabel et al.
[220]uncminuncminTOMSmini(#500)TOMSsmsno(#611)sumsl(#611)TOMSbbvscg(#630)bbvscg(#630)TOMStnpack(#702)TOMStensor(#739)tensor(#739)Software for minimizing a function f (x) typically requires the user to supply the nameof a routine that computes the value of the function f for any given value of x. The usermust also supply absolute or relative error tolerances that are used in the stopping criterionfor the iterative solution process. Additional input for one-dimensional problems usuallyincludes the endpoints of an interval in which the function is unimodal. (If the function isnot unimodal, then the routine often will still find a local minimum, but it may not be theglobal minimum on the interval.) Additional input for multidimensional problems includesthe dimension of the problem and a starting guess for the solution, and may also include thename of a routine for computing the gradient (and possibly the Hessian) of the function andthe name of an array to be used as workspace for storing the Hessian or an approximationto it.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
