A gradient‐only line search method for the conjugate gradient method applied to constrained optimization problems with severe noise in the objective function

A new implementation of the conjugate gradient method is presented that economically overcomes the problem of severe numerical noise superimposed on an otherwise smooth underlying objective function of a constrained optimization problem. This is done by the use of a novel gradient‐only line search technique, which requires only two gradient vector evaluations per search direction and no explicit function evaluations. The use of this line search technique is not restricted to the conjugate gradient method but may be applied to any line search descent method. This method, in which the gradients may be computed by central finite differences with relatively large perturbations, allows for the effective smoothing out of any numerical noise present in the objective function. This new implementation of the conjugate gradient method, referred to as the ETOPC algorithm, is tested using a large number of well‐known test problems. For initial tests with no noise introduced in the objective functions, and with high accuracy requirements set, it is found that the proposed new conjugate gradient implementation is as robust and reliable as traditional first‐order penalty function methods. With the introduction of severe relative random noise in the objective function, the results are surprisingly good, with accuracies obtained that are more than sufficient compared to that required for engineering design optimization problems with similar noise. Copyright © 2004 John Wiley & Sons, Ltd.     

A comparison of Lanczos and optimization methods in the partial solution of sparse symmetric eigenproblems

In the present paper, we analyse the computational performance of the Lanczos method and a recent optimization technique for the calculation of the p (p ≤ 40) leftmost eigenpairs of generalized symmetric eigenproblems arising from the finite element integration of elliptic PDEs. The accelerated conjugate gradient method is used to minimize successive Rayleigh quotients defined in deflated subspaces of decreasing size. The pointwise Lanczos scheme is employed in combination with both the Cholesky factorization of the stiffness matrix and the preconditioned conjugate gradient method for evaluating the recursive Lanczos vectors. The three algorithms are applied to five sample problems of varying size up to almost 5000. The numerical results show that the Lanczos approach with Cholesky triangularization is generally faster (up to a factor of 5) for small to moderately large matrices, while the optimization method is superior for large problems in terms of both storage requirement and CPU time. In the large case, the Lanczos–Cholesky scheme may be very expensive to run even on modern quite powerful computers.     

A fast first-order optimization approach to elastoplastic analysis of skeletal structures

It is classical that, when the small deformation is assumed, the incremental analysis problem of an elastoplastic structure with a piecewise-linear yield condition and a linear strain hardening model can be formulated as a convex quadratic programming problem. Alternatively, this paper presents a different formulation, an unconstrained nonsmooth convex optimization problem, and proposes to solve it with an accelerated gradient-like method. Specifically, we adopt an accelerated proximal gradient method, that has been developed for a regularized least squares problem. Numerical experiments show that the presented algorithm is effective for large-scale elastoplastic analysis. Also, a simple warm-start strategy can speed up the algorithm when the path-dependent incremental analysis is carried out.     

Extending interior-point methods to nonlinear second-order cone programming: Application to finite-strain elastoplasticity

Interior-point methods (IPMs) are well suited for solving convex nonsmooth optimization problems which arise for instance in problems involving plasticity or contact conditions. This work attempts at extending their field of application to optimization problems involving either smooth but nonconvex or nonsmooth but convex objectives or constraints. A typical application for such kind of problems is finite-strain elastoplasticity which we address using a total Lagrangian formulation based on logarithmic strain measures. The proposed interior-point algorithm is implemented and tested on 3D examples involving plastic collapse and geometrical changes. Comparison with classical, Newton-Raphson/return mapping methods show that the IPM exhibits good computational performance, especially in terms of convergence robustness. Similar to what is observed for convex small-strain plasticity, the IPM is able to converge for much larger load steps than classical methods.     

Pareto archived dynamically dimensioned search with hypervolume-based selection for multi-objective optimization

Pareto archived dynamically dimensioned search (PA-DDS) is a parsimonious multi-objective optimization algorithm with only one parameter to diminish the user's effort for fine-tuning algorithm parameters. This study demonstrates that hypervolume contribution (HVC) is a very effective selection metric for PA-DDS and Monte Carlo sampling-based HVC is very effective for higher dimensional problems (five objectives in this study). PA-DDS with HVC performs comparably to algorithms commonly applied to water resources problems (?-NSGAII and AMALGAM under recommended parameter values). Comparisons on the CEC09 competition show that with sufficient computational budget, PA-DDS with HVC performs comparably to 13 benchmark algorithms and shows improved relative performance as the number of objectives increases. Lastly, it is empirically demonstrated that the total optimization runtime of PA-DDS with HVC is dominated (90% or higher) by solution evaluation runtime whenever evaluation exceeds 10 seconds/solution. Therefore, optimization algorithm runtime associated with the unbounded archive of PA-DDS is negligible in solving computationally intensive problems.     

Difference of convex functions algorithms (DCA) for image restoration via a Markov random field model

In this paper, we introduce a novel approach in the nonconvex optimization framework for image restoration via a Markov random field (MRF) model. While image restoration is elegantly expressed in the language of MRF’s, the resulting energy minimization problem was widely viewed as intractable: it exhibits a highly nonsmooth nonconvex energy function with many local minima, and is known to be NP-hard. The main goal of this paper is to develop fast and scalable approximation optimization approaches to a nonsmooth nonconvex MRF model which corresponds to an MRF with a truncated quadratic (also known as half-quadratic) prior. For this aim, we use the difference of convex functions (DC) programming and DC algorithm (DCA), a fast and robust approach in smooth/nonsmooth nonconvex programming, which have been successfully applied in various fields in recent years. We propose two DC formulations and investigate the two corresponding versions of DCA. Numerical simulations show the efficiency, reliability and robustness of our customized DCAs with respect to the standard GNC algorithm and the Graph-Cut based method—a more recent and efficient approach to image analysis.     

Conjugate gradient method for the Robin inverse problem associated with the Laplace equation

This paper studies a non-linear inverse problem associated with the Laplace equation of identifying the Robin coefficient from boundary measurements. A variational formulation of the problem is suggested, thereby transforming it into an optimization problem. Mathematical properties relevant to its numerical computation are established. The optimization problem is solved using the conjugate gradient method in conjunction with the discrepancy principle, and the algorithm is implemented using the boundary element method. Numerical results are presented for several benchmark problems with both exact and noisy data, and the convergence of the algorithm with respect to mesh refinement and decreasing the amount of noise in the data is investigated. Copyright © 2006 John Wiley & Sons, Ltd.     

OPTIMIZATION OF A WATER RESOURCES SYSTEM BY NON-LINEAR PROGRAMMING

Optimization of a water resources system necessarily must appropriately mesh the modeling of the system with the optimization technique used. If the system model is linear, many effective optimization techniques exist. But if the model is non-linear in the objective function and/or constraints, very few effective optimization methods exist. This paper describes how a water resources system, including both water quantity and water quality, can be modeled to form a non-linear programming problem. The latter is solved by two techniques: (a) a Generalized Reduced Gradient method, and (b) a conjugate gradient projection method. The relationship between the model and the formulation of the non-linear programming problem is discussed, and computational experience with each of the algorithms is described.     

Dark Forest Algorithm: A Novel Metaheuristic Algorithm for Global Optimization Problems

Metaheuristic algorithms, as effective methods for solving optimization problems, have recently attracted considerable attention in science and engineering fields. They are popular and have broad applications owing to their high efficiency and low complexity. These algorithms are generally based on the behaviors observed in nature, physical sciences, or humans. This study proposes a novel metaheuristic algorithm called dark forest algorithm (DFA), which can yield improved optimization results for global optimization problems. In DFA, the population is divided into four groups: highest civilization, advanced civilization, normal civilization, and low civilization. Each civilization has a unique way of iteration. To verify DFA’s capability, the performance of DFA on 35 well-known benchmark functions is compared with that of six other metaheuristic algorithms, including artificial bee colony algorithm, firefly algorithm, grey wolf optimizer, harmony search algorithm, grasshopper optimization algorithm, and whale optimization algorithm. The results show that DFA provides solutions with improved efficiency for problems with low dimensions and outperforms most other algorithms when solving high dimensional problems. DFA is applied to five engineering projects to demonstrate its applicability. The results show that the performance of DFA is competitive to that of current well-known metaheuristic algorithms. Finally, potential upgrading routes for DFA are proposed as possible future developments.     

Hessian approximation algorithms for hybrid optimization methods

This article introduces Hessian approximation algorithms to estimate the search direction of the quasi-Newton methods for solving optimization problems of continuous parameters. The proposed algorithms are quite different from other well-known quasi-Newton methods, such as symmetric rank-one, Davidon–Fletcher–Powell, and Broyden–Fletcher–Goldfarb–Shanno, in that the Hessian matrix is not calculated from the gradient information, rather directly from the function values. The proposed algorithms are designed for a class of hybrid algorithms that combine evolutionary search with the gradient-based methods of quasi-Newton type. The function values calculated for the evolutionary search are used for estimation of the Hessian matrix (or its inverse) as well as the gradient vector. Since the estimation process of the Hessian matrix is independent of that of the gradient vector, more reliable Hessian estimation with a small population is possible compared with the previous methods based upon the classical quasi-Newton methods. Numerical experiments show that the proposed algorithms are very competitive with state-of-the-art evolutionary algorithms for continuous optimization problems.     

IRKO: An Improved Runge-Kutta Optimization Algorithm for Global Optimization Problems

Optimization is a key technique for maximizing or minimizing functions and achieving optimal cost, gains, energy, mass, and so on. In order to solve optimization problems, metaheuristic algorithms are essential. Most of these techniques are influenced by collective knowledge and natural foraging. There is no such thing as the best or worst algorithm; instead, there are more effective algorithms for certain problems. Therefore, in this paper, a new improved variant of a recently proposed metaphorless Runge-Kutta Optimization (RKO) algorithm, called Improved Runge-Kutta Optimization (IRKO) algorithm, is suggested for solving optimization problems. The IRKO is formulated using the basic RKO and local escaping operator to enhance the diversification and intensification capability of the basic RKO version. The performance of the proposed IRKO algorithm is validated on 23 standard benchmark functions and three engineering constrained optimization problems. The outcomes of IRKO are compared with seven state-of-the-art algorithms, including the basic RKO algorithm. Compared to other algorithms, the recommended IRKO algorithm is superior in discovering the optimal results for all selected optimization problems. The runtime of IRKO is less than 0.5 s for most of the 23 benchmark problems and stands first for most of the selected problems, including real-world optimization problems.     

A hybrid cellular automaton–bi-directional evolutionary optimization algorithm for topological optimization of crashworthiness

This article proposes a new algorithm for topological optimization under dynamic loading which combines cellular automata with bi-directional evolutionary structural optimization (BESO). The local rules of cellular automata are used to update the design variables, which avoids the difficulty of obtaining gradient information under nonlinear collision conditions. The intermediate-density design problem of hybrid cellular automata is solved using the BESO concept of 0–1 binary discrete variables. Some improvement strategies are also proposed for the hybrid algorithm to solve certain problems in nonlinear topological optimization, e.g. numerical oscillation. Some typical examples of crashworthiness problems are provided to illustrate the efficiency of the proposed method and its ability to find the final optimal solution. Finally, numerical results obtained using the proposed algorithms are compared with reference examples taken from the literature. The results show that the hybrid method is computationally efficient and stable.     

一个充分下降的修正 PRP 型谱共轭梯度法

谱共轭梯度法是共轭梯度法的一种重要延拓,可以通过共轭参数和谱参数二维度调整,使得所设计算法的搜索方向满足某一预设条件,比如充分下降条件或共轭条件等。谱参数和共轭参数的设计是谱共轭梯度法的两大核心工作,决定方法的收敛性和数值效果。基于 PRP 方法,构造了一个修正的 PRP 型共轭参数,该共轭参数不仅保持了 PRP 公式的结构和性能,而且具有 FR 方法的收敛性质。利用充分下降条件取定一个谱参数,与修正的 PRP 型共轭参数结合,建立一个新的谱共轭梯度算法。该算法不依赖于任何线搜索就可以满足充分下降条件。常规假设条件下,采用强 Wolfe 线搜索准则产生步长,证明了新算法的全局敛性。通过 100 个算例对该算法进行数值测试并与其他五个算法进行比较,同时采用性能图对数值结果进行直观展示,结果表明该算法是有效的。     

A new surrogate modeling method combining polynomial chaos expansion and Gaussian kernel in a sparse Bayesian learning framework

Surrogate modeling techniques have been increasingly developed for optimization and uncertainty quantification problems in many engineering fields. The development of surrogates requires modeling high-dimensional and nonsmooth functions with limited information. To this end, the hybrid surrogate modeling method, where different surrogate models are combined, offers an effective solution. In this paper, a new hybrid modeling technique is proposed by combining polynomial chaos expansion and kernel function in a sparse Bayesian learning framework. The proposed hybrid model possesses both the global characteristic advantage of polynomial chaos expansion and the local characteristic advantage of the Gaussian kernel. The parameterized priors are utilized to encourage the sparsity of the model. Moreover, an optimization algorithm aiming at maximizing Bayesian evidence is proposed for parameter optimization. To assess the performance of the proposed method, a detailed comparison is made with the well-established PC-Kriging technique. The results show that the proposed method is superior in terms of accuracy and robustness.     

Optimal subgradient methods: computational properties for large-scale linear inverse problems

This paper studies the computational properties of the optimal subgradient algorithm (OSGA) for applications of linear inverse problems involving high-dimensional data. First, such convex problems are formulated as a class of convex problems with multi-term composite objective functions involving linear mappings. Next, an efficient procedure for computing the first-order oracle for such problems is provided and OSGA is equipped with some prox-functions such that the OSGA subproblem is solved in a closed form. Further, a comprehensive comparison among the most popular first-order methods is given. Then, several Nesterov-type optimal methods (originally proposed for smooth problems) are adapted to solve nonsmooth problems by simply passing a subgradient instead of the gradient, where the results of these subgradient methods are competitive and totally interesting for solving nonsmooth problems. Finally, numerical results with several inverse problems (deblurring with isotropic total variation, elastic net, and \(\ell _1\)-minimization) show the efficiency of OSGA and the adapted Nesterov-type optimal methods for large-scale problems. For the deblurring problem, the efficiency measures of the improvement on the signl-to-noise ratio and the peak signal-to-noise ratio are used. The software package implementing OSGA is publicly available.     

Application of the inverse elasticity problem to identify irregular interfacial configurations

An inverse elasticity problem is solved to identify the irregular boundary between the components of a multiple connected domain using displacement measurements obtained from an uniaxial tension test. The boundary elements method (BEM) coupled with the particle swarm optimization (PSO) and conjugate gradient method (CGM) are employed. Due to the ill-posed nature of this inverse elasticity problem, and the need for an initial guess of the unknown interfacial boundary when local optimization methods are implemented, a Meta heuristic procedure based on the PSO algorithm is presented. The CGM is then employed using the best initial guess obtained by the PSO to reach convergence. This procedure is highly effective, since the computational time reduces considerably and accuracy of the results is reasonable. Several example problems are solved and the accuracy of obtained results is discussed. The influence of material properties and the effect of measurement errors on the estimation process are also addressed.     

基于信息熵改进的粒子群算法在桁架结构

提出了信息熵改进的粒子群优化算法用于解决有应力约束、位移约束的桁架结构杆件截面尺寸优化设计问题.首先介绍了信息熵基本理论和基本粒子群优化算法理论,然后对粒子群优化算法作了合理的参数设置,并将信息熵引入粒子群优化算法的适应函数和停机判别准则中.最后对2个经典的优化问题进行求解并与其他算法进行了比较.数据结果表明信息熵改进后的粒子群优化算法在桁架结构优化设计中优于其他同类算法.     

结合广义Armijo步长搜索的一类记忆梯度算法及其收敛特征

本文对求解无约束规划的超记忆梯度算法中线搜索方向中的参数,给了一个假设条件,从而确定了它的一个新的取值范围,保证了搜索方向是目标函数的充分下降方向,由此提出了一类新的记忆梯度算法.并在去掉迭代点列有界和广义Armijo步长搜索下,讨论了算法的全局收敛性,且给出了结合形如共轭梯度法FR,PR,HS的记忆梯度法的修正形式,数值实验表明,新算法比Armijo线搜索下的FR,PR,HS共轭梯度法和超记忆梯度法更稳定、更有效.     

Evolutionary computation of unconstrained and constrained problems using a novel momentum-type particle swarm optimization

This study proposes a novel momentum-type particle swarm optimization (PSO) method, which will find good solutions of unconstrained and constrained problems using a delta momentum rule to update the particle velocity. The algorithm modifies Shi and Eberhart's PSO to enhance the computational efficiency and solution accuracy. This study also presents a continuous non-stationary penalty function, to force design variables to satisfy all constrained functions. Several well-known and widely used benchmark problems were employed to compare the performance of the proposed PSO with Kennedy and Eberhart's PSO and Shi and Eberhart's modified PSO. Additionally, an engineering optimization task for designing a pressure vessel was applied to test the three PSO algorithms. The optimal solutions are presented and compared with the data from other works using different evolutionary algorithms. To show that the proposed momentum-type PSO algorithm is robust, its convergence rate, solution accuracy, mean absolute error, standard deviation, and CPU time were compared with those of both the other PSO algorithms. The experimental results reveal that the proposed momentum-type PSO algorithm can efficiently solve unconstrained and constrained engineering optimization problems.     

Metamodel Assisted Evolutionary Algorithm for Multi-objective Optimization of Non-steady Metal Forming Problems

Multiobjective optimization problems are considered in the field of nonsteady metal forming processes, such as forging or wire drawing. The Pareto optimal front of the problem solution set is calculated by a Genetic Algorithm. In order to reduce the inherent computational cost of such algorithms, a surrogate model is developed and replaces the exact the function simulations. It is based on the Meshless Finite Difference Method and is coupled to the NSGAII Evolutionary Multiobjective Optimization Algorithm, in a way that uses the merit function. This function offers the best way to select new evaluation points: it combines the exploitation of obtained results with the exploration of parameter space. The algorithm is evaluated on a wide range of analytical multiobjective optimization problems, showing the importance to update the metamodel along with the algorithm convergence. The application to metal forming multiobjective optimization problems show both the efficiency of the metamodel based algorithms and the type of practical information that can be derived from a multiobjective approach.