Testing convergence

The final optimized structure appears immediately after the final convergence tests ... 

Because of the physical equilibrium, the association in the liquid phase is determinded by that in the vapour phase. Therefore no additional association constants are required for the liquid phase. In the case of liquid-liquid equilibrium calculations, an analogous procedure was adopted using convergence test (5), with y. referring to the second liquid phase. 

Convergence Test. We iterate the following sequential computations until (X, y ,S ) satisfies the constraints in Eqs. (l)-(2) with S =... 

Accuracy. The results must be sufficiently accurate to interpret the experiments of interest. In a complete quantum-mechanical calculation, this accuracy can be verified by convergence tests within the calculation. In classical, or other approximate methods, accuracy and reliability generally must be judged by experience with test comparisons with complete quantum-mechanical calculations. The numerical stability of the method must also be considered. 

The key idea in GCD is to make extensive use of phase I (i.e., primal, dual subproblems) and limit as much as possible the use of phase II (i.e., master problem) by the application of appropriate convergence tests. This is because the master problem is known to be a more difficult and cpu time consuming problem, than the primal and dual subproblems of phase I. 

This section presents the theoretical development of the Generalized Cross Decomposition, GCD. Phase I is discussed first with the analysis of the primal and dual subproblems. Phase II is presented subsequently for the derivation of the problem while the convergence tests are discussed last. 

The convergence tests of the GCD make use of the notions of (i) upper bound improvement, (ii) lower bound improvement, and (iii) cut improvement. An upper bound improvement corresponds to a decrease in the upper bound UBD obtained by the primal subproblem P(yk)- A lower bound improvement corresponds to an increase in the lower bound LBD obtained by the dual subproblem D (ik). A cut improvement corresponds to generating a new cut which becomes active and hence is not dominated by the cuts generated in previous iterations. If the cut is generated in the relaxed primal master problem (RPM) it is denoted as a primal cut improvement. If the cut is generated in the relaxed Lagrange relaxation master problem then the improvement is classified as Lagrange relaxation cut improvement. 

The basic idea in the convergence tests CT is to provide answers to the following three questions ... 

The convergence tests CT that provide the answers to the aforementioned questions are formulated as... 

Holmberg (1990) proved the following theorem and lemma for finite termination after applying the convergence tests CT ... 

The convergence tests CTP and CTD are necessary for bound improvement and sufficient for bound improvement or cut improvement. The convergence test CTDU is sufficient for cut improvement. 

Lemma 6.9.1 For model (6.52) in which Y is a finite discrete set the convergence test CT will fail after a finite number of iterations, and hence the generalized cross decomposition GBD algorithms will solve (6.52) exactly in a finite number of steps. 

Figure 6.9 presented the generic algorithmic steps of the generalized cross decomposition GCD algorithm, while in the previous section we discussed the primal and dual subproblems, the relaxed primal master problem, the relaxed Lagrange relaxation master problem, and the convergence tests. 

Remark 1 Note that the GCD is based on the idea that it is desirable to solve as few master problems as possible since these are the time consuming problems. Therefore, if the convergence tests CTP, CTD, CTDU are passed at each iteration, then we generate cuts and improved bounds on the sought solution of (6.52). This is denoted as the subproblem phase. If a sufficiently large number of cuts are generated in the subproblem phase then we may need to solve a master problem only a few times prior to obtaining the optimal solution. 

The convergence tests, however, need to be modified on the grounds that it is possible to have an infinite number of both primal and dual improvements if Y is continuous, and hence not attain termination in a finite number of steps. To circumvent this difficulty, Holmberg (1990) defined the following stronger e-improvements ... 

Remark 1 The first condition of CTP-e and the CTD-e are classified as e-value convergence tests since they correspond to feasible problems. The second condition of CTP-e and the CTDU-e are denoted as e-feasibility convergence tests since they correspond to feasibility problems. 

Remark 2 The e-convergence test are sufficient for e-improvement but they are not necessary. An additional condition, which is an inverse Lipschitz assumption, needs to be introduced so as to prove the necessity. This additional condition states that for points of a certain distance apart the value of the feasibility cut should differ by at least some amount. This is stated in the following theorem of Holmberg (1990). 

The e-value convergence tests of CTP-e, the feasibility tests ofCTP, and the e-convergence tests of CTD-e are necessary for e-bound improvement. The e-convergence tests are sufficient for one of the following ... 

With the above theorem as a basis Holmberg (1990) proved the finiteness of the convergence tests which is stated as... 

Lemma 6.9.2 The e-convergence tests will fail after a finite number of steps. 

Remark 4 If the primal subproblem has a feasible solution for every y e Y, then the GCD algorithm will attain finite e-convergence (i.e. UBD - LBD < e) in a finite number of steps for any given e > 0. Obviously, in this case the e-feasibility convergence tests are not needed. 

Figure 2.8 DMNO-(H2O)30 cluster and convergence test of nitrogen HCC (see Colour Plate section).

---