资源描述
,Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,Chapter 8 The Maximum Principle: Discrete Time,8.1 Nonlinear Programming Problems,We begin by starting a general form of a nonlinear,programming problem.,y,: be an,n,-component column vector,a,: be an,r,-component column vector,b,: be an,s,-component column vector.,h: E,n,E,1,g:,E,n,E,r,w: E,n,E,s,be given functions,.,We assume functions,g,and,w,to be column vectors,with components,r,and,s, respectively. We consider,the nonlinear programming problem:,subject to,8.1.1 Lagrange Multipliers,Suppose we want to solve (8.1) without imposing,constraint (8.2) or (8.3). The problem is now the,classical unconstrained maximization problem of,calculus, and the first-order necessary conditions for,its solution are,The points satisfying (8.4) are called,critical points.,With equality constraints, the,Lagrangian,is,where,is an,r-,component row vector,.,The necessary condition for,y,* to be a (maximum),solution to be (8.1) and (8.2) is that there exists an,r,- component row vector,such that,Suppose (,y*,*,),is a solution of (8.6) and (8.7). Note that,y*,depends on,a,i.e.,y*=y*(a).,Now,is the optimum value of the objective function. The Lagrange multipliers satisfy the relation,which means that,*,i,is the negative of the imputed value of the unit of,a,i,.,Example 8.1,Consider the problem:,Solution.,From the first two equations we get,solving this with the last equation yields the quantities,8.1.2 Inequality Constraints,Note that,(8.10) is analogous to (8.6). Also (8.11),repeats the inequality constraint (8.3) in the same,way that (8.7) repeated the equality constraint (8.2).,However, the conditions in (8.12) are new and are,particular to the inequality-constrained problem.,Example 8.2,Solution.,We form the Lagrangian,The necessary conditions (8.10)-(8.12) become,Case 1:,From (8.13) we get,x,= 4, which also satisfies (8.14).,Hence, this solution, which makes,h,(4)=16, is a,possible candidate for the maximum solution.,Case 2:,Here from (8.13) we get,= - 4, which does not satisfy,the inequality, 0 in (8.15).,From these two cases we conclude that the optimum,solution is,x* =,4 and,Example 8.3,solve the problem:,Solution.,The Lagrangian is,The necessary conditions are,Case 1:, =,0,From (8.16) we obtain,x,= 4 , which does not satisfy,(8.17), thus, infeasible.,Case 2:,x,=6,(8.17) holds. From (8.16) we get, =,4, so that (8.18),holds. The optimal solution is then,since it is the only solution satisfying the necessary,conditions.,Example 8.4,Find the shortest distance between the,point (2.2) and the upper half of the semicircle of,radius one, whose center is at the origin. In order to,simplify the calculation, we minimize,h, the square of,the distance:,The Lagrangian function for this problem is,The necessary conditions are,From (8.24) we see that either,=0 or,x,2,+y,2,=1,i.e., we,are on the boundary of the semicircle. If,=0, we see,from (8.20) that,x,=2. But,x,=2 does not satisfy (8.22) for,any,y, and hence we conclude,0,and,x,2,+y,2,=1.,Figure 8.1 Shortest Distance from a Point to a Semi-Circle,From (8.25) we conclude that either or,y,=0. If, then from (8.20), (8.21) and,0, we get,x = y,. Solving the latter with,x,2,+y,2,=1 , gives,If,y,=0, then solving with,x,2,+y,2,=1,gives,These three points are shown in figure 8.1. Of the,three points found that satisfy the necessary,conditions, clearly the point found in (,a,) is,the nearest point and solves the closest-point,problem. The point (-1,0) in (,c,) is in fact the farthest,point; and the point (1,0) in (,b,) is neither the closest,nor the farthest point.,Example 8.5,Consider the problem:,subject to,The set of points satisfying the constraints is shown,shaded in figure 8.2. From the figure it is obvious that,the solution point (0,1) maximizes the value of,y,. Let,us see if we can find it using the above procedure.,Figure 8.2: Graph of Example 8.5,The Lagrangian is,The necessary conditions are,together with (8.27) and (8.28). From (8.30) we get,=0, since,x,-1/3,is never 0 in the range -1,x, 1. But,substitution of,=0 into (8.31) gives,= - 1 0, which,fails to solve (8.33).,Example 8.6,Consider the problem:,subject to,The constraints are now differentiable, and the,optimum solution is (,x*,y*)=(,0,1) and,h*=,1. But once,again the Kuhn-Tucker method fails, as we will see.,The Lagrangian is,so that the necessary conditions are,together with (8.35) and (8.36). From (8.41) we get,either,y =,0,or,=,0. Since,y,=0 minimizes the objective,function, we choose, =,0. From (8.38) we get either,=0 or,x,=0. Since substitution of,=, =,0 into (8.39),shows that it is unsolvable, we choose,x,=0, ,0. But,then (8.40) gives (1-,y,),3,= 0 or,y,=1. However, =,0,and,y,=1 means that once more there is no solution to,(8.39).,The reason for failure of the method in Example 8.6 is,that the constraints do not satisfy what is called the,constraint qualification, which will be discussed in the,next section.,In order to motivate the definition we illustrate two,different situation in figure 8.3. In figure 8.3(a) we,show two boundary curves and,intersecting the boundary point . The two tangents,to these curves are shown, and,is a vector lying,between the two tangents. Starting at , there is a,differentiable curve drawn so that it lies,entirely within the feasible set,Y,such that its initial,slope is equal to,.,Figure 8.3: Kuhn-Tucker Constraint Qualifications,Whenever such a curve can be drawn from every,boundary point in,Y,and every,contained between,the tangent lines, we say that the constraints defining,Y,satisfy the,Kuhn-Tucker constraint qualification,.,Figure 8.3(b) illustrates a case of a cusp at which the,constraint qualification does not hold. Here the two,tangents to the graphs and coincide,so that,1,and,2,are vectors lying between these two,tangents. Notice that for vector,1, it is possible to find,the differentiable curve satisfying the above,condition, but for vector,2,no such,curve exists.,Hence, the constraint qualification does not hold for,the example in figure 8.3(b).,8.1.3 Theorems from Nonlinear Programming,We first state the constraint qualification symbolically.,For the problem defined by (8.1), (8.2), and (8.3), let,Y,be the set of all feasible vectors satisfying (8.2) and,(8.3), i.e.,Let be any point of,Y,and let be the vector of tight constraints at point , i.e.,z,includes all the,g,constraints in (8.2) and those constraints in (8.3),which are satisfied as equalities.,Define the set,Then, we shall say that the constraints set,Y,satisfies,the,Kuhn-Tucker constraint qualification,at if,z,is differentiable at and if, for every , there,exists a differentiable curve defined for,such that,The Lagrangian function is,The Kuhn-Tucker conditions at for this problem,are,where,and,are row vectors of multipliers to be,determined.,Theorem 8.1,(,Sufficient Conditions,).,If h,g, and w are differentiable, h is concave, g is,affine, w is concave, and solve the conditions,(8.44)-(8.47), then is a solution to the,maximization problem (8.1)-(8.3).,Theorem 8.2,(,Necessary Conditions,).,If h,g, and w are differentiable, and solve the,maximization problem, and the constraint qualification,holds at , then there exist multipliers and such,that satisfy conditions (8.44)-(8.47).,8.1.4 A Discrete-Time Optimal Control Problem,Here, the sate,x,k,is assumed to be measured at the,beginning of period k and control,u,k,is implemented,during period,k,. this convention is depicted in figure,8.4.,We also define continuously differentiable functions,f:,F:,g:,S:,Then, a discrete-time optimal problem in the Bolza,form is,subject to the difference equations,In (8.49) the term is known as the,difference operator,.,8.1.5 A Discrete Maximum Principle,The Lagrangian function of the problem is,We now define the Hamiltonian function,H,k,to be,Using (8.52) we can rewrite (8.51) as,If we differentiate (8.53) with respect to,x,k,for,k =1,2,T-1 ,we obtain,which upon rearranging terms becomes,If we differentiate (8.53) with respect to,x,T, we get,The difference equations (8.54) with terminal boundary,conditions (8.55) are called,adjoint equations.,If we differentiate,L,with respect to,k,and state the,corresponding Kuhn-Tucker conditions for the,multiplies,k,and constraint,(8.50), we have,and,We note that, if,H,k,is concave in,k, is,concave in,k, and the constraint qualification holds,then conditions (8.56) and (8.57) are precisely the,necessary and sufficient conditions for solving the,following Hamiltonian maximization problem:,Theorem 8.3.,If for every k , H,k,in (8.52) and,g(u,k,k,),arc concave in,u,k, and the constraint qualification,holds, then the necessary conditions for,u,k,* ,k =0,1,T-1, to be an optimal control for the problem,(8.48)-(8.50) are,Example 8.7,Consider the discrete-time optimal,control problem:,subject to,We shall solve this problem for,T,=6 and,T, 7.,Solution.,The Hamiltonian is,Let us assume, as we did in Example 2.3, that,k, 0,as long as,x,k,is positive so that,k,=-1. Given this,assumption, (8.61) becomes , whose solution,is,By differentiating (8.63), we obtain the adjoint equation,Let us assume,T,=6. Substitute (8.65) into (8.66) to,obtain,From Appendix A.11, we find the solution to be,where,c,is a constant. Since,6,=,0, we can obtain the,value of,c,by setting,k,=6 in the above equation. Thus,so that,A sketch of the value for,k,and,x,k,appears in figure,8.5. Note that,5,=0, so that the control,4,is singular.,However, since,x,4,=1, we choose,4,=-1 in order to,bring,x,5,down to 0.,Figure 8.5: Sketch of,x,k,and,k,The solution of the problem for,T, 7 is carried out in,the same way that we solved example 2.3. Namely,observe that,x,5,=0 and,5,=,6,=0, so that the control,is singular. We simply make,k,=0 for,k, 7 so that,k,=0 for all,k, 7 . It is clear without a formal proof,That this maximizes (8.60).,Example 8.8,Let us,consider a discrete version of the,production-inventory example of Section 6.1; see,Kleindorfer (1975). Let,I,k, P,k,and,S,k,be the inventory,production, and demand at time,k, respectively.,Let,I,0,be the initial inventory, let and be the goal,levels of inventory and production, and let,h,and,c,be,inventory and production cost coefficients. The,problem is:,subject to,Form the Hamiltonian,where the adjoint variable satisfies,To maximize the Hamiltonian, let us differentiate (8.70),to obtain,Since production must be nonnegative, we obtain the,optimal production as,Expressions (8.69), (8.71), and (8.72) determine a,two-point boundary value problem. For a given set of,data, it can be solved numerically by using a,spreadsheet software EXCEL; see Section 2.5. If the,constraint,P,k, 0 is dropped it can be solved,analytically by the method of Section 6.1, with,difference equations replacing the differential,equations used there.,8.2 A General Discrete Maximum Principle,subject to,Assumptions required are:,(i) and are continuously,differentiable in,x,k,for every,u,k,and,k,.,(ii) The sets are b-directionally,convex for every,x,and,k, where,b,=(-1,0,0). That is,given,and,w,in and 0,1 , there exists,such that,and,for every,x,and,k,. It should be noted that convexity,implies,b-directional convexity, but not the converse.,(iii) satisfies the Kuhn-Tucker constraint,qualification.,
展开阅读全文