Nonlinear Programming 13 - Massachusetts Institute of ...

1 Nonlinear Programming13 Numerous mathematical- Programming applications, including many introduced in previous chapters, arecast naturally as linear programs. linear Programming assumptions or approximations may also lead toappropriate problem representations over the range of decision variables being considered. At other times,though, nonlinearities in the form of either Nonlinear objectivefunctions or Nonlinear constraints are crucialfor representing an application properly as a mathematical program. This chapter provides an initial steptoward coping with such nonlinearities, first by introducing several characteristics of Nonlinear programs andthen by treating problems that can be solved using simplex-like pivoting procedures.

2 As a consequence, thetechniques to be discussed are primarily algebra-based. The final two sections comment on some techniquesthat do not involve our discussion of Nonlinear Programming unfolds, the reader is urged to reflect upon the linear - Programming theory that we have developed previously, contrasting the two theories to understand why thenonlinear problems are intrinsically more difficult to solve. At the same time, we should try to understandthe similarities between the two theories, particularly since the Nonlinear results often are motivated by, andare direct extensions of, their linear analogs. The similarities will be particularly visible for the material ofthis chapter where simplex-like techniques Nonlinear Programming PROBLEMSA general optimization problem is to selectndecision variablesx1,x2.

3 ,xnfrom a given feasible regionin such a way as to optimize (minimize or maximize) a given objective functionf(x1,x2,..,xn)of the decision variables. The problem is called anonlinear Programming problem(NLP) if the objectivefunction is Nonlinear and/or thefeasible region is determined by Nonlinear constraints. Thus, in maximizationform, the general Nonlinear program is stated as:Maximizef(x1,x2,..,xn),subject to:g1(x1,x2,..,xn) b1,..gm(x1,x2,..,xn) bm,where each of the constraint functionsg1throughgmis given. A special case is the linear program that hasbeen treated previously. The obvious association for this case isf(x1,x2,..,xn)=n j=1cjxj, Programming Problems411andgi(x1,x2,..,xn)=n j=1ai jxj(i=1,2.)

4 ,m).Note that nonnegativity restrictions on variables can be included simply by appending the additional con-straints:gm+i(x1,x2,..,xn)= xi 0(i=1,2,..,n).Sometimes these constraints will be treated explicitly, just like any other problem constraints. At other times,it will be convenient to consider them implicitly in the same way that nonnegativity constraints are handledimplicitly in the simplex notational convenience, we usually letxdenote the vector ofndecision variablesx1,x2,..,xn that is,x=(x1,x2,..,xn) and write the problem more concisely asMaximizef(x),subject to:gi(x) bi(i=1,2,..,m).As in linear Programming , we are not restricted to this formulation. To minimizef(x), we can of coursemaximize f(x).

5 Equality constraintsh(x)=bcan be written as two inequality constraintsh(x) band h(x) b. In addition, if we introduce a slack variable, each inequality constraint is transformed to anequality constraint. Thus sometimes we will consider an alternative equality form:Maximizef(x),subject to:hi(x)=bi(i=1,2,..,m)xj 0(j=1,2,..,n).Usually the problem context suggests either an equality or inequality formulation (or a formulation with bothtypes of constraints), and we will not wish to force the problem into either following three simplified examples illustrate how Nonlinear programs can arise in SelectionAn investor has $5000 and two potential investments. Letxjforj=1 andj=2denote his allocation to investmentjin thousands of dollars.

6 From historical data, investments 1 and 2 havean expected annual return of 20 and 16 percent, respectively. Also, the total risk involved with investments 1and 2, as measured by the variance of total return, is given by 2x21+x22+(x1+x2)2, so that risk increases withtotal investment and with the amount of each individual investment. The investor would like to maximize hisexpected return and at the same time minimize his risk. Clearly, both of these objectives cannot, in general, besatisfied simultaneously. There are several possible approaches. For example, he can minimize risk subjectto a constraint imposing a lower bound on expected return. Alternatively, expected return and risk can becombined in an objective function, to give the model:Maximizef(x)=20x1+16x2 [2x21+x22+(x1+x2)2],subject to:g1(x)=x1+x2 5,x1 0,x2 0,(that is,g2(x)= x1,g3(x)= x2).

7 The nonnegative constant reflects his tradeoff between risk and return. If =0, the model is a linearprogram, and he will invest completely in the investment with greatest expected return. For very large , theobjective contribution due to expected return becomes negligible and he is essentially minimizing his Resources PlanningIn regional water planning, sources emitting pollutants might be required toremove waste from the water system. Letxjbe the pounds of Biological Oxygen Demand (an often-usedmeasure of pollution) to be removed at model might be to minimize total costs to the region to meet specified pollution standards:Minimizen j=1fj(xj),subject to:n j=1ai jxj bi(i=1,2,..,m)0 xj uj(j=1,2.)

8 ,n),wherefj(xj)=Cost of removingxjpounds of Biological Oxygen Demand atsourcej,bi=Minimum desired improvement in water quality at pointiin thesystem,ai j=Quality response, at pointiin the water system, caused by removingone pound of Biological Oxygen Demand at sourcej,uj=Maximum pounds of Biological Oxygen Demand that can beremoved at RegressionA university wishes to assess the job placements of its graduates. For simplicity,it assumes that each graduate accepts either a government, industrial, or academic position. LetNj=Number of graduates in yearj(j=1,2,..,n),and letGj,Ij,andAjdenote the number entering government, industry, and academia, respectively, in yearj(Gj+Ij+Aj=Nj).One model being considered assumes that a given fraction of the student population joins each jobcategory each year.

9 If these fractions are denoted as 1, 2, and 3, then the predicted number entering thejob categories in yearjis given by the expressions Gj= 1Nj, Ij= 2Nj, Aj= reasonable performance measure of the model s validity might be the difference between the actual numberof graduatesGj,Ij, andAjentering the three job categories and the predicted numbers Gj, Ij, and Aj, asin the least-squares estimate:Minimizen j=1[(Gj Gj)2+(Ij Ij)2+(Aj Aj)2],subject to the constraint that all graduates are employed in one of the professions. In terms of the fractionsentering each profession, the model can be written as:Minimizen j=1[(Gj 1Nj)2+(Ij 2Nj)2+(Aj 3Nj)2], vs. Global optimum413subject to: 1+ 2+ 3=1, 1 0, 2 0, 3 is a Nonlinear program in three variables 1, 2, and are alternative ways to approach this problem.

10 For example, the objective function can be changedto:Minimizen j=1[ Gj Gj|+|Ij Ij|+|Aj Aj ]. This formulation is appealing since the problem now can be transformed into a linear program. Exercise 28(see also Exercise 20) from Chapter 1 illustrates this range of Nonlinear - Programming applications is practically unlimited. For example, it is usually simpleto give a Nonlinear extension to any linear program. Moreover, the constraintx=0 or 1 can be modeledasx(1 x)=0 and the constraintxinteger as sin( x)=0. Consequently,in theoryany application ofinteger Programming can be modeled as a Nonlinear program. We should not be overly optimistic about theseformulations, however; later we shall explain why Nonlinear Programming is not attractive for solving LOCAL vs.