Nash - Compact Numerical Methods for Computers (523163), страница 36
Текст из файла (страница 36)
Figure 13.1 shows plots of the twofunctions obtained on a Hewlett-Packard 9830 calculator.One-dimensional problems165TABLE 13.1. Values found in example 13.2.bf(b)00·10·20·30·40·410·420·430·440·450·460·470·480·490·50·60·70·80·91·0-1·00001-1·00001-1·00001-1·00001-1·00001-1·00001-0·999987-0·999844-0·998783-0·990939-0·932944-0·5054712·597222·840498·9994199199199199199Example 13.3. Actuarial calculationsThe computation of the premium for a given insurance benefit or the level ofbenefit for a given premium are also root-finding problems. To avoid oversimplifying a real-world situation and thereby presenting a possibly misleadingimage of what is a very difficult problem, consider the situation faced by someenterprising burglars who wish to protect their income in case of arrest.
In theirforesight, the criminals establish a cooperative fund into which each pays apremium p every period that the scheme operates. If a burglar is arrested he ispaid a fixed benefit b. For simplicity, let the number of members of the scheme befixed at m. This can of course be altered to reflect the arrests and/or admission ofnew members. The fund, in addition to moneys mp received as premiums in eachperiod, may borrow money at a rate rb to meet its obligations and may also earnmoney at rate re. The fund is started at some level f 0. The scheme, to operateeffectively, should attain some target fT after T periods of operation.
However, inorder to do this, it must set the premium p to offset the benefits nib in each periodi, where ni is the number of arrests in this period. If historical data are available,then these could be used to simulate the behaviour of the scheme. However,historical data may reflect particular events whose timing may profoundly influence the profitability of the scheme.
That is to say, the equationF (p ,n) -f T = 0(13.32)may require a very much higher premium to be satisfied if all the arrests occur166Compact numerical methods for computersFIGURE 13.1. Function (13.28) for (a) t = 0·5, z = 100, s = 100. w =0·99, and (b) t = 0·5, z = 100, s = 1, w = 0·2.early in the simulation period than if they occur at the end. Therefore. it is likelythat any sensible simulation.
will use root-finding to solve (13.32) for p for avariety of sets of arrest figures n. In particular, a pseudo-random-numbergenerator can be used to provide such sets of numbers chosen from somedistribution or other. The function is then computed via one of the two recurrencerelationsf i+ 1 (p)=f i(p)(1+r e ) +mp(1+0·5r e ) -n i bfor fi (p)>0(13.33)orf i+ 1 (p ) =f i(p )(1+r b ) +m p(1+0·5r e ) -n i bf o r f i(p)<0.(13.34)Note that our shrewd criminals invest their premium money to increase the fund.The rate 0·5r e is used to take account of the continuous collection of premiumpayments over a period.To give a specific example consider the following parameters: benefit b=1200,membership m=2000, interest rates r=0·08 and rb=0·15, initial fund f 0=0and after 10 periods f10=0 (a non-profit scheme!).
The root-finding algorithm isthen applied using u=0, v=2000. Three sets of arrest figures were used to167One-dimensional problemssimulate the operation of the scheme. The results are given in table 13.2. Thearrests are drawn from a uniform distribution on (0,400).TABLE 13.2. Simulated operation of an income insurance program.86·0792·90Premium =Periodnj123456789100227912437435610128123117Total1657f i (P)nj193237·50399533·94289934·12357566·31130609·06-92904·75-34802·94-183985·87-49546·25-0·6917232317677455152304113181109·92f i (P)njf i (P)158630·9471952·31-123660·62-43578·7540115·38156355·50165494·81-7034·6935341·00-0·81188315194313357127387551483029·50146098·69-172183·94-344982·00-210099·75-21385·1951636·50-180003·12-44374·06-0·6915121769Function evaluationsto find root1014(Total benefits)/(numberof premiums paid)99·4290·7211106·14The last entry in each column is an approximation based on no interest paid or earned in the fundmanagement.
Thusapproximate premium = total arrests * b/(n* T)= total arrests * 0·06.These examples were run inFORTRANonan IBM 370/168.Previous Home NextChapter 14DIRECT SEARCH METHODS14.1. THE NELDER-MEAD SIMPLEX SEARCH FOR THEMINIMUM OF A FUNCTION OF SEVERAL PARAMETERSThe first method to be examined for minimising a function of n parameters is asearch procedure based on heuristic ideas.
Its strengths are that it requires noderivatives to be computed, so it can cope with functions which are not easilywritten as analytic expressions (for instance, the result of simulations), and that italways increases the information available concerning the function by reporting itsvalue at a number of points.
Its weakness is primarily that it does not use thisinformation very effectively, so may take an unnecessarily large number offunction evaluations to locate a solution. Furthermore, the method requires (n+1)by (n+2) storage locations to hold intermediate results in the algorithm, so is notwell adapted to problems in a large number of parameters. However.
for morethan about five parameters the procedure appears to become inefficient. Justification of the choice of this algorithm is postponed until §14.4.The original paper of Nelder and Mead (1965) outlines quite clearly andsuccinctly their method, which is based on that of Spendley et al (1962). Themethod will be described here to point out some particular modifications neededto improve its reliability on small machines, particularly those with arithmetichaving few digits in the mantissa.A simplex is the structure formed by (n+1) points, not in the same plane, in ann-dimensional space. The essence of the algorithm is as follows: the function isevaluated at each point (vertex) of the simplex and the vertex having the highestfunction value is replaced by a new point with a lower function value.
This is donein such a way that ‘the simplex adapts itself to the local landscape, and contractson to the final minimum.’ There are four main operations which are made on thesimplex: reflection, expansion, reduction and contraction. In order to operate onthe simplex, it is necessary to order the points so that the highest is b H, the nextto-highest bN, and the lowest b L.
Thus the associated function values obeyS(b H )>S(b N )>S(b i)>S(b L )(14.1)for all i H, N or L. Figure 14.1 illustrates the situation.The centroid of all the points other than b H is defined by(14.2)Direct search methods169FIGURE 14.1. Points generated by the Nelder-Mead simplex algorithmin two dimensions. Point 1, b L, the lowest vertex in the simplex; point2, bN, the next-to-highest vertex: and point 3, b H, the highest vertex.Point 4, b C, the centroid of all points except b H, that is, of bN and b L .Also one of the points generated by a general contraction of thesimplex towards bL. Point 5, b R, the reflection of b H through bc; point 6,b E, the result of extension of the line (b C, b R); point 7, the result ofreduction of the line (b C, b R) which occurs when b R is lower than b Hbut higher than b N; and point 8, the result of reduction of the line(b C, b H).
Point 9, one of the points of the simplex generated by ageneral contraction of the simplex made up of vertices 1, 2 and 3towards b L .The operation of reflection then reflects bH through b C using a reflection factor (a,that isb R = b C +a(b C -bH )= ( l +a)b C -ab H .(14.3)If S(b R) is less than S(b L) a new lowest point has been found, and the simplex canbe expanded by extending the line (bR -b C ) to give the point(14.4)where γ, the expansion factor, is greater than unity or else (14.4) represents acontraction. If S(bE)<S(b R) then b H is replaced by b E and the procedurerepeated by finding a new highest point and a new centroid of n points b C .Otherwise b R is the new lowest point and it replaces b H .170Compact numerical methods for computersIn the case where b R is not a new lowest point, but is less than b N, thenext-to-highest point, that isS( b L )<S(b R ) <S(b N )(14.5)b H is replaced by b R and the procedure repeated.
In the remaining situation, wehave S(b R) at least as great as S(b N) and should reduce the simplex.There are two possibilities. (a) IfS (b N )<S(b R )<S(b H )(14.6)then the reduction is made by replacing b H by b R and finding a new vertexbetween bC and b R (now b H). This is a reduction on the side of the reflection(‘low’ side). (b) If(14.7)S(bR )>S(b H )the reduction is made by finding a new vertex between b C and b H (‘high’ side).In either of the above cases the reduction is controlled by a factor β between 0and 1. Since case (a) above replaces b H by bR the same formula applies for thenew point bS (‘S’ denotes that the simplex is smaller) in both cases.
b H is used todenote both bR and b H since in case (a) b R has become the new highest point inthe simplex(14.8)The new point b S then replaces the current b H, which in case (a) is, in fact, b R ,unless(14.9)S(b S)>min(S(b H ),S( b R ) ) .The replacement of b H by b R in case (a) will, in an implementation, mean thatthis minimum has already been saved with its associated point. When (14.9) issatisfied a reduction has given a point higher than S( b N), so a general contractionof the simplex about the-lowest point so far, b L, is suggested. That is(14.10)for all i L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
