Downloaded from https://www.everyspec.com AMCP 706-197 The second necessary condition is that the Define also, matrix of second partial derivatives evaluated s, =-TfAxI), (124) at x* be positive sermidefinite. Any point x* t g o f . (12a ) that satisfies Eq. 12-2 is called a stationary the gradient of f. Both x v and r ae known point of f(x). Sufficient conditions for a rel- vectors; a is the only unknown variable in Eq. tive minimum are that the matrix of second 12-3. partial derivatives of f(x) be poaztive definite The method of steepest descent converges and that Eq. 12-2 must hold. to at least a local minimum of (x), providing certain mWl restrictions are met (Ref. 5).
The 12-2 NUMERICAL METHODS FOR F!!'JD- computations in Stelp 2, 3, -A- 4 of the -: ING UNCONSTRAINED MINIMA steepest descent method are repeated until a satisfactory value for x is found. The most obvious approach to finding the Several tests for determining when the minimum of f(x) is to solve Eq. 12-2. If f(x) is computation should be stopped are also listed not quadratic, Eq. 12-2-the set of n equa- in Table 12-1. Stop Criteria 1 and 2 are based tions in n unknowns-is nonlinear, and solving on the fact that the gradient vanishes at a large sets of nonlinear equations is usually a minimum. When Criteria 3 and 4 are used, the very difficult task.
The function f(x) may be computation will stop if the function value or so complicated that it is difficult even to current point changes by less than some small write Eq. 12-2 in closed form. Further, even if value e. It has been found that Criterion 3 is the equations could be solved, there would be the most depeihdable, providing it is met for no guarantee that a given solution represented several successive values of i. In all criteria, e an actual minimum rither than some saddle is a small positive number which the user se- point or maximum. We will, therefore, consid- lects.
As e decreases, the location of the mini- er other methods of locating unconstrained mum is more accurate, but more iterations are minima, required to achieve this accuracy. * 12-2.1 GRADIENT METHODS 12-2.1.2 Cubic and Quadratic Interpolation If f(x) is continuous and differentiable, a Fum ntunber of minimization techniques using the Finding a value a* to minimize Eq. 12-3 gradient of f(x) are available. The gradient can be thought of as a problem of 1-dimen- Vf(x) is a vector pointing in the direction of sional minimization in the direction of s i . The greatest increase of f(x).
At any pointx, the cubic interpolation procedure outlined in gratstin reseof &) A a y oit 0,th Tble 12-1 so :es this problem for any given vector f(x) is normal to the contour of con- dabe 11 so in his poe fony in stant function value which passes through x. directin of; in which the function f(x) ini- Two methods are presented. tially decreases. For the cubic interpolation procedure and 12-2.1.1 Steepest Descent the quadratic interpolation which follows, the components of x are scaled so that a unit The method of steepest descent for mini- change in any variable is an important (but mizing f(x) is detailed in Table 12-1.
In Step not too large) fractional change in that vari- 2, the gradient can be found either by analyt- able. For example, if a capacitor is expected ic formulas or by computing differences. Step to have a value near 100pF, then a lpF 3 uses the direction of search determined hn change would be important, but a 10pF Step 2 and decides how far to move in this change would be too large. direction. The computer spends most of its Steps 1 and 2 of the cubic interpolation time computing the gradient in this method, procedure normalize s so that its components so the step length, a, for Step i is selected to are less than or equal to 1 in magnitude.
This, get the largest possible decrease in f(x) for along with scaling, insures that s is a reason- each gradient computation. Therefore, aj is able change in x. Step 3 moves along the di- selected to minimize the function rection s to place the desired minimum value g(A) = f(x + Qsj) . (12-3) a* in the interval a ** b. Steps 4 thro-,igh 12-2