An analytical approach to global optimization (Q1181733)

The paper explores the solution of global optimization problems using analytical methods. The approach is to develop a series of tests organized in a branch-and-bound framework. The algorithm uses the computer algebra system MACSYMA. The algorithm is tested on several difficult test problems. The main thrust of the paper is solving global optimization problems numerically and to prove the optimality of the solution. The approach uses a variety of techniques including: elimination of inactive constraints, elimination of variables numerically and analytically, relaxation and Lagrangian relaxation, bounding, and monotonicity. The authors implement the algorithm using MACSYMA and the algorithm does not include any heuristic methods. They note that as the problems increase in size and complexity the subproblems may be too complicated to allow further elimination of variables. At this point it may be necessary to include other global optimization methods such as interval arithmetic, cutting planes, and homotopy methods.