Broyden formula

It is opportune to consider updating the Jacobian using the Broyden formula, from a geometrical point of view also. 

The Jacobian of the system of constraints can be calculated without considering its structure or it can be updated using the Broyden formula (see Chapter 7). 

One of the most efficient and widely used updating formula is the BFGS update. Broyden (1970), Fletcher (1970), Goldfarb (1970), and Shanno (1970) independently published this algorithm in the same year, hence the combined name BFGS. Here the approximate Hessian is given by... 

The methods differ in the formula used to generate the sequence S, k=0,l,2,., and after Fletcher and Powell s 3 analysis of Davidon s method a whole spate of formulae were invented in the sixties. Broyden 4 introduced some rationalization by identifying a one-parameter family, and recommended a particular member, now commonly referred to as the BFGS (Broyden-Fletcher-Goldfarb-Shanno) formula. Huang 5 widened the family, but by the end of the sixties numerical experience was producing a consensus that the BFGS formula was the most robust of the formulae available. The formula is... 

Produced from the manipulation of the Jacobian are the changes in the variables, i,e., the Ax vector. The variables for the next trial are calculated from x + = x + s Ax (i.e,, . + T = xlk + sk Ajc1jA, etc,). The s scalar is generated to ensure that the norm of functions improve between trial k + 1 and trial k. Usually, s = 1 but may have to be smaller on some trials. The Newton-Raphson method assumes that the curves of the independent functions are close to linear and the slopes will point toward the answers. The MESH equations can be far from linear and the full predicted steps, Ax, can take the next trial well off the curves. The s scaler helps give an improved step search or prevente overstepping the solution. Holland (8) and Broyden (119) present formulas for getting s. ... 

The quasi-Newton methods. In the Newton-Raphson method, the Jacobian is filled and then solved to get a new set of independent variables in eveiy trial. The computer time consumed in doing this can be very high and increases dramatically with the number of stages and components. In quasi-Newton methods, recalculation of the Jacobian and its inverse or LU factors is avoided. Instead, these are updated using a formula based on the current values of the independent functions and variables. Broyden s (119) method for updating the Jacobian and its inverse is most commonly used. For LU factorization, Bennett s (120) method can be used to update the LU factors. The Bennett formula is... 

One of the most successful and widely used updating formulas is known as BFGS for its four developers Broyden, Fletcher, Goldfarb, and Shanno.6 95 It is a rank 2 update with inherent positive-definiteness (i.e., Bk positive-definite Bk+j positive-definite) that was derived bj symmetrizing the Broyden rank 1 update.5 6 95 A sequence of matrices B is generated from a positive-definite B0 (which may be taken as the identity) by the BFGS formula... 

Tomich25 was the first to apply Broyden s method (developed in chap. 15) to the solution of distillation problems. Broyden s method is based on the use of numerical approximations of the partial derivatives appearing in the jacobian matrix. The approach proposed by Broyden permits the inverse of the jacobian matrix to be updated each trial after the first through the use of Householder s formula.6 Thus, it is necessary to invert the jacobian matrix only once. Since approximate values for the partial derivatives are used, procedure 2 generally requires more trials than does procedure 1. However, since the evaluation of the partial derivatives and the inversion of the jacobian matrix are not generally required after the first trial of procedure 2, it requires less computer time per trial than does procedure 1. 

Broyden obtained a first approximation of the elements of J0 by use of the formula... 

In the method proposed by Broyden, Householder s formula was used to obtain the formula for the inverted matrix shown in step 6. The second term on the right-hand side of the expression in step 6 contains the correction proposed by Broyden. 

Instead of applying Householder s formula, the calculation of an inverse of the jacobian may be avoided altogether by use of the algorithm proposed by Bennett for updating the LU factors of the jacobian matrix. Example 4-9 will show that fewer numerical operations are required to compute the LU factors than are required to compute the inverse of a matrix. Bennett s algorithm is applied to the Broyden equations as follows. 

Less time is consumed by procedure 3 than by procedure 1. Calculation of the LU factors of the matrix J in step 2 of procedure 3 requires approximately n3/3 operations, whereas the calculation of the inverse of J in step 2 of procedure 2 requires approximately n3 operations, where the matrix J is a square matrix of order n. To update the LU factors in step 6 of procedure 3 by use of Bennett s algorithm requires approximately In2 operation, whereas approximately 3n2 operations are required to update the inverse of J by use of Householder s formula as proposed by Broyden in step 6 of procedure 2. 

After the Broyden correction for the independent variables has been computed, Broyden proposed that the inverse of the jacobian matrix of the Newton-Raphson equations be updated by use of Householder s formula. Herein lies the difficulty with Broyden s method. For Newton-Raphson formulations such as the Almost Band Algorithm for problems involving highly nonideal solutions, the corresponding jacobian matrices are exceedingly sparse, and the inverse of a sparse matrix is not necessarily sparse. The sparse characteristic of these jacobian matrices makes the application of Broyden s method (wherein the inverse of the jacobian matrix is updated by use of Householder s formula) impractical. 

As shown in Chap. 4, Broyden proposed the following formula for updating the jacobian matrix Jfc to obtain Jfc+1... 

In this algorithm, Broyden s method is applied by updating the jacobian matrices by use of Householder s formula.13 Let J0 be the initial approximation of the jacobian matrix with which the iterative procedure is started. Then... 

An algorithm is given elow for solving the Newton-Raphson equations by use of only the LU factorization of J0 and the Broyden update terms given by Eqs. (5-29), (5-30), and (5-31). As shown in App. 5-1, this algorithm is based on the successive application of Householder s formula to Eq. (5-29). 

In the formulation of Schubert s method,21 it is convenient to denote the kth approximation of the jacobian by G(k), where the iteration number is carried as a superscript enclosed by parentheses. Then Broyden s formula for computing the next approximation of the jacobian is given by... 

If this value of sk satisfies Eq. (15-63), it is used otherwise, a second value is computed by use of the following formula which was developed by Broyden... 

The BFGS correction formula was discovered independently and more-or-less simultaneously by Broyden (1970), Fletcher (1970), Goldfkrb (1970) and Shanno (1970). The idea is to pretend one is using a DFP-type scheme to estimate F instead of F1, i.e. take F0 = I and try to get Fk pk q The update scheme would be the same as above with p s and q s interchanged. Again, the subscript k is omitted from every term on the right side, and we write ... 

These two formulae belong to a larger family of formulae called the Broyden... 

If Broyden s updating formula is used, it is possible to avoid the solution of the... 

An alternative to factorization upgrading is Broyden s updating formula applied to the inverse matrix ... 

The rank one update formulas for Broyden s method that approximate the Jacobian ensure superlinear convergence that is slower than Newton s method but significantly faster than direct substitution. 

Remark 1 Step 5 must still be specified. The matrix has been introduced to indicate that the matrix k is modified by a (low-rank) correction matrix. When step 5 is reset by a specific update formula, the quasi-Newton method is named after that update (for instance BFGS-method, DFP-method, Broyden-method,. ..). 

One of the most successful QN formulas in practice is associated with the BFGS method (for its developers Broyden, Fletcher, Goldfard, and Shanno). The BFGS update matrix has rank 2 and inherent positive-definiteness (i.e., if B is positive definite then Bj + i is positive definite) as long as yjsk < 0. This condition is satisfied automatically for convex functions but may not hold in general. In practice, the line search must check for the descent property updates that do not satisfy this condition may be skipped. 

---