Minimum energy configurations on a toric lattice as a quadratic assignment problem

We consider three known bounds for the quadratic assignment problem (QAP): an eigenvalue, a convex quadratic programming (CQP), and a semidefinite programming (SDP) bound. Since the last two bounds were not compared directly before, we prove that the SDP bound is stronger than the CQP bound. We then apply these to improve known bounds on a discrete energy minimization problem, reformulated as a QAP, which aims to minimize the potential energy between repulsive particles on a toric grid. Thus we are able to prove optimality for several configurations of particles and grid sizes, complementing earlier results by Bouman et al. (2013). The semidefinite programs in question are too large to solve without pre-processing, and we use a symmetry reduction method by Permenter and Parrilo (2020) to make computation of the SDP bounds possible.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds

We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an activity set. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.Corresponding author.     

Heuristic methods for evolutionary computation techniques

Evolutionary computation techniques, which are based on a powerful principle of evolution—survival of the fittest, constitute an interesting category of heuristic search. In other words, evolutionary techniques are stochastic algorithms whose search methods model some natural phenomena: genetic inheritance and Darwinian strife for survival.Any evolutionary algorithm applied to a particular problem must address the issue of genetic representation of solutions to the problem and genetic operators that would alter the genetic composition of offspring during the reproduction process. However, additional heuristics should be incorporated in the algorithm as well; some of these heuristic rules provide guidelines for evaluating (feasible and infeasible) individuals in the population. This paper surveys such heuristics and discusses their merits and drawbacks.An abridged version of this paper appears in the volume entitled META-HEURISTICS: Theory & Application, edited by Ibrahim H. Osman and James P. Kelly, to be published by Kluwer Academic Publishers in March 1996.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

高硅沸石骨架结构及其稳定性的模拟计算(I)*

The lattice energy of a series of high-silica zeolites was determined using the lattice energy minimization method. The results were compared to the lattice energy of dense polymorphs of SiO2. All high-silica zeolites frameworks are only 30～67kJ•mol-1 less stable than α-quartz This may imply that there is little energy barrier to the formation of high-silica zeolites frame-works and explain the structural diversity observed for high-silica zeolites. The relationships of calculated lattice energies and framework Structures was disscussed. The results revealed a good linear relationship between framework density of these molecular sieves and all-silica framework lattice energies.     

An algebraic method that includes Gibbs minimization for performing phase equilibrium calculations for any number of components or phases

The most widely used technique for performing phase equilibria calculations is the K-value method (equality of chemical potentials). This paper proposes a more efficient algorithm to achieve the results that includes Gibbs minimization when we know the number of phases. Using the orthogonal derivatives, the tangent plane equation and mass balances, it is possible to reduce the Gibbs minimization procedure to the task of finding the solution of a system of non-linear equations. Such an operation is easier and faster than finding tangents or areas, and appears to converge as fast as the K-value method. Examples illustrate application of the new technique to two and three phases in equilibrium for binary and ternary mixtures.     

Nondifferential optimization via adaptive smoothing

The problem of minimizing a nondifferential functionx f(x) (subject, possibly, to nondifferential constraints) is considered. Conventional algorithms are employed for minimizing a differential approximationf off (subject to differentiable approximations ofg). The parameter is adaptively reduced in such a way as to ensure convergence to points satisfying necessary conditions of optimality for the original problem.This research was supported by the UK Science and Engineering Research Council, the National Science Foundation under Grant No. ECS-8121149, and the Joint Services Electronics Program, Contract No. F49620-79-C-0178.     

Thermal analysis study of the effect of molecular weight on constrained amorphous phase in poly(phenylene sulfide)

We report a thermal analysis study of the effect of molecular weight on the amorphous phase structure of poly(phenylene sulfide), PPS, crystallized at temperatures just above the glass transition temperature. Thermal properties of Fortron PPS, having viscosity average molecular weights of 30000 to 91000, were characterized using temperature modulated differential scanning calorimetry (MDSC). We find that while crystallinity varies little with molecular weight, the heat capacity increment at the glass transition decreases as molecular weight decreases. This leads to a smaller liquid-like amorphous phase, and a larger rigid amorphous fraction, in the lower molecular weight PPS. For all molecular weights, constrained fraction decreases as the scan rate decreases.This research is supported by the U. S. Army Research Office through contract DAAH04-96-1-0009. The authors thank Hoechst Celanese for providing different molecular weight Fortron samples and Dr. George Collins for providing sample information. The authors acknowledge the assistance of Elizabeth Oyebode and Leonardo Grimaldi with sample preparation and MDSC work.