Fast algorithm for the cutting angle method of global optimization

The cutting angle method for global optimization was proposed in 1999 by Andramonov et al. (Appl. Math. Lett. 12 (1999) 95). Computer implementation of the resulting algorithm indicates that running time could be improved with appropriate modifications to the underlying mathematical description. In this article, we describe the initial algorithm and introduce a new one which we prove is significantly faster at each stage. Results of numerical experiments performed on a Pentium III 750 Mhz processor are presented.

Predicting molecular structures: an application of the cutting angle method

The ability to predict molecular geometries has important applications in chemistry. Specific examples include the areas of protein space structure elucidation, the investigation of host–guest interactions, the understanding of properties of superconductors and of zeolites. This prediction of molecular geometries often depends on finding the global minimum or maximum of a function such as the potential energy. In this paper, we consider several well-known molecular conformation problems to which we apply a new method of deterministic global optimization called the cutting angle method. We demonstrate that this method is competitive with other global optimization techniques for these molecular conformation problems.

Geometry and combinatorics of the cutting angle method

Lower approximation of Lipschitz functions plays an important role in deterministic global optimization. This article examines in detail the lower piecewise linear approximation which arises in the cutting angle method. All its local minima can be explicitly enumerated, and a special data structure was designed to process them very efficiently, improving previous results by several orders of magnitude. Further, some geometrical properties of the lower approximation have been studied, and regions on which this function is linear have been identified explicitly. Connection to a special distance function and Voronoi diagrams was established. An application of these results is a black-box multivariate random number generator, based on acceptance-rejection approach.

Cutting angle method - a tool for constrained global optimization

Cutting angle method (CAM) is a deterministic global optimization technique applicable to Lipschitz functions f: Rn → R. The method builds a sequence of piecewise linear lower approximations to the objective function f. The sequence of solutions to these relaxed problems converges to the global minimum of f. This article adapts CAM to the case of linear constraints on the feasible domain. We show how the relaxed problems are modified, and how the numerical efficiency of solving these problems can be preserved. A number of numerical experiments confirms the improved numerical efficiency.

A new method for locating the global optimum : application of the cutting angle method to molecular structure prediction

Many problems in chemistry depend on the ability to identify the global minimum or maximum of a function. Examples include applications in chemometrics, optimization of reaction or operating conditions, and non-linear least-squares analysis. This paper presents the results of the application of a new method of deterministic global optimization, called the cutting angle method (CAM), as applied to the prediction of molecular geometries. CAM is shown to be competitive with other global optimization techniques for several benchmark molecular conformation problem. CAM is a general method that can also be applied to other computational problems involving global minima, global maxima or finding the roots of nonlinear equations.

Extended cutting angle method of global optimization

Methods of Lipschitz optimization allow one to find and confirm the global minimum of multivariate Lipschitz functions using a finite number of function evaluations. This paper extends the Cutting Angle method, in which the optimization problem is solved by building a sequence of piecewise linear underestimates of the objective function. We use a more flexible set of support functions, which yields a better underestimate of a Lipschitz objective function. An efficient algorithm for enumeration of all local minima of the underestimate is presented, along with the results of numerical experiments. One dimensional Pijavski-Shubert method arises as a special case of the proposed approach.

Solving DC programs using the cutting angle method

In this paper, we propose a new algorithm for global minimization of functions represented as a difference of two convex functions. The proposed method is a derivative free method and it is designed by adapting the extended cutting angle method. We present preliminary results of numerical experiments using test problems with difference of convex objective functions and box-constraints. We also compare the proposed algorithm with a classical one that uses prismatical subdivisions. © 2014 Springer Science+Business Media New York.

Efficient serial and parallel implementations of the cutting angle global optimisation technique

We examine efficient computer implementation of one method of deterministic global optimisation, the cutting angle method. In this method the objective function is approximated from values below the function with a piecewise linear auxiliary function. The global minimum of the objective function is approximated from the sequence of minima of this auxiliary function. Computing the minima of the auxiliary function is a combinatorial problem, and we show that it can be effectively parallelised. We discuss the improvements made to the serial implementation of the cutting angle method, and ways of distributing computations across multiple processors on parallel and cluster computers.

Review of applications of the Cutting Angle methods

The theory of abstract convexity provides us with the necessary tools for building accurate one-sided approximations of functions. Cutting angle methods have recently emerged as a tool for global optimization of families of abstract convex functions. Their applicability have been subsequently extended to other problems, such as scattered data interpolation. This paper reviews three different applications of cutting angle methods, namely global optimization, generation of nonuniform random variates and multivatiate interpolation.

Critical surface tension of acrylamide-grafted polypropylene copolymer by the contact angle method

The contact angles theta of polar liquids on PP-g-AM copolymer (AM content 0.19, 0.26, and 0.37 wt%) were measured. The critical surface tension gamma(c) of PP-g-AM films were evaluated by the Zisman plot (cos theta versus gamma(L)), the Young-Dupre-Good-Girifalco plot (1 + cos theta) versus 1/gamma(L)(0.5), and the log(1 + cos theta) versus log gamma(L) plot. The gamma(L) values estimated by the plot log(1 + cos theta) versus log gamma(L) were smaller than those obtained by the other plots.

The determination of ethylene-propylene copolymer-grafted-glycidyl methacrylate by the contact angle method

The contact angles theta of some liquids on ethylene-propylene copolymer-grafted-glycidyl methacrylate (EPM-g-GMA) were measured. The critical surface tensions r(c) of EPM-g-GMA were evaluated by the Zisman Plot (cos theta versus r(L)), Young-Dupre-Good-Girifalco plot (1 + cos theta versus 1/r(L)(0.5)) and log (1 + cos theta) versus log(r(L)) plot. The following results were obtained: the r(c) values varied significantly with the estimation methods. The critical surface tension r(c) decreased with the increase of the degree of grafting of EPM-g-GMA.

Least squares splines with free knots: global optimization approach

Splines with free knots have been extensively studied in regard to calculating the optimal knot positions. The dependence of the accuracy of approximation on the knot distribution is highly nonlinear, and optimisation techniques face a difficult problem of multiple local minima. The domain of the problem is a simplex, which adds to the complexity. We have applied a recently developed cutting angle method of deterministic global optimisation, which allows one to solve a wide class of optimisation problems on a simplex. The results of the cutting angle method are subsequently improved by local discrete gradient method. The resulting algorithm is sufficiently fast and guarantees that the global minimum has been reached. The results of numerical experiments are presented.

Mathematical modelling of the refractive index reconstruction through global optimization

We examine a mathematical model of non-destructive testing of planar waveguides, based on numerical solution of a nonlinear integral equation. Such problem is ill-posed, and the method of Tikhonov regularization is applied. To minimize Tikhonov functional, and find the parameters of the waveguide, we use two new optimization methods: the cutting angle method of global optimization, and the discrete gradient method of nonsmooth local optimization. We examine how the noise in the experimental data influences the solution, and how the regularization parameter has to be chosen. We show that even with significant noise in the data, the numerical solution is of high accuracy, and the method can be used to process real experimental da.ta..