Update Broyden

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). 

Remark In step 7 the Broyden update is used. Of course other updates can also be employed. 

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 (k+l)-th iteration of the Broyden method consists of updating the inverse according to (2.38) and then performing a correction by (2.35). 

Various update methods carry the names of Broyden, Davidon, Fletcher, Goldfarb, Powell, and Shanno, in different combinations. We recommend a comprehensive textbook, namely... 

It is often desirable that the approximate Hessian is positive definite so that the quadratic model has a minimum. To ensure this we may use the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update given by... 

The BFGS (Broyden [42], Fletcher [124], Goldfarb [145], Shanno [379]) algorithm is an update procedure for the Hessian matrix that is widely used in iterative optimization [125]. The simpler Rm update takes the form... 

Distillation Calculations, Work done with flash calculations and sparse matrix methods was extended to distillation calculations. Holland and Gallun (51) explored the use of Broyden s method coupled with sparse updating procedures to distillation calculations with highly non-ideal solutions. Shah and Boston (52), and Ross and Seider (53j discuss the case of multiple liquids phases on a tray. 

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... 

Tomich recommends filling and inverting the Jacobian only once and using the Broyden method (Sec. 4.2.6) to update the inverse. This reduces computer time per trial but increases the number of column trials or passes through the procedure and for 6ome columns may also decrease reliability of the method. It is the author 6 experience that for many columns, solution is easier to reach when the Jacobian is filled and inverted in each trial and Brcyden s method is not used. 

Get a new set of stripping factors by solving the energy balances and specification equations as the independent functions of the quasi-Newton technique of Broyden (Sec. 4.2.6). The derivatives of the Jacobian matrix are generated numerically and must include steps 4, 5, and 6 each time the independent variables are perturbed, The Jacobian is not recalculated after the first trial in the loop but is instead updated by Broyden s equation. 

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... 

In the classical Newton-Raphson technique, the Jacobian matrix is inverted every iteration in order to compute the corrections AT] and Al]. The method of Tomich, however, uses the Broyden procedure (Broyden, 1965) in subsequent iterations for updating the inverted Jacobian matrix. 

The 78 equality constraints in the complete model were thus reduced to 6 nonlinear equations as the genetic algorithm, NSGA-II-aJG is not effective in handling multiple equality constraints. Its inadequateness was also observed even when the equations had been reduced to 6 equations. Hence, the Broyden s update and finite-difference Jacobian function (DNEQBF) of the IMSL Library was embedded in the objective evaluation to solve the nonlinear equations 10.1 to 10.6. 

The Murtaugh-Sargent update, which was already discussed in Section 10.3.1, is one option [79,130,131]. Another common choice is the Powell-symmetric-Broyden (PSB) update, which was hrst recommended for TS optimization by Simons et al. [132]. A PSB updated Hessian is given by... 

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. 

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. 

Broyden s algorithm consists of successively updating of the jacobian matrix of the Newton-Raphson equations by use of the correction matrix xCy7, that is,... 

Bennett proposed the algorithm presented in Fig. 4-4 for updating the matrices Lk and Uk to obtain the updated matrices Lk+1 and Uk+1. When Bennett s algorithm is used to make the Broyden correction, the following calcu-lational procedure is used. 

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. 

Two methods have been proposed for retaining the desirable characteristics of Broyden s method and eliminating the undesirable characteristic of the loss of sparsity of the jacobian matrix through the use of inverses. In both of these modifications of Broyden s method, the necessity for the development of analytical expressions for the partial derivations is eliminated. To initiate the calcula-tional procedure in each of these modified versions of Broyden s method, the partial derivatives appearing in the jacobian matrix are evaluated numerically, and the jacobian matrix is updated in subsequent trials through the use of functional evaluations. The first modified form of Broyden s method is the one proposed by Gallun and Holland,9 and the second modification is the one proposed by Schubert.21... 

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... 

---