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.

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.

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.

Parallelization of the discrete gradient method of non-smooth optimization and its applications

We investigate parallelization and performance of the discrete gradient method of nonsmooth optimization. This derivative free method is shown to be an effective optimization tool, able to skip many shallow local minima of nonconvex nondifferentiable objective functions. Although this is a sequential iterative method, we were able to parallelize critical steps of the algorithm, and this lead to a significant improvement in performance on multiprocessor computer clusters. We applied this method to a difficult polyatomic clusters problem in computational chemistry, and found this method to outperform other algorithms.

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.

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.

An nmr investigation of ionic structure and mobility in plasticized solid polymer electrolytes

²³Na and ¹⁹F nuclear magnetic resonance spectroscopy is used to investigate the effect of plasticizer addition on ionic structure and mobility in a urethane crosslinked polyether solid polymer electrolyte. The incorporation of dimethyl formamide and propylene carbonate plasticizers in a sodium triflate/polyether system results in an upfield chemical shift for the ²³Na resonance consistent with decreased anion-cation association and increased cation-plasticizer interactions. The ¹⁹F resonances appears less susceptible to changes in chemical environment with only minor chemical shift changes recorded. Spin lattice relaxation measurements for the ¹⁹F nucleus are also reported. Two minima are observed in the relaxation measurements consistent with both an inter and intramolecular relaxation mechanism.

Evaluating the stability of disulfide bridges in proteins: a torsional potential energy surface for diethyl disulfide

Disulfide bonds formed by the oxidation of cysteine residues in proteins are the major form of intra- and inter-molecular covalent linkages in the polypeptide chain. To better understand the conformational energetics of this linkage, we have used the MP2(full)/6-31G(d) method to generate a full potential energy surface (PES) for the torsion of the model compound diethyl disulfide (DEDS) around its three critical dihedral angles (χ2, χ3, χ2′). The use of ten degree increments for each of the parameters resulted in a continuous, fine-grained surface. This allowed us to accurately predict the relative stabilities of disulfide bonds in high resolution structures from the Protein Data Bank. The MP2(full) surface showed significant qualitative differences from the PES calculated using the Amber force field. In particular, a different ordering was seen for the relative energies of the local minima. Thus, Amber energies are not reliable for comparison of the relative stabilities of disulfide bonds. Surprisingly, the surface did not show a minimum associated with χ2 − 60°, χ390, χ2′ − 60°. This is due to steric interference between Hα atoms. Despite this, significant populations of disulfides were found to adopt this conformation. In most cases this conformation is associated with an unusual secondary structure motif, the cross-strand disulfide. The relative instability of cross-strand disulfides is of great interest, as they have the potential to act as functional switches in redox processes.

Structuring in liquid alkanes between solid surfaces : force measurements and mean-field theory

Measurements have been made of the solvation forces between mica surfaces in the even-numbered n-alkanes from hexane to hexadecane. In all cases the force law is qualitatively very similar, characterized by a decaying oscillatory function of distance, as occurs for simple isotropic liquids. The spacing between successive minima in the force does not increase with carbon number, and is comparable to the width of a linear alkane molecule rather than its length or any average diameter. This suggests that the alkanes have some tendency towards a parallel orientation near the mica surfaces. The measurements give no indication of any strong repulsive component expected from mean-field theories of higher alkanes or polymers. The results of one such theory are presented, and the reasons for its failure to match the experimental data are discussed.

Measurement of forces due to structure in hydrocarbon liquids

Direct measurements of the force between two molecularly smooth mica sheets immersed in cyclohexane show not a monotonic van der Waals attraction, but an oscillatory function of distance, where the spacing between successive minima corresponds to the molecular diameter of cyclohexane. As surface separation increases the oscillations become less pronounced, and beyond 5 nm (typically seven or eight oscillations) they are no longer detected. These results accord with theoretical ideas on structural forces resulting from the inhomogeneous arrangement of molecules of the liquid near the solid surface. In n-octane the force law does not show the same pronounced oscillations, except at very small separations where repulsive barriers are found. These are attributed to the difficulty of removing the last layers of adsorbed molecules of the liquid from the mica surfaces, and they reduce the mice-mica adhesion significantly. Small amounts of water in the hydrocarbon liquids condense to form a bridge between the surfaces at small separations, causing a very strong adhesion between them. Some implications of these results for the stability of colloids in organic media are discussed.

Benzene adsorption at the aqueous (011) α-quartz interface : is surface flexibility important?

Atomistic simulations of molecular adsorption onto inorganic substrates under aqueous conditions can be used to guide the rational design of new materials, fabricated using biomimetic methods. The success of such work depends critically on the model used. Here, we investigate the impact of using a rigid structural model of the (0 1 1) ?-quartz surface, over a fully flexible model, on the calculated free energy change in the adsorption of a single molecule of benzene (a simple analogue of the amino acid phenylalanine) from liquid water. Subtle differences in the mobility of the adsorbate close to the surface result in the free energy of adsorption being overestimated by the rigid model, relative to the fully flexible case. Moreover, we find that the distribution of bound configurations of the adsorbate at their respective free energy minima is different between the two models.

Pedometers may not provide a positive effect on walking activity

Electronic pedometers are gaining credibility as a reliable method for objectively measuring physical activity. The feedback from a pedometer is immediate and objective, providing unbiased measure of physical activity to the individual. Previous research has shown that objective feedback has a positive effect on adherence. Other authors have suggested that a pedometer may be used as a motivational tool to enhance adherence to exercise programs. However, there is little evidence in the literature that this possibility has been investigated and measured. This study investigated the effect of feedback from a pedometer as an intervention strategy to increase adherence to a walking program. When used in a walking program that specifies a daily step count, a pedometer offers frequent and immediate feedback (positive and negative) on performance. Regular feedback on performance is likely to increase the likelihood of adherence to a walking program. 

Nonorthogonal approximate joint diagonalization with well-conditioned diagonalizers

To make the results reasonable, existing joint diagonalization algorithms have imposed a variety of constraints on diagonalizers. Actually, those constraints can be imposed uniformly by minimizing the condition number of diagonalizers. Motivated by this, the approximate joint diagonalization problem is reviewed as a multiobjective optimization problem for the first time. Based on this, a new algorithm for nonorthogonal joint diagonalization is developed. The new algorithm yields diagonalizers which not only minimize the diagonalization error but also have as small condition numbers as possible. Meanwhile, degenerate solutions are avoided strictly. Besides, the new algorithm imposes few restrictions on the target set of matrices to be diagonalized, which makes it widely applicable. Primary results on convergence are presented and we also show that, for exactly jointly diagonalizable sets, no local minima exist and the solutions are unique under mild conditions. Extensive numerical simulations illustrate the performance of the algorithm and provide comparison with other leading diagonalization methods. The practical use of our algorithm is shown for blind source separation (BSS) problems, especially when ill-conditioned mixing matrices are involved.