Lp-Based Strategies for Deterministic Global Optimization Using Interval Methods

The interval Newton method can provide mathematical and computational guarantee that all roots will be found in nonlinear equation solving problems, and that the global optimum will be found in nonlinear, nonconvex optimization problems. Thus this provides a methodology for deterministic global optimization, including the problem of finding all stationary points in unconstrained optimization, or all Fritz-John points in constrained optimization. We present here a new strategy based on the use of linear programming (LP) techniques to exactly (within round out) bound the solution set of the linear interval equation system that must be solved in the context of the interval-Newton method. The tighter bound on solution set thus enhances may greatly enhance the efficiency of the interval-Newton method. An implementation of this technique is described and several important issues are considered. These include combination with a simple, low-overhead pivoting preconditioning technique, selection of the interval conner required by the LP strategy, and determination of rigorous bounds on the solution of the LP problems. The procedure based on these techniques, LISS_LP, will then be demonstrated using several global optimization problems, with focus on problems arising in chemical engineering. The comparative computational performance results between LISS_LP and the HP/RP approach of Gau and Stadtherr, have shown that the new LP strategy leads to substantial reductions in computation time requirements. In addition, LISS_LP has also been applied to some global optimization problems arising in molecular modeling, such as locating all stationary points of the potential energy surface of a sorbate particle in silicalite, locating all stationary points of the potential energy surface of triatomic molecules, and seeking molecular conformation with global minimum potential energy. It has been shown that the new LP-based strategy for the interval Newton method implemented in LISS_LP, is very effective on these problems.