Nash - Compact Numerical Methods for Computers (523163), страница 31
Текст из файла (страница 31)
Because it has only one parameter it isusually termed the linear search problem. The comparable nonlinear-equationproblem is usually called root-finding. For the case that f ( b) is a polynomial ofdegree (K – 1), that is(12.8)the problem has a particularly large literature (see, for instance, Jenkins andTraub 1975).144Compact numerical methods for computersExample 12.1. Function minimisation-optimal operation of a public lotteryPerry and Soland (1975) discuss the problem of deciding values for the mainvariables under the control of the organisers of a public lottery.
These are p, theprice per ticket; u, the value of the first prize; w, the total value of all other prizes;and t, the time interval between draws. If N is the number of tickets sold, theexpected cost of a single draw isK1 + K2 Nthat is, a fixed amount plus some cost per ticket sold. In addition, a fixed cost pertime K3 is assumed. The number of tickets sold is assumed to obey a CobbDouglas-type production functionwhere F is a scale factor (to avoid confusion the notation has been changed fromthat of Perry and Soland). There are a number of assumptions that have not beenstated in this summary, but from the information given it is fairly easy to see thateach draw will generate a revenueR = Np – (v + w + K2 + K2N + K3t).Thus the revenue per unit time isR/t = –S = [(p – K2 )N – (v + w + K1)]/ t – K3.Therefore, maximum revenue per unit time is found by minimising S( b) whereExample 12.2.
Nonlinear least squaresThe data of table 12.1 are thought to approximate the logistic growth function(Oliver 1964)g(x) = b 1/[1 + b2exp(xb3 )]for each point x=i. Thus the residuals for this problem aref i = b 1 /[1 + b 2exp(ib3)] – Yi1 .(12.9)(12.10)Example 12.3. An illustration of a system of simultaneous nonlinear equationsIn the econometric study of the behaviour of a market for a given commodity, thefollowing relationships are observed:quantity produced = q = Kpαwhere p is the price of the commodity and K and α are constants, andquantity consumed or demanded = q = Zp- βOptimisation and nonlinear equations145T ABLE 12.1. Nonlinear leastsquares data of example 12.2.iYil1234567891011125·3087·249·63812·86617·06923·19231·44338·55850·15662·94875·99591·972where Z and β are constants. In this simple example, the equations reduce toorso thatHowever, in general, the system will involve more than one commodity and willnot offer a simple analytic solution.Example 12.4.
Root-findingIn the economic analysis of capital projects, a measure of return on investmentthat is commonly used is the internal rate of return r. This is the rate of interestapplicable over the life of the project which causes the net present value of theproject at the time of the first investment to be zero.
Let yli be the net revenue ofthe project, that is, revenue or income minus loss or investment, in the ith timeperiod. This has a present value at the first time period ofy l i /(1 + 0·01r)i -1where r is the interest rate in per cent per period. Thus the total present value atthe beginning of the first time period iswhere K is the number of time periods in the life of the project. By settingb = 1/(1 + 0·01r)this problem is identified as a polynomial root-finding problem (12.8).146Compact numerical methods for computersExample 12.5. Minimum of a function of one variableSuppose we wish to buy some relatively expensive item, say a car, a house or anew computer.
The present era being afflicted by inflation at some rate r, we willpay a priceP(1 + r) tat some time t after the present. We can save at s dollars (pounds) per unit time,and when we buy we can borrow money at an overall cost of (F – 1) dollars perdollar borrowed, that is, we must pay back F dollars for every dollar borrowed. Fcan be evaluated given the interest rate R and number of periods N of a loan asF = NR (1 + R )N/[(1 + R ) N – 1].Then, to minimise the total cost of our purchase, we must minimiseS(t) = ts + [P(1 + r)t – ts]F= ts(1 – F) + FP(1 + r)t.This has an analytic solutiont = 1n{(F – 1)s/[FP ln(1 + r)]}/ln(1 + r).However, it is easy to construct examples for which analytic solutions are harderto obtain, for instance by changing inflation rate r with time.12.2.
DIFFICULTIES ENCOUNTERED IN THE SOLUTION OFOPTIMISATION AND NONLINEAR-EQUATION PROBLEMSIt is usually relatively easy to state an optimisation or nonlinear-equation problem. It may even be straightforward, if tedious, to find one solution. However, tofind the solution of interest may be very nearly impossible.In unconstrained minimisation problems the principal difficulty arises due tolocal minima. If the global minimum is sought, these local minima will tend toattract algorithms to themselves much as sand bunkers attract golf balls on thecourse. That is to say, there may be no reason why a particular local minimum willbe found; equally there is no reason why it will not.
The nonlinear-equationproblem which arises by setting the derivatives of the function to zero will havesolutions at each of these local minima. Local maxima and saddle points will alsocause these equations to be satisfied.Unfortunately, very little research has been done on how to get the desiredsolution. One of the very few studies of this problem is that of Brown andGearhart (1971) who discuss deflation techniques to calculate several solutions ofsimultaneous nonlinear equations. These methods seek to change the equationsbeing solved so that solutions already found are not solutions of the modifiedequations. The interested reader will also find an excellent discussion of thedifficulties attendant on solving nonlinear equations and minimisation problems inActon (1970, chaps 2 and 14).
The traditional advice given to users wishing toavoid unwanted solutions is always to provide starting values for the parameterswhich are close to the expected answer. As Brown and Gearhart (1971) haveOptimisation and nonlinear equations147pointed out, however, starting points can be close to the desired solution withoutguaranteeing convergence to that solution. They found that certain problems incombination with certain methods have what they termed magnetic zeros to whichthe method in use converged almost regardless of the starting parameters employed.
However, I did not discover this ‘magnetism’ when attempting to solve thecubic-parabola problem of Brown and Gearhart using a version of algorithm 23.In cases where one root appears to be magnetic, the only course of action onceseveral deflation methods have been tried is to reformulate the problem so thedesired solution dominates. This may be asking the impossible!Another approach to ‘global’ minimisation is to use a pseudo-random-numbergenerator to generate points in the domain of the function (see Bremmerman(1970) for discussion of such a procedure including a FORTRAN program). Suchmethods are primarily heuristic and are designed to sample the surface defined bythe function. They are probably more efficient than an n-dimensional grid search,especially if used to generate starting points for more sophisticated minimisationalgorithms. However, they cannot be presumed to be reliable, and there is a lackof elegance in the need for the shot-gun quality of the pseudo-random-numbergenerator.
It is my opinion that wherever possible the properties of the functionshould be examined to gain insight into the nature of a global minimum, andwhatever information is available about the problem should be used to increasethe chance that the desired solution is found. Good starting values can greatlyreduce the cost of finding a solution and greatly enhance the likelihood that thedesired solution will be found.Previous Home NextChapter 13ONE-DIMENSIONAL PROBLEMS13.1. INTRODUCTIONOne-dimensional problems are important less in their own right than as a part oflarger problems.
‘Minimisation’ along a line is a part of both the conjugategradients and variable metric methods for solution of general function minimisation problems, though in this book the search for a minimum will only proceeduntil a satisfactory new point has been found. Alternatively a linear search isuseful when only one parameter is varied in a complicated function, for instancewhen trying to discover the behaviour of some model of a system to changes inone of the controls. Roots of functions of one variable are less commonly neededas a part of larger algorithms. They arise in attempts to minimise functions bysetting derivatives to zero. This means maxima and saddle points are also found,so I do not recommend this approach in normal circumstances. Roots of polynomials are another problem which I normally avoid, as some clients have a nastyhabit of trying to solve eigenproblems by means of the characteristic equation.The polynomial root-finding problem is very often inherently unstable in that verysmall changes in the polynomial coefficients give rise to large changes in the roots.Furthermore, this situation is easily worsened by ill chosen solution methods.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
