Nash - Compact Numerical Methods for Computers (523163), страница 48
Текст из файла (страница 48)
Note that both smallerand larger values of h generated better approximations for the derivative of thisfunction. The exponential function is changing only very slowly near this point.18.3. CONSTRAINED OPTIMISATIONThe general constrained function minimisation problem is stated: minimise S ( b )with respect to the parameters bi, i=1, 2, . . . , n, subject to the constraintsc j(b)=0j =1, 2, . .
. ,m(18.7)hk (b) <0k=1, 2, . . . , q.(18.8)andIn general, if the constraints c are independent, m must be less than n , since viasolution of each constraint for one of the parameters b in terms of the others, thedimensionality of the problem may be reduced. The inequality restrictions h, onthe other hand, reduce the size of the domain in which the solution can be foundwithout necessarily reducing the dimensionality.
Thus there is no formal bound tothe number, q, of such constraints. Note, however, that the two inequalitiesh(b)<0h(b)> 0(18.9)are obviously equivalent to a single equality constraint. Moreover, a very simplechange to the constraints (1 8.9) to giveh(b)+ ε < 0h(b) - ε > 0(18.10)for ε > 0 shows that the inequality constraints may be such that they can never besatisfied simultaneously. Problems which have such sets of constraints are termedinfeasible.
While mutually contradicting constraints such as (18.10) are quiteobvious, in general it is not trivial to detect infeasible problems so that theirdetection can be regarded as one of the tasks which any solution method shouldbe able to accomplish.There are a number of effective techniques for dealing with constraints inminimisation problems (see, for instance, Gill and Murray 1974). The problem isby and large a difficult one, and the programs to solve it generally long andcomplicated.
For this reason, several of the more mathematically sophisticatedmethods, such as Lagrange multiplier or gradient projection techniques, will notbe considered here. In fact, all the procedures proposed are quite simple and allinvolve modifying the objective function S(b) so that the resulting function has itsunconstrained minimum at or near the constrained minimum of the originalfunction. Thus no new algorithms will be introduced in this section.Elimination or substitutionThe equality constraints (18.7) provide m relationships between the n parametersb.
Therefore, it may be possible to solve for as many as m of the b ’s in terms of222Compact numerical methods for computersthe other (n-m). This yields a new problem involving fewer parameters whichautomatically satisfy the constraints.Simple inequality constraints may frequently be removed by substitutions whichsatisfy them. In particular, if the constraint is simplybk > 0then a substitution of(18.11)for bk suffices. If, as a further case, we havev > bk > u(18.12)then we can replace bk by(18.13)It should be noted that while the constraint has obviously disappeared, thesesubstitutions tend to complicate the resulting unconstrained minimisation byintroducing local minima and multiple solutions.
Furthermore, in many casessuitable substitutions are very difficult to construct.Penalty functionsThe basis of the penalty function approach is simply to add to the function S( b )some positive quantity reflecting the degree to which a constraint is violated. Suchpenalties may be global, that is, added in everywhere, or partial, that is, onlyadded in where the constraint is violated. While there are many possibilities, herewe will consider only two very simple choices.
These are, for equality constraints,the penalty functions(18.14)and for inequalities, the partial penalty(18.15)where H is the Heaviside functionf o r x >0f o r x<0.(18.16)The quantities wj, j=1, 2, . . . , m, and Wk , k=1, 2, . . . , q, are weights whichhave to be assigned to each of the constraints.
The function(18.17)then has an unconstrained minimum which approaches the constrained minimumof S(b) as the weights w, W become large.The two methods outlined above, while obviously acceptable as theoreticalapproaches to constrained minimisation, may nonetheless suffer serious difficultiesin the finite-length arithmetic of the computer. Consider first the example:minimise( b 1 +b 2 - 2 ) 2(18.18 a)Left-overs223subject to(18.18b)This can be solved by elimination. However, in order to perform the elimination itis necessary to decide whether(18.19)or(18.20)The first choice leads to the constrained minimum at b 1= b 2=2-½.
The secondleads to the constrained maximum at b1 =b 2=-2-½. This problem is quite easilysolved approximately by means of the penalty (18.14) and any of the unconstrained minimisation methods.A somewhat different question concerning elimination arises in the followingproblem due to Dr Z Hassan who wished to estimate demand equations forcommodities of which stocks are kept: minimise(18.21)subject tob3 b6= b4 b5 .(18.22)The data for this problem are given in table 18.2. The decision that must nowbe made is which variable is to be eliminated via (18.22); for instance, b 6 can befound as(18.23)b 6= b 4 b 5 /b3 .The behaviour of the Marquardt algorithm 23 on each of the four unconstrainedminimisation problems which can result from elimination in this fashion is shownin table 18.3.
Numerical approximation of the Jacobian elements was used to savesome effort in running these comparisons. Note that in two cases the algorithmhas failed to reach the minimum. The starting point for the iterations was bj =1,j=l, 2, . . . , 6, in every case, and these failures are most likely due to the largedifferences in scale between the variables. Certainly, this poor scaling is responsible for the failure of the variable metric and conjugate gradients algorithms whenthe problem is solved by eliminating b 6. (Analytic derivatives were used in thesecases.)The penalty function approach avoids the necessity of choosing which parameter is eliminated.
The lower half of table 18.3 presents the results of computationswith the Marquardt-like algorithm 23. Similar results were obtained using theNelder-Mead and variable metric algorithms, but the conjugate gradients methodfailed to converge to the true minimum. Note that as the penalty weighting w isincreased the minimum function value increases. This will always be the case if aconstraint is active, since enforcement of the constraint pushes the solution ‘upthe hill’.Usually the penalty method will involve more computational effort than theelimination approach (a) because there are more parameters in the resulting224Compact numerical methods for computersTABLE 18.2.
Data for the problem of Z Hassan specified by (18.21) and (18.22). Column j belowgives the observations yij , for rows i=1, 2, . . . , m, for m = 26.12286·75274·857286·756283·461286·05295·925299·863305·198317·953317·941312·646319·625324·063318·566320·239319·582326·646330·788326·205336·785333·414341·555352·068367·147378·424385·381309·935286·75274·857286·756283·461286·05295·925299·863305·198317·953317·941312·646319·625324·063318·566320·239319·582326·646330·788326·205336·785333·414341·555352·068367·147378·42434-40·40261·370743·1876-20·032431·222647·27994·885562·2257·36613·48287·030338·717715·120421·309842·788145·746457·992365·038351·866167·043339·674749·06118·449174·5368106·711134·6711132·661092·261093·631136·811116·7811481195·281200·171262·391319·761323·241330·271368·991384·111405·421448·211493·951551·941616·981668·851735·891775·571824·631843·081917·612024·3250·14170·016260·017550·114850·001937-0·03540·002210·001310·011560·039820·03795-0·007370·0041410·010530·0210·032550·0169110·03080·0698210·017460·0451530·039820·020950·014270·101130·2146760·64290·78460·80090·81840·93330·93520·89980·9020·90340·91490·95470·99270·98530·989511·0211·05361·07051·10131·17111·18851·23371·27351·29451·30881·4099unconstrained problem, in our example six instead of five, and (b) because theunconstrained problem must be solved for each increase of the weighting w.Furthermore, the ultimate de-scaling of the problem as w is made large may causeslow convergence of the iterative algorithms.In order to see how the penalty function approach works for inequalityconstraints where there is no corresponding elimination, consider the followingproblem (Dixon 1972, p 92): minimise(18.24)subject to3b1+4b2 <6(18.25)-b1+4 b2 <2.(18.26)andThe constraints were weighted equally in (18.15) and added to (18.24).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
