New Imperfect Conjugate Gradient Algorithm

We present a method which generates conjugate search directions and maintains the quadratic convergence property, when applied to a quadratic function, even when the line searches are not exact. The method is similar to that given by Dixon, but needs one less vector store. When the method is applied to a number of general functions of different dimensionality, results show the efficiency of the method.     

TOSAR – A Topological Method for the Representation of Synthetic and Analytical Relations of Concepts

In mechanized systems used for searching in literature stores there is a steadily growing necessity not only to be able to formulate concepts as a search condition but also the characteristic connections under which these concepts appear in the inquiry. In this way the precision of the mechanized literature search is considerably increased. TOSAR has been developed in order to improve computerized literature searching in this respect.     

Computational structural determination and energy landscape analysis of the hepatic carcinogen 2-(acetylamino)fluorene

 2-(Acetylamino)fluorene (AAF), a potent mutagen and a prototypical example of the mutagenic aromatic amines, forms covalent adducts to DNA after metabolic activation in the liver. A benchmark study of AAF is presented using a number of the most widely used molecular mechanics and semiempirical computational methods and models. The results are compared to higher-level quantum calculations and to experimentally obtained crystal structures. Hydrogen bonding between AAF molecules in the crystal phase complicates the direct comparison of gas-phase theoretical calculations with experiment, so Hartree–Fock (HF) and Becke–Perdew (BP) density functional theory (DFT) calculations are used as benchmarks for the semiempirical and molecular mechanics results. Systematic conformer searches and dihedral energy landscapes were carried out for AAF using the SYBYL and MMFF94 molecular mechanics force fields; the AM1, PM3 and MNDO semiempirical quantum mechanics methods; HF using the 3-21G*and 6-31G* basis sets; and DFT using the nonlocal BP functional and double numerical polarization basis sets. MMFF94, AM1, HF and DFT calculations all predict the same planar structures, whereas SYBYL, MNDO and PM3 all predict various nonplanar geometries. The AM1 energy landscape is in substantial agreement with HF and DFT predictions; MMFF94 is qualitatively similar to HF and DFT; and the MNDO, PM3 and SYBYL results are qualitatively different from the HF and DFT results and from each other. These results are attributed to deficiencies in MNDO, PM3 and SYBYL. The MNDO, PM3 and SYBYL models may be unreliable for compounds in which an amide group is immediately adjacent to an aromatic ring. Received: 26 May 2002 / Accepted: 12 December 2002 / Published online: 14 February 2003     

Numerical analysis of a quadratic matrix equation

The quadratic matrix equation AX²+ BX + C = 0in n x nmatricesarises in applications and is of intrinsic interest as oneof the simplest nonlinear matrix equations. We give a completecharacterization of solutions in terms of the generalized Schurdecomposition and describe and compare various numerical solutiontechniques. In particular, we give a thorough treatment offunctional iteration methods based on Bernoulli’s method.Other methods considered include Newton’s method with exact line searches, symbolic solution and continued fractions.We show that functional iteration applied to the quadraticmatrix equation can provide an efficient way to solve the associated quadratic eigenvalue problem (²A + B + C)x = 0.     

Generalized Polak-Ribière algorithm

A new generalized Polak-Ribière conjugate gradient algorithm is proposed for unconstrained optimization, and its numerical and theoretical properties are discussed. The new method is, in fact, a particular type of two-dimensional Newton method and is based on a finite-difference approximation to the product of a Hessian and a vector.     

A family of variable metric methods in function space,without exact line searches

The purpose of this paper is to extend a family of variable metric methods, of which the BFGS algorithm (Ref. 1) is a member, into function space, in particular, for the solution of unconstrained optimal control problems. An inexact one-dimensional minimization as suggested by Fletcher (ref. 2) is used. It is shown that, with this stepsize rule and under some mild assumptions, the sequence constructed by this family of methods converges superlinearly for a strictly convex functional defined on a suitable Banach space. This result is shown to remain valid on a Hilbert space and on a Euclidean space under more relaxed assumptions. The BFGS method without line searches is used to solve several standard numerical examples, and excellent performance is observed.This work was supported by the Consejo Nacional de Ciencia y Tecnologia de Mexico, and by the National Research Council of Canada, Grant No. A-8835. The authors are indebted to Dr. C. Charalambous for suggesting the topic and stimulating discussions.     

探索上帝粒子与质量起源

欧洲大型强子对撞机(LHC) 上发现的125 GeV新希格斯粒子可能成为标准模型预期的“上帝粒子”。这一革命性发现开启了探索宇宙中一切基本粒子质量起源的新时代,成为21世纪粒子物理学的转折点。文章着重介绍：(1) 探寻上帝粒子的重大科学意义;(2) 探索质量起源的历史,以及为什么牛顿力学和爱因斯坦相对论均未解决质量起源问题;(3) 神秘的真空与希格斯机制;(4) 上帝粒子是如何提出的和怎样在LHC上发现的;(5) 展望21世纪质量起源的探索与新物理定律的革命。     

A Theoretical Approach to Restart in Global Optimization

While searching for the global minimum of a cost function we haveoftento decide if a restart from a different initial point would bemoreadvantageous than continuing current optimization. This is aparticularcase of the efficiency comparison between repeatedminimizations and singleextended search having the same total length.A theoretical approach forthe treatment of this general problem formsthe subject of the present paper.A fundamental role is played by theprobability of reaching the globalminimum, whose asymptoticalbehavior allows to provide useful information onthe efficiency ofrepeated trials.The second part of this work is devoted toa detailed analysis of threeoptimization algorithms whose evolution isindependent of the costfunction to be minimized: pure random search, grid search and randomwalk. These three examples give an interesting validationof thetheoretical results and provide a general procedure which can beemployed in the study of more complex optimization problems.     

Local search procedures for improving feasible solutions to the sequential ordering problem

Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for=3 and 4. The complexity of the algorithm isO(bn ⁴), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.