A Simplicial Approach for Discrete Fixed Point Theorems (Extended Abstract)
- 格式:pdf
- 大小:160.38 KB
- 文档页数:13
2Deformation:Displacements and Strains We begin development of the basicfield equations of elasticity theory byfirst investigating thekinematics of material deformation.As a result of applied loadings,elastic solids will changeshape or deform,and these deformations can be quantified by knowing the displacements ofmaterial points in the body.The continuum hypothesis establishes a displacementfield at allpoints within the elastic ing appropriate geometry,particular measures of deformationcan be constructed leading to the development of the strain tensor.As expected,the straincomponents are related to the displacementfield.The purpose of this chapter is to introduce thebasic definitions of displacement and strain,establish relations between these twofieldquantities,andfinally investigate requirements to ensure single-valued,continuous displace-mentfields.As appropriate for linear elasticity,these kinematical results are developed underthe conditions of small deformation theory.Developments in this chapter lead to two funda-mental sets offield equations:the strain-displacement relations and the compatibility equa-tions.Furtherfield equation development,including internal force and stress distribution,equilibrium and elastic constitutive behavior,occurs in subsequent chapters.2.1General DeformationsUnder the application of external loading,elastic solids deform.A simple two-dimensionalcantilever beam example is shown in Figure2-1.The undeformed configuration is taken withthe rectangular beam in the vertical position,and the end loading displaces material points tothe deformed shape as shown.As is typical in most problems,the deformation varies frompoint to point and is thus said to be nonhomogenous.A superimposed square mesh is shown inthe two configurations,and this indicates how elements within the material deform locally.It isapparent that elements within the mesh undergo extensional and shearing deformation.Anelastic solid is said to be deformed or strained when the relative displacements between pointsin the body are changed.This is in contrast to rigid-body motion where the distance betweenpoints remains the same.In order to quantify deformation,consider the general example shown in Figure2-2.In the undeformed configuration,we identify two neighboring material points P o and P connected withthe relative position vector r as shown.Through a general deformation,these points are mappedand P0in the deformed configuration.Forfinite or large deformation theory,the to locations P0o27undeformed and deformed configurations can be significantly different,and a distinction between these two configurations must be maintained leading to Lagrangian and Eulerian descriptions;see,for example,Malvern(1969)or Chandrasekharaiah and Debnath(1994). However,since we are developing linear elasticity,which uses only small deformation theory, the distinction between undeformed and deformed configurations can be dropped.Using Cartesian coordinates,define the displacement vectors of points P o and P to be u o and u,respectively.Since P and P o are neighboring points,we can use a Taylor series expansion around point P o to express the components of u asu¼u oþ@u@xr xþ@u@yr yþ@u@zr zv¼v oþ@v@xr xþ@v@yr yþ@v@zr zw¼w oþ@w@xr xþ@w@yr yþ@w@zr z(2:1:1)FIGURE2-1Two-dimensional deformation example.(Undeformed)(Deformed) FIGURE2-2General deformation between two neighboring points.28FOUNDATIONS AND ELEMENTARY APPLICATIONSNote that the higher-order terms of the expansion have been dropped since the components of r are small.The change in the relative position vector r can be written asD r¼r0Àr¼uÀu o(2:1:2) and using(2.1.1)givesD r x¼@u@xr xþ@u@yr yþ@u@zr zD r y¼@v@xr xþ@v@yr yþ@v@zr zD r z¼@w@xr xþ@w@yr yþ@w@zr z(2:1:3)or in index notationD r i¼u i,j r j(2:1:4) The tensor u i,j is called the displacement gradient tensor,and may be written out asu i,j¼@u@x@u@y@u@z@v@x@v@y@v@z@w@x@w@y@w@z2666666437777775(2:1:5)From relation(1.2.10),this tensor can be decomposed into symmetric and antisymmetric parts asu i,j¼e ijþ!ij(2:1:6) wheree ij¼12(u i,jþu j,i)!ij¼12(u i,jÀu j,i)(2:1:7)The tensor e ij is called the strain tensor,while!ij is referred to as the rotation tensor.Relations (2.1.4)and(2.1.6)thus imply that for small deformation theory,the change in the relative position vector between neighboring points can be expressed in terms of a sum of strain and rotation bining relations(2.1.2),(2.1.4),and(2.1.6),and choosing r i¼dx i, we can also write the general result in the formu i¼u o iþe ij dx jþ!ij dx j(2:1:8) Because we are considering a general displacementfield,these results include both strain deformation and rigid-body motion.Recall from Exercise1-14that a dual vector!i canDeformation:Displacements and Strains29be associated with the rotation tensor such that !i ¼À1=2e ijk !jk .Using this definition,it is found that!1¼!32¼12@u 3@x 2À@u 2@x 3 !2¼!13¼12@u 1@x 3À@u 3@x 1 !3¼!21¼12@u 2@x 1À@u 1@x 2 (2:1:9)which can be expressed collectively in vector format as v ¼(1=2)(r Âu ).As is shown in the next section,these components represent rigid-body rotation of material elements about the coordinate axes.These general results indicate that the strain deformation is related to the strain tensor e ij ,which in turn is a related to the displacement gradients.We next pursue a more geometric approach and determine specific connections between the strain tensor components and geometric deformation of material elements.2.2Geometric Construction of Small Deformation TheoryAlthough the previous section developed general relations for small deformation theory,we now wish to establish a more geometrical interpretation of these results.Typically,elasticity variables and equations are field quantities defined at each point in the material continuum.However,particular field equations are often developed by first investigating the behavior of infinitesimal elements (with coordinate boundaries),and then a limiting process is invoked that allows the element to shrink to a point.Thus,consider the common deformational behavior of a rectangular element as shown in Figure 2-3.The usual types of motion include rigid-body rotation and extensional and shearing deformations as illustrated.Rigid-body motion does not contribute to the strain field,and thus also does not affect the stresses.We therefore focus our study primarily on the extensional and shearing deformation.Figure 2-4illustrates the two-dimensional deformation of a rectangular element with original dimensions dx by dy .After deformation,the element takes a rhombus form as shown in the dotted outline.The displacements of various corner reference points areindicated(Rigid Body Rotation)(Undeformed Element)(Horizontal Extension)(Vertical Extension)(Shearing Deformation)FIGURE 2-3Typical deformations of a rectangular element.30FOUNDATIONS AND ELEMENTARY APPLICATIONSin the figure.Reference point A is taken at location (x,y ),and the displacement components of this point are thus u (x,y )and v (x,y ).The corresponding displacements of point B are u (x þdx ,y )and v (x þdx ,y ),and the displacements of the other corner points are defined in an analogous manner.According to small deformation theory,u (x þdx ,y )%u (x ,y )þ(@u =@x )dx ,with similar expansions for all other terms.The normal or extensional strain component in a direction n is defined as the change in length per unit length of fibers oriented in the n -direction.Normal strain is positive if fibers increase in length and negative if the fiber is shortened.In Figure 2-4,the normal strain in the x direction can thus be defined bye x ¼A 0B 0ÀAB From the geometry in Figure 2-4,A 0B 0¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffidx þ@u @x dx 2þ@v @x dx 2s ¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi1þ2@u @x þ@u @x 2þ@v @x 2dx s %1þ@u @xdx where,consistent with small deformation theory,we have dropped the higher-order ing these results and the fact that AB ¼dx ,the normal strain in the x -direction reduces toe x ¼@u@x (2:2:1)In similar fashion,the normal strain in the y -direction becomese y ¼@v@y (2:2:2)A second type of strain is shearing deformation,which involves angles changes (see Figure 2-3).Shear strain is defined as the change in angle between two originally orthogonalx FIGURE 2-4Two-dimensional geometric strain deformation.Deformation:Displacements and Strains 31directions in the continuum material.This definition is actually referred to as the engineering shear strain.Theory of elasticity applications generally use a tensor formalism that requires a shear strain definition corresponding to one-half the angle change between orthogonal axes; see previous relation(2:1:7)1.Measured in radians,shear strain is positive if the right angle between the positive directions of the two axes decreases.Thus,the sign of the shear strain depends on the coordinate system.In Figure2-4,the engineering shear strain with respect to the x-and y-directions can be defined asg xy¼p2ÀffC0A0B0¼aþbFor small deformations,a%tan a and b%tan b,and the shear strain can then be expressed asg xy¼@v@xdxdxþ@u@xdxþ@u@ydydyþ@v@ydy¼@u@yþ@v@x(2:2:3)where we have again neglected higher-order terms in the displacement gradients.Note that each derivative term is positive if lines AB and AC rotate inward as shown in thefigure.By simple interchange of x and y and u and v,it is apparent that g xy¼g yx.By considering similar behaviors in the y-z and x-z planes,these results can be easily extended to the general three-dimensional case,giving the results:e x¼@u@x,e y¼@v@y,e z¼@w@zg xy¼@u@yþ@v@x,g yz¼@v@zþ@w@y,g zx¼@w@xþ@u@z(2:2:4)Thus,we define three normal and three shearing strain components leading to a total of six independent components that completely describe small deformation theory.This set of equations is normally referred to as the strain-displacement relations.However,these results are written in terms of the engineering strain components,and tensorial elasticity theory prefers to use the strain tensor e ij defined by(2:1:7)1.This represents only a minor change because the normal strains are identical and shearing strains differ by a factor of one-half;for example,e11¼e x¼e x and e12¼e xy¼1=2g xy,and so forth.Therefore,using the strain tensor e ij,the strain-displacement relations can be expressed in component form ase x¼@u@x,e y¼@v@y,e z¼@w@ze xy¼1@uþ@v,e yz¼1@vþ@w,e zx¼1@wþ@u(2:2:5)Using the more compact tensor notation,these relations are written ase ij¼12(u i,jþu j,i)(2:2:6)32FOUNDATIONS AND ELEMENTARY APPLICATIONSwhile in direct vector/matrix notation as the form reads:e¼12r uþ(r u)TÂÃ(2:2:7)where e is the strain matrix and r u is the displacement gradient matrix and(r u)T is its transpose.The strain is a symmetric second-order tensor(e ij¼e ji)and is commonly written in matrix format:e¼[e]¼e x e xy e xze xy e y e yze xz e yz e z2435(2:2:8)Before we conclude this geometric presentation,consider the rigid-body rotation of our two-dimensional element in the x-y plane,as shown in Figure2-5.If the element is rotated through a small rigid-body angular displacement about the z-axis,using the bottom element edge,the rotation angle is determined as@v=@x,while using the left edge,the angle is given byÀ@u=@y. These two expressions are of course the same;that is,@v=@x¼À@u=@y and note that this would imply e xy¼0.The rotation can then be expressed as!z¼[(@v=@x)À(@u=@y)]=2, which matches with the expression given earlier in(2:1:9)3.The other components of rotation follow in an analogous manner.Relations for the constant rotation!z can be integrated to give the result:u*¼u oÀ!z yv*¼v oþ!z x(2:2:9)where u o and v o are arbitrary constant translations in the x-and y-directions.This result then specifies the general form of the displacementfield for two-dimensional rigid-body motion.We can easily verify that the displacementfield given by(2.2.9)yields zero strain.xFIGURE2-5Two-dimensional rigid-body rotation.Deformation:Displacements and Strains33For the three-dimensional case,the most general form of rigid-body displacement can beexpressed asu*¼u oÀ!z yþ!y zv*¼v oÀ!x zþ!z xw*¼w oÀ!y xþ!x y(2:2:10)As shown later,integrating the strain-displacement relations to determine the displacementfield produces arbitrary constants and functions of integration,which are equivalent to rigid-body motion terms of the form given by(2.2.9)or(2.2.10).Thus,it is important to recognizesuch terms because we normally want to drop them from the analysis since they do notcontribute to the strain or stressfields.2.3Strain TransformationBecause the strains are components of a second-order tensor,the transformation theorydiscussed in Section1.5can be applied.Transformation relation(1:5:1)3is applicable forsecond-order tensors,and applying this to the strain givese0ij¼Q ip Q jq e pq(2:3:1)where the rotation matrix Q ij¼cos(x0i,x j).Thus,given the strain in one coordinate system,we can determine the new components in any other rotated system.For the general three-dimensional case,define the rotation matrix asQ ij¼l1m1n1l2m2n2l3m3n32435(2:3:2)Using this notational scheme,the specific transformation relations from equation(2.3.1)becomee0x¼e x l21þe y m21þe z n21þ2(e xy l1m1þe yz m1n1þe zx n1l1)e0y¼e x l22þe y m22þe z n22þ2(e xy l2m2þe yz m2n2þe zx n2l2)e0z¼e x l23þe y m23þe z n23þ2(e xy l3m3þe yz m3n3þe zx n3l3)e0xy¼e x l1l2þe y m1m2þe z n1n2þe xy(l1m2þm1l2)þe yz(m1n2þn1m2)þe zx(n1l2þl1n2)e0yz¼e x l2l3þe y m2m3þe z n2n3þe xy(l2m3þm2l3)þe yz(m2n3þn2m3)þe zx(n2l3þl2n3)e0zx¼e x l3l1þe y m3m1þe z n3n1þe xy(l3m1þm3l1)þe yz(m3n1þn3m1)þe zx(n3l1þl3n1)(2:3:3)For the two-dimensional case shown in Figure2-6,the transformation matrix can be ex-pressed asQ ij¼cos y sin y0Àsin y cos y00012435(2:3:4)34FOUNDATIONS AND ELEMENTARY APPLICATIONSUnder this transformation,the in-plane strain components transform according toe 0x ¼e x cos 2y þe y sin 2y þ2e xy sin y cos ye 0y ¼e x sin 2y þe y cos 2y À2e xy sin y cos ye 0xy ¼Àe x sin y cos y þe y sin y cos y þe xy (cos 2y Àsin 2y )(2:3:5)which is commonly rewritten in terms of the double angle:e 0x ¼e x þe y 2þe x Àe y 2cos 2y þe xy sin 2y e 0y ¼e x þe y Àe x Àe y cos 2y Àe xy sin 2y e 0xy ¼e y Àe x 2sin 2y þe xy cos 2y (2:3:6)Transformation relations (2.3.6)can be directly applied to establish transformations between Cartesian and polar coordinate systems (see Exercise 2-6).Additional applications of these results can be found when dealing with experimental strain gage measurement systems.For example,standard experimental methods using a rosette strain gage allow the determination of extensional strains in three different directions on the surface of a ing this type of data,relation (2:3:6)1can be repeatedly used to establish three independent equations that can be solved for the state of strain (e x ,e y ,e xy )at the surface point under study (see Exercise 2-7).Both two-and three-dimensional transformation equations can be easily incorporated in MATLAB to provide numerical solutions to problems of interest.Such examples are given in Exercises 2-8and 2-9.2.4Principal StrainsFrom the previous discussion in Section 1.6,it follows that because the strain is a symmetric second-order tensor,we can identify and determine its principal axes and values.According to this theory,for any given strain tensor we can establish the principal value problem and solvey ′FIGURE 2-6Two-dimensional rotational transformation.Deformation:Displacements and Strains 35the characteristic equation to explicitly determine the principal values and directions.The general characteristic equation for the strain tensor can be written asdet[e ijÀe d ij]¼Àe3þW1e2ÀW2eþW3¼0(2:4:1) where e is the principal strain and the fundamental invariants of the strain tensor can be expressed in terms of the three principal strains e1,e2,e3asW1¼e1þe2þe3W2¼e1e2þe2e3þe3e1W3¼e1e2e3(2:4:2)Thefirst invariant W1¼W is normally called the cubical dilatation,because it is related to the change in volume of material elements(see Exercise2-11).The strain matrix in the principal coordinate system takes the special diagonal forme ij¼e1000e2000e32435(2:4:3)Notice that for this principal coordinate system,the deformation does not produce anyshearing and thus is only extensional.Therefore,a rectangular element oriented alongprincipal axes of strain will retain its orthogonal shape and undergo only extensional deform-ation of its sides.2.5Spherical and Deviatoric StrainsIn particular applications it is convenient to decompose the strain tensor into two parts calledspherical and deviatoric strain tensors.The spherical strain is defined by~e ij¼13e kk d ij¼13Wd ij(2:5:1)while the deviatoric strain is specified as^e ij¼e ijÀ13e kk d ij(2:5:2)Note that the total strain is then simply the sume ij¼~e ijþ^e ij(2:5:3)The spherical strain represents only volumetric deformation and is an isotropic tensor,being the same in all coordinate systems(as per the discussion in Section1.5).The deviatoricstrain tensor then accounts for changes in shape of material elements.It can be shownthat the principal directions of the deviatoric strain are the same as those of the straintensor.36FOUNDATIONS AND ELEMENTARY APPLICATIONS2.6Strain CompatibilityWe now investigate in more detail the nature of the strain-displacement relations (2.2.5),and this will lead to the development of some additional relations necessary to ensure continuous,single-valued displacement field solutions.Relations (2.2.5),or the index notation form (2.2.6),represent six equations for the six strain components in terms of three displacements.If we specify continuous,single-valued displacements u,v,w,then through differentiation the resulting strain field will be equally well behaved.However,the converse is not necessarily true;that is,given the six strain components,integration of the strain-displacement relations (2.2.5)does not necessarily produce continuous,single-valued displacements.This should not be totally surprising since we are trying to solve six equations for only three unknown displacement components.In order to ensure continuous,single-valued displacements,the strains must satisfy additional relations called integrability or compatibility equations .Before we proceed with the mathematics to develop these equations,it is instructive to consider a geometric interpretation of this concept.A two-dimensional example is shown in Figure 2-7whereby an elastic solid is first divided into a series of elements in case (a).For simple visualization,consider only four such elements.In the undeformed configuration shown in case (b),these elements of course fit together perfectly.Next,let us arbitrarily specify the strain of each of the four elements and attempt to reconstruct the solid.For case (c),the elements have been carefully strained,taking into consideration neighboring elements so that the system fits together thus yielding continuous,single-valued displacements.However,for(b) Undeformed Configuration(c) Deformed ConfigurationContinuous Displacements (a) Discretized Elastic Solid (d) Deformed Configuration Discontinuous DisplacementsFIGURE 2-7Physical interpretation of strain compatibility.case(d),the elements have been individually deformed without any concern for neighboring deformations.It is observed for this case that the system will notfit together without voids and gaps,and this situation produces a discontinuous displacementfield.So,we again conclude that the strain components must be somehow related to yield continuous,single-valued displacements.We now pursue these particular relations.The process to develop these equations is based on eliminating the displacements from the strain-displacement relations.Working in index notation,we start by differentiating(2.2.6) twice with respect to x k and x l:e ij,kl¼12(u i,jklþu j,ikl)Through simple interchange of subscripts,we can generate the following additional relations:e kl,ij¼12(u k,lijþu l,kij)e jl,ik¼12(u j,likþu l,jik)e ik,jl¼12(u i,kjlþu k,ijl)Working under the assumption of continuous displacements,we can interchange the order of differentiation on u,and the displacements can be eliminated from the preceding set to gete ij,klþe kl,ijÀe ik,jlÀe jl,ik¼0(2:6:1) These are called the Saint Venant compatibility equations.Although the system would lead to 81individual equations,most are either simple identities or repetitions,and only6are meaningful.These six relations may be determined by letting k¼l,and in scalar notation, they become@2e x @y2þ@2e y@x2¼2@2e xy@x@y@2e y @z2þ@2e z@y2¼2@2e yz@y@z@2e z @x2þ@2e x@z2¼2@2e zx@z@x@2e x @y@z ¼@@xÀ@e yz@xþ@e zx@yþ@e xy@z@2e y @z@x ¼@@yÀ@e zx@yþ@e xy@zþ@e yz@x@2e z @x@y ¼@@zÀ@e xy@zþ@e yz@xþ@e zx@y(2:6:2)It can be shown that these six equations are equivalent to three independent fourth-order relations(see Exercise2-14).However,it is usually more convenient to use the six second-order equations given by(2.6.2).In the development of the compatibility relations,we assumed that the displacements were continuous,and thus the resulting equations (2.6.2)are actually only a necessary condition.In order to show that they are also sufficient,consider two arbitrary points P and P o in an elastic solid,as shown in Figure 2-8.Without loss in generality,the origin may be placed at point P o .The displacements of points P and P o are denoted by u P i and u o i ,and the displacement ofpoint P can be expressed asu P i ¼u o i þðC du i ¼u o i þðC @u i @x j dx j (2:6:3)where C is any continuous curve connecting points P o and P .Using relation (2.1.6)for the displacement gradient,(2.6.3)becomesu P i ¼u o i þðC (e ij þ!ij )dx j (2:6:4)Integrating the last term by parts givesðC !ij dx j ¼!P ij x P j ÀðC x j !ij ,k dx k (2:6:5)where !P ij is the rotation tensor at point P .Using relation (2:1:7)2,!ij ,k ¼12(u i ,jk Àu j ,ik )¼12(u i ,jk Àu j ,ik )þ12(u k ,ji Àu k ,ji )¼12@@x j (u i ,k þu k ,i )À12@@x i(u j ,k þu k ,j )¼e ik ,j Àe jk ,i (2:6:6)Substituting results (2.6.5)and (2.6.6)into (2.6.4)yieldsu P i¼u o i þ!P ij x P j þðC U ik dx k (2:6:7)where U ik ¼e ik Àx j (e ik ,j Àe jk ,i ).P oFIGURE 2-8Continuity of displacements.Now if the displacements are to be continuous,single-valued functions,the line integral appearing in(2.6.7)must be the same for any curve C;that is,the integral must be independent of the path of integration.This implies that the integrand must be an exact differential,so that the value of the integral depends only on the end points.Invoking Stokes theorem,we can show that if the region is simply connected(definition of the term simply connected is postponed for the moment),a necessary and sufficient condition for the integral to be path independent is for U ik,l¼U il,ing this result yieldse ik,lÀd jl(e ik,jÀe jk,i)Àx j(e ik,jlÀe jk,il)¼e il,kÀd jk(e il,jÀe jl,i)Àx j(e il,jkÀe jl,ik) which reduces tox j(e ik,jlÀe jk,ilÀe il,jkþe jl,ik)¼0Because this equation must be true for all values of x j,the terms in parentheses must vanish, and after some index renaming this gives the identical result previously stated by the compati-bility relations(2.6.1):e ij,klþe kl,ijÀe ik,jlÀe jl,ik¼0Thus,relations(2.6.1)or(2.6.2)are the necessary and sufficient conditions for continuous, single-valued displacements in simply connected regions.Now let us get back to the term simply connected.This concept is related to the topology or geometry of the region under study.There are several places in elasticity theory where the connectivity of the region fundamentally affects the formulation and solution method. The term simply connected refers to regions of space for which all simple closed curves drawn in the region can be continuously shrunk to a point without going outside the region. Domains not having this property are called multiply connected.Several examples of such regions are illustrated in Figure2-9.A general simply connected two-dimensional region is shown in case(a),and clearly this case allows any contour within the region to be shrunk to a point without going out of the domain.However,if we create a hole in the region as shown in case(b),a closed contour surrounding the hole cannot be shrunk to a point without going into the hole and thus outside of the region.Thus,for two-dimensional regions,the presence of one or more holes makes the region multiply connected.Note that by introducing a cut between the outer and inner boundaries in case(b),a new region is created that is now simply connected. Thus,multiply connected regions can be made simply connected by introducing one or more cuts between appropriate boundaries.Case(c)illustrates a simply connected three-dimensional example of a solid circular cylinder.If a spherical cavity is placed inside this cylinder as shown in case(d),the region is still simply connected because any closed contour can still be shrunk to a point by sliding around the interior cavity.However,if the cylinder has a through hole as shown in case(e),then an interior contour encircling the axial through hole cannot be reduced to a point without going into the hole and outside the body.Thus,case(e)is an example of the multiply connected three-dimensional region.It was found that the compatibility equations are necessary and sufficient conditions for continuous,single-valued displacements only for simply connected regions.However, for multiply connected domains,relations(2.6.1)or(2.6.2)provide only necessary but。
《2024年1月浙江首考英语卷深度解析及变式训练》专题05 阅读理解D篇(解析+词汇+变式+技巧+模拟) 原卷版养成良好的答题习惯,是决定高考英语成败的决定性因素之一。
做题前,要认真阅读题目要求、题干和选项,并对答案内容作出合理预测;答题时,切忌跟着感觉走,最好按照题目序号来做,不会的或存在疑问的,要做好标记,要善于发现,找到题目的题眼所在,规范答题,书写工整;答题完毕时,要认真检查,查漏补缺,纠正错误。
关键词:说明文, 人与社会, 棉花糖测试, 心理测试, 信息轰炸, 抵御诱惑The Stanford marshmallow (棉花糖) test was originally conducted by psychologist Walter Mischel in the late 1960s. Children aged four to six at a nursery school were placed in a room. A single sugary treat, selected by the child, was placed on a table. Each child was told if they waited for 15 minutes before eating the treat, they would be given a second treat. Then they were left alone in the room. Follow-up studies with the children later in life showed a connect ion between an ability to wait long enough to obtain a second treat and various forms of success.As adults we face a version of the marshmallow test every day. We’ re not tempted (诱惑) by sugary treats, but by our computers, phones, and tablets — all the devices that connect us to the global delivery system for various types of information that do to us what marshmallows do to preschoolers.We are tempted by sugary treats because our ancestors lived in a calorie-poor world, and our brains developed a response mechanism to these treats that reflected their value —a feeling of reward and satisfaction. But as we’ve reshaped the world around us, dramatically reducing the cost and effort involved in obtaining calories, we still have the same brains we had thousands of years ago, and this mismatch is at the heart of why so many of us struggle to resist tempting foods that we know we shouldn’t eat.A similar process is at work in our response to information. Our formative environment as a species was information-poor, so our brains developed a mechanism that prized new information. But global connectivity has greatly changed our information environment. We are now ceaselessly bombarded (轰炸) with new information. Therefore, just as we need to be more thoughtful about our caloric consumption, we also need to be more thoughtful about our information consumption, resisting the temptation of the mental “junk food” in order to manage our time most effectively.32. What did the children need to do to get a second treat in Mischel’s test?A. Take an examination alone.B. Show respect for the researchers.C. Share their treats with others.D. Delay eating for fifteen minutes.33. According to paragraph 3, there is a mismatch between_______.A. the calorie-poor world and our good appetitesB. the shortage of sugar and our nutritional needsC. the rich food supply and our unchanged brainsD. the tempting foods and our efforts to keep fit34. What does the author suggest readers do?A. Absorb new information readily.B. Be selective information consumers.C. Use diverse information sources.D. Protect the information environment.35. Which of the following is the best title for the text?A. Eat Less, Read MoreB. The Bitter Truth about Early HumansC. The Later, the BetterD. The Marshmallow Test for Grownups一、高频单词1. originally ad.2. psychologist n.3. nursery n.4. treat n.5. follow-up a.6. version n.7. tempt vt.8. tablet n.9. device n.10. delivery n.11. preschooler n.12. ancestor n.13. calorie-poor a.14. mechanism n. 15. reflect vt.16. reward n.17. reshape vt.18. dramatically ad.19. calorie n.20. mismatch n.21. species n.22. information-poor a.23. prize vt.24. connectivity n.25. ceaselessly ad.26. thoughtful a.27. consumption n.28. resist vt.29. mental a.30. effectively ad.31. delay vt.32. appetite n.33. shortage n. 34. absorb vt.35. readily ad.36. selective a.37. diverse a.38. bitter a.二、高频词块1. in the late 1960s2. sugary treat3. leave sb alone4. be involved in5. at the heart of6. in response to7. show respect for8. delay doing三、长难句翻译1. We are tempted by sugary treats because our ancestors lived in a calorie-poor world, and our brains developed a response mechanism to these treats that reflected their value —a feeling of reward and satisfaction.我们被含糖食物所诱惑,因为我们的祖先生活在一个热量匮乏的世界里,我们的大脑对这些食物产生了反应机制,反映了它们的价值——一种奖励和满足感。
IIASAFrom Stochastic Dominanceto Mean–Risk Models:Semideviations as Risk MeasuresWłodzimierz OgryczakAndrzej Ruszczy´nskiInterim Reports on work of the International Institute for Applied Systems Analysis receive only limited review.Views or opinions expressed herein do not necessarily represent those of the Institute,its National Member Organizations,or other organizations supporting the work.AbstractTwo methods are frequently used for modeling the choice among uncertain outcomes: stochastic dominance and mean–risk approaches.The former is based on an axiomatic model of risk-averse preferences but does not provide a convenient computational recipe. The latter quantifies the problem in a lucid form of two criteria with possible trade-offanalysis,but cannot model all risk-averse preferences.In particular,if variance is used as a measure of risk,the resulting mean–variance(Markowitz)model is,in general, not consistent with stochastic dominance rules.This paper shows that the standard semideviation(square root of the semivariance)as the risk measure makes the mean–risk model consistent with the second degree stochastic dominance,provided that the trade-offcoefficient is bounded by a certain constant.Similar results are obtained for the absolute semideviation,and for the absolute and standard deviations in the case of symmetric or bounded distributions.In the analysis we use a new tool,the Outcome–Risk diagram, which appears to be particularly useful for comparing uncertain outcomes.Key Words:Decisions under Risk,Portfolio Optimization,Stochastic Dom-inance,Mean–Risk Models.Contents1Introduction1 2Stochastic dominance and mean–risk models2 3The O–R diagram5 4Absolute deviation as risk measure8 5Standard semideviation as risk measure11 6Standard deviation as risk measure13 7Concluding remarks15From Stochastic Dominanceto Mean–Risk Models:Semideviations as Risk MeasuresW l odzimierz Ogryczak∗Andrzej Ruszczy´n ski1IntroductionComparing uncertain outcomes is one of fundamental interests of decision theory.Our objective is to analyze relations between the existing approaches and to provide some tools to facilitate the analysis.We consider decisions with real-valued outcomes,such as return,net profit or number of lives saved.A leading example,originating fromfinance,is the problem of choice among mutually exclusive investment opportunities or portfolios having uncertain returns. Although we discuss the consequences of our analysis in the portfolio selection context, we do not assume any specificity related to this or another application.We consider the general problem of comparing real-valued random variables(distributions),assuming that larger outcomes are preferred.We describe a random variable˜x by the probability measure P x induced by it on the real line R.It is a general framework:the random variables considered may be discrete,continuous,or mixed(Pratt et al.,1995).Owing to that,our analysis covers a variety of problems of choosing among uncertain prospects that occur in economics and management.Two methods are frequently used for modeling choice among uncertain prospects: stochastic dominance(Whitmore and Findlay,1978;Levy,1992),and mean–risk analysis (Markowitz,1987).The former is based on an axiomatic model of risk-averse preferences: it leads to conclusions which are consistent with the axioms.Unfortunately,the stochastic dominance approach does not provide us with a simple computational recipe—it is,in fact, a multiple criteria model with a continuum of criteria.The mean–risk approach quantifies the problem in a lucid form of only two criteria:the mean,representing the expected outcome,and the risk:a scalar measure of the variability of outcomes.The mean–risk model is appealing to decision makers and allows a simple trade-offanalysis,analytical or geometrical.On the other hand,mean–risk approaches are not capable of modeling the entire richness of various risk-averse preferences.Moreover,for typical dispersion statistics used as risk measures,the mean–risk approach may lead to inferior conclusions.The seminal Markowitz(1952)portfolio optimization model uses the variance as the risk measure in the mean–risk analysis.Since then many authors have pointed out that the mean–variance model is,in general,not consistent with stochastic dominance rules.Theuse of the semivariance rather than variance as the risk measure was already suggested by Markowitz(1959)himself.Porter(1974)showed that the mean–risk model using the fixed-target semivariance as the risk measure is consistent with stochastic dominance.This approach was extended by Fishburn(1977)to more general risk measures associated with outcomes below somefixed target.There are many arguments for the use offixed targets. On the other hand,when one of performance measures is the expected return,the risk measure should take into account all possible outcomes below the mean.Therefore,we focus our analysis on central semimoments which measure the expected value of deviations below the mean.To be more precise,we consider the absolute semideviation(from the mean)¯δx= µx−∞(µx−ξ)P x(dξ)=1The second performance function F(2)x is given by areas below the distribution function F x:F(2)x(η)= η−∞F x(ξ)dξforη∈R,and defines the weak relation of the second degree stochastic dominance(SSD):˜xSSD ˜y⇔F(2)x(η)≤F(2)y(η)for allη∈R.(2.2)The corresponding strict dominance relations≻F SD and≻SSDare defined by the standardrule˜x≻˜y⇔˜x ˜y and˜y ˜x.(2.3)Thus,we say that˜x dominates˜y by the FSD rules(˜x≻F SD ˜y),if F x(η)≤F y(η)for allη∈R,where at least one strict inequality holds.Similarly,we say that˜x dominates˜y bythe SSD rules(˜x≻SSD ˜y),if F(2)x(η)≤F(2)y(η)for allη∈R,with at least one inequalitystrict.Certainly,˜xF SD ˜y implies˜xSSD˜y and˜x≻F SD˜y implies˜x≻SSD˜y.Note that F x(η)expresses the probability of underachievement for a given target valueη.Thus thefirst degree stochastic dominance is based on the multidimensional (continuum-dimensional)objective defined by the probabilities of underachievement forall target values.The FSD is the most general relation.If˜x≻F SD ˜y,then˜x is preferred to˜y within all models preferring larger outcomes,no matter how risk-averse or risk-seeking they are.For decision making under risk most important is the second degree stochastic dom-inance relation,associated with the function F(2)x.If˜x≻SSD˜y,then˜x is preferred to ˜y within all risk-averse preference models that prefer larger outcomes.It is therefore a matter of primary importance that an approach to the comparison of random outcomes be consistent with the second degree stochastic dominance relation.Our paper focuses on the consistency of mean–risk approaches with SSD.Mean–risk approaches are based on comparing two scalar characteristics(summary statistics),thefirst of which—denotedµ—represents the expected outcome(reward),and the second—denoted r—is some measure of risk.The weak relation of mean–risk domi-nance is defined as follows:˜xµ/r˜y⇔µx≥µy and r x≤r y.The corresponding strict dominance relation≻µ/r is defined in the standard way,as in(2.3).We say that˜x dominates˜y by theµ/r rules(˜x≻µ/r ˜y),ifµx≥µy and r x≤r y,andat least one of these inequalities is strict.An important advantage of mean–risk approaches is the possibility of a pictorial trade-offanalysis.Having assumed a trade-offcoefficientλbetween the risk and the mean,one may directly compare real values ofµx−λr x andµy−λr y.Indeed,the following implication holds:˜xµ/r˜y⇒µx−λr x≥µy−λr y for allλ>0.We say that the trade-offapproach is consistent with the mean–risk dominance.Suppose now that the mean–risk model is consistent with the SSD model by the im-plication˜xSSD ˜y⇒˜xµ/r˜y.Then mean–risk and trade-offapproaches lead to guaranteed results:˜x≻µ/r ˜y⇒˜ySSD˜xandµx−λr x>µy−λr y for someλ>0⇒˜y SSD˜x.In other words,they cannot strictly prefer an inferior decision.In this paper we show that some mean–risk models are consistent with the SSD model in the following sense:there exists a positive constantαsuch that for all˜x and˜y˜xSSD˜y⇒µx≥µy andµx−αr x≥µy−αr y.(2.4) In particular,for the risk measure r defined as the absolute semideviation(1.1)or standard semideviation(1.2),the constantαturns out to be equal to1.1Relation(2.4)directly expresses the consistency with SSD of the model using only two criteria:µandµ−αr.Both,however,are defined byµand r,and we haveµx≥µy andµx−αr x≥µy−αr y⇒µx−λr x≥µy−λr y for0<λ≤α. Consequently,(2.4)may be interpreted as the consistency with SSD of the mean–risk model,provided that the trade-offcoefficient is bounded from above byα.Namely,(2.4) guarantees thatµx−λr x>µy−λr y for some0<λ≤α⇒˜y SSD˜x.It follows that a single objective can be used to safely remove inferior decisions,provided that the trade-offcoefficient is not too large.Comparison of random variables is usually related to the problem of choice among risky alternatives in a given feasible set Q.For instance,in the simplest problem of portfolio selection(Markowitz,1987)the feasible set of random variables is defined as all convex combinations(weighted averages with nonnegative weights totaling1)of a given number of investment opportunities(securities).A feasible random variable˜x∈Q is called efficient by the relation if there is no˜y∈Q such that˜y≻˜x.Consistency(2.4)leads to the following result.Proposition1.If the mean–risk model satisfies(2.4),then except for random variables with identicalµand r,every random variable that is maximal byµ−λr with0<λ<αis efficient by the SSD rules.Proof.Let0<λ<αand˜x∈Q be maximal byµ−λr.This means thatµx−λr x≥µy−λr y for all˜y∈Q.Suppose that there exists˜z∈Q such that˜z≻SSD˜x.Then,from (2.4),µz≥µx andµz−αr z≥µx−αr x.(2.5) Adding these inequalities multiplied by(1−λ/α)andλ/α,respectively,we obtain (1−λ/α)µz+(λ/α)(µz−αr z)≥(1−λ/α)µx+(λ/α)(µx−αr x),(2.6) which after simplification reads:µz−λr z≥µx−λr x.But˜x is maximal,so we must have µz−λr z=µx−λr x,that is,equality in(2.6)holds.This combined with(2.5)implies µz=µx and r z=r x.2 |ξ−η|P x(dξ)P x(dη).Proposition1justifies the results of the mean–risk trade-offanalysis for0<λ<α. This can be extended toλ=αprovided that the inequalityµx−αr x≥µy−αr y turns into equality only in the case ofµx=µy.Corollary1.If the mean–risk model satisfies(2.4)as well as˜xSSD˜y andµx>µy⇒µx−αr x>µy−αr y(2.7) then except for random variables with identicalµand r,every random variable that is maximal byµ−λr with0<λ≤αis efficient by the SSD rules.Proof.Due to Proposition1,we only need to prove the case ofλ=α.Let˜x∈Q bemaximal byµ−αr.Suppose that there exists˜z∈Q such that˜z≻SSD ˜x.Hence,by(2.4),µz≥µx.Ifµz>µx,then(2.7)yieldsµx−αr x<µz−αr z,which contradicts the maximality of˜x.Thus,µz=µx and,by(2.4)and the maximality of˜x,one has µx−αr x=µz−αr z.Hence,µz=µx and r z=r x.It follows from Proposition1that for mean–risk models satisfying(2.4)the optimal solution of the problemmax{µx−λr x:˜x∈Q}(2.8) with0<λ<α,if it is unique,is efficient by the SSD rules.However,in the case of nonunique optimal solutions,we only know that the optimal set of(2.8)contains a solution which is efficient by the SSD rules.The optimal set may contain,however,also some SSD-dominated solutions.A question arises whether it is possible to additionally regularize(refine)problem(2.8)in order to select those optimal solutions that are efficient by the SSD rules.We resolve this question during the analysis of specific risk measures.In many applications,especially in the portfolio selection problem,the mean–risk model is analyzed with the so-called critical line algorithm(Markowitz,1987).This isa technique for identifying theµ/r efficient frontier by parametric optimization(2.8)forvaryingλ>0.Proposition1guarantees that the part of the efficient frontier(in theµ/r image space)corresponding to trade-offcoefficients0<λ<αis also efficient by the SSD rules.3The O–R diagramThe second degree stochastic dominance is based on the pointwise dominance of functions F(2).Therefore,properties of the function F(2)are important for the analysis of rela-tions between the SSD dominance and the mean–risk models.The following proposition summarizes the basic properties which we use in our analysis.Proposition2.If E{|˜x|}<∞,then the function F(2)x(η)is well defined for allη∈R and has the following properties:P1.F(2)x(η)is continuous,convex,nonnegative and nondecreasing.P2.If F x(η0)>0,then F(2)x(η)is strictly increasing for allη≥η0.P3.F(2)x(η)= η−∞(η−ξ)dF x(ξ)= η−∞(η−ξ)P x(dξ)=P{˜x≤η}E{η−˜x|˜x≤η}.P4.limη→−∞F(2)x(η)=0.P5.F(2)x(η)−(η−µx)= ∞η(ξ−η)dF x(ξ)= ∞η(ξ−η)P x(dξ)=P{˜x≥η}E{˜x−η|˜x≥η}.P6.F(2)x(η)−(η−µx)is a continuous,convex,nonnegative and nonincreasing function ofη.P7.limη→∞[F(2)x(η)−(η−µx)]=0.P8.For any givenη0∈RF(2) x (η)≥F(2)x(η0)+(η−η0)sup{F x(ξ)|ξ<η0}≥F(2)x(η0)+η−η0,ifη<η0,F(2) x (η)≤F(2)x(η0)+(η−η0)sup{F x(ξ)|ξ<η}≤F(2)x(η0)+η−η0,ifη>η0.Properties P1–P4are rather commonly known but frequently not expressed in such a rigorous form for general random variables.Properties P5–P8seem to be less known or at least not widely used in the stochastic dominance literature.In the Appendix we give a formal proof of Proposition2.From now on,we assume that all random variables under consideration are integrable in the sense that E{|˜x|}<∞.Therefore,we are allowed to use all the properties P1–P8 in our analysis.Note that,due to property P3,F(2)x(η)=P{x≤η}E{η−x|x≤η}thus expressing the expected shortage for each target outcomeη.So,in addition to being the most general dominance relation for all risk-averse preferences,SSD is a rather intuitive multidimen-sional(continuum-dimensional)risk measure.Therefore,we will refer to the graph of F(2)x as to the Outcome–Risk(O–R)diagram for the random variable˜x(Figure7.1).The graph of the function F(2)x has two asymptotes which intersect at the point(µx,0). Specifically,theη-axis is the left asymptote(property P4)and the lineη−µx is the right asymptote(property P7).In the case of a deterministic outcome(˜x=µx),the graphof F(2)x coincides with the asymptotes,whereas any uncertain outcome with the same expected valueµx yields a graph above(precisely,not below)the asymptotes.Hence,thespace between the curve(η,F(2)x(η)),η∈R,and its asymptotes represents the dispersion (and thereby the riskiness)of˜x in comparison to the deterministic outcome ofµx.We shall call it the dispersion space.Both size and shape of the dispersion space are important for complete description of the riskiness.Nevertheless,it is quite natural to consider some size parameters as summary characteristics of riskiness.As the simplest size parameter one may consider the maximal vertical diameter.Byproperties P1and P6,it is equal to F(2)x(µx).Moreover,property P3yields the following corollary.Corollary2.If E{|˜x|}<∞,then F(2)x(µx)=¯δx.The absolute semideviation¯δx turns out to be a linear measure of the dispersion space.There are many arguments(see,e.g.,Markowitz,1959)that only the dispersion related to underachievements should be considered as a measure of riskiness.In such a case weshould rather focus on the downside dispersion space,that is,to the left ofµx.Note that ¯δx is the largest vertical diameter for both the entire dispersion space and the downside dispersion space.Thus¯δx seems to be a quite reasonable linear measure of the risk related to the representation of a random variable˜x by its expected valueµx.Moreover,the absolute deviationδx= ∞−∞|ξ−µx|P x(dξ)(3.1) is symmetric in the sense thatδx=2¯δx for any(possible nonsymmetric)random variable ˜x.Thus absolute meanδalso can be considered a linear measure of riskiness.A better measure of the dispersion space should be given by its area.To evaluate it one needs to calculate the corresponding integrals.The following proposition gives these results.Proposition3.If E{˜x2}<∞,thenη−∞F(2)x(ζ)dζ=12P{˜x≤η}E{(η−˜x)2|˜x≤η},(3.2)∞η[F(2)x(ζ)−(ζ−η)]dζ=12P{˜x≥η}E{(˜x−η)2|˜x≥η}.(3.3)Formula(3.2)was shown by Porter(1974)for continuous random variables.The second formula seems to be new in the SSD literature.In the Appendix we give a formal proof of both formulas for general random variables.Corollary3.If E{˜x2}<∞,then¯σ2x=2 µx−∞F(2)x(ζ)dζ,(3.4)σ2x=2 µx−∞F(2)x(ζ)dζ+2 ∞µx[F(2)x(ζ)−(ζ−µx)]dζ.(3.5)Hereafter,whenever considering varianceσ2or semivariance¯σ2(standard deviationσor standard semideviation¯σ)we will assume that E{˜x2}<∞.Therefore,we are eligible to use formulas(3.4)and(3.5)in our analysis.By Corollary3,the varianceσ2x represents the doubled area of the dispersion space of the random variable˜x,whereas the semivariance¯σ2x is the doubled area of the downside dispersion space.Thus the semimoments¯δand¯σ2,as well as the absolute momentsδand σ2,can be regarded as some risk characteristics and they are well depicted in the O–R diagram(Figures7.2and7.3).In further sections we will use the O–R diagram to prove that the mean–risk model using the semideviations¯δand¯σis consistent with the SSD dominance.Geometrical relations in the O–R diagram make the proofs easy.However, as the geometrical relations are the consequences of Propositions2and3,the proofs are rigorous.To conclude this section we derive some additional consequences of Propositions2and3.Let us observe that in the O–R diagram the diagonal line F(2)x(η0)+η−η0is parallel tothe right asymptote η−µx and intersects the graph of F (2)x (η)at the point (η0,F (2)x (η0)).Therefore,property P8can be interpreted as follows.If a diagonal line (parallel to the right asymptote)intersects the graph of F (2)x (η)at η=η0,then for η<η0,F (2)x (η)isbounded from below by the line,and for η>η0,F (2)x (η)is bounded from above by theline.Moreover,the bounding is strict except of the case of sup {F x (ξ)|ξ<η0}=1or F x (η0)=1,respectively.Setting η0=µx we obtain the following proposition (Figure 7.4).Proposition 4.If E {˜x 2}<∞,then ¯σx ≥¯δx and this inequality is strict except of the case ¯σx =¯δx =0.Proof.From P8in Proposition 2,F (2)x (η)>F (2)x (µx )+η−µx for all η<µx ,since sup {F x (ξ)|ξ<µx }<1.Hence,in the case of F (2)x (µx )>0,one has 12¯δ2x and ¯σx >¯δx .Otherwise ¯σx =¯δx =0.Recall that,due to the Lyapunov inequality for absolute moments (Kendall and Stuart,1958),the standard deviation and the absolute deviation satisfy the following inequality:σx ≥δx .(3.6)Proposition 4is its analogue for absolute and standard semideviations.While considering two random variables ˜x and ˜y in the common O–R diagram one may easily notice that,if µx <µy ,then the right asymptote of F (2)x (the diagonal line η−µx )must intersect the graph of F (2)y (η)at some η0.By property P8,F (2)x (η)≥η−µx ≥F (2)y (η)for η≥η0.Moreover,since η−µy is the right asymptote of F (2)y (property P7),the existsη1>η0such that F (2)x (η)>F (2)y (η)for η≥η1.Thus,from the O–R diagram one caneasily derive the following,commonly known,necessary condition for the SSD dominance (Fishburn,1980;Levy,1992).Proposition 5.If ˜x SSD ˜y ,then µx ≥µy .While considering in the common O–R diagram two random variables ˜x and ˜y with equal expected values µx =µy ,one may easily notice that the functions F (2)x and F (2)y have the same asymptotes.It leads us to the following commonly known result (Fishburn,1980;Levy,1992).Proposition 6.For random variables ˜x and ˜y with equal means µx =µy˜x SSD ˜y ⇒σ2x ≤σ2y ,(3.7)˜x ≻SSD ˜y ⇒σ2x <σ2y .(3.8)4Absolute deviation as risk measureIn this section we analyze the mean–risk model with the risk defined by the absolute semideviation ¯δgiven by (1.1).Recall that ¯δx =F (2)x (µx )(Corollary 2)and it represents the largest vertical diameter of the (downside)dispersion space.Hence,¯δis a well defined geometrical characteristic in the O–R diagram.Consider two random variables ˜x and ˜y in the common O–R diagram (Figure 7.5).If˜x SSD ˜y ,then,by the definition of SSD,F (2)x is bounded from above by F (2)y ,and,byProposition 5,µx ≥µy .For η≥µy ,F (2)y (η)is bounded from above by ¯δy +η−µy (second inequality of P8in Proposition 2).Hence,¯δx =F (2)x (µx )≤F (2)y (µx )≤¯δy +µx −µy .This simple analysis of the O–R diagram allows us to derive the following necessary condition for the SSD dominance.Proposition 7.If ˜x SSD ˜y ,then µx ≥µy and µx −¯δx ≥µy −¯δy ,where the second inequality is strict whenever µx >µy .Proof.Due to the considerations preceding the proposition,we only need to prove that µx −¯δx >µy −¯δy whenever ˜x SSD ˜y and µx >µy .Note that from the second inequality of P8(η=µx ,η0=µy ),in such a case,¯δx =F (2)x (µx )≤F (2)x(µy )+(µx −µy )sup {F x (ξ)|ξ<µx }<¯δy +µx −µy .Proposition 7says that the µ/¯δmean–risk model is consistent with the SSD dominance by the rule (2.4)with α=1.Therefore,a µ/¯δcomparison leads to guaranteed results in the sense thatµx −λ¯δx >µy −λ¯δy for some 0<λ≤1⇒˜y SSD ˜x .For problems of choice among risky alternatives in a given feasible set,due to Corollary 1,the following observation can be made.Corollary 4.Except for random variables with identical mean and absolute semidevia-tion,every random variable ˜x ∈Q that is maximal by µx −λ¯δx with 0<λ≤1is efficient by the SSD rules.The upper bound on the trade-offcoefficients λin Corollary 4cannot be increased for general distributions.For any ε>0there exist random variables ˜x ≻SSD ˜y such that µx >µy and µx −(1+ε)¯δx =µy −(1+ε)¯δy .As an example one may consider two finite random variables:˜x defined as P {˜x =0}=11+ε;and ˜y defined as P {˜y =0}=1.Konno and Yamazaki (1991)introduced the portfolio selection model based on the µ/δmean–risk model.The model is very attractive computationally,since (for finite random variables)it leads to linear programming problems.Note that the absolute deviation δis a symmetric measure and the absolute semideviation ¯δis its half.Hence,Proposition 7is also valid (with factor 1/2)for the µ/δmean–risk model.Thus,for the µ/δmodel there exists a bound on the trade-offs such that for smaller trade-offs the model is consistent with the SSD rules.Specifically,due to Corollary 4,the following observation can be made.Corollary 5.Except for random variables with identical mean and absolute deviation,every random variable ˜x ∈Q that is maximal by µx −λδx with 0<λ≤1/2is efficient by the SSD rules.The upper bound on the trade-offcoefficients λin Corollary 5can be substantially increased for symmetric distributions.Proposition8.For symmetric random variables˜x and˜y,˜xSSD˜y⇒µx≥µy andµx−δx≥µy−δy.Proof.If˜xSSD ˜y then,due to Proposition5,µx≥µy.From the second inequality ofP8in Proposition2,12δy+12Consider twofinite random variables:˜x defined as P{˜x=−20}=0.5,P{˜x=20}=0.5;and˜y defined as P{˜y=−1000}=0.01,P{˜y=0}=0.98,P{˜y=1000}=0.01.They areµ/¯δindifferent,becauseµx=µy=0and¯δx=¯δy=10.Nevertheless,˜x≻SSD ˜y and F(2)x(η)<F(2)y(η)for all0<|η|<1000.The lexicographic relation defines a linear order.Hence,for problems of choice among risky alternatives in a given feasible set,the lexicographic maximization of (µ−λ¯δ,−σ)is well defined.It has two phases:the maximization of µ−λ¯δwithin the feasible set,and the selection of the optimal solution that has the smallest standard deviation σ.Owing to (3.8),such a selection results in SSD efficient solutions.Corollary 7.Every random variable ˜x ∈Q that is lexicographically maximal by (µx −λ¯δx ,−σx )with 0<λ≤1is efficient by the SSD rules.For the µ/δportfolio selection model (Konno and Yamazaki,1991)the results of our analysis can be summarized as follows.While identifying the µ/δefficient frontier by parametric optimizationmax {µx −λδx :˜x ∈Q }(4.2)for trade-offλvarying in the interval (0,0.5]the corresponding image in the µ/δspace represents SSD efficient solutions.Thus it can be used as the mean–risk map to seek a satisfactory µ/δcompromise.It does not mean,however,that the solutions generated during the parametric optimization (4.2)are SSD efficient.Therefore,having decided on some values of µand δone should apply the regularization technique (minimization of standard deviation)to select a specific portfolio which is SSD efficient.5Standard semideviation as risk measureIn this section we analyze the mean–risk model with the risk defined by the standard semideviation ¯σgiven by (1.2).Recall that the standard semideviation is the square root of the semivariance which equals to the doubled area of the downside dispersion space (Corollary 3).Hence,¯σis a well defined geometrical characteristic in the O–R diagram.Consider two random variables ˜x and ˜y in the common O–R diagram (Figure 7.7).If˜x SSD ˜y ,then,by the definition of SSD,F (2)x is bounded from above by F (2)y ,and,byProposition 5,µx ≥µy .Due to the convexity of F (2)x ,the downside dispersion space of ˜x is no greater than the downside dispersion space of ˜y plus the area of the trapezoid with the vertices:(µy ,0),(µx ,0),(µx ,F (2)x (µx ))and (µy ,F (2)y (µy )).Formally,12¯σ2y +1Moreover,from Proposition 4,¯σx =¯δx and ¯σy =¯δy can occur only if ¯σx =¯σy =0.Hence,˜x SSD ˜y and µx >µy ⇒µx −¯σx >µy −¯σy ,which completes the proof.The message of Proposition 9is that the µ/¯σmean–risk model is consistent with the SSD dominance by the rule (2.4)with α=1.Therefore,µ/¯σcomparisons lead to guaranteed results in the sense thatµx −λ¯σx >µy −λ¯σy for some 0<λ≤1⇒˜y SSD ˜x .For problems of choice among risky alternatives in a given feasible set,Corollary 1results in the following observation.Corollary 8.Except for random variables with identical mean and standard semidevia-tion,every random variable ˜x ∈Q that is maximal by µx −λ¯σx with 0<λ≤1is efficient by the SSD rules.The upper bound on the trade-offcoefficients λin Corollary 8cannot be increased for general distributions.For any ε>0there exist random variables ˜x ≻SSD ˜y such that µx >µy and µx −(1+ε)¯σx =µy −(1+ε)¯σy .As an example one may consider two finite random variables:˜x defined as P {˜x =0}=(1+ε)−2,P {˜x =1}=1−(1+ε)−2;and ˜y =0.It follows from Corollary 8that the optimal solution of the problemmax {µx −λ¯σx :˜x ∈Q },0<λ≤1,(5.2)is efficient by the SSD rules,if it is unique.In the case of nonunique optimal solutions,however,we only know that the optimal set of (4.1)contains a solution which is efficient by SSD rules.Thus,similar to the µ/¯δmodel,the µ/¯σmodel may generate ties (Figure 7.8)and the optimal set of (5.2)may contain also some SSD dominated solutions.However,two random variables that generate a tie (are indifferent)in the µ/¯σmean–risk model cannot be so much different as in the µ/¯δmodel.Standard semideviation ¯σx is an area measure of the downside dispersion space and therefore it takes into account all values of F (2)x (η)for η≤µx .Note that,if two random variables ˜x and ˜y generate a tie in the µ/¯σmodel,then µx =µy and µx−∞F (2)x (ζ)dζ= µy−∞F (2)y (ζ)dζ.Functions F (2)(η)are continuous and nonnegative.Hence,if ˜x SSD ˜y generate a µ/¯σtie,then F (2)x (η)=F (2)y (η)for all η≤µx .Thus a tie in the µ/¯σmodel may happen for ˜x ≻SSD ˜y but the SSD dominance ˜x over ˜y is then related to overperformances rather than the underperformances.Summing up,the µ/¯σmodel needs some additional regularization to resolve ties in comparisons,but it is not such a dramatic need as in the µ/¯δmodel.Similar to the µ/¯δmodel,ties in the µ/¯σmodel can be resolved by additional compar-isons of standard deviations or variances.In the case when comparison of µx −λ¯σx and µy −λ¯σy results in a tie,one may select from ˜x and ˜y the one that has a smaller standard deviation.It can be formalized as the following lexicographic comparison(µx −λ¯σx ,−σx )≥lex (µy −λ¯σy ,−σy )⇔µx −λ¯σx >µy −λ¯σyor µx −λ¯σx =µy −λ¯σy and −σx ≥−σy .。
目录1. 目的 (3)2. 范围 (3)3. 相关文件 (3)4. 定义及缩略语 (3)5. 职责 (3)6. 指南 (3)7. 安全事项 (3)8. 变更历史 (4)9. 回顾历史 (4)10. 附录 (4)1. 目的本指南的目的是实施应用ISPE的Risk-MaPP (Risk-Based manufacture of Pharmaceutical Products) Baseline指南,该指南描述了一个管理评估交叉污染风险的科学方法。
适用于下述情况,●新的设施和设备的筹建●已存在的设施和设备的整改●产品转移到其他设施或设备上●生产外包其目标是识别产品交叉污染的风险等级并采取恰当措施保证产品质量和人员安全。
要完成上述目标,必须按照下述主要步骤操作:1.遵循逻辑图表(图2和图4)制定适用决策和控制点。
2.评估并记录交叉污染的风险点和制定相应措施。
3.测试并/或监测控制点。
本指南会详细描述具体操作步骤。
2. 范围本指南适用于产品的整个生命周期,从原料药(包括中间体)到制粒压片以及成品。
在这整个过程中都应确保产品(商业产品、临床产品和研发产品)没有交叉污染。
本文件着重于GMP要求的落实。
此外,也明确了GMP和职业卫生(IH)方面的区别,以及对于生产过程中直接接触人员的控制措施。
本指南所遵循的原则也适用于承包商和供应商的选择及日常评估。
3. 相关文件3-G34-X-M Risk-Based Approach to managing Cross-Contamination in Multi-ProductFacilities4. 定义及缩略语本文件中所使用的术语均出自于术语表。
下述所列为理解本文件关键的术语条目。
4.1 全球定义(术语表)下述所列的条目均可在全球术语表中查询得到:4.1.1 API(活性成分)4.1.2 Acceptable Daily Exposure (ADE) 日允许暴露量4.1.3 Beta-Lactams β-内酰胺4.1.4 Cleaning Validation清洁验证4.1.5 Closed Process 密闭式加工4.1.6 Containment 防护4.1.7 Equipment 设备4.1.8 Facility 设施4.1.9 GMP 药品生产质量管理规范4.1.10 Harm 伤害4.1.11 Hazard 危害4.1.12 Local Exhaust/Extract System 局部排风/排风系统4.1.13 Occupational Exposure Limit (OEL) 职业暴露极限4.1.14 Occupational (Industrial) Hygiene职业(行业)卫生4.1.15 Risk Assessment 风险评估4.1.16 Sensitiser 致敏物4.1.17 Toxicity 毒性4.2 本文特定术语4.2.1 Risk 风险由危害(或者多种危害结合)所引发的严重潜在后果的总和,以及这些后果能被识别的可能性。
Intelligence Analysis Using Quantitative PreferencesDavy Van Nieuwenborgh,Stijn Heymans,and Dirk VermeirDept.of Computer ScienceVrije Universiteit Brussel,VUBPleinlaan2,B1050Brussels,Belgiumdvnieuwe,sheymans,dvermeir@vub.ac.beAbstract.The extended answer set semantics for simple logic programs,i.e.programs with only classical negation,allows for the defeat of rules to resolvecontradictions.In addition,a partial order relation on the program’s rules can beused to deduce a preference relation on its extended answer sets.In this paper,wepropose a“quantitative”preference relation that associates a weight with eachrule in a program.Intuitively,these weights define the“cost”of defeating a rule.An extended answer set is preferred if it minimizes the sum of the weights of itsdefeated rules.We characterize the expressiveness of the resulting semantics andshow how the semantics can be conveniently extended to sequences of weightpreferences,without increasing the expressiveness.We illustrate an applicationof the approach by showing how it can elegantly express largest common sub-graph and subgraph isomorphic approximation problems,a concept often usedin intelligence analysis tofind similarities or specific regions of interest in largegraphs of observed activity.1IntroductionOver the last decade a lot of research has been done on declarative programming us-ing the answer set semantics[10,2,18],a generalization of the stable model semantics [8].In answer set programming,one uses a logic program to modularly describe the requirements that must be fulfilled by the solutions to a particular problem,i.e.the an-swer sets of the program correspond to the intended solutions of the problem.One of the possible problems in answer set programming is the absence of any solutions in case of inconsistent programs.To remedy this,the authors proposed[16]the extended answer set semantics which allows for the defeat of problematic rules.E.g.,the rules ,and are clearly inconsistent and have no classical answer sets,while both and will be recognized as extended answer sets.Intuitively,is defeated by in,while defeats in.Within the context of inconsistent programs,it is natural to have some kind of pref-erence relation that is used to prefer certain extended answer sets above others.In[16],234Davy Van Nieuwenborgh,Stijn Heymans,and Dirk Vermeira“qualitative”preference semantics is proposed,using a preference relation on rules, to induce a partial ordering on the extended answer sets of a program.As an alternative,this paper considers a“quantitative”preference relation for the extended answer set semantics on simple programs,i.e.programs containing only clas-sical negation.We assign each rule in a program a(nonnegative)weight,represent-ing the cost associated with defeating the rule.Solutions for these weighted programs, called weighted answer sets,are those extended answer sets that minimize the sum of the weights of defeated rules.The resulting semantics turns out to be more expressive than classical answer set programming,even in the absence of negation as failure.We demonstrate that e.g.the membership problem is complete for the second level of the deterministic class of the polynomial hierarchy,i.e.-complete.In some situations more than one actor is involved in the process offinding a solu-tion to a particular problem.Quite often we have a sequence of decision makers,where each one sorts out the best solutions according to her preferences among the solutions that are preferred by the previous one in the sequence.Intuitively,the solutions that are still preferred by the last decision maker in the sequence are the ones that are acceptable by all parties.E.g.,in a job selection procedure,the secretary will only keep the appli-cants that passed all the tests.Secondly,the head of the department will prefer people that have better marks on their math tests,and among those,the management of thefirm will select those with a better psychological profile.Such hierarchies of individual weight preferences are supported by weight sequence programs,where each rule in a program is equipped with a sequence of weights corresponding to the cost each decision maker associates with defeating this rule(has a higher priority than).Semantically,weighted answer sets for such programs will be obtained fromfirstfinding the weighted answer sets w.r.t.the weights of thefirst decision maker,i.e.the weights,and among thosefinding the ones that are minimal w.r.t.the weights of the second decision maker,i.e.the weights,etc. Regarding the complexity,it turns out that such sequences of weights do not result in any additional expressiveness of the formalism,nevertheless allowing to express certain problems more intuitively.The proposed semantics has applications in several areas where quantitative prefer-ences are useful.E.g.,in the area of subgraph isomorphism algorithms[14]it is use-ful,in case of absence of an exact match of the pattern graph in the larger graph,to search for subgraph isomorphic approximations(SIA for short)of the larger graph that are minimal in some sense,i.e.searching for a“minimal”set of items to add to the larger graph such that the pattern occurs in it.We show how the solutions of such SIA problems correspond with the weighted answer sets of a weighted program that can be constructed out of the given instance graphs.Applications of SIA can be found in the area of intelligence analysis[9,4],where it is common to search for a pattern of interest in a large attributed relational graph[9](ARG for short).An ARG is a normal graph where nodes and edges can carry additional attributes e.g.denoting relationships. In intelligence analysis,ARGs are used to model observed activity in the world un-der consideration.We show how the translation of the SIA problem for graphs into weighted programs can be intuitively adapted to the setting of ARGs,thus providing aIntelligence Analysis Using Quantitative Preferences235 useful tool for intelligence analysis.A similar approach can be applied forfinding the largest common subgraphs between two ARGs.The remainder of this paper is organized as follows:Section2introduces weighted programs and the corresponding weighted answer set semantics,together with a char-acterization of the expressiveness.Section3formalizes weight sequence programs and we show that these systems do not have additional expressiveness in comparison to normal weighted programs.In Section4,we introduce the problem of largest common subgraphs,as well as subgraph isomorphic approximations in graph theory,and show how weighted programs can be conveniently used to compute them.Section5discusses a generalization of these graphs in the area of attributed relational graphs.Finally,we conclude in Section6.Due to space restrictions,proofs have been omitted.12Weighted ProgramsWe use the following basic definitions and notation.A literal is an atom or a negated atom.For a set of literals,denotes where.is consistent if.An interpretation is a consistent set of literals.A simple rule is of the form with afinite set of literals2.The rule is satisfied by,denoted,if whenever,i.e.if is applicable(),then it must be applied().A countable set of simple rules is called a simple logic program(SLP).The Her-brand base of a SLP contains all atoms appearing in.For a SLP and an interpretation we say that a rule is defeated w.r.t.iff there exists an applied competing rule.Furthermore,we use to denote the reduct of w.r.t.,i.e.,the set of rules satisfied by.An interpretation is called a model of a SLP if,i.e.satisfies all rules in.If there is no model of such that,is a minimal model or answer set of.An extended answer set for is any interpretation such that is an answer set of and each unsatisfied rule in is defeated.Example1.Consider the following SLP about diabetes..The extended answer sets of a program are not always equally preferred.E.g.,in the above example,when low on sugar(),one would prefer drinking ,rather than taking no sugar at all().So,defeating the ruleis“worse”than defeating the rule.Therefore,we equip the rules in simple programs with a weight representing the“penalty”involved236Davy Van Nieuwenborgh,Stijn Heymans,and Dirk Vermeirwhen defeating the rule.Naturally,extended answer sets that minimize the total penalty of a program are to be preferred over others.Definition1.A simple weight rule is a rule of the form,whereis afinite set of literals and is an associated weight value,i.e.a non-negative integer. We use to denote the weight of.A countable set of such simple weight rules is a simple weight program(SWP).The extended answer sets of a SWP coincide with the extended answer sets of the SLP obtained from by removing the weights from the rules.The program from Example1can be extended to a SWP containing a larger“penalty”weight for the hypoglycemia rules,i.e.the program:Intelligence Analysis Using Quantitative Preferences237 psychological test will be tolerated only if it is the only failed test.Finally,the rule expresses the company’s policy:defeating this rule is cheaper from the moment the penalty gets higher than.Some of the program’s extended answer sets are,,,and.Computing the penalties for these extended answer sets results in,and.These values imply the fol-lowing order among the given extended answer sets:.It can be checked,that is the only(proper)weighted answer set of.While has a penalty of2by defeating two rules with weight1,only defeats a single rule,but with weight2,yielding that and are incomparable,and thus equally preferred. Similarly,and only differ in the atom and are incomparable with each other,both having a penalty of.Combining simple programs with weights turns out to be rather expressive. Theorem1.Let be a SWP and let be a literal.Deciding whether there exists a weighted answer set of containing is-complete.3Weight SequencesIn[15]an intuitive semantics is presented for sequences of individual complex qualita-tive preferences.The idea is to apply each individual preference in the sequence in turn and to let it sort out the preferred answer sets left over by the previous preferences in the sequence.It is shown in[15]that this semantics is quite expressive as it can han-dle arbitrary complete problems of the polynomial hierarchy.More specifically,for a sequence of preference relations,the semantics is-complete.It is natural to wonder if a similar semantics for sequences of individual weights will also yield a complexity blow-up depending on the length of the sequence.It turns out that this is not the case as sequences of weights remain-complete.Definition3.An-weight sequence rule is a rule of the form, where is afinite set of literals and is a sequence of associated weight values,i.e.a sequence of non-negative integers.We use to denote the weight of.A countable set of-weight sequence rules is an n-weight sequence program(WSP).The extended answer sets of an WSP coincide with the extended answer sets of the SLP obtained from by removing the weight sequences from the rules.The penalty of an extended answer set w.r.t.the weights()and an WSP,is defined by,i.e.the sum of the weights of all defeated rules in w.r.t..Each of the penalties induces a preference relation between the extended answer sets,as in Definition2.We define the preference of extended answer sets up to a certain weight level by induction.238Davy Van Nieuwenborgh,Stijn Heymans,and Dirk VermeirDefinition4.Let be a WSP.An extended answer set is preferable up to weight level,,iff–and is minimal w.r.t.,or–,is preferable up to,and there is no,preferable up to,such that.An extended answer set of is a weighted answer set iff it is preferable up to. Example3.Consider the problem of two people having to decide what to eat for dinner. After checking the available ingredients,the cook preparing the dinner decides to let his wife propose some possible combinations from which he will choose thefinal one.As his wife is rather hungry,she decides to choose the meal which is quickest to make, the reason for which she assigns weights corresponding with times needed to make a particular part of the meal.On the other hand,her husband is tired and wants to make a meal that is easy to prepare,yielding weights representing the difficulty to make a particular part of the meal.Further,they agree on some constraints that each meal should satisfy,e.g.with french fries they take mayonnaise,etc.The WSP corresponding with this problem is shown below.Note that the rule enforces the satisfaction of the common con-straints,as it implies that every solution not making one of the rules with in the head applicable,is better than any solution making one of those rules applicable.For the extended answer sets33To keep the size of the extended answer sets small,we only provide the positive literals.Intelligence Analysis Using Quantitative Preferences239 Theorem2.Let be an WSP and let be the SWP defined bywhere and otherwise,withthe number of digits in,e.g..Then,is a weighted answer set of iff is a weighted answer set of.Reconsider the rule from Example3.In the SWP version of this program,the rule would yield the rules and,as ,yielding that and.The above transformation can be performed in polynomial time,yielding the fol-lowing complexity result for-weighted sequence programs.Corollary1.Let be an WSP.Deciding whether there exists a weighted answer set of containing is-complete.This result implies that,unlike for sequences of qualitative preferences[15],introducing sequences of weights does not yield an increase of expressiveness.Nevertheless,these sequences allow for a more intuitive expression of certain problems.4Largest Common Subgraphsand Approximate Subgraph IsomorphismsWhile largest common subgraphs and approximate subgraph isomorphisms are similar tofinding largest common subtrees[1],the formalization we introduce in this section is,to the best of our knowledge,new.A graph is a tuple,where is afinite set of nodes,and is a set of tuples representing the edges in the graph.We assume that graphs are directed; an undirected edge from to can still be represented by having both and in.Two graphs and are said to be isomorphic,denoted ,if there exists a bijection such that,where denotes.On the other hand,is called a subgraph of,denoted,iff and.Furthermore,is called subgraph isomorphic to,denoted,if there exists a subgraphsuch that.A graph is called a common subgraph of and,denoted ,if and4.For certain applications the notion of common subgraphs is too weak and one is more interested infinding the largest common subgraph between two given graphs. Formally,a graph is a largest common subgraph of and,denoted if and there does not exist a graph such that.The set of all largest common subgraphs is denoted by.240Davy Van Nieuwenborgh,Stijn Heymans,and Dirk VermeirOn the other hand,subgraph isomorphism is sometimes too strong a notion for certain applications.E.g.,when a graph is not subgraph isomorphic to a graph,it may be interesting to know what is“missing”in forto be subgraph isomorphic to it.In this context,a graph is called an extension of w.r.t.just when and when orotherwise,where the are new nodes not occurring in.The latter construction of is necessary to handle the cases in which the graph to search for is bigger than the graph to search in.A graph is a subgraph isomorphic approximation of w.r.t.iff is an extension of w.r.t.and .We use to denote that is approximately subgraph isomorphic to w.r.t.,i.e.is a subgraph isomorphic approximation of w.r.t..The set of all subgraph isomorphic approximations of w.r.t.is denoted by.Obviously,not every subgraph isomorphic approximation is equally interesting.E.g.,the fully connected graph is,clearly,always a subgraph isomorphic approximation and thus in.However,in most cases there will ex-ist smaller extensions of in.Therefore,we are particularly interested in elements from that have a minimal,in some sense,difference with the original graph.Here we use to denote the unidirectional edge difference between and,i.e..Two minimality criteria,which are widely used in areas like diagnostic reasoning [5,6,17],are cardinal minimality and subset minimality.In the former case,we select those elements from that are minimal w.r.t.cardinality among the elements in.Formally,a graph is said to be a subgraph isomorphic c-approximation iff there does not exist a graph such that.The set of all c-approximations is denoted by.Example4.Consider the four undirected graphs,,and represented in Figure1.It is clear that is one of the largest common subgraphs between andFig.1.The graphs,,and of Example4.,i.e..On the other hand,is subgraph isomorphic to,i.e.,but not to .However,adding a single(bidirectional)edge between e.g.and in,i.e.,results in a subgraph isomorphic approximationIntelligence Analysis Using Quantitative Preferences241 of w.r.t.,i.e..Obviously,is cardinal minimal yielding that .Subset minimal isomorphic approximations can be defined in a similar way.How-ever,in contrast with diagnostic reasoning,subset minimality is less intuitive in thissetting.E.g.adding the edges,,and(and their reverses)toin Example4yields a subset minimal isomorphic approximation w.r.t..However, if we see as an activity graph and as a pattern of interest,as is often done byintelligence agencies for detecting possible threats[4],the previously mentioned subset minimal approximation is not very useful as it forces the agency to check possiblerelations between currently unrelated things.On the other hand,the approximations in are of much more value as they all yield one missing link to complete the pattern,implying that the agency can quickly confirm these solutions(see also the nextsection).Obviously,when a graph is subgraph isomorphic to another one,the latter is the only c-approximation of itself.Theorem3.Let and be graphs such that.Then,.Using the weighted answer set semantics,we have the means to effectively compute,for given graphs and,the largest common subgraphs of and;or the c-approximations of w.r.t..In what follows,we will sometimes use non-grounded rules for clarity,but grounding is performed as puting the largest common subgraphs can be done using the following transformation.Definition5.Let and be graphs.The weighted pro-gram,denoted,computing the largest common subgraphs between and is defined by the rules(where):1.2.3.4.6.8.9.10.Intuitively,the rules in(1)introduce the nodes of the given graphs as facts,while the rules in(2)and(3)introduce the edges of the graphs as positive facts and the edges not appearing in the graphs as negative facts.Further,the rules in(4)are used to introduce negation as failure for the242Davy Van Nieuwenborgh,Stijn Heymans,and Dirk Vermeirmissing edges in the subgraph w.r.t.the original graph as missing edges lead to defeated rules.Reconsidering the graphs and from Example4,one of the possible weighted answer sets for will contain,besides the numerous other predicates,the pred-icates,corresponding to the largest common subgraph in Example4.This behavior is confirmed by the following theorem.Theorem4.Let and be two graphs.Then,iff there exists a weighted answer set of,with ,such that.To compute c-approximations of given graphs,we introduce the edges of as facts of the form,where.For each possible edge, with,we give a choice to either include it or not in an approximation by introducing the facts and.The penalty involved in the latter fact is to ensure that the computed approximations are cardinal minimal, i.e.not inserting an edge(defeating the former rule)can be done freely,but inserting an edge(defeating the latter rule)has to be minimized.In case we also add edges to the new nodes.To match with the possible approximations,we need to introduce for each nodea unique new variable name.Searching for a match of in the ap-proximation is done by the single rule,where.Finally,we add the single rule not which forces any solution to contain a match(note that this rule cannot be defeated).Definition6.Let and be graphs.The program com-puting the c-approximations of w.r.t.,denoted,is defined by the rules:–––,whereand–notIf we reconsider the graphs and from Example4,the program contains,besides the numerous facts,the ruleOne of the possible weighted answer sets of is e.g..Clearly,corresponds with the extension from Example4,which is a cardinal minimal approximation of w.r.t..This behavior is confirmed by the following theorem.Intelligence Analysis Using Quantitative Preferences243 Theorem5.Let and be graphs.Then,iffis a weighted answer set of.In the current approach no distinction is made between the edges that can be added to a graph to obtain an approximation.However,one can imagine situations in which adding one edge is more“difficult”than adding another,i.e.the cost of adding an edge may vary.E.g.,for an intelligence agency,it may be easier to check a relationship be-tween people in the home country,than between people in foreign countries,but check-ing internal relationships may be as hard as checking external relationship,resulting in a cost of for edges between externals and a cost of for edges between internals. Such costs represent a quantitative preference relation between edge additions.In this case,optimal solutions are approximations that minimize the sum of all costs associated with the added edges in the approximation.It is not difficult to see that this kind of minimization can easily be computed by an adapted version of the program in Definition6:just replace the weights with the cost associated for adding the edge to an approximation.Clearly,Theorem5remains valid in this extension.Similarly,we could think of an agency where possible threats arefirst selected,by somefield agent,depending on the effort needed to check certain relationships.After-ward,the supervisor will apply,on the proposed investigations of hisfield agent,another kind of quantitative preferences,ing information from other departments.In case there are still a number of possible solutions left over after the supervisor,even a third individual,e.g.the director,could apply his preferences on these possibilities.Again,it is not difficult to see that this problem can be elegantly modeled by an adapted version of the program in Definition6,this time using the-weight sequence programs intro-duced in Section3.Also in this extension,an adapted version of Theorem5remains valid.5An Application in Intelligence AnalysisAttributed relational graphs(ARGs),an extension of the abstract directed graphs de-fined in the previous section,are often used in e.g.intelligence analysis to understand complex,and often uncertain,situations.The nodes in such ARGs are used to describe objects in the observed world,e.g.persons,organizations,...,while the edges are used to represent relationships between the nodes,e.g.interaction,ownership,trust,....In addition,ARG nodes and edges may have additional attributes that describe the details of the specific objects or relationships:e.g.the name of a person,the kind of chemical,the type of conversation.An example of such an ARG,based on an example from[4],can be found in Figure3.Here,a person named Bill has rented a truck for carrying liquids and that same person resides in a house at123Main street together with a person called Ted.Furthermore,Ted has been observing a factory called Acme Inc.and he also bought large quantities of the chemical.Intelligence analysts normally define small abstract patterns which are believed to be indications of possible threats.An example of such a pattern,based on the same ex-ample from[4],can be found in Figure2.Intuitively,it states that two persons residing244Davy Van Nieuwenborgh,Stijn Heymans,and DirkVermeirFig.2.Thepattern graph[4].Harry Fig.3.The observed activity graph [4].at the same place and both observing the same factory can be dangerous if one person buys some chemical,while the other rents a truck.Having both an ARG of observed activity and a pattern,the analysts need tools for finding specific regions in the ARG that “closely”match the defined threat pat-tern.Subgraph isomorphic approximations turn out to be valuable tools to accomplish this task [4].The framework and results we developed in Section 4can be intuitively adapted to the setting of ARGs,where the transformation into a weighted program al-lows an analyst to compute subgraph isomorphic approximations that are minimal in some quantitative sense.In situations where investigating missing additional relation-ships is equally hard,the analyst can use the cardinal minimal approximations.On the other hand,if investigating some relationship has a higher cost than investigating oth-ers,an analyst could rely upon the extension of the framework of Section 4,i.e.defining a cost with each relationship (edge)that can be added to have a subgraph isomorphic approximation and only keeping the approximations that minimize the sum of the costs.Similarly,it could be the case that the analyst is not the only one in charge of making the final decision or that he has multiple equivalent possibilities.In such situations,it can be useful to apply the quantitative preferences of some other people,e.g.a super-visor or the director,to refine the number of solutions,so obtaining the most preferred solution.By using the second extension of the framework of Section 4,also this kind of reasoning with ARGs can be solved,i.e.by using weight sequence programs.Instead of formally adapting the framework and the results,we illustrate the adap-tation,and its usefulness,using the example on intelligence analysis:we will translate the ARG and pattern of Figures 3and 2into a weighted program and show that the so-lutions of the program correspond with the regions of threat in the ARG w.r.t.the given pattern.First we translate,for convenience,the nodes of the ARG to node -predicates.E.g.a person named Bill forces the factinto the program,while the factory Acme Inc.is responsible for the factIntelligence Analysis Using Quantitative Preferences245 house in123Main street gives rise to the factwhile the conversation between Jennifer and Bill can be described by the factNote that the different edge-facts can have different arities,which is not a problem as long as the arities,and the ordering of the arguments,are the same for the same relationship.E.g.edge-facts representing the conversation relationship always have six arguments:thefirst two correspond to a node,the third has to be“conversation”,the fourth the type of conversation and the last two again correspond to a node.Also note that ARGs are directed graphs,but certain relations are bidirectional,e.g. friends and married.For these relationships we have to explicitly add both directions using the edge-facts:e.g.both andhave to be present in the weighted program.One could argue that a conversation through phone is also bidirectional,but we use a directed edge here to represent who initiated the call.The pattern in Figure2can be translated into the following rule,where names start-ing with an uppercase letter correspond to a variable:The above pattern matching rule also matches situations where only one person observes a factory and does both the renting of the truck and the buying of the chemi-cals.If one wants to have explicitly two different persons,we need to add the conditionto the rule.Finally,we have to add rules for the edges that can eventually be added to our ac-tivity graph to obtain a subgraph isomorphic approximation.These edges will directly point out the region of interest in the activity graph as the minimization assures that only edges are added where necessary,i.e.on those places in the activity graph where the pattern(almost)matches.While we introduced all possible edges in the simula-tion of Section4,doing the same in the context of ARGs may not be the best way to go.Indeed,ARGs can have multiple edges between the same nodes but with differ-ent attributes,which are not always useful to define between certain types of nodes.E.g.is theoretically possible, but useless in real life.Therefore,one should avoid the introduction of meaningless edges in the program,possibly by adding extra semantical constraints,e.g.typing the。
485[Journal of Political Economy,2005,vol.113,no.3]᭧2005by The University of Chicago.All rights reserved.0022-3808/2005/11303-0002$10.00Exchange Rates and FundamentalsCharles Engel and Kenneth D.WestUniversity of Wisconsin and National Bureau of Economic ResearchWe show analytically that in a rational expectations present-value model,an asset price manifests near–random walk behavior if fun-damentals are I(1)and the factor for discounting future fundamentals is near one.We argue that this result helps explain the well-known puzzle that fundamental variables such as relative money supplies,outputs,inflation,and interest rates provide little help in predicting changes in floating exchange rates.As well,we show that the data do exhibit a related link suggested by standard models—that the exchange rate helps predict these fundamentals.The implication is that exchange rates and fundamentals are linked in a way that is broadly consistent with asset-pricing models of the exchange rate.I.IntroductionA long-standing puzzle in international economics is the difficulty of tying floating exchange rates to macroeconomic fundamentals such as money supplies,outputs,and interest rates.Our theories state that the exchange rate is determined by such fundamental variables,but floating exchange rates between countries with roughly similar inflation rates are in fact well approximated as random walks.Fundamental variables do not help predict future changes in exchange rates.Meese and Rogoff (1983a ,1983b )first established this result.They evaluated the out-of-sample fit of several models of exchange rates,using We thank Shiu-Sheng Chen,Akito Matsumoto,Benjamin T.West,and Yu Yuan for research assistance;the National Science Foundation for financial support;and two anon-ymous referees,the editor,and many seminar audiences for helpful comments.Portions of this paper were completed while West was a Houblon-Norman Fellow at the Bank of England and the Professorial Fellow in Monetary Economics at Victoria University and the Reserve Bank of New Zealand.486journal of political economy data from the1970s.They found that by standard measures of forecast accuracy,such as the mean-squared deviation between predicted and actual exchange rates,accuracy generally increased when one simply forecast the exchange rate to remain unchanged compared to when one used the predictions from the exchange rate models.While a large number of studies have subsequently claimed tofind success for various versions of fundamentals-based models,sometimes at longer horizons and over different time periods,the success of these models has not proved to be robust.A recent comprehensive study by Cheung,Chinn, and Pascual(2002,19)concludes that“the results do not point to any given model/specification combination as being very successful.On the other hand...,it may be that one model will do well for one exchange rate,and not for another.”In this paper,we take a new line of attack on the question of the link between exchange rates and fundamentals.We work with a conventional class of asset-pricing models in which the exchange rate is the expected present discounted value of a linear combination of observable fun-damentals and unobservable shocks.Linear driving processes are pos-ited for fundamentals and shocks.Wefirst present a theorem concerning the behavior of an asset price determined in a present-value model.We show analytically that in the class of present-value models we consider,asset prices will follow a pro-cess arbitrarily close to a random walk if(1)at least one forcing variable (observable fundamental or unobservable shock)has a unit autore-gressive root and(2)the discount factor is near unity.So,in the limit, as the discount factor approaches unity,the change in the time t assettϪ1 price will be uncorrelated with information known at time.We explain below that our result is not an application of the simple efficient markets model of Samuelson(1965)and others.When that model is applied to exchange rates,it implies that cross-country interest rate differentials will predict exchange rate changes and thus that exchange rates will not follow a random walk.Intuitively,as the discount factor approaches unity,the model puts relatively more weight on fundamentals far into the future in explaining the asset price.Transitory movements in the fundamentals become rel-atively less important than the permanent components.Imagine per-forming a Beveridge-Nelson decomposition on the linear combination of fundamentals that drive the asset price,expressing it as the sum of a random walk component and a transitory component.The class of theoretical models we are considering then expresses the asset price as the discounted sum of the current and expected future fundamentals. As the discount factor approaches one,the variance of the change of the discounted sum of the random walk component approaches infinity, whereas the variance of the change of the stationary component ap-exchange rates and fundamentals487 proaches a constant.So the variance of the change of the asset price is dominated by the change of the random walk component as the dis-count factor approaches one.We view as unexceptionable the assumption that a forcing variable has a unit root,at least as a working hypothesis for our study.The assumption about the discount factor is,however,open to debate.We note that in reasonable calibrations of some exchange rate models,this discount factor in fact is quite near unity.Of course our analytical result is a limiting one.Whether a discount factor of0.9or0.99or0.999is required to deliver a process statistically indistinguishable from a random walk depends on the sample size used to test for random walk behavior and the entire set of parameters of the model.Hence we present some correlations calculated analytically in a simple stylized model.We assume a simple univariate process for fundamentals,with parameters chosen to reflect quarterly data from the recentfloating period.Wefind that discount factors above0.9suffice to yield near-zero correlations between the period t exchange rate and tϪ1period information.We do not attempt to verify our theoretical conclusion that large discount factors account for random walk behavior in exchange rates using any particular fundamentals model from the literature.That is,we do not pick specific models that we claim satisfy the conditions of our theorem and then estimate them and verify that they produce random walks.But if the present-value models of exchange rates imply random walk behavior,so that exchange rate changes are unpredictable,how then can we validate the models?We ask instead if these conventional models have implications for whether the exchange rate helps predict funda-mentals.It is plausible to look in this direction.Surely much of the short-termfluctuation in exchange rates is driven by changes in expec-tations about the future.If the models are good approximations and expectations reflect information about future fundamentals,the ex-change rate changes will likely be useful in forecasting these funda-mentals.So these models suggest that exchange rates Granger-cause the ing quarterly bilateral dollar exchange rates,1974–2001,for the dollar versus the currencies of the six other Group of Seven countries,wefind some evidence of such causality,especially for nominal variables.The statistical significance of the predictability is not uniform and suggests a link between exchange rates and fundamentals that perhaps is modest in comparison with the links between other sets of economic variables.But in our view,the statistical predictability is notable in light of the far weaker causality from fundamentals to exchange rates.For countries and data series for which there is statistically significant evidence of Granger causality,we next gauge whether the Granger cau-488journal of political economy sality results are consistent with our models.We compare the correlation of exchange rate changes with two estimates of the change in the present discounted value of fundamentals.One estimate uses only the lagged value of fundamentals.The other uses both the exchange rate and own lags.Wefind that the correlation is substantially higher when the exchange rate is used in estimating the present discounted value.To prevent confusion,we note that ourfinding that exchange rates predict fundamentals is distinct from ourfinding that large discount factors rationalize a random walk in exchange rates.It may be reasonable to link the twofindings.When expectations of future fundamentals are very important in determining the exchange rate,it seems natural to pursue the question of whether exchange rates can forecast those fun-damentals.But one can be persuaded that exchange rates Granger-cause fundamentals and still argue that the approximate random walk in exchange rates is not substantially attributable to a large discount factor. In the class of models we consider,all our empirical results are consistent with at least one other explanation,namely,that exchange rate move-ments are dominated by unobserved shocks that follow a random walk. The plausibility of this explanation is underscored by the fact that we generally fail tofind cointegration between the exchange rate and ob-servable fundamentals,a failure that is rationalized in our class of models by the presence of an I(1)(though not necessarily random walk)shock. As well,the random walk also can arise in models that fall outside the class we consider.It does so in models with small-sample biases,perhaps combined with nonlinearities/threshold effects(see Taylor,Peel,and Sarno2001;Kilian and Taylor2003;Rossi2003).Exchange rates will still predict fundamentals in such models,though a nonlinear fore-casting process may be required.Our suggestion that the exchange rate will nearly follow a random walk when the discount factor is close to unity means that forecasting changes in exchange rates is difficult but perhaps still possible.Some recent studies have found success at forecasting changes in exchange rates at longer horizons or using nonlinear methods,and further re-search along these lines may prove fruitful.MacDonald and Taylor (1994),Chinn and Meese(1995),and Mark(1995)have all found some success in forecasting exchange rates at longer horizons imposing long-run restrictions from monetary models.Groen(2000)and Mark and Sul(2001)find greater success using panel methods.Kilian and Taylor (2003)suggest that models that incorporate nonlinear mean reversion can improve the forecasting accuracy of fundamentals models,though it will be difficult to detect the improvement in out-of-sample forecasting exercises.The paper is organized as follows.Section II presents the theorem that the random walk in asset prices may result from a discount factorexchange rates and fundamentals 489near one in a present-value model.Section III demonstrates how the theorem applies to some models of exchange rates.Section IV presents evidence that changes in exchange rates help predict fundamentals.Section V presents conclusions.The Appendix has some algebraic de-tails.An additional appendix containing empirical results omitted from the paper to save space is available on request.II.Random Walk in Asset Prices as the Discount Factor Goes toOneWe consider models in which an asset price,,can be expressed as a s t discounted sum of current and expected future “fundamentals.”We examine asset-pricing models of the formϱϱj j s p (1Ϫb )b E (a x )ϩb b E (a x ),0!b !1,(1)t t 1t ϩj t 2t ϩj j p 0j p 0where is the vector of fundamentals,b is a discount factor,and x n #1t and are vectors.For example,the model for stock prices a a n #112considered by Campbell and Shiller (1987)and West (1988)has this form,where is the level of the stock price,the dividend (a scalar),s x t t ,and .The log-linearized model of the stock price of a p 0a p 112Campbell and Shiller (1988)also has this form,where is the log of s t the stock price,is the log of the dividend,,and .The x a p 1a p 0t 12term structure model of Campbell and Shiller also is a present-value model,where is the yield on a consol,is the short-term rate,s x t t ,and .In Section III,we review models in which is the a p 1a p 0s 12t log of the exchange rate and contains such variables as interest rates x t and logs of prices,money supplies,and income.We spell out here the sense in which the asset price should follow a random walk for a discount factor b that is near one.Assume that at least one element of the vector is an I(1)process,whose Wold in-x t novation is the vector .Our result requires that either (1)n #1e t and or (2),with the order of integration a x ∼I(1)a p 0a x ∼I(1)1t 22t of essentially unrestricted (I(0),I(1),or identically zero).In either a x 1t case,for b near one,will be well approximated by a linear combi-D s t nation of the elements of the unpredictable innovation .In a sense e t made precise in the Appendix,this approximation is arbitrarily good for b arbitrarily near one.This means,for example,that all autocor-relations of will be very near zero for b very near one.D s t Of course,there is continuity in the autocorrelations in the following sense:for b near one,the autocorrelations of will be near zero if the D s t previous paragraph’s condition that certain variables are I(1)is replaced with the condition that those variables are I(0)but with an autoregres-490journal of political economy TABLE 1Population Autocorrelations and Cross Correlations of D s tb (1)J 1(2)J (3)Correlation of with :D s t D s t Ϫ1(4)D s t Ϫ2(5)D s t Ϫ3(6)D x t Ϫ1(7)D x t Ϫ2(8)D x t Ϫ3(9)1..50 1.0.3.15.05.01.16.05.012..5.27.14.07.28.14.073..8.52.42.34.56.44.364..90 1.0.3.03.01.00.03.01.005..5.05.03.01.06.03.016..8.09.07.06.13.11.097..95 1.0.3.02.01.00.02.01.008..5.03.01.01.03.01.019..8.04.04.03.07.05.0410..90.90.5.04Ϫ.01Ϫ.03.02Ϫ.03Ϫ.0511..90.95.5.05.01Ϫ.01.04Ϫ.00Ϫ.0212..95.95.5.02Ϫ.00Ϫ.01.01Ϫ.02Ϫ.0313..95.99.5.02.01.00.03.01Ϫ.00Note.—The model is or .The scalar variable follows an AR(2)process with ϱϱj j s p (1Ϫb )b E x s p b b E x x t t t ϩj t t t ϩj t j p 0j p 0autoregressive roots and J .When ,with parameter J .The correlations in cols.4–9were computed J J p 1.0D x ∼AR(1)11t analytically.If ,as in rows 1–9,then in the limit,as ,each of these correlations approaches zero.J p 1.0b r 11sive root very near one.For a given autoregressive root less than one,the autocorrelations will not converge to zero as b approaches one.But they will be very small for b very near one.Table 1gives an indication of just how small “small”is.The table gives correlations of with time information when follows a scalar D s t Ϫ1x t t univariate AR(2).(One can think of and or and a p 0a p 1a p 1121.One can consider these two possibilities interchangeably since,a p 02for given ,the autocorrelations of are not affected by whether b !1D s t or not a factor of multiplies the present value of fundamentals.)1Ϫb Rows 1–9assume that —specifically,with parameter x ∼I(1)D x ∼AR(1)t t J .We see that for the autocorrelations in columns 4–6and the b p 0.5cross correlations in columns 7–9are appreciable.Specifically,suppose that one uses the conventional standard error of .Then when ͱ1/T ,a sample size larger than 55will likely suffice to reject the null J p 0.5that the first autocorrelation of is zero (since row 2,col.5,gives D s t and ).(In this argument,ͱcorr(D s ,D s )p 0.2690.269/[1/55]≈2.0t t Ϫ1we abstract from sampling error in estimation of the autocorrelation.)But for ,the autocorrelations are dramatically smaller.For b p 0.9and ,a sample size larger than 1,600will be required,b p 0.9J p 0.5since .Finally,in connection with the previous ͱ0.051/(1/1,600)≈2.0paragraph’s reference to autoregressive roots less than one,we see in rows 10–13in the table that if the unit root in is replaced by an x t autoregressive root of 0.9or higher,the autocorrelations and cross cor-relations of are not much changed.D s texchange rates and fundamentals 491To develop intuition on this result,consider the following example.Suppose that the asset price is determined by a simple equation:s p (1Ϫb )m ϩb r ϩbE (s ).t t t t t ϩ1The “no-bubbles”solution to this expectational difference equation is a present-value model like (1):ϱϱj j s p (1Ϫb )b E m ϩb b E r .t t t ϩj t t ϩj j p 0j p 0Assume that the first differences of the fundamentals follow first-order autoregressions:D m p fD m ϩe ;Dr p gDr ϩe .t t Ϫ1mt t t Ϫ1r t Then we can write the solution asf (1Ϫb )1bg b D s p D m ϩe ϩDr ϩe .t t Ϫ1mt t Ϫ1r t 1Ϫb f 1Ϫb f 1Ϫb g (1Ϫb )(1Ϫb g )Consider first the special case of .Then as ,r p 0b r 1D s ≈[1/(1Ϫt t .In this case,the variance of the change in the exchange rate is f )]e mt finite as .If ,then as ,.In this case,b r 1r (0b r 1D s ≈constant #e t t r t as b increases,the variance of the change in the exchange rate gets large,but the variance is dominated by the independently and identi-cally distributed term .e r t In Section III,we demonstrate the applicability of this result to exchange rates.III.Exchange Rate ModelsExchange rate models since the 1970s have emphasized that nominal exchange rates are asset prices and are influenced by expectations about the future.The “asset market approach to exchange rates”refers to models in which the exchange rate is driven by a present discounted sum of expected future fundamentals.Obstfeld and Rogoff (1996,529)say that “one very important and quite robust insight is that the nominal exchange rate must be viewed as an asset price .Like other assets,the exchange rate depends on expectations of future variables”(italics in the original).Frenkel and Mussa’s (1985)survey explains the asset market approach:These facts suggest that exchange rates should be viewed as prices of durable assets determined in organized markets (like stock and commodity exchanges)in which current prices re-flect the market’s expectations concerning present and future492journal of political economyeconomic conditions relevant for determining the appropriate values of these durable assets,and in which price changes are largely unpredictable and reflect primarily new information that alters expectations concerning these present and future economic conditions.(726)A variety of models relate the exchange rate to economic fundamen-tals and to the expected future exchange rate.We write this relationship ass p (1Ϫb )(f ϩz )ϩb (f ϩz )ϩbE s .(2)t 1t 1t 2t 2t t t ϩ1Here,we define the exchange rate as the log of the home currency s t price of foreign currency (dollars per unit of foreign currency if the United States is the home country).The terms and ()are f z i p 1,2it it economic fundamentals that ultimately drive the exchange rate,such as money supplies,money demand shocks,productivity shocks,and so forth.We differentiate between fundamentals that are observable to the econometrician,,and those that are not observable,.One possibility f z it it is that the true fundamental is measured with error,so that is the f it measured fundamental and the include the measurement error;an-z it other is that the are unobserved shocks.z it Upon imposing the “no-bubbles”condition that goes to zero j b E s t t ϩj as ,we have the present-value relationshipj r ϱϱϱj j s p (1Ϫb )b E (f ϩz )ϩb b E (f ϩz ).(3)t t 1t ϩj 1t ϩj t 2t ϩj 2t ϩj j p 0j p 0This equation has the form of equation (1),where we have a x p1t ϩj and .We now outline some models thatf ϩz a x p f ϩz 1t ϩj 1t ϩj 2t ϩj 2t ϩj 2t ϩj fit into this framework.A.Money Income ModelConsider first the familiar monetary models of Frenkel (1976),Mussa (1976),and Bilson (1978)and their close cousins,the sticky-price mon-etary models of Dornbusch (1976)and Frankel (1979).Assume that in the home country there is a money market relationship given bym p p ϩg y Ϫa i ϩv .(4)t t t t mt Here,is the log of the home money supply,is the log of the home m p t t price level,is the level of the home interest rate,is the log of output,i y t t and is a shock to money demand.Here and throughout we use the v mt term “shock”in a somewhat unusual sense.Our “shocks”potentially include constant and trend terms,may be serially correlated,and mayexchange rates and fundamentals493 include omitted variables that in principle could be measured.Assume that a similar equation holds in the foreign country.The analogousm*p*i*y*v*foreign variables are,,,,and,and the parameters of thet t t t mtforeign money demand are identical to the home country’s parameters. The nominal exchange rate equals its purchasing power parity(PPP) value plus the real exchange rate:s p pϪp*ϩq.(5)t t t tInfinancial markets,the interest parity relationship isE sϪs p iϪi*ϩr.(6)t tϩ1t t t trHere is the deviation from rational expectations uncovered interest tparity.It can be interpreted as a risk premium or an expectational error. Putting these equations together and rearranging,we get1s p[mϪm*Ϫg(yϪy*)ϩqϪ(vϪv*)Ϫar]t t t t t t mt mt t1ϩaaϩE s.(7)t tϩ11ϩaThis equation takes the form of equation(2)when the discount factorb p a/(1ϩa)is given by,the observable fundamentals are given by f p mϪm*Ϫg(yϪy*)z p qϪ(vϪ,and the unobservables are1t t t t t1t t mtv*)z pϪrand.As in Mark(1995),our empirical work in Section IV mt2t tg p1f p sets.We also investigate a version of this model setting1t and moving to.We do so largely because we wish to mϪm*yϪy*zt t t t1tconduct a relatively unstructured investigation into the link between exchange rates and various measures of fundamentals.But we couldmϪm*argue that we focus on becausefinancial innovation has madet tstandard income measures poor proxies for the level of transactions.s yϪy* Similarly,we investigate the relationship between and.t t t Equation(7)is implied by both theflexible-price and sticky-price versions of the monetary model.In theflexible-price monetarist modelsyof Frenkel(1976),Mussa(1976),and Bilson(1978),output,,and thetreal exchange rate,,are exogenous.In the sticky-price models ofqtDornbusch(1976)and Frankel(1979),these two variables are endog-enous.Because nominal prices adjust slowly,the real exchange rate is influenced by changes in the nominal exchange rate.Output is demand determined and may respond to changes in the real exchange rate, income,and real interest rates.Nonetheless,since equations(4)(and its foreign counterpart),(5),and(6)hold in the Dornbusch-Frankel model,one can derive relationship(7)in those models.Dornbusch and Frankel each consider special cases for the exogenous monetary pro-cesses(in Dornbusch’s model,all shocks to the money supply are per-494journal of political economy manent;Frankel considers permanent shocks to the level and to the growth rate of money).As a result of their assumption that all shocks are permanent,they each can express the exchange rate purely in terms of current fundamentals,which may obscure the general implication that exchange rates depend on expected future fundamentals.We note here that some recent exchange rate models developed from the “new open economy macroeconomics”yield relationships very sim-ilar to the ones we describe in this section.For example,in Obstfeld and Rogoff (2003),the exchange rate is given by (their eq.[30])ϱj s p b E [(1Ϫb )(m Ϫm *)Ϫb r ],(8)t t t ϩj t ϩj t ϩj j p 0where we have translated their notation to be consistent with ours.Equation (8)is in fact the forward solution to a special case of equation(7)above.The discount factor,b ,in Obstfeld and Rogoff’s model is related to the semi-elasticity of money demand exactly as in equation(7).However,their money demand function is derived from a utility-maximizing framework in which real balances appear in the utility func-tion,and their risk premium is derived endogenously from first r t principles.B.Taylor Rule ModelHere we draw on the burgeoning literature on Taylor rules.Let p p t denote the inflation rate and be the “output gap.”We assume g p Ϫp y t t Ϫ1t that the home country (the United States in our empirical work)follows a Taylor rule of the formg i p b y ϩb p ϩv .(9)t 1t 2t t In (9),,,and the shock contains omitted terms.1b 10b 11v 12t The foreign country follows a Taylor rule that explicitly includes exchange rates:g ¯i *p Ϫb (s Ϫs *)ϩb y *ϩb p *ϩv *.(10)t 0t t 1t 2t t In (10),,and is a target for the exchange rate.We shall ¯0!b !1s*0t 1Much of the Taylor rule literature—wisely,in our view—puts expected inflation in the monetary policy rule.Among other benefits,this facilitates thinking of the monetary authority as setting an ex ante real rate.We use actual inflation for notational simplicity.If expected inflation is in the monetary rule,then inflation in the formulas below is replaced by expected inflation.exchange rates and fundamentals495 assume that monetary authorities target the PPP level of the exchange rate:¯s*p pϪp*.(11)t t tsSince is measured in dollars per unit of foreign currency,the rule tindicates that,ceteris paribus,the foreign country raises interest rates when its currency depreciates relative to the target.Clarida,Gali,and Gertler(1998)estimate monetary policy reaction functions for Germany and Japan(using data from1979–94)of a form similar to equation(10). Theyfind that a1percent real depreciation of the mark relative to the dollar led the Bundesbank to increase interest rates(expressed in an-nualized terms)byfive basis points,whereas the Bank of Japan increased rates by nine basis points in response to a real yen depreciation relative to the dollar.As the next equation makes clear,our argument still follows if the United States were also to target exchange rates.We omit the exchange rate target in(9)on the interpretation that U.S.monetary policy has virtually ignored exchange rates except,perhaps,as an indicator. Subtracting the foreign from the home money rule,we obtaing g¯iϪi*p b(sϪs*)ϩb(yϪy*)ϩb(pϪp*)ϩvϪv*.(12)t t0t t1t t2t t t tiϪi*Use interest parity(6)to substitute out for and(11)to sub-t tstitute out for the exchange rate target:b10g gs p(pϪp*)Ϫ[b(yϪy*)ϩb(pϪp*)t t t1t t2t t1ϩb1ϩb001ϩvϪv*ϩr]ϩE s.(13) t t t t tϩ11ϩbThis equation has the general form of(2)of the expected discounted1/(1ϩb) present-value models.The discount factor is equal to.Wef p pϪp*have.In our empirical work(in Sec.IV),we shall treat the 1t t tremaining variables as unobservable,so we haveg gz pϪ[b(yϪy*)ϩb(pϪp*)ϩvϪv*ϩr].2t1t t2t t t t tEquation(12)can be expressed another way,again using interest parity(6)and the equation for the target exchange rate(11):g gs p b(iϪi*)ϩb(pϪp*)Ϫb(yϪy*)Ϫb(pϪp*)t0t t0t t1t t2t tϪvϩv*Ϫ(1Ϫb)rϩ(1Ϫb)E s.(14) t t0t0t tϩ1This equation is very much like(13),except that it incorporates the interest differential,,as a“fundamental.”The discount factor iniϪi*t t496journal of political economythis formulation is given by .The observed fundamental is given1Ϫb 0by .In our empirical work,we treat the remainingf p i Ϫi *ϩp Ϫp *1t t t t t period t variables in equation (14)as unobserved.C.DiscussionWe begin by noting that the classic efficient markets model of Samuelson(1965)and others does not predict a random walk in exchange rates.The essence of this model is that there are no predictable profit op-portunities for a risk-neutral investor to exploit.If the U.S.interest rateis higher than the foreign interest rate by x percent,then the U.S.i i *t t dollar must be expected to fall by x percent over the period of theinvestment if there are to be no such opportunities.In terms of equation(6),then,the classic efficient markets model says that the risk premiumis zero and that a population regression of on will yieldr D s i Ϫi *t t ϩ1t t a coefficient of one.(For equities,the parallel prediction is that on theday on which a stock goes ex-dividend,its price should fall by the amountof the dividend [e.g.,Elton and Gruber 1970].)Our explanation yields a random walk approximation even when,asin the previous paragraph,uncovered interest parity holds.The readermay wonder how the data can simultaneously satisfy the following con-ditions:(1)a regression of on yields a nonzero coefficient,D s i Ϫi *t ϩ1t t and (2)is arbitrarily well approximated as a random walk (i.e.,s t is arbitrarily well approximated as white noise).The answer is thatD s t ϩ1when b is arbitrarily close to one,the of the regression of on2R D s t ϩ1will be arbitrarily close to zero and the correlation of withi Ϫi *D s t t t ϩ1will be arbitrarily small.It is in those senses that the random walki Ϫi *t t approximation will be arbitrarily good.The key question is not the logic of our result but its empirical validity.The result does not require uncovered interest parity,which was main-tained in the previous two paragraphs merely to clarify the relation ofour result to the standard efficient markets result.Instead,two condi-tions are required.The first is that fundamentals variables be very per-sistent—I(1)or nearly so.This is arguably the case with our data onthe observed fundamentals.We shall present evidence in Section IV thatwe cannot reject the null of a unit root in any of our data.Further,there is evidence in other research that the unobservable variables arevery persistent.For the money income model (eq.[7]),this is suggestedfor ,,and by the literature on money demand (e.g.,Sriram 2000),v q r mt t t PPP (e.g.,Rogoff 1996),and interest parity (e.g.,Engel 1996).(Werecognize that theory suggests that a risk premium like is I(0);ourr t interpretation is that if is I(0),it has a very large autoregressive root.)r t We are not concerned if or other variables are highly persistent I(0)r t。
THE HUMANISTIC APPROACHContentsIntroduction to the Humanistic ApproachCarl RogersAbraham MaslowExistential PsychologyExtending the Humanistic ApproachApplying the Concepts: Maslow's Hierarchy in the WorkplacePublications Related to the Humanistic ApproachIntroduction to the Humanistic ApproachThe Humanistic Approach began in response to concerns by therapists against perceived limitations of Psychodynamic theories, especially psychoanalysis. Individuals like Carl Rogers and Abraham Maslow felt existing (psychodynamic) theories failed to adequately address issues like the meaning of behaviour, and the nature of healthy growth. However, the result was not simply new variations on psychodynamic theory, but rather a fundamentally new approach.There are several factors which distinguish the Humanistic Approach from other approaches within psychology, including the emphasis on subjective meaning, a rejection of determinism, and a concern for positive growth rather than pathology. While one might argue that some psychodynamic theories provide a vision of healthy growth (including Jung's concept of individuation), the other characteristics distinguish the Humanistic Approach from every other approach within psychology (and sometimes lead theorists from other approaches to say the Humanistic Approach is not a science at all). Most psychologists believe that behaviour can only be understood objectively (by an impartial observer), but the humanists argue that this results in concluding that an individual is incapable of understanding their own behaviour – a view which they see as both paradoxical and dangerous to well-being. Instead, humanists like Rogers argue that the meaning of behaviour is essentially personal and subjective; they further argue that accepting this idea is not unscientific, because ultimately all individuals are subjective: what makes science reliable is not that scientists are purely objective, but that the nature of observed events can be agreed upon by different observers (a process Rogers calls intersubjective verification).The issues underlying the Humanistic Approach, and its differences from other approaches, are discussed more fully in the text, but the sources below provide usefulsupplementary information. One point worth noting: if you want to fully grasp the nature of the Humanistic Approach, you cannot consider it in abstract terms. Instead, you must consider if and how the ideas connect to your own experience – for that is how the meaning of behaviour is derived!ResourcesAbout Humanistic PsychologyIntroductory discussion of history and nature of the humanistic approach, by the Association for Humanistic PsychologyA Guide to Humanistic PsychologyExtensive introduction, broken into chapters by topic, by John Rowan, Assoc. for Humanistic Psychology; chapters include bibliographies for further reading.Carl RogersCarl Rogers was not only one of the founders of the Humanistic Approach, but also arguably the most influential therapist in the 20th century: a number of surveys, including several done after his death, found that more therapists cited Rogers as a major influence on their thinking and clinical practice than any other person in psychology (including Freud). To understand this, one must know something about Rogers as a person, as well as his theoretical ideas.I never met him, but have seen several videos of him, and have read a number of accounts, both biographical and anecdotal, by individuals who know him well. Consistently, what comes across is a person who was caring and respectful of others, a man who found value in all people, yet was humble about his own achievements – in many ways, he represented the fully functioning person which his theory describes! In terms of his theory, there are two fundamental ideas which are particularly worth noting. (For a more complete discussion, see the text.) First, Rogers talked about healthy development in terms of how the individual perceived their own being. A healthy individual will tend to see congruence between their sense of who they are (self) and who they feel they should be (ideal self). While no one tends to experience perfect congruence at all times, the relative degree of congruence is an indicator of health. Some researchers have tried to measure congruence by using a self-assessment technique called a Q-Sort. (If you are interested in exploring this, click here for a version of a Q-sort I've created.)The second fundamental idea is Rogers's concept of the conditions for healthy growth, and the role of a therapist in fostering healthy growth. Through a process Rogers called person-centred therapy, the therapist seeks to provide empathy, openness, and unconditional positive regard. These conditions for growth are discussed further in the text; for information on person-centred therapy, see the links below. (Onenote about person-centred therapy: originally, Rogers called his technique non-directive therapy, based on the concept that the therapist is simply a ‘mirror’ who reflects the individual's thoughts and feelings. As his own research showed, no therapist is truly non-directive – and if they were, it would likely be poor therapy, as the following joke illustrates!)ResourcesCarl RogersBiography and other material, on site maintained by his daughter, Natalie Rogers (who is also trained as a therapist).Carl Rogers and EducationSite providing biographical information as well as examination of Rogers's ideas about education.Introduction to Person-Centred CounsellingA clear overview by Dr. Greg Mulhauser, on .Abraham MaslowLike Carl Rogers, Abraham Maslow is widely regarded as one of the founders of the Humanistic Approach. While less influential among therapists than Rogers, Maslow may actually be better known to the general public, because of his interest in applying psychological principles to areas like behaviour in business settings. In this regard, his hierarchy of needs has been a basic concept in human resources and organisational behaviour for several decades.Maslow coined the term "the Third Force" to describe the Humanistic Approach, to emphasise how it differed from the Psychodynamic and Behaviourist Approaches, which dominated psychology (at least in North America) in the 1950s. His theory emphasises motivation as the key to understanding human behaviour (an emphasis which is somewhat reminiscent of Freud's theory, though the two models focus on very different types of motives). Nonetheless, it becomes the basis of a theory of personality (as discussed in the text, talking about motives implies a person who experiences those motives!), and ends up describing the characteristics of healthy growth in ways that are very similar to Rogers's "fully functioning person".One difference between Maslow and Rogers is the emphasis that Maslow gave to peak experiences. Peak experiences are moments in life which take us beyond our ordinary perceptions, thoughts, and feelings. Typically, the individual feels energised, more‘alive’. In some ways, peak experiences are similar to the Zen concept of satori (literally ‘enlightenment’), which, like a peak experience, comes unexpectedly, and transforms the individual's understanding of themselves and the world. Because of the ‘mystical’ natureof peak experiences, some psychologists are less comfortable with Maslow's theory than with Rogers's, which uses concepts more easily related to ‘mainstream’ psychology. Possibly, this accounts for Maslow being viewed as less influential among therapists. In any case, there is no doubt that Maslow's ideas about motivation have become widely known and used, as the links below help to illustrate.ResourcesAbraham Provides full listing of his publications, and links to other Maslow-related sites.People and Discoveries: Abraham MaslowBrief biography from A Science Odyssey, PBS series on famous discoverers. Abraham MaslowChapter from Dr. George Boeree's online personality textbook.Revisiting MaslowDiscussion of relevance of Maslow's ideas for education and living; part of New Horizons for Learning website.Existential PsychologyAs in many areas of psychology, there are close linkages between the Humanistic Approach and philosophy. For example, Rogers's concept of the phenomenal field as the basis of defining the self can be linked to the ideas of phenomenological philosophers like Edmund Husserl. Similarly, the existentialist tradition began with European philosophers like Soren Kierkegaard and Jean-Paul Sartre. While its roots extend back to the turn of the 20th century (and some would say even earlier), it really gained momentum as a result of World War II, whose devastation and destruction gave a sense of immediacy to questions about the purpose of living. (For example, Albert Camus, a leading existentialist writer, was a member of the French Resistance.) Existentialists start from the premise that there is no absolute meaning to life, and hence that life in a purely rational sense is without purpose. Interestingly, however, from this bleak beginning, many arrive at interpretations that nonetheless affirm a value to life. Asking about what life means to an individual provides an overlapping area of concern between existentialism and humanistic psychology, since the humanists seek to identify a positive model for human growth. As a result, while some psychologists prefer one term over the other, the theories often share a focus on similar kinds of issues, especially the questions of what an individual finds meaningful in life, and how individuals deal with the prospect of death. Among the psychologists who have developed theories related to existential ideas are Rollo May, Ernest Becker, and ViktorFrankl. Of these, Frankl is arguably the best known to the general public; his best-known book, Man's Search for Meaning, went through multiple editions and reprintings, and was translated into dozens of languages. Frankl, who began as a doctor and therapist in Vienna, was a prisoner in various Nazi concentration camps during the war, and it was partly his exposure to the horrors of the camps that contributed to his existentialist orientation. To learn more about him and other existential psychologists, and how their ideas relate to humanistic theories more generally, see the text or the following links.ResourcesMeaningful TherapyBasic introduction to existential forms of therapy, with links to material on particular therapists/theorists, including Frankl; part of International Network on Personal Meaning site, in Vancouver, Canada.Viktor Frankl InstituteOfficial website for Institute founded by Frankl; contains biography, videos, and other material on Frankl and his work.Viktor FranklBiography, discussion of Frankl's ideas, and large set of links to other sites on Frankl and existentialism; by Boston psychotherapist Tracy Marks.The Existential PrimerProvides a variety of material related to existentialism, especially its philosophical origins, by a non-psychologist, Christopher Scott Wyatt.Extending the Humanistic ApproachIn recent years, a number of initiatives have appeared which, while influenced significantly by humanistic ideas and theories, have in new directions. Perhaps the most significant is positive psychology, a term coined by Dr. Martin Seligman when he was President of the American Psychological Association in 2000. Positive psychology, like the humanistic approach, focusses on enhancing human potential--but embraces research methods (e.g., surveys, group data) which humanists have traditionally avoided. Another area influenced by the humanistic approach has been coaching psychology. While the term originated in "personal coaching" in sports, it more generally refers to a focus on enhancing individual potential, and the field has gradually become a specific area within many psychology associations.ResourcesPositive Psychology Center--Website for Seligman's research group at the University of Pennsylvania; provides a variety of information and resources.Authentic Happiness--An offshoot of Seligman's work (the title comes from one of his books), but more focussed on providing resources for individuals (including a variety of self-test questionnaires).Special Group in Coaching Psychology--Site for section of British Psychological Society; includes a variety of background information, as well as on-line articles.Applying the Concepts: Maslow's Hierarchy in the Workplace Several researchers in the 1950s recognised the practical importance of Abraham Maslow's hierarchy of needs to the working world. It was not difficult to establish that for nonmanagement workers, jobs mainly fulfilled the basic physical and security needs of the individual: if the work is done, the worker is paid and more-or-less assured of being paid for subsequent work. Higher order needs, such as social, esteem and self-actualisation needs were not considered. Lyman Porter (1961) at the University of California at Berkeley, suggested that higher needs might be of more concern on the management level of an organisation. He saw that people in most organisations received promotions from one job to another based on their technical qualifications, but nothing else. That is, it was assumed that because an individual could do the job, that job was the best one for him or her. There was no indication that anyone regarded the psychological satisfaction with a job as being an important factor. Consequently, people might sometimes be promoted out of jobs that gave them satisfaction into jobs that were less satisfying for them, potentially rendering them less effective in their work. Porter realised that for individual satisfaction and for organisational efficiency, it was necessary to discover how people perceived their jobs in terms of need satisfaction, as Maslow had outlined. Knowing this might allow organisations to match people to jobs that they were not only qualified for, but which would give them the most satisfaction as well.In order to study this, Porter sent a fixed alternative survey to 228 people in three companies. These people worked at different managerial levels, from bottom level supervisors or foremen up to middle level management who were just below vice presidency or major department head. The survey studied 15 characteristics or qualities that Porter thought were connected with management positions and were relevant to Maslow's need hierarchy. For example, to determine whether esteem needs were being met by the job, Porter asked about the prestige of a managerial position; to determine whether social needs were being met by the job, he asked about the opportunities to develop friendships on the job; to determine whether self-actualisation needs were being met by the job, he asked about feelings of self-fulfillment derived from the individual's working position. The respondents to the survey were asked to indicate on a 7-point scale (with 1 indicating the lowest amount and 7 indicating the highest amount) first, how much of that quality was connected with the individual's management position; second, how much of that quality should be connected with the individual's management position; and third, how important that quality was to the respondent. So questions on the survey might look like this:The feeling of self-esteem a person gets from being in my management position:a) How much is there now? (min) 1 2 3 4 5 6 7 (max)b) How much should there be? (min) 1 2 3 4 5 6 7 (max)c) How important is this to me? (min) 1 2 3 4 5 6 7 (max)Of the 228 people who were given the survey, 139 (61%) filled it out. While Porter attempted to give the surveys to a representative sample of low to middle management personnel, it cannot be claimed that the individuals who actually returned the survey constitute such a sample, so the results of this study must be interpreted with caution. Porter found that among these respondents, there was no difference in the amount of fulfillment of social needs, and that esteem needs are more often satisfied in middle management than in low management levels, not surprisingly. But in both low and middle management, the respondents indicated that self-actualisation needs are of great importance to them, but there were few opportunities for these needs to be fulfilled at work. It seems, then, that among the people who answered this survey, at least, their work did not offer them a sense of self-fulfillment, or an opportunity for personal growth and development or a feeling of worthwhile accomplishment. It would be expected that in higher management, the level at which policy decisions are made, there may be a greater chance to find areas of self-actualisation.What are the implications of this study? While we must be careful in making conclusions since a survey cannot demonstrate a causal relationship and since we have no way of knowing whether the sample was indeed representative of the population, we may still make some tentative conclusions. Most of us spend almost 30% of our lives at work, and yet this work may not give us the opportunity to pursue what we find important: self-actualisation. Our deficiency needs may be met to a greater or lesser extent, but our growth needs may not. What if our work gave us opportunity to fulfill growth needs, though? What if the organisation we work for allowed us to help make the policy decisions that would affect the well-being of ourselves and others, for example? Orpen (1998) has found that among the respondents to his survey, job satisfaction is indeed greater when there is more opportunity for such decision-making. Did his respondents feel greater satisfaction because this gave them a chance to pursue self-actualisation? We don't know, but maybe.ReferencesOrpen, C. (1998). The effects of organisational centrality on employee success and satisfaction. Social Behaviour and Personality, 26. 85-88.Porter, L. (1961). A study of perceived need satisfactions in bottom and middle management jobs. Journal of Applied Psychology, 45. 1-10.Publications Related to the Humanistic ApproachJournal of Humanistic PsychologyPublished by the Association for Humanistic Psychology; has monthly contents, and searchable archive of contents, but no open access to articles.The Humanistic PsychologistJournal of APA Division on Humanistic Psychology; contains article titles listed by author, but no online archive.© William Glassman and Marilyn Hadad, 2008.。
英语专业八级考试TEM-8阅读理解练习册(1)(英语专业2012级)UNIT 1Text AEvery minute of every day, what ecologist生态学家James Carlton calls a global ―conveyor belt‖, redistributes ocean organisms生物.It’s planetwide biological disruption生物的破坏that scientists have barely begun to understand.Dr. Carlton —an oceanographer at Williams College in Williamstown,Mass.—explains that, at any given moment, ―There are several thousand marine species traveling… in the ballast water of ships.‖ These creatures move from coastal waters where they fit into the local web of life to places where some of them could tear that web apart. This is the larger dimension of the infamous无耻的,邪恶的invasion of fish-destroying, pipe-clogging zebra mussels有斑马纹的贻贝.Such voracious贪婪的invaders at least make their presence known. What concerns Carlton and his fellow marine ecologists is the lack of knowledge about the hundreds of alien invaders that quietly enter coastal waters around the world every day. Many of them probably just die out. Some benignly亲切地,仁慈地—or even beneficially — join the local scene. But some will make trouble.In one sense, this is an old story. Organisms have ridden ships for centuries. They have clung to hulls and come along with cargo. What’s new is the scale and speed of the migrations made possible by the massive volume of ship-ballast water压载水— taken in to provide ship stability—continuously moving around the world…Ships load up with ballast water and its inhabitants in coastal waters of one port and dump the ballast in another port that may be thousands of kilometers away. A single load can run to hundreds of gallons. Some larger ships take on as much as 40 million gallons. The creatures that come along tend to be in their larva free-floating stage. When discharged排出in alien waters they can mature into crabs, jellyfish水母, slugs鼻涕虫,蛞蝓, and many other forms.Since the problem involves coastal species, simply banning ballast dumps in coastal waters would, in theory, solve it. Coastal organisms in ballast water that is flushed into midocean would not survive. Such a ban has worked for North American Inland Waterway. But it would be hard to enforce it worldwide. Heating ballast water or straining it should also halt the species spread. But before any such worldwide regulations were imposed, scientists would need a clearer view of what is going on.The continuous shuffling洗牌of marine organisms has changed the biology of the sea on a global scale. It can have devastating effects as in the case of the American comb jellyfish that recently invaded the Black Sea. It has destroyed that sea’s anchovy鳀鱼fishery by eating anchovy eggs. It may soon spread to western and northern European waters.The maritime nations that created the biological ―conveyor belt‖ should support a coordinated international effort to find out what is going on and what should be done about it. (456 words)1.According to Dr. Carlton, ocean organism‟s are_______.A.being moved to new environmentsB.destroying the planetC.succumbing to the zebra musselD.developing alien characteristics2.Oceanographers海洋学家are concerned because_________.A.their knowledge of this phenomenon is limitedB.they believe the oceans are dyingC.they fear an invasion from outer-spaceD.they have identified thousands of alien webs3.According to marine ecologists, transplanted marinespecies____________.A.may upset the ecosystems of coastal watersB.are all compatible with one anotherC.can only survive in their home watersD.sometimes disrupt shipping lanes4.The identified cause of the problem is_______.A.the rapidity with which larvae matureB. a common practice of the shipping industryC. a centuries old speciesD.the world wide movement of ocean currents5.The article suggests that a solution to the problem__________.A.is unlikely to be identifiedB.must precede further researchC.is hypothetically假设地,假想地easyD.will limit global shippingText BNew …Endangered‟ List Targets Many US RiversIt is hard to think of a major natural resource or pollution issue in North America today that does not affect rivers.Farm chemical runoff残渣, industrial waste, urban storm sewers, sewage treatment, mining, logging, grazing放牧,military bases, residential and business development, hydropower水力发电,loss of wetlands. The list goes on.Legislation like the Clean Water Act and Wild and Scenic Rivers Act have provided some protection, but threats continue.The Environmental Protection Agency (EPA) reported yesterday that an assessment of 642,000 miles of rivers and streams showed 34 percent in less than good condition. In a major study of the Clean Water Act, the Natural Resources Defense Council last fall reported that poison runoff impairs损害more than 125,000 miles of rivers.More recently, the NRDC and Izaak Walton League warned that pollution and loss of wetlands—made worse by last year’s flooding—is degrading恶化the Mississippi River ecosystem.On Tuesday, the conservation group保护组织American Rivers issued its annual list of 10 ―endangered‖ and 20 ―threatened‖ rivers in 32 states, the District of Colombia, and Canada.At the top of the list is the Clarks Fork of the Yellowstone River, whereCanadian mining firms plan to build a 74-acre英亩reservoir水库,蓄水池as part of a gold mine less than three miles from Yellowstone National Park. The reservoir would hold the runoff from the sulfuric acid 硫酸used to extract gold from crushed rock.―In the event this tailings pond failed, the impact to th e greater Yellowstone ecosystem would be cataclysmic大变动的,灾难性的and the damage irreversible不可逆转的.‖ Sen. Max Baucus of Montana, chairman of the Environment and Public Works Committee, wrote to Noranda Minerals Inc., an owner of the ― New World Mine‖.Last fall, an EPA official expressed concern about the mine and its potential impact, especially the plastic-lined storage reservoir. ― I am unaware of any studies evaluating how a tailings pond尾矿池,残渣池could be maintained to ensure its structural integrity forev er,‖ said Stephen Hoffman, chief of the EPA’s Mining Waste Section. ―It is my opinion that underwater disposal of tailings at New World may present a potentially significant threat to human health and the environment.‖The results of an environmental-impact statement, now being drafted by the Forest Service and Montana Department of State Lands, could determine the mine’s future…In its recent proposal to reauthorize the Clean Water Act, the Clinton administration noted ―dramatically improved water quality since 1972,‖ when the act was passed. But it also reported that 30 percent of riverscontinue to be degraded, mainly by silt泥沙and nutrients from farm and urban runoff, combined sewer overflows, and municipal sewage城市污水. Bottom sediments沉积物are contaminated污染in more than 1,000 waterways, the administration reported in releasing its proposal in January. Between 60 and 80 percent of riparian corridors (riverbank lands) have been degraded.As with endangered species and their habitats in forests and deserts, the complexity of ecosystems is seen in rivers and the effects of development----beyond the obvious threats of industrial pollution, municipal waste, and in-stream diversions改道to slake消除the thirst of new communities in dry regions like the Southwes t…While there are many political hurdles障碍ahead, reauthorization of the Clean Water Act this year holds promise for US rivers. Rep. Norm Mineta of California, who chairs the House Committee overseeing the bill, calls it ―probably the most important env ironmental legislation this Congress will enact.‖ (553 words)6.According to the passage, the Clean Water Act______.A.has been ineffectiveB.will definitely be renewedC.has never been evaluatedD.was enacted some 30 years ago7.“Endangered” rivers are _________.A.catalogued annuallyB.less polluted than ―threatened rivers‖C.caused by floodingD.adjacent to large cities8.The “cataclysmic” event referred to in paragraph eight would be__________.A. fortuitous偶然的,意外的B. adventitious外加的,偶然的C. catastrophicD. precarious不稳定的,危险的9. The owners of the New World Mine appear to be______.A. ecologically aware of the impact of miningB. determined to construct a safe tailings pondC. indifferent to the concerns voiced by the EPAD. willing to relocate operations10. The passage conveys the impression that_______.A. Canadians are disinterested in natural resourcesB. private and public environmental groups aboundC. river banks are erodingD. the majority of US rivers are in poor conditionText CA classic series of experiments to determine the effects ofoverpopulation on communities of rats was reported in February of 1962 in an article in Scientific American. The experiments were conducted by a psychologist, John B. Calhoun and his associates. In each of these experiments, an equal number of male and female adult rats were placed in an enclosure and given an adequate supply of food, water, and other necessities. The rat populations were allowed to increase. Calhoun knew from experience approximately how many rats could live in the enclosures without experiencing stress due to overcrowding. He allowed the population to increase to approximately twice this number. Then he stabilized the population by removing offspring that were not dependent on their mothers. He and his associates then carefully observed and recorded behavior in these overpopulated communities. At the end of their experiments, Calhoun and his associates were able to conclude that overcrowding causes a breakdown in the normal social relationships among rats, a kind of social disease. The rats in the experiments did not follow the same patterns of behavior as rats would in a community without overcrowding.The females in the rat population were the most seriously affected by the high population density: They showed deviant异常的maternal behavior; they did not behave as mother rats normally do. In fact, many of the pups幼兽,幼崽, as rat babies are called, died as a result of poor maternal care. For example, mothers sometimes abandoned their pups,and, without their mothers' care, the pups died. Under normal conditions, a mother rat would not leave her pups alone to die. However, the experiments verified that in overpopulated communities, mother rats do not behave normally. Their behavior may be considered pathologically 病理上,病理学地diseased.The dominant males in the rat population were the least affected by overpopulation. Each of these strong males claimed an area of the enclosure as his own. Therefore, these individuals did not experience the overcrowding in the same way as the other rats did. The fact that the dominant males had adequate space in which to live may explain why they were not as seriously affected by overpopulation as the other rats. However, dominant males did behave pathologically at times. Their antisocial behavior consisted of attacks on weaker male,female, and immature rats. This deviant behavior showed that even though the dominant males had enough living space, they too were affected by the general overcrowding in the enclosure.Non-dominant males in the experimental rat communities also exhibited deviant social behavior. Some withdrew completely; they moved very little and ate and drank at times when the other rats were sleeping in order to avoid contact with them. Other non-dominant males were hyperactive; they were much more active than is normal, chasing other rats and fighting each other. This segment of the rat population, likeall the other parts, was affected by the overpopulation.The behavior of the non-dominant males and of the other components of the rat population has parallels in human behavior. People in densely populated areas exhibit deviant behavior similar to that of the rats in Calhoun's experiments. In large urban areas such as New York City, London, Mexican City, and Cairo, there are abandoned children. There are cruel, powerful individuals, both men and women. There are also people who withdraw and people who become hyperactive. The quantity of other forms of social pathology such as murder, rape, and robbery also frequently occur in densely populated human communities. Is the principal cause of these disorders overpopulation? Calhoun’s experiments suggest that it might be. In any case, social scientists and city planners have been influenced by the results of this series of experiments.11. Paragraph l is organized according to__________.A. reasonsB. descriptionC. examplesD. definition12.Calhoun stabilized the rat population_________.A. when it was double the number that could live in the enclosure without stressB. by removing young ratsC. at a constant number of adult rats in the enclosureD. all of the above are correct13.W hich of the following inferences CANNOT be made from theinformation inPara. 1?A. Calhoun's experiment is still considered important today.B. Overpopulation causes pathological behavior in rat populations.C. Stress does not occur in rat communities unless there is overcrowding.D. Calhoun had experimented with rats before.14. Which of the following behavior didn‟t happen in this experiment?A. All the male rats exhibited pathological behavior.B. Mother rats abandoned their pups.C. Female rats showed deviant maternal behavior.D. Mother rats left their rat babies alone.15. The main idea of the paragraph three is that __________.A. dominant males had adequate living spaceB. dominant males were not as seriously affected by overcrowding as the otherratsC. dominant males attacked weaker ratsD. the strongest males are always able to adapt to bad conditionsText DThe first mention of slavery in the statutes法令,法规of the English colonies of North America does not occur until after 1660—some forty years after the importation of the first Black people. Lest we think that existed in fact before it did in law, Oscar and Mary Handlin assure us, that the status of B lack people down to the 1660’s was that of servants. A critique批判of the Handlins’ interpretation of why legal slavery did not appear until the 1660’s suggests that assumptions about the relation between slavery and racial prejudice should be reexamined, and that explanation for the different treatment of Black slaves in North and South America should be expanded.The Handlins explain the appearance of legal slavery by arguing that, during the 1660’s, the position of white servants was improving relative to that of black servants. Thus, the Handlins contend, Black and White servants, heretofore treated alike, each attained a different status. There are, however, important objections to this argument. First, the Handlins cannot adequately demonstrate that t he White servant’s position was improving, during and after the 1660’s; several acts of the Maryland and Virginia legislatures indicate otherwise. Another flaw in the Handlins’ interpretation is their assumption that prior to the establishment of legal slavery there was no discrimination against Black people. It is true that before the 1660’s Black people were rarely called slaves. But this shouldnot overshadow evidence from the 1630’s on that points to racial discrimination without using the term slavery. Such discrimination sometimes stopped short of lifetime servitude or inherited status—the two attributes of true slavery—yet in other cases it included both. The Handlins’ argument excludes the real possibility that Black people in the English colonies were never treated as the equals of White people.The possibility has important ramifications后果,影响.If from the outset Black people were discriminated against, then legal slavery should be viewed as a reflection and an extension of racial prejudice rather than, as many historians including the Handlins have argued, the cause of prejudice. In addition, the existence of discrimination before the advent of legal slavery offers a further explanation for the harsher treatment of Black slaves in North than in South America. Freyre and Tannenbaum have rightly argued that the lack of certain traditions in North America—such as a Roman conception of slavery and a Roman Catholic emphasis on equality— explains why the treatment of Black slaves was more severe there than in the Spanish and Portuguese colonies of South America. But this cannot be the whole explanation since it is merely negative, based only on a lack of something. A more compelling令人信服的explanation is that the early and sometimes extreme racial discrimination in the English colonies helped determine the particular nature of the slavery that followed. (462 words)16. Which of the following is the most logical inference to be drawn from the passage about the effects of “several acts of the Maryland and Virginia legislatures” (Para.2) passed during and after the 1660‟s?A. The acts negatively affected the pre-1660’s position of Black as wellas of White servants.B. The acts had the effect of impairing rather than improving theposition of White servants relative to what it had been before the 1660’s.C. The acts had a different effect on the position of white servants thandid many of the acts passed during this time by the legislatures of other colonies.D. The acts, at the very least, caused the position of White servants toremain no better than it had been before the 1660’s.17. With which of the following statements regarding the status ofBlack people in the English colonies of North America before the 1660‟s would the author be LEAST likely to agree?A. Although black people were not legally considered to be slaves,they were often called slaves.B. Although subject to some discrimination, black people had a higherlegal status than they did after the 1660’s.C. Although sometimes subject to lifetime servitude, black peoplewere not legally considered to be slaves.D. Although often not treated the same as White people, black people,like many white people, possessed the legal status of servants.18. According to the passage, the Handlins have argued which of thefollowing about the relationship between racial prejudice and the institution of legal slavery in the English colonies of North America?A. Racial prejudice and the institution of slavery arose simultaneously.B. Racial prejudice most often the form of the imposition of inheritedstatus, one of the attributes of slavery.C. The source of racial prejudice was the institution of slavery.D. Because of the influence of the Roman Catholic Church, racialprejudice sometimes did not result in slavery.19. The passage suggests that the existence of a Roman conception ofslavery in Spanish and Portuguese colonies had the effect of _________.A. extending rather than causing racial prejudice in these coloniesB. hastening the legalization of slavery in these colonies.C. mitigating some of the conditions of slavery for black people in these coloniesD. delaying the introduction of slavery into the English colonies20. The author considers the explanation put forward by Freyre andTannenbaum for the treatment accorded B lack slaves in the English colonies of North America to be _____________.A. ambitious but misguidedB. valid有根据的but limitedC. popular but suspectD. anachronistic过时的,时代错误的and controversialUNIT 2Text AThe sea lay like an unbroken mirror all around the pine-girt, lonely shores of Orr’s Island. Tall, kingly spruce s wore their regal王室的crowns of cones high in air, sparkling with diamonds of clear exuded gum流出的树胶; vast old hemlocks铁杉of primeval原始的growth stood darkling in their forest shadows, their branches hung with long hoary moss久远的青苔;while feathery larches羽毛般的落叶松,turned to brilliant gold by autumn frosts, lighted up the darker shadows of the evergreens. It was one of those hazy朦胧的, calm, dissolving days of Indian summer, when everything is so quiet that the fainest kiss of the wave on the beach can be heard, and white clouds seem to faint into the blue of the sky, and soft swathing一长条bands of violet vapor make all earth look dreamy, and give to the sharp, clear-cut outlines of the northern landscape all those mysteries of light and shade which impart such tenderness to Italian scenery.The funeral was over,--- the tread鞋底的花纹/ 踏of many feet, bearing the heavy burden of two broken lives, had been to the lonely graveyard, and had come back again,--- each footstep lighter and more unconstrained不受拘束的as each one went his way from the great old tragedy of Death to the common cheerful of Life.The solemn black clock stood swaying with its eternal ―tick-tock, tick-tock,‖ in the kitchen of the brown house on Orr’s Island. There was there that sense of a stillness that can be felt,---such as settles down on a dwelling住处when any of its inmates have passed through its doors for the last time, to go whence they shall not return. The best room was shut up and darkened, with only so much light as could fall through a little heart-shaped hole in the window-shutter,---for except on solemn visits, or prayer-meetings or weddings, or funerals, that room formed no part of the daily family scenery.The kitchen was clean and ample, hearth灶台, and oven on one side, and rows of old-fashioned splint-bottomed chairs against the wall. A table scoured to snowy whiteness, and a little work-stand whereon lay the Bible, the Missionary Herald, and the Weekly Christian Mirror, before named, formed the principal furniture. One feature, however, must not be forgotten, ---a great sea-chest水手用的储物箱,which had been the companion of Zephaniah through all the countries of the earth. Old, and battered破旧的,磨损的, and unsightly难看的it looked, yet report said that there was good store within which men for the most part respect more than anything else; and, indeed it proved often when a deed of grace was to be done--- when a woman was suddenly made a widow in a coast gale大风,狂风, or a fishing-smack小渔船was run down in the fogs off the banks, leaving in some neighboring cottage a family of orphans,---in all such cases, the opening of this sea-chest was an event of good omen 预兆to the bereaved丧亲者;for Zephaniah had a large heart and a large hand, and was apt有…的倾向to take it out full of silver dollars when once it went in. So the ark of the covenant约柜could not have been looked on with more reverence崇敬than the neighbours usually showed to Captain Pennel’s sea-chest.1. The author describes Orr‟s Island in a(n)______way.A.emotionally appealing, imaginativeB.rational, logically preciseC.factually detailed, objectiveD.vague, uncertain2.According to the passage, the “best room”_____.A.has its many windows boarded upB.has had the furniture removedC.is used only on formal and ceremonious occasionsD.is the busiest room in the house3.From the description of the kitchen we can infer that thehouse belongs to people who_____.A.never have guestsB.like modern appliancesC.are probably religiousD.dislike housework4.The passage implies that_______.A.few people attended the funeralB.fishing is a secure vocationC.the island is densely populatedD.the house belonged to the deceased5.From the description of Zephaniah we can see thathe_________.A.was physically a very big manB.preferred the lonely life of a sailorC.always stayed at homeD.was frugal and saved a lotText BBasic to any understanding of Canada in the 20 years after the Second World War is the country' s impressive population growth. For every three Canadians in 1945, there were over five in 1966. In September 1966 Canada's population passed the 20 million mark. Most of this surging growth came from natural increase. The depression of the 1930s and the war had held back marriages, and the catching-up process began after 1945. The baby boom continued through the decade of the 1950s, producing a population increase of nearly fifteen percent in the five years from 1951 to 1956. This rate of increase had been exceeded only once before in Canada's history, in the decade before 1911 when the prairies were being settled. Undoubtedly, the good economic conditions of the 1950s supported a growth in the population, but the expansion also derived from a trend toward earlier marriages and an increase in the average size of families; In 1957 the Canadian birth rate stood at 28 per thousand, one of the highest in the world. After the peak year of 1957, thebirth rate in Canada began to decline. It continued falling until in 1966 it stood at the lowest level in 25 years. Partly this decline reflected the low level of births during the depression and the war, but it was also caused by changes in Canadian society. Young people were staying at school longer, more women were working; young married couples were buying automobiles or houses before starting families; rising living standards were cutting down the size of families. It appeared that Canada was once more falling in step with the trend toward smaller families that had occurred all through theWestern world since the time of the Industrial Revolution. Although the growth in Canada’s population had slowed down by 1966 (the cent), another increase in the first half of the 1960s was only nine percent), another large population wave was coming over the horizon. It would be composed of the children of the children who were born during the period of the high birth rate prior to 1957.6. What does the passage mainly discuss?A. Educational changes in Canadian society.B. Canada during the Second World War.C. Population trends in postwar Canada.D. Standards of living in Canada.7. According to the passage, when did Canada's baby boom begin?A. In the decade after 1911.B. After 1945.C. During the depression of the 1930s.D. In 1966.8. The author suggests that in Canada during the 1950s____________.A. the urban population decreased rapidlyB. fewer people marriedC. economic conditions were poorD. the birth rate was very high9. When was the birth rate in Canada at its lowest postwar level?A. 1966.B. 1957.C. 1956.D. 1951.10. The author mentions all of the following as causes of declines inpopulation growth after 1957 EXCEPT_________________.A. people being better educatedB. people getting married earlierC. better standards of livingD. couples buying houses11.I t can be inferred from the passage that before the IndustrialRevolution_______________.A. families were largerB. population statistics were unreliableC. the population grew steadilyD. economic conditions were badText CI was just a boy when my father brought me to Harlem for the first time, almost 50 years ago. We stayed at the hotel Theresa, a grand brick structure at 125th Street and Seventh avenue. Once, in the hotel restaurant, my father pointed out Joe Louis. He even got Mr. Brown, the hotel manager, to introduce me to him, a bit punchy强力的but still champ焦急as fast as I was concerned.Much has changed since then. Business and real estate are booming. Some say a new renaissance is under way. Others decry责难what they see as outside forces running roughshod肆意践踏over the old Harlem. New York meant Harlem to me, and as a young man I visited it whenever I could. But many of my old haunts are gone. The Theresa shut down in 1966. National chains that once ignored Harlem now anticipate yuppie money and want pieces of this prime Manhattan real estate. So here I am on a hot August afternoon, sitting in a Starbucks that two years ago opened a block away from the Theresa, snatching抓取,攫取at memories between sips of high-priced coffee. I am about to open up a piece of the old Harlem---the New York Amsterdam News---when a tourist。
A Simplified Finite-Control-Set Model-PredictiveControl for Power ConvertersChangliang Xia,Senior Member,IEEE,Tao Liu,Tingna Shi,and Zhanfeng SongAbstract—Finite-control-set model-predictive control(FCS-MPC)requires a large amount of calculation,which is an obstacle for its application.However,compared with the classical linear control algorithm,FCS-MPC requires a shorter control loop cycle time to reach the same control performance.To resolve this contradiction,this paper presents an effective method to simplify the conventional FCS-MPC.With equivalent transformation and specialized sector distribution method,the computation load of FCS-MPC is greatly reduced while the control performance is not affected.The proposed method can be used in various circuit topologies and cases with multiple constraints.Experiments on two-level converter and three-level NPC converter verify the good performance and application value of the proposed method. Index Terms—Finite-control-set model-predictive control (FCS-MPC),power converter,sector distribution method,simpli-fied algorithm.I.I NTRODUCTIONO PTIMAL control of multiple objectives not only realizes the high-quality and high-efficiency power conversion but also ensures the high reliability of the power converters.For example,in the transformerless photovoltaic(PV)applications, the vibration suppression of the common-mode(CM)voltage in power converters helps to reduce the current harmonics and power losses and to improve the system safety[1]–[4].For the medium-voltage power conversion system,the multilevel power-converter technique is proposed,and the balancing of the neutral point voltage is considered in order to obtain better control performance and enhance the reliability of the entire system[5],[6].Thefinite-control-set model-predictive control(FCS-MPC) can realize the optimal control of multiple objectives,and it has been attracting growing interest due to many of its advantages, such as fast dynamic response,inherent decoupling,and easyManuscript received March02,2013;revised July05,2013and August19, 2013;accepted September27,2013.Date of publication October04,2013; date of current version May02,2014.This work was supported in part by the National Key Basic Research Program of China(973project)under Grant 2013CB035602,by the National Natural Science Foundation of China under Grant51107084,and by the Key Technologies Research and Development Pro-gram of Tianjin under Grant13ZCZDGX01100.Paper no.TII-13-0125.C.Xia is with the School of Electrical Engineering and Automation,Tianjin University,Tianjin300072,China,and also with Tianjin Key Laboratory of Ad-vanced Technology of Electrical Engineering and Energy,Tianjin Polytechnic University,Tianjin300387,China(e-mail:motor@).T.Liu,T.Shi,and Z.Song are with the School of Electrical Engineering and Automation,Tianjin University,Tianjin300072,China(e-mail:taoliu@tju. ;tnshi@;zfsong@).Color versions of one or more of thefigures in this paper are available online at .Digital Object Identifier10.1109/TII.2013.2284558inclusion of nonlinear constraints[7]–[20].FCS-MPC has de-veloped rapidly in the past few years,and studies on this topic have been spread out across variousfields,for example,renew-able energy,uninterruptible power supply(UPS)systems,and electric motor drivers[21]–[27].However,there exists an ob-vious challenge for the actual application of FCS-MPC.As is known,FCS-MPC undergoes no pulse-width modula-tion(PWM)process,and it outputs only one switching state in each control loop cycle,so its switching frequency is un-fixed.To achieve the same current waveform quality,the con-trol loop cycle time of FCS-MPC should be much shorter than that of the conventional linear control methods[28],[29].As a result,the time allowed to complete the FCS-MPC algorithm becomes so short that it is impractical in reality.For example, in the case of a three-level neutral point clamped(NPC)con-verter,the minimum time needed for completing the FCS-MPC is approximately52s[30];this is still longer than the control loop cycle time required for achieving satisfying control perfor-mances.Moreover,the amount of calculation will also increase with the complexity of circuit topology.The additional multiple constraints,such as balancing of the neutral point voltage and vibration reduction of the common-mode voltage,will also in-crease the calculation amount of FCS-MPC.In summary,time-consuming computation is an obstacle that limits the application of FCS-MPC.In recent years,simplification of the FCS-MPC algorithm has been proposed and discussed[31]–[35].For example,one approach uses sector distribution on a source voltage vector to reduce the number of candidate vectors in the prediction process[31].With this approach,the program running time can be significantly shortened but the control performance may be affected as the proposed simplified algorithm is not an exact equivalent to the original algorithm.Another approach,men-tioned in hybrid hysteresis-SVM algorithms,shed lights also on reducing the computational time of FCS-MPC.However, there is a lack of extensive studies on this issue.In this paper,an effective method for FCS-MPC algorithm simplification is proposed to reduce the running time without affecting the control performance.This method is divided into two steps:thefirst step is to eliminate the calculation for cur-rent prediction;the second step is to reduce the number of cost function calculations.With the above two steps,the calculation time is shortened while the control performance is not affected. The proposed method has some versatility,and it is effective not only in different circuit topologies but also in cases with mul-tiple constraints.Finally,the experiments on a two-level con-verter and a three-level NPC converter prove the effectiveness of the proposed method.1551-3203©2014IEEE.Personal use is permitted,but republication/redistribution requires IEEE permission.See /publications_standards/publications/rights/index.html for more information.Fig.1.Topological structure of the main circuit of a two-level power converter.II.O PERATING P RINCIPLE OF C ONVENTIONAL FCS-MPC The computational demand required by the conventional FCS-MPC for power converters is discussed with the two-level power converter,shown in Fig.1,where are the ac-side source voltages,are the ac-side currents, are the converter voltages,is the equivalent series resistance,is thefilter inductance;is the dc-link capacitor, and are the switching states of three converter legs, respectively.For simplicity,the vectors are defined as follows:(1) The voltage balance equation based on stationary frameis described as(2) where is the vector of ac-side current,is the vector of ac-side source voltage,and is the vector of converter voltage.To realize the current control strategy,the forward Euler al-gorithm(or called standard Euler algorithm)is applied to(2), and the discrete-time expression of(2)is obtained as(3) where is the step size from time instant to time instant,;is also the control loop cycle time. For the existing error in the forward Euler method,(3)is the approximate expression of(2).Equation(3)says the current at time instant,,is determined by the source voltage,converter voltage,and current at time instant,denoted with,,and, respectively.As known,the converter voltage can be any one of the eight voltage vectors,listed in Table I,due to the fact that there are total eight switching states generated by the converter.The predicted current at time instant can be any one of the following eight current vectors calculated according to(4): (4)TABLE IV OLTAGE V ECTORSFig.2.Schematic diagram of a conventional FCS-MPC scheme.where is the current predicted for time instant corresponding to the converter voltage acting from time instant to time instant.To evaluate the predictions,a cost function is needed and therefore defined as follows:(5)where is the reference current for time instant. The realization of FCS-MPC is tofind the switching state ,which will minimize the cost function defined in(5), and then apply it to converter.(6)where is the combination of the switching states during the time interval,that is,.Finally,for clarity,the following equation summarizes the mathematic expression of conventional FCS-MPC applied to a power converter:(7) Fig.2shows the schematic diagram corresponding to(7).In conclusion,a conventional FCS-MPC of two-level power converters,described by(7)and Fig.2,requires current pre-diction calculations and calculations of the cost function.XIA et al.:SIMPLIFIED FINITE-CONTROL-SET MODEL-PREDICTIVE CONTROL FOR POWER CONVERTERS993Fig.3.“Required voltage vector”and space distribution of eight voltage vec-tors in a two-level power converter.III.S IMPLIFIED FCS-MPC W ITH S INGLE P REDICTION M ETHOD A.Two-Level Power ConverterAs presented above,in the case of two-level power con-verters,conventional FCS-MPC needscurrent prediction calculations.The method proposed here in this paper avoids thecurrent predictions for time instant .Instead,it uses the “required voltage vector”for prediction process.The idea of conventional FCS-MPC is to select voltage vector which makes the predicted current close to its refer-ence .Considering the predicted current in (3),one can obtain the determination of as follows.Replacing with in (3)and making rearrangement of the equation,one has(8)Equation (8)says the currentwill be exactly equal to its reference if the converter voltage acting at time instant can be managed to be the same as ,calculated with (8).Fig.3shows the space distribution of the “required voltage vector”along with the eight voltage vectors .Then,the current predictive control needs to identify one voltage vector among which meets the requirement given below:(9)This means determining the switching state which should be applied to power converter at time instant through identifying which voltage vector is the one nearest to the “required voltage vector”.Similarly,the following equation summarizes the mathematic description of the FCS-MPC proposed in this paper:(10)In this paper,the simpli fied algorithm described with (10)is called “single predictive FCS-MPC.”With a simple derivation process,it is easy to prove that the “single predictive FCS-MPC”Fig.4.Schematic diagram of the single predictive FCS-MPC.(10)and the conventional FCS-MPC (7)are equivalent.By sub-stituting (4)into (10)and rearranging the equations,the simpli-fied algorithm (10)can be transformed into(11)where .Comparing (11)and (7),one knows that the cost functions of the “single predictive FCS-MPC”and the conventional FCS-MPC are different only by the positive multiplication factor .Such a fact ensures that the performance of “single predictive FCS-MPC”will be the same as that of the conven-tional FCS-MPC.Again,similarly,Fig.4shows the schematic diagram of the “single predictive FCS-MPC”given by (10).The proposed algorithm reduces the predictions to one,and this method can also be applied to other circuit topologies.B.Three-Level NPC Power ConverterOne of main advantages of FCS-MPC is in its ability to in-clude other constraints,for example,common-mode voltage re-duction and neutral point voltage balancing,which will lead to the realization of the optimal control of multiple objectives.The general expression of the conventional FCS-MPC is shown as follows:(12)where ,,and are the predicted values of current con-straint and additional constraints and ,is the pre-dictive function of current constraint ,and are the predictive functions of additional constraints and ,re-spectively,,,and are the weight factors corresponding to constraints ,,and ,and means the number of the th voltage vector .The general expression of “single predictive FCS-MPC”is shown as follows:(13)994IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS,VOL.10,NO.2,MAY2014Fig.5.(a)Circuit topology of a three-level NPC converter.(b)Voltage vectors space distribution of the three-level NPC converter.where is the calculation equation of the“required voltage vector”and is the weight factor. The“single predictive FCS-MPC”is still effective under the condition that the additional constraints are considered. Taking the control of a three-level NPC converter as an ex-ample,one has the circuit topology and the voltage vectors dis-tribution of the three-level NPC converter shown in Fig.5.In Fig.5(a),the switching states of the converter are defined as follows.The“1”state means the converter’s phase leg is connected to positive bus bar(P),whereas the“1”state means the converter’s phase leg is connected to the negative bus bar(N),the“0”state means the converter’s phase leg is con-nected to the neutral point(o)of the dc-link.In Fig.5(b),to be concise,the switching states“1,”“0,”“1”are replaced with symbols“”,“0,”“,”respectively.In three-level NPC converter cases,the additional constraint is the balancing of neutral point voltage.The deviation of the neutral point voltage at is given as follows:(14) where,,and are the switching state of the corresponding phases at time instant,and is the de-viation of the neutral point voltage at time instant,which is the difference between the voltages of the two capacitors and,as shown in Fig.5(a)..The conventional FCS-MPC for three-level NPC converters is described as(15) where is the constraint for the balancing of neutral point voltage,which is necessary in case of three-level converter circuits and is the weight factor correspondingly. With the adjusting of,the impact of the neutral point voltage balancing control can be enhanced or weakened as desired. With the single prediction method,the“single predictive FCS-MPC”for three-level NPC converters is obtained as(16) Comparing(16)with(15),one can see27current predic-tions are eliminated through one time calculation of the“re-quired voltage vector”.Compared with two-level con-verters,the proposed FCS-MPC brings more significant time savings in three-level NPC converter cases.IV.F URTHER S IMPLIFIED FCS-MPC W ITH S ECTORD ISTRIBUTION M ETHODA.Two-Level Power ConverterThe“single predictive FCS-MPC”is further simplified by di-viding the space of the eight voltage vectors into sections.As shown in Fig.6(a),a shadowed hexagon region is defined,which is formed with the perpendicular bisectors of the voltage vectors .If falls into the shadowed hexagon region,zero voltage vector or will be closest to.If falls into sectors I VI rather than the shadowed hexagon region,the nonzero voltage vector located in the corresponding sector will be closest to.Finally,for clarity,steps are summarized below.1)Calculate using(8);2)Identify the sector which falls into(In this paper,it iscalled the“chosen sector”.Approach used in space vector modulation(SVM)can be adopted for sector determination[36]).3)Select either or if falls into the shadowedhexagon region;otherwise,select the nonzero voltage vector which locates inside“chosen sector”.With sector distribution method adopted,the proposed FCS-MPC eliminates not only current predictions but also cost function evaluations required by the conventional FCS-MPC.To select the optimal voltage vector,only region identification is required.Fig.6(b)is for cases in which additional constraints are con-sidered.As the calculation results of the cost function are deter-mined by both current constraint and additional constraints,the voltage vectors which have high cost in every one of all con-straints will be excluded from the candidate voltage vectors be-fore the cost function evaluations.Therefore,the total numberXIA et al.:SIMPLIFIED FINITE-CONTROL-SET MODEL-PREDICTIVE CONTROL FOR POWER CONVERTERS995Fig.6.Sector distribution of voltage vector space for further simpli fication of FCS-MPC algorithm.(a)Only with current constraint.(b)With current con-straint and common-mode voltage constraint.TABLE IIC ANDIDATE V ECTORS FOR E ACH SECTORof the cost function calculations can be reduced and the running time will be further shortened.The additional constraints can be divided into two types.In this paper,for any voltage vector,the constraints whose results change with time are referred to as “variable constraint”in this paper;the constraints whose results do not change with time are referred to as “invariable constraint.”For the “invariable constraint,”the corresponding cost of each voltage vector is fixed,so the candidate voltage vectors of the corresponding sector can be determined in advance.For the “variable constraint,”the corresponding cost of each voltage vector is un fixed,so some candidate voltage vectors of the corresponding sector cannot be determined in advance,and they can be determined only when additional calculations are added.Taking common-mode voltage reduction as an example,in the case of two-level converters,the common-mode voltage cor-responding to is calculated with(17)It can be seen that the common-mode voltage constraint is an “invariable constraint”,because it is only related to theswitching state (the dc-link voltageis almost constant under steady state conditions).With the constraint on the common-mode voltage included,the conventional FCS-MPC for two-level converters is given as follows:(18)where is the common-mode voltage when the voltage vector is selected.For example,is the common-mode voltage when the voltage vector is The whole cost function in (18)takes the format of “current constraint+invariable constraint.”With the sector distribution shown in Fig.6(b),each sector has two zero vectors (000,111)and one nonzero vector.As for the current constraint,the vector which has the lowest cost belongs to the “chosen sector”;as for the common-mode voltage constraint,all of the nonzero vectors have the same cost.Thus,in the final results of the cost function,the vectors outside the “chosen sector”will impossibly have the lowest cost.The candidate vectors are the zero vectors and the nonzero vector in the “chosen sector.”As is known,the costs of two zero vectors and are equal,and only one of them will be chosen as the candidate vector.Then,the simpli fied FCS-MPC can be written as(19)where is the number assigned to the nonzero vector which is located inside the “chosen sector.”Table II summarizes the candidate vectors for each sector.In conclusion,the simpli fied FCS-MPC is still effective under the condition that the constraint on the common-mode voltage is considered.The simpli fied FCS-MPC needs calculations of the cost function;while the conventional FCS-MPC requires eight-time calculations.B.Three-Level NPC Power ConverterThe sector distribution method is also effective in three-level converter cases.Taking the three-level NPC converter as an ex-ample,the additional neutral point voltage constraint is a “vari-able constraint,”and the whole cost function takes the format of “current constraint+variable constraint.”The sector distribution is similar to that in two-level converter cases,and it is shown in Fig.7.The vector with the lowest cost in current constraint be-longs to the “chosen sector,”but some vectors outside the “chosen sector”may have lower cost in terms of neutral point voltage constraint,possibly making them the optimal vectors.In Fig.7,the “chosen sector”is sector III,and the vectors “”belong to this sector.There-fore,these eight voltage vectors are included into the pool of candidate vectors.The final cost function results of vectors “”may be lower than any vector which belongs to sector III,so these vectors are also included into the pool of candidate vectors and therefore the shadowed hexagon region is996IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS,VOL.10,NO.2,MAY2014Fig.7.Neutral point voltage influence of all27voltage vectors.The vectors with the same color have the same cost in terms of the neutral point voltage constraint.formed.For any vector which does not belong to the shadowed hexagon region,,there is always a vector which belongs to the shadowed hexagon region,,making thefinal cost function result of less than that of.Therefore,can be excluded from the candidate vector pool.For example, for,there is a which gives the same result in terms of the neutral point voltage constraint.As has higher cost than in terms of the current constraint.Therefore, the vector cannot be the optimal vector and is excluded from the pool of candidate vectors.Similarly,for, one has,it can be seen that,in terms of the current constraint,has higher cost than,while in terms of the neutral point voltage constraint,the cost of is equal to that of.Therefore,the vector cannot be the optimal vector and is excluded from the pool of candidate vectors.At last,all of the vectors which do not belong to the shadowed hexagon region are excluded from the pool of candidate vectors.So the final candidate vectors corresponding to sector III are those vectors which belong to the shadowed hexagon region.The further simplified FCS-MPC for three-level NPC con-verters with the neutral point voltage constraint considered is described as(20) where means the numbers assigned to the candidate vectors which belong to the shadowed hexagon region which is determined by the“chosen sector.”The candidate vectors for each sector are shownin TableIII.In addition,the zero vectors have the same cost,so only one of them is included in the candidate vectors.TABLE IIIC ANDIDATE V ECTORS FOR E ACH SECTORFig.8.Candidate vectors(vectors with dark background)corresponding to sector III when the neutral point voltage constraint is considered.TABLE IVS MALL V ECTORS S ELECTED BY E ACH S ECTORWhen Section III is the“chosen sector,”the small vectors “”in the shadowed hexagon region have the same cost under the current constraint,but different cost under the neutral point voltage constraint.It is also the same with“”and“.”With simple additional calculations,three small vectors can be excluded from the candidate vectors.Under the condition that“;;”,candidate vectors corresponding to Section III are given in Fig.8.When is located in other sectors,the small vectors se-lected by these sectors are shown in Table IV.Therefore,the number of voltage vectors to be calculated and compared with the cost function is reduced to7,which will greatly shorten the running time of FCS-MPC.Under the condition that the constraint on the common-mode voltage is considered,the cost function takes the format of “current constraint+variable constraint+invariable constraint.”In the case of three-level NPC converters,the common-mode voltage constraint is,and can be calculated by(17)with,.The conventionalXIA et al.:SIMPLIFIED FINITE-CONTROL-SET MODEL-PREDICTIVE CONTROL FOR POWER CONVERTERS997Fig.9.Cost of27voltage vectors in terms of the common-mode voltage con-straint.The vectors with the same color play the same cost.FCS-MPC algorithm with the constraint on the common-mode voltage added is described as(21) Analysis similar to what was explained for cases of“cur-rent constraint+neutral point voltage constraint”has been performed.Fig.9shows the common-mode voltage in-fluence of each voltage vector.When is located in sector III,with carefully analysis of every voltage vector in Fig.7and Fig.9,It tells only and can compete with the vectors in the shadowed hexagon region.There-fore,the candidate vectors are those voltage vectors linked with the bold lines.(For sector III,the candidate vectors are “”).In reality,the weight factor of the common-mode voltage con-straint is a small number that makes the current constraint to be a dominant term of the cost function.For example,com-pared with the vectors at the shadowed hexagon region,vectors “”are far away from,this makes their cost much higher than those vectors at the shadowed hexagon region in terms of the current constraint.Therefore,vectors and can be excluded from the candidate vectors.Finally,the number of candidate vectors is reduced to ten.Fig.10shows the ten voltage vectors selected.With the inclusion of common-mode voltage constraint,the further simplified FCS-MPC is describedas(22)Fig.10.Candidate vectors(vectors with dark background)corresponding to sector III when the common-mode voltage constraint and the neutral point voltage constraint are considered.Fig.11.Platform of the two-level converter.where means the numbers assigned to the candi-date vectors which belong to the vector set which is determined by the“chosen sector”.It is important to note that the conclusion given above (reducing the candidate vectors to ten),as shown in Fig.10, is achieved based on the assumption that the common-mode voltage constraint plays the lowest impact on the cost function result.Such an assumption introduces an implicit priority among the control objectives;and therefore the proposed FCS-MPC in(22)is approximately equivalent to the conven-tional FCS-MPC.To ensure the proposed FCS-MPC exactly equivalent to the conventional FCS-MPC,two more voltage vectors need to be added back to the candidate vectors.For example,in Section III,vectors“”should be kept to be the candidate vectors(as shown in Fig.9).consequently,the number of candidate vectors is increased to12.V.E XAMINATION V IA E XPERIMENTThe experimental platform is developed using a TIfloating-point digital signal processor(DSP)TMS320F28335.In the ex-periment,time-delay compensation[29]is applied to both the conventional FCS-MPC and the simplified FCS-MPC.A.Two-Level Power ConverterThe platform of the two-level converter(with the circuit topology shown in Fig.1)is shown in Fig.11,and the system pa-rameters are as follows:source line voltage92V(rms); dc-link voltage160V;filter inductance 5.0mH; equivalent series resistance 1.2;dc-link capacitor998IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS,VOL.10,NO.2,MAY2014parative experimental results of the conventional FCS-MPC and the sector distribution based FCS-MPC.(a)Waveform of current(2A/div) and its THD.(b)Transient response of three-phase currents,and (2A/div).2200F;control loop cycle time33s;equivalent load resistance.Fig.12shows the comparative experimental results of the conventional FCS-MPC and the simplified FCS-MPC with sector distribution method.Fig.12(a)shows that the steady-state results of the two algorithms are similar to each other in current waveforms and corresponding total harmonic distortion(THD).Fig.12(b)shows that the transient responses of the two algorithms are similar to each other when the current amplitude steps from3to6A.The rising time is about0.2ms. With the inclusion of common-mode voltage constraint, the comparative experimental results of the conventional FCS-MPC and the simplified FCS-MPC with sector distribu-tion method are shown in Fig.13.It can be seen that,when the weight factor changes from0.0to0.1,the suppression effects of the common-mode voltage resulted by these two algorithmsare basically the same.As time goes on,the current harmonics increase,and the high frequency components of the currents resulted by these two algorithms are basically the parative experimental results of the two algorithms when the common-mode voltage constraint is added.(a)Current waveforms(,and ,2A/div)and common-mode voltage(,50V/div)obtained with the conventional FCS-MPC.(b)Current waveforms(,and,2A/div)and common-mode voltage(,50V/div)obtained with the sector distribution based FCS-MPC.parison between the running time required by the conventional FCS-MPC and the simplified FCS-MPC in two-level converter cases.(a)Con-ventional FCS-MPC.(b)Simplified FCS-MPC with single prediction method.(c)Simplified FCS-MPC with sector distribution method.In thefigures,(1)rep-resents the A/D conversion,(2)represents other algorithms,(3)represents the prediction process,(4)represents the calculation and comparison of cost func-tion,and(5)represents the free time.The comparison between the running time required by the conventional FCS-MPC and the simplified FCS-MPC is shown in Fig.14and Fig.15.The column chart is used in Fig.16to fa-cilitate pared with the conventional algorithm, the simplified algorithms significantly reduce the running time needed for the prediction and cost function calculation.The run-ning time of the sector distribution based FCS-MPC is much shorter than that of the single predictive FCS-MPC.Also,it can be seen that the simplified algorithm is still effective in cases that the additional constraints are added.。
A Simplicial Approach for DiscreteFixed Point Theorems(Extended Abstract)Xi Chen1and Xiaotie Deng2⋆1Department of Computer Science,Tsinghua Universityxichen00@2Department of Computer Science,City University of Hong Kongdeng@.hkAbstract.We present a new discretefixed point theorem based on anovel definition of direction-preserving maps over simplicial structures.We show that the result is more general and simpler than the two re-cent discretefixed point theorems by deriving both of them from ours.The simplicial approach applied in the development of the new theoremreveals a clear structural comparison with the classical approach for thecontinuous case.1IntroductionThere has recently been a sequence of works related tofixed point theorems in a discrete disguise,started with the seminal work of Iimura[12]which introduced a crucial concept of direction-preserving maps.Iimura,Murota and Tamura[13] corrected the proof of Iimura for the definition domains of the maps.With a different technique,Chen and Deng introduced another discretefixed point the-orem in order to achieve the optimal algorithmic bound forfinding a discrete fixed point for allfinite dimensions[1].In[14],Laan,Talman and Yang designed an iterative algorithm for the discrete zero point problem.Based on Sperner’s lemma which is fundamental for deriving Brouwer’sfixed point theorem,Friedl, Ivanyosy,Santha and Verhoeven defined the black-box Sperner problems.They √also obtained aon the simplicial structure in the study of the discrete version will help us gain a full and clear understanding of the mathematical structures and properties related to discretefixed point theorems.Furthermore,even for continuousfixed point theorems,discrete structural propositions are needed to derive them.Our study would provide a unified view of thefixed point theorem,both discrete and continuous,instead of treating them with ad hoc techniques.Our simplicial ap-proach unveils the mystery behind the recent results on discretefixed points and settles them under the same mathematical foundation as the classical continuous fixed point theorems.The discrete nature of thefixed point theorem has been noticed previously, mainly due to the proof techniques of Sperner’s lemma[15].The recent effort in direct formulation of the discrete version of thefixed point theorem would be especially useful in the complexity analysis of related problems.The recent work in characterizing the complexity of Nash Equilibria,by Daskalakis,Goldberg, Papadimitriou[8],Chen and Deng[2],Daskalakis and Papadimitriou[9],Chen and Deng[3],has been based on another innovative formulation of the2D(or 3D)discretefixed point problem,where afixed point is a collection of four[6] (or eight[8])corners of a unit square(or cube).It’s difficult to generalize such a formulation to high dimensional spaces,since a hypercube has an exponential number of corners,which is computationally infeasible.Instead,a simplicial de-finition has been necessary in extending those results to a non-approximability work obtained recently[9].Wefirst introduce notations and definitions with a review of previous works of Murota,Iimura and Tamura[13],as well as Chen and Deng[1].The simplicial model is then introduced in section3and the fundamental discretefixed point theorem is proved in section4.In section5,we present the discrete Brouwer’s fixed point theorem for simplicial direction-preserving maps,with the theorem of Murota,Iimura and Tamura[13]derived as a simple corollary.In Section6, we give an explicit explanation for the definition of bad cubes in[1]and show that,the theorem of Chen and Deng is a special case of the fundamentalfixed point theorem.Finally,we conclude in section7.2Preliminaries2.1Notations and DefinitionsInformally speaking,map F(or function f)is hypercubic direction-preserving on afinite set X⊂Z d if for every two neighboring points in X,their directions given by F(or f)are not opposite.The neighborhood relation considered here is defined by the infinity norm.Definition1(Hypercubic Direction-Preserving Maps)Let X be afinite subset of Z d.Map F from X to R d is said to be hypercubic direction-preserving on X if for every two points r1,r2∈X with||r1−r2||∞≤1,we have(F i(r1)−r1i)(F i(r2)−r2i)≥0,for all i:1≤i≤d.2Definition2(Hypercubic Direction-Preserving Functions)Let X be a finite subset of Z d.Function f from set X to{0,±e1,±e2...±e d−1,±e d}is said to be hypercubic direction-preserving if for every two points r1,r2∈X such that ||r1−r2||∞≤1,we have||f(r1)−f(r2)||∞≤1.Point r∈X is called afixed point of F(or f)if F(r)=r(or f(r)=0). 2.2The Fixed Point Theorem of Murota,Iimura and TamuraMurota,Iimura and Tamura proved in[13]that every hypercubic direction-pre-serving map from an integrally convex set X toX to denote the convex hull offinite set X⊂Z d.Definition3(Integrally Convex Sets)Finite set X⊂Z d is integrally con-vex if for all x∈X∩N(x)where N(x)={r∈Z d|||r−x||∞<1}.Theorem1([13])Let X be an integrally convex set in Z d,then every hyper-cubic direction-preserving map F from X to3Simplicial Direction-Preserving Maps and FunctionsIn this section,we introduce simplicial direction-preserving maps and functions based on simplicial structures.Let X be afinite set in R d.Here we only con-sider nondegenerate cases whereX such that for every S∈S,V S⊂X,where V S is the vertex set of simplex S.Given a simplicial decomposition S of X,we use F S to denote the set of (d−1)-simplices on the boundary ofX:F S={(d−1)-simplex S∈S|S⊂F and F is a facet ofX}.Definition8(Simplicial Direction-Preserving Maps)A simplicial direc-tion-preserving map is a triple M=(F,X,S).Here X is afinite set in R d and S is a simplicial decomposition of X.Map F from X to R d satisfies for every two points r1,r2∈X,if there exists a simplex S∈S such that r1,r2∈V S,then (F i(r1)−r1i)(F i(r2)−r2i)≥0,for all i:1≤i≤d.Definition9(Simplicial Direction-Preserving Functions)A triple G= (f,X,S)is said to be a simplicial direction-preserving function if X is afinite set in R d,S is a simplicial decomposition of X,and function f from set X to {0,±e1,...±e d}satisfies for every two points r1,r2∈X,if there exists S∈S such that r1,r2∈V S,then||f(r1)−f(r2)||∞≤1.In other words,for every two neighboring points in X,their directions given by map F(or function f)can’t be opposite.The only difference with the hy-percubic model is that the neighborhood relation is now defined by simplices in the simplicial decomposition S instead of unit d-cubes in Z d.4The Fundamental Discrete Fixed Point TheoremIn this section,we present the fundamental discretefixed point theorem which is both simple and powerful.Any simplicial direction-preserving function which satisfies the boundary condition of the theorem must have afixed point.Definition10(Bad Simplices)Let G=(f,X,S)be a simplicial direction-preserving function,where X⊂Z d.A t-simplex S∈S where0≤t≤d is said to be bad(relative to function G)if f(V S)={e1,e2,...e t+1},where V S is the vertex set of S.We use N G to denote the number of bad(d−1)-simplices in F S.4Lemma1For any simplicial direction-preserving function G=(f,X,S),if there exists nofixed point in X,then N G is even.Proof.Firstly,one can show that for every(d−1)-simplex S∈S,if S∈F S, then there exists exactly one d-simplex in S containing S.Otherwise,there are exactly two such ing this property,the parity of N G is same as the one of the following summation:d-simplex S d∈Sbad(d−1)-simplices in S d.As G is direction-preserving and has nofixed point,the number of bad(d−1)-simplices in S d is either0or2.Therefore,the summation above must be even.We now get the fundamental theorem as a simple corollary of Lemma1. Theorem3(The Fundamental Discrete Fixed Point Theorem)Let G=(f,X,S)be a simplicial direction-preserving function.If N G,i.e.the number of bad(d−1)-simplices on the boundary is odd,then G must have afixed point r∈X such that f(r)=0.5The Discrete Brouwer’s Fixed Point TheoremIn this section,the fundamental discretefixed point theorem will be employed to prove afixed point theorem concerning simplicial direction-preserving maps. It can be recognized as a discrete version of Brouwer’sfixed point theorem.It states that for any simplicial direction-preserving map from somefinite set to its convex hull,there must exist afixed point in the definition domain.We will also derive the theorem of Murota,Iimura and Tamura as a simple corollary.Actually,the one derived here is much stronger than theirs.5.1PreliminariesWe use e k to denote the k th unit vector of Z d where e k k=1and e k i=0for all i:1≤i=k≤d.Definition11For every(d−1)-simplex S∈F S,we let e S be the unit vector which is outgoing and perpendicular to S.For all r∈X if e S·(r−r S)>0for some r S∈S. Construction1(Extension of Simplicial Decomposition)Let X⊂R d be afinite set and S be a simplicial decomposition of X.For every point r/∈Given a simplicial direction-preserving map M=(F,X,S),we can convert it into a direction-preserving function G=(f,X,S)as follows.Construction2Given a simplicial direction-preserving map M=(F,X,S), we can build a simplicial direction-preserving function G=(f,X,S)as follows. For every r∈X,if F(r)=r,then f(r)=0.Otherwise,let i:1≤i≤d be the smallest integer such that F i(r)−r i=0,then f(r)=sign(F i(r)−r i)e i.5.2The Key LemmaLemma2Let M=(F,X,S)be a simplicial direction-preserving map where F is from X toX′where F′(r)=F((n+1)r) n+1.Let G′be the function constructed from map M′=(F′,X′,S′),then it is easy to check that N G=N G′.Therefore,we only need to prove the lemma for maps M=(F,X,S)with X⊂(−1,1)d.From now on,we always assume that X⊂(−1,1)d.If f has afixed point in set B X,then the lemma is proven.Otherwise,we extend(by applying Construction1for d times)G=(f,X,S)to be a new function G∗=(f∗,X∗,S∗)such that X⊂X∗,Lemma3guarantees the existence of G′.Lemma3For every triple G=(f,X,S)which satisfies all the conditions inDefinition12,there exists a triple G′=(f′,X′,S′)which is an extension of G along the k th coordinate.Proof.We only need to prove that there exists a simplicial decomposition S′ofX′satisfies S⊂S′.Actually,it can be constructed as follows.We list all the points in X′−X using the lexicographic order,add them into X one by one,and extend the original decomposition S step by step using the method described inDefinition1.Definition13G∗is said to be an extension of G if there exists a sequence G d+1...G2,G1such that G d+1=G,G∗=G1and G i is an extension of G i+1along the i th coordinate.The existence of G∗is guaranteed by Lemma3.Let G k=(f k,X k,S k).The following lemma is easy to check.Lemma4If r∈X k,r′∈[−1,1]d and r i=r′i for all1≤i<k,then r′∈X k.The following two corollaries can be derived from Lemma4.Corollary1X. Corollary2If v=e k−1or−e k−1is an outgoing vector at r∈X k,thenr+ǫv+di=kc i e i/∈X.If G is the function constructed from M using the method in Definition2,then any extension G∗of G is also simplicial direction-preserving.7Proof.We will use induction on k to prove that triple G k=(f k,X k,S k)is a simplicial direction-preserving function.The case for k=d+1is trivial.For case k≤d,if G k is not direction-preserving,then there must exist S∈S k−S k+1 and r1,r2∈V S such that f k(r1)and f k(r2)are opposite.As G k+1is direction-preserving,one of these two points belongs to X k+1,and the other is added into X k when G k+1is extended along the k th coordinate.Without loss of generality,we assume r1∈X k+1and r2k=1.As a result, f k(r2)=−e k and f k(r1)=+e k,as f k(r1)is opposite to f k(r2).The value of f k(r1)implies r1∈X and f(r1)=+e k.The way we construct G from map M guarantees F i(r1)=r1i for any1≤i<k and F k(r1)>ing Corollary2, we see that+e k is not an outgoing vector at r1∈X k+1,as F(r1)∈X k+1. Hence lemma5asserts that no pair(r2,S)where r2∈X k−X k+1and S∈S k−S k+1can satisfy that r2k=+1and r1,r2∈V S,which contradicts with our assumption in thefirst paragraph.Property1is a simple corollary of Lemma7.Lemma7For every triple G=(f,X,S)wherefinite set X⊂(−1,1)d,S is a simplicial decomposition of X and f is a direction function on X,if G∗= (f∗,X∗,S∗)is an extension of G,then N G∗is odd.Proof.We will use induction on d.The base case for d=1is trivial.For case d≥2,wefirst prove that every bad(d−1)-simplex S∈S∗on the boundary of [−1,1]d satisfies r d=−1for any r∈V S.Let S∈F S∗be such a simplex,then there exists r∈V S satisfies f∗(r)=+e d according to the definition of badness. Thus r is added into X when it is extended along the d th coordinate.We have r d=−1and−1<r i<1for any1≤i<d.This shows that S is covered by the hyperplane H which passes0[d→−1]and is perpendicular to+e d.Assume N is the number of bad(d−1)-simplices in H,then we only need to prove N is odd.Let X′=P(X)and X′′=P(H∩X∗)where projection P(r)=(r1,r2,...r d−1)∈R d−1,then S′and S′′are simplicial decompositions of X′and X′′respectively whereS′= P(S)S∈S∗and V S⊂X[d→−1] ,S′′= P(S)S∈S∗and S⊂H .Let f′be an arbitrary direction function on X′,then we extend it to be direc-tion function f′′on X′′as follows.For any r∈X′,f′′(r)=f′(r).Otherwise, f′′(r)=f∗((r1,r2,...r d−1,−1)).It’s easy to check that G′′=(f′′,X′′,S′′)is an extension of triple G′=(f′,X′,S′)in the(d−1)-dimensional space.Using arguments which are similar to those in the proof of Lemma1,the parity of N is same as the number of bad(d−2)-simplices on the boundary of8G′′.We know that the latter is odd according to the induction hypothesis,and Property1is proven.Property2.Let M=(F,X,S)be a simplicial direction-preserving map where F maps X toX, there must exist afixed point in X.Now we prove thefixed point theorem of Murota,Iimura and Tamura[13] as a direct corollary of Theorem4.Lemma8(Property of Integrally Convex Sets[13])For every integrally convex set X,there exists a simplicial decomposition S ofX,letting S x∈S be the smallest simplex containing x,then all of its vertices belong to N(x)={r∈Z d|||r−x||∞<1}.Let F be a hypercubic direction-preserving map from integrally convex set X⊂Z d todirection-preserving map from X toC a,b=X=∪P∈P P,and for every polytope P∈P, all of its vertices are drawn from X;2).For every two polytopes P1,P2∈P,if P1∩P2=∅,then P1∩P2is a face of both P1and P2.Definition16Let P be a convex t-polytope in R d and V P be its vertex set.The center point c P of polytope P is defined as c P= r∈V P(r/|V P|).Obviously,we have c P∈P and c P/∈V P.For example,let C⊂Z d be a t-cube centered at r∈Z d and perpendicular to T,then the center point c ofX into X and construct a simplicial decomposition S′for the new set X′. Details of the construction are described by the algorithm in Figure1. Every lattice set C a,b⊂R d has a natural convex subdivision P where P= {Fig.1.The Construction of S′and X′6.2Extension of Hypercubic Direction-Preserving FunctionsLet f be a hypercubic direction-preserving function on C a,b,we now extend it onto set D a,b as follows.For every r∈D a,b−C a,b,assume it is the center point of t-cube C⊂C a,b.If0∈f(C),then f(r)=0.Otherwise,let1≤t≤d be the largest integer such that f(C)∩{±e t}=∅,then f(r)=e t if e t∈f(C)and f(r)=−e t if−e t∈f(C).One can prove the following two properties.Property1Let f be a hypercubic direction-preserving function on C a,b⊂Z d, then G=(f,D a,b,S)is a simplicial direction-preserving function.Property2If the extended function G=(f,D a,b,S)has afixed point in D a,b, then the original function must have afixed point in C a,b.6.3The Nature of Bad CubesWe are ready to give an explicit explanation for the definition of bad cubes. Lemma9Let f be a hypercubic direction-preserving function on C a,b⊂Z d and G=(f,D a,b,S)be the extend function.For every t-cube C t in C a,b where 0≤t≤d−1,it is bad relative to f iffthe cardinality of the following set is odd:S C t= t-simplex S∈S is bad relative to G S⊂C t,then the way we build simplicial decomposition S implies that t-simplex S t⊂C t where S t−1is used to denote(t−1)-simplices in S.Firstly,we prove that,if t-cube C t⊂Z d is not bad,then|S C t|is even.If 0∈f(C t),then f(c)=0.As each t-simplex inC t,e k/∈f(V S),and thus,S C t=∅.Otherwise,we have f(C t)= {e1,...,e t+1},and thus f(c)=e t+1.Because C t is not bad,the number of bad11(t−1)-cubes on the boundary of C t is ing the induction hypothesis on t−1,a(t−1)-cube is bad iffthe number of bad(t−1)-simplices in it is odd. As a result,the number of bad(t−1)-simplices on the boundary of C t is even. Using the equation in thefirst paragraph,we know|S C t|is even too.On the other hand,we prove if C t is bad,then|S C t|is odd.Since f(C t)= {e1,...,e t+1},we have f(c)=e t+1.As the number of bad(t−1)-cubes on the boundary of C t is odd,the number of bad(t−1)-simplices on the boundary of C t is also odd,according to the induction hypothesis on case t−ing the equation in thefirst paragraph again,we know|S C t|is odd.We now get Lemma10as a direct corollary of Lemma9.Lemma10The parity of N B(the number of bad(d−1)-cubes on the boundary of C a,b)is same as the one of N G(the number of bad(d−1)-simplices on the boundary of D a,b).With Property1,2and Lemma10above,Chen and Deng’s theorem can be immediately derived from the fundamental discretefixed point theorem.7Concluding RemarksIn this paper,we generalize the concept of direction-preserving maps and char-acterize a new class of discrete maps over simplicial structures.The fundamental discretefixed point theorem is then proposed,which is based on the counting of bad(d−1)-simplices on the boundary.The power of this theorem is demon-strated in two ways.First,it is applied to prove the discrete Brouwer’sfixed point theorem which is much more general than the one of Murota,Iimura and Tamura.Second,we resolve the puzzle of bad cubes,and show that the bound-ary condition of Chen and Deng’s theorem is exactly equivalent to the one of the fundamental theorem.Our work would immediately imply the corresponding discrete concept of degree.It would be an especially interesting problem to study the case when the fixed point is defined in the recent model of a set of points.An immediate follow-up research direction is to understand other concepts and theorems related to degree.A clear understanding would definitely advance the state of art of the numerical computation of related problems,such as the case of discretefixed points versus approximatefixed points[1].References1.X.Chen and X.Deng.On Algorithms for Discrete and Approximate BrouwerFixed Points.In STOC2005,pages323–330.2.X.Chen and X.Deng.3-Nash is PPAD-complete.ECCC,TR05-134,2005.3.X.Chen and X.Deng.Settling the Complexity of Two-Player Nash-Equilibrium.FOCS,2006.124.X.Chen,X.Deng,and S-H puting Nash Equilibria:Approximationand Smoothed Complexity.FOCS,2006.5.X.Chen and ttice Embedding of Direction-Preserving CorrespondenceOver Integrally Convex Set.AAIM2006,2006,pp.53–63.6.X.Chen and X.Deng.On the Complexity of2D Discrete Fixed Point Problem.ICALP2006,pp.489–5007.P.Crescenzi and R.Silvestri.Sperner’s lemma and robust put.Complexity,7(2):163–173,1998.8. C.Daskalakis,P.W.Goldberg,and C.H.Papadimitriou.The Complexity of Com-puting a Nash Equilibrium.STOC,2005.9. C.Daskalakis and C.H.Papadimitriou.Three-player games are hard.ECCC,TR05-139.10.K.Friedl,G.Ivanyos,M.Santha,and F.Verhoeven.On the black-box complexityof Sperner’s Lemma.In FCT2005.11.M.D.Hirsch,C.H.Papadimitriou,and S.Vavasis.Exponential lower bounds forfinding Brouwerfixed plexity,5:379–416,1989.12.T.Iimura.A discretefixed point theorem and its applications.Journal of Mathe-matical Economics,39(7):725–742,2003.13.T.Iimura,K.Murota,and A.Tamura.Discrete Fixed Point Theorem Reconsid-ered.Journal of Mathematical Economics,to appear.an,D.Talman,and Z.Yang.Solving discrete zero point problems.TinbergenInstitute Discussion Papers,2004.15. E.Sperner.Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes.16.G.M.Ziegler.Lectures on Polytopes.Springer-Verlag,New York,1982.13。