A Conjugate Gradient Algorithm with Function Value Information and N-Step Quadratic Convergence for Unconstrained Optimization

It is generally acknowledged that the conjugate gradient (CG) method achieves global convergence—with at most a linear convergence rate—because CG formulas are generated by linear approximations of the objective functions. The quadratically convergent results are very limited. We introduce a new PRP method in which the restart strategy is also used. Moreover, the method we developed includes not only n-step quadratic convergence but also both the function value information and gradient value information. In this paper, we will show that the new PRP method (with either the Armijo line search or the Wolfe line search) is both linearly and quadratically convergent. The numerical experiments demonstrate that the new PRP algorithm is competitive with the normal CG method.     

An Efficient Augmented Lagrangian Method for Statistical X-Ray CT Image Reconstruction

Statistical iterative reconstruction (SIR) for X-ray computed tomography (CT) under the penalized weighted least-squares criteria can yield significant gains over conventional analytical reconstruction from the noisy measurement. However, due to the nonlinear expression of the objective function, most exiting algorithms related to the SIR unavoidably suffer from heavy computation load and slow convergence rate, especially when an edge-preserving or sparsity-based penalty or regularization is incorporated. In this work, to address abovementioned issues of the general algorithms related to the SIR, we propose an adaptive nonmonotone alternating direction algorithm in the framework of augmented Lagrangian multiplier method, which is termed as “ALM-ANAD”. The algorithm effectively combines an alternating direction technique with an adaptive nonmonotone line search to minimize the augmented Lagrangian function at each iteration. To evaluate the present ALM-ANAD algorithm, both qualitative and quantitative studies were conducted by using digital and physical phantoms. Experimental results show that the present ALM-ANAD algorithm can achieve noticeable gains over the classical nonlinear conjugate gradient algorithm and state-of-the-art split Bregman algorithm in terms of noise reduction, contrast-to-noise ratio, convergence rate, and universal quality index metrics.     

A Conjugate Gradient Algorithm with a Trust Region for Molecular Geometry Optimization

An algorithm is presented for the optimization of molecular geometries and general nonquadratic functions using the nonlinear conjugate gradient method with a restricted step and restart procedure. The algorithm only requires the evaluation of the energy function and its gradient, therefor less memory storage is needed than for other conjugate gradient algorithms. Some numerical results are also presented and the efficiency and behaviour of the algorithm is compared with the standard conjugate gradient method. We also present comparisons of both conjugate gradient and variable metric methods with and without the trust region technique. One of the main conclusions of the present work is that a trust region always improves the converge of any optimization method. A sketch of the algorithm is also given.     

Structure optimization in a three-dimensional off-lattice protein model

We studied a three-dimensional off-lattice AB model with two species of monomers, hydrophobic (A) and hydrophilic (B), and present two optimization algorithms: face-centered-cubic (FCC)-lattice pruned-enriched-Rosenbluth method (PERM) and subsequent conjugate gradient (PERM++) minimization and heuristic conjugate gradient (HCG) simulation based on "off-trap" strategy. In PERM++, we apply the PERM to the FCC-lattice to produce the initial conformation, and conjugate gradient minimization is then used to reach the minimum energy state. Both algorithms have been tested in the three-dimensional AB model for all sequences with lengths 13 < or = n < or = 55. The numerical results show that the proposed methods are very promising for finding the ground states of proteins. In several cases, we renew the putative ground states energy values.     

Protein Electrostatics: Rapid Multigrid-Based Newton Algorithm for Solution of the Full Nonlinear Poisson-Boltzmann Equation

Abstract

A new method for solving the full nonlinear Poisson-Boltzmann equation is outlined. This method is robust and efficient, and uses a combination of the multigrid and inexact Newton algorithms. The novelty of this approach lies in the appropriate combination of the two methods, neither of which by themselves are capable of solving the nonlinear problem accurately. Features of the Poisson-Boltzmann equation are fully exploited by each component of the hybrid algorithm to provide robustness and speed. The advantages inherent in this method increase with the size of the problem. The efficacy of the method is illustrated by calculations of the electrostatic potential around the enzyme Superoxide Dismutase. The CPU time required to solve the full nonlinear equation is less than half that needed for a conjugate gradient solution of the corresponding linearized Poisson-Boltzmann equation. The solutions reveal that the field around the active sites is significantly reduced as compared to that obtained by solving the corresponding linearized Poisson-Boltzmann equation. This new method for the nonlinear Poisson-Boltzmann equation will enable fast and accurate solutions of large protein electrostatics problems.     

Solving traveling salesman problems with DNA molecules encoding numerical values

We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.     

Hybrid Global Optimization Algorithms for Protein Structure Prediction: Alternating Hybrids

Hybrid global optimization methods attempt to combine the beneficial features of two or more algorithms, and can be powerful methods for solving challenging nonconvex optimization problems. In this paper, novel classes of hybrid global optimization methods, termed alternating hybrids, are introduced for application as a tool in treating the peptide and protein structure prediction problems. In particular, these new optimization methods take the form of hybrids between a deterministic global optimization algorithm, the αBB, and a stochastically based method, conformational space annealing (CSA). The αBB method, as a theoretically proven global optimization approach, exhibits consistency, as it guarantees convergence to the global minimum for twice-continuously differentiable constrained nonlinear programming problems, but can benefit from computationally related enhancements. On the other hand, the independent CSA algorithm is highly efficient, though the method lacks theoretical guarantees of convergence. Furthermore, both the αBB method and the CSA method are found to identify ensembles of low-energy conformers, an important feature for determining the true free energy minimum of the system. The proposed hybrid methods combine the desirable features of efficiency and consistency, thus enabling the accurate prediction of the structures of larger peptides. Computational studies for met-enkephalin and melittin, employing sequential and parallel computing frameworks, demonstrate the promise for these proposed hybrid methods.     

New Operational Matrices for Solving Fractional Differential Equations on the Half-Line

In this paper, the fractional-order generalized Laguerre operational matrices (FGLOM) of fractional derivatives and fractional integration are derived. These operational matrices are used together with spectral tau method for solving linear fractional differential equations (FDEs) of order ν (0 < ν < 1) on the half line. An upper bound of the absolute errors is obtained for the approximate and exact solutions. Fractional-order generalized Laguerre pseudo-spectral approximation is investigated for solving nonlinear initial value problem of fractional order ν. The extension of the fractional-order generalized Laguerre pseudo-spectral method is given to solve systems of FDEs. We present the advantages of using the spectral schemes based on fractional-order generalized Laguerre functions and compare them with other methods. Several numerical examples are implemented for FDEs and systems of FDEs including linear and nonlinear terms. We demonstrate the high accuracy and the efficiency of the proposed techniques.     

ABC-X: a generalized,automatically configurable artificial bee colony framework

The artificial bee colony (ABC) algorithm is a popular metaheuristic that was originally conceived for tackling continuous function optimization tasks. Over the last decade, a large number of variants of ABC have been proposed, making it by now a well-studied swarm intelligence algorithm. Typically, in a paper on algorithmic variants of ABC algorithms, one or at most two of its algorithmic components are modified. Possible changes include variations on the search equations, the selection of candidate solutions to be explored, or the adoption of features from other algorithmic techniques. In this article, we propose to follow a different direction and to build a generalized ABC algorithm, which we call ABC-X. ABC-X collects algorithmic components available from known ABC algorithms into a common algorithm framework that allows not only to instantiate known ABC variants but, more importantly, also many ABC algorithm variants that have never been explored before in the literature. Automatic algorithm configuration techniques can generate from this template new ABC variants that perform better than known ABC algorithms, even when their numerical parameters are fine-tuned using the same automatic configuration process.     

Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Fast k-NNG Construction with GPU-Based Quick Multi-Select

In this paper, we describe a new brute force algorithm for building the -Nearest Neighbor Graph (k-NNG). The k-NNG algorithm has many applications in areas such as machine learning, bio-informatics, and clustering analysis. While there are very efficient algorithms for data of low dimensions, for high dimensional data the brute force search is the best algorithm. There are two main parts to the algorithm: the first part is finding the distances between the input vectors, which may be formulated as a matrix multiplication problem; the second is the selection of the k-NNs for each of the query vectors. For the second part, we describe a novel graphics processing unit (GPU)-based multi-select algorithm based on quick sort. Our optimization makes clever use of warp voting functions available on the latest GPUs along with user-controlled cache. Benchmarks show significant improvement over state-of-the-art implementations of the k-NN search on GPUs.     

A Newton Cooperative Genetic Algorithm Method for In Silico Optimization of Metabolic Pathway Production

This paper presents an in silico optimization method of metabolic pathway production. The metabolic pathway can be represented by a mathematical model known as the generalized mass action model, which leads to a complex nonlinear equations system. The optimization process becomes difficult when steady state and the constraints of the components in the metabolic pathway are involved. To deal with this situation, this paper presents an in silico optimization method, namely the Newton Cooperative Genetic Algorithm (NCGA). The NCGA used Newton method in dealing with the metabolic pathway, and then integrated genetic algorithm and cooperative co-evolutionary algorithm. The proposed method was experimentally applied on the benchmark metabolic pathways, and the results showed that the NCGA achieved better results compared to the existing methods.     

A direct substitution, equation error technique for solving the thermographic tomography problem

A new technique for solving the combined state and parameter estimation problem in thermographic tomography is presented. The technique involves the direct substitution of known skin temperatures into the finite difference form of the bio-heat transfer equation as formulated for solving an initial value problem with a convection boundary condition at the skin surface. These equations are then used to solve the inverse bio-heat transfer problem for the unknown subcutaneous tissue temperatures and physiological parameters. For a small number of nodal points, closed form algebraic solutions are obtained. For larger sets of equations, a hybrid technique is used in which the problem is initially posed as an unconstrained optimization problem in which the model equation error is minimized using the conjugate gradient descent technique to get close to a solution. Then a generalized Newton-Raphson technique was used to solve the equations. A numerical simulation of a one-dimensional problem is investigated both with and without noise superimposed on the input (transient) skin temperature data. The results show that the technique gives very accurate results if the skin temperature data contains little noise. It is also shown that if the physical properties of the tissue and the metabolism are known, that a given set of proper transient skin temperature inputs yields a unique solution for the unknown internal temperatures and blood perfusion rates. However, the similar problem with known blood perfusion rates and unknown metabolisms does not yield a unique solution for the internal temperatures and metabolisms.     

The numerical method for the optimal supporting position and related optimal control for the catalytic reaction system

This paper considers the numerical approximation for the optimal supporting position and related optimal control of a catalytic reaction system with some control and state constraints, which is governed by a nonlinear partial differential equations with given initial and boundary conditions. By the Galerkin finite element method, the original problem is projected into a semi-discrete optimal control problem governed by a system of ordinary differential equations. Then the control parameterization method is applied to approximate the control and reduce the original system to an optimal parameter selection problem, in which both the position and related control are taken as decision variables to be optimized. This problem can be solved as a nonlinear optimization problem by a particle swarm optimization algorithm. The numerical simulations are given to illustrate the effectiveness of the proposed numerical approximation method.     

Biomimicry of symbiotic multi-species coevolution for discrete and continuous optimization in RFID networks

In recent years, symbiosis as a rich source of potential engineering applications and computational model has attracted more and more attentions in the adaptive complex systems and evolution computing domains. Inspired by different symbiotic coevolution forms in nature, this paper proposed a series of multi-swarm particle swarm optimizers called PS²Os, which extend the single population particle swarm optimization (PSO) algorithm to interacting multi-swarms model by constructing hierarchical interaction topologies and enhanced dynamical update equations. According to different symbiotic interrelationships, four versions of PS²O are initiated to mimic mutualism, commensalism, predation, and competition mechanism, respectively. In the experiments, with five benchmark problems, the proposed algorithms are proved to have considerable potential for solving complex optimization problems. The coevolutionary dynamics of symbiotic species in each PS²O version are also studied respectively to demonstrate the heterogeneity of different symbiotic interrelationships that effect on the algorithm’s performance. Then PS²O is used for solving the radio frequency identification (RFID) network planning (RNP) problem with a mixture of discrete and continuous variables. Simulation results show that the proposed algorithm outperforms the reference algorithms for planning RFID networks, in terms of optimization accuracy and computation robustness.     

A survey of non-linear optimization techniques

Optimization means the provision of a set of numerical parameter values which will give the best fit of an equation, or series of equations, to a set of data. For simple systems this can be done by differentiating the equations with respect to each parameter in turn, setting the set of partial differential equations to zero, and solving this set of simultaneous equations (as for exwnple in linear regression). In more complicated cases, however, it may be impossible to differentiate the equations, or very difficultly soluble non-linear equations may result. Many numerical optimization techniques to overcome these difficulties have been developed in the least ten years, and this review explains the logical basis of most of them, without going into the detail of computational procedures.The methods fall naturally into two classes - direct search methods, in which only values of the function to be minimized (or maximized) are used - and gradient methods, which also use derivatives of the function. The author considers all the accepted methods in each class, although warning that gradient methods should not be used unless the analytical differentiation of the function to be minimized is possible.If the solution is constrained, that is, certain values of the parameters are regarded as impossible or certain relations between the parameter values must be obeyed, the problem is more difficult. The second part of the review considers methods which have been proposed for the solution of constrained optimization problems.     

An optimal shape problem related to the realistic design of river fishways

A river fishway is a hydraulic structure that facilitates fish in overcoming obstacles (dams, waterfalls, etc.) to their spawning and other migrations in rivers. In this work we present a mathematical formulation of an optimal design problem for a vertical slot fishway, where the state system is given by the 2D shallow water equations fixing the height and velocity of water, the design variables are the geometry of the slots, and the objective function is determined by the existence of rest areas for fish and of a water velocity suitable for fish swimming capability. We also derive an expression for the gradient of the objective function via the adjoint system. From the numerical point of view, we present a characteristic-Galerkin method for solving the shallow water equations, and a direct search algorithm for the computation of the optimal design variables. Finally, we give numerical results obtained for a standard ten pools channel.     

Solution of large compartmental models using numerical transform inversion

Compartmental models of biological or physical systems are often described by a system of “stiff” differential equations. In this paper an algorithm for solving a system with linear coefficients is presented that employs numerical inversion of the Laplace transform of the model equations. The inversion algorithms and Gear's backward differentiation method are compared for two stiff test problems and a differential system governing a 27-compartment model of bile acid transport and metabolism. The inversion algorithm is reliable, requires modest computation time on a desktop computer and provides better accuracy than Gear's method, especially for the extremely stiff example.