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.

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.

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.

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

Fuzzy clustering of non-convex patterns using global optimization

This paper discusses various extensions of the classical within-group sum of squared errors functional, routinely used as the clustering criterion. Fuzzy c-means algorithm is extended to the case when clusters have irregular shapes, by representing the clusters with more than one prototype. The resulting minimization problem is non-convex and non-smooth. A recently developed cutting angle method of global optimization is applied to this difficult problem

Construction of aggregation operators for automated decision making via optimal interpolation and global optimization

This paper examines methods of point wise construction of aggregation operators via optimal interpolation. It is shown that several types of application-specific requirements lead to interpolatory type constraints on the aggregation function. These constraints are translated into global optimization problems, which are the focus of this paper. We present several methods of reduction of the number of variables, and formulate suitable numerical algorithms based on Lipschitz optimization.

Challenges of continuous global optimization in molecular structure prediction

The molecular geometry, the three dimensional arrangement of atoms in space, is a major factor determining the properties and reactivity of molecules, biomolecules and macromolecules. Computation of stable molecular conformations can be done by locating minima on the potential energy surface (PES). This is a very challenging global optimization problem because of extremely large numbers of shallow local minima and complicated landscape of PES. This paper illustrates the mathematical and computational challenges on one important instance of the problem, computation of molecular geometry of oligopeptides, and proposes the use of the Extended Cutting Angle Method (ECAM) to solve this problem.

ECAM is a deterministic global optimization technique, which computes tight lower bounds on the values of the objective function and fathoms those part of the domain where the global minimum cannot reside. As with any domain partitioning scheme, its challenge is an extremely large partition of the domain required for accurate lower bounds. We address this challenge by providing an efficient combinatorial algorithm for calculating the lower bounds, and by combining ECAM with a local optimization method, while preserving the deterministic character of ECAM.

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.

Planar waveguide refractive index profile reconstruction using global optimization

The approach taken here of reconstruction of the refractive index profile of planar waveguides involves solving a non-linear integral equation with Tikhonov regularization. Using global optimization with the new cutting angle and discrete gradient methods has yielded an acceptable reconstruction, even in the presence of significant noise in the data.

Implementation of novel methods of global and nonsmooth optimization : GANSO programming library

We discuss the implementation of a number of modern methods of global and nonsmooth continuous optimization, based on the ideas of Rubinov, in a programming library GANSO. GANSO implements the derivative-free bundle method, the extended cutting angle method, dynamical system-based optimization and their various combinations and heuristics. We outline the main ideas behind each method, and report on the interfacing with Matlab and Maple packages.

Global non-smooth optimization in robust multivariate regression

Robust regression in statistics leads to challenging optimization problems. Here, we study one such problem, in which the objective is non-smooth, non-convex and expensive to calculate. We study the numerical performance of several derivative-free optimization algorithms with the aim of computing robust multivariate estimators. Our experiences demonstrate that the existing algorithms often fail to deliver optimal solutions. We introduce three new methods that use Powell's derivative-free algorithm. The proposed methods are reliable and can be used when processing very large data sets containing outliers.

Global optimisation of neural networks using a deterministic hybrid approach

Selection of the topology of a neural network and correct parameters for the learning algorithm is a tedious task for designing an optimal artificial neural network, which is smaller, faster and with a better generalization performance. In this paper we introduce a recently developed cutting angle method (a deterministic technique) for global optimization of connection weights. Neural networks are initially trained using the cutting angle method and later the learning is fine-tuned (meta-learning) using conventional gradient descent or other optimization techniques. Experiments were carried out on three time series benchmarks and a comparison was done using evolutionary neural networks. Our preliminary experimentation results show that the proposed deterministic approach could provide near optimal results much faster than the evolutionary approach.

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.