A filled function method for finding a global minimizer of a function of several variables

The concept of a filled function is introduced. We construct a particular filled function and analyze its properties. An algorithm for global minimization is generated based on the concept and properties of the filled function. Some typical examples with 1 to 10 variables are tested and computational results show that in most cases this algorithm works better than the tunneling algorithm. The advantages and disadvantages are analyzed and further research directions are discussed.     

On the convergence,invariance, and related aspects of a modification of Huang's algorithm

We consider a certain generalization of the Huang family of updates and discuss, firstly, convergence, dependence on parameters, and descent property; secondly, invariance under nonlinear scaling, conjugacy of search directions, and possibility of achieving a better approximation of the inverse of the Hessian. The last three aspects are shown to be dependent on particular choices of parameters. A numerical experiment is presented comparing the performances of the usual and modified BFGS algorithms.The author is indebted to Professor D. H. Jacobson and Professor M. J. D. Powell for helpful discussions during the preparation of this paper.This work was partially supported by a grant from Control Data.     

On the Huang Class of Variable Metric Methods

Several authors have created one-parameter families of variable metric methods for function minimization. These families contain the methods known as Davidon–Fletcher–Powell, Broyden–Fletcher–Goldfarb–Shanno, and symmetric rank one. It is shown here that the same one-parameter families of methods are obtained from the Huang update by requiring the update to be symmetric.     

A quasi-discrete Newton algorithm with a nonmonotone stabilization technique

In this paper, we define an unconstrained optimization algorithm employing only first-order derivatives, in which a nonmonotone stabilization technique is used in conjunction with a quasidiscrete Newton method for the computation of the search direction. Global and superlinear convergence is proved, and numerical results are reported.     

A modified Newton method for minimization

Some promising ideas for minimizing a nonlinear function, whose first and second derivatives are given, by a modified Newton method, were introduced by Fiacco and McCormick (Ref. 1). Unfortunately, in developing a method around these ideas, Fiacco and McCormick used a potentially unstable, or even impossible, matrix factorization. Using some recently developed techniques for factorizing an indefinite symmetric matrix, we are able to produce a method which is similar to Fiacco and McCormick's original method, but avoids the difficulties of the original method.Both authors gratefully acknowledge the award of a research fellowship from the British Science Research Council.     

基于非线性尺度不变性的CCG法

１．引言 ＣＧ法对于变量个数很多的问题,是很有用的．１９７０年后它有了许多改进和发展,ＣＣＧ法以正定圆锥函数为基础［１］,它的一般方法是：设圆锥函数为 ２］其中： Ｖ＝ Ｖ（ｘ）＝１＋ ａＴｘ ≠ ０;, ｒ ∈Ｒ１为常量; ａ,ｇ ∈ Ｒｎ为常向量;ｘ ∈ Ｒｎ为变向量;Ａ∈Ｒｎ×ｎ为对称正定矩阵．算法［１］：预先给出初始近似点ｘ０∈ Ｒｎ及初始搜索方向 ｐ０;满足：其中“Ｉ”是单位矩阵, Ｖ０＝ Ｖ（ｘ０）＝ １＋ ａｔｘ０及记号“”是函数的梯度．迭代格式为： ｘｋ＋１＝ ｘｋ ＋λｋｐｋ,ｋ＝ ０,１,２,…（３…     

On the accelerating property of an algorithm for function minimization without calculating derivatives

It is shown that the alogrithm of Ref. E1, when converging on a uniformly convex function and when technical condition (13) of Ref. E1 is satisfied, has ann-iterationQ-superlinear rate of convergence and a behaviour which is a precursor of every-iterationQ-superlinearity. This result overrides and corrects main result Theorem 3.1 of Ref. E1.     

On the accelerating property of an algorithm for function minimization without calculating derivatives

This paper studies the speed of convergence of a general algorithm for function minimization without calculating derivatives. This algorithm contains Powell's 1964 algorithm as well as Zangwill's second modification of this procedure. The main results are Theorems 3.1 and 4.1 which show that, if the algorithm behaves well, then asymptotically almost conjugate directions are built; therefore, the algorithm has an every-iteration superlinear speed of convergence. The paper hinges on ideas of McCormick and Ritter and Powell.The authors wish to thank the Namur Department of Mathematics, especially its optimization group, for many discussions and encouragements. The authors also thank the reviewer for many helpful suggestions.     

A variable-metric method for function minimization derived from invariancy to nonlinear scaling

The effect of nonlinearly scaling the objective function on the variable-metric method is investigated, and Broyden's update is modified so that a property of invariancy to the scaling is satisfied. A new three-parameter class of updates is generated, and criteria for an optimal choice of the parameters are given. Numerical experiments compare the performance of a number of algorithms of the resulting class.The author is indebted to Professor S. S. Oren, Economic Engineering Department, Stanford University, Stanford, California, for stimulating discussions during the development of this paper. He also recognizes the financial support by the National Research Council of Italy (CNR) for his stay at Stanford University.     

CGS algorithms for unconstrained minimization of functions

In 1952, Hestenes and Stiefel first established, along with the conjugate-gradient algorithm, fundamental relations which exist between conjugate direction methods for function minimization on the one hand and Gram-Schmidt processes relative to a given positive-definite, symmetric matrix on the other. This paper is based on a recent reformulation of these relations by Hestenes which yield the conjugate Gram-Schmidt (CGS) algorithm. CGS includes a variety of function minimization routines, one of which is the conjugate-gradient routine. This paper gives the basic equations of CGS, including the form applicable to minimizing general nonquadratic functions ofn variables. Results of numerical experiments of one form of CGS on five standard test functions are presented. These results show that this version of CGS is very effective.The preparation of this paper was sponsored in part by the US Army Research Office, Grant No. DH-ARO-D-31-124-71-G18.The authors wish to thank Mr. Paul Speckman for the many computer runs made using these algorithms. They served as a good check on the results which they had obtained earlier. Special thanks must go to Professor M. R. Hestenes whose constant encouragement and assistance made this paper possible.     

Some investigations about a unified approach to quadratically convergent algorithms for function minimization

In 1969, Huang (Ref. 1) proposed a unified approach to quadratically convergent algorithms for function minimization without constraints; if we slightly modify a few points of his development, some other algorithms can be generated, among which several were published after 1969. It is also possible to generate a class of algorithms which provide quadratic convergence without linear search at each step.     

Gilding the Lily: A Variant of the Nelder-Mead Algorithm Based on Golden-Section Search

We propose a variant of the Nelder-Mead algorithm derived from a reinterpretation of univariate golden-section direct search. In the univariate case, convergence of the variant can be analyzed analogously to golden-section search. In the multivariate case, we modify the variant by replacing strict descent with fortified descent and maintaining the interior angles of the simplex bounded away from zero. Convergence of the modified variant can be analyzed by applying results for a fortified-descent simplicial search method. Some numerical experience with the variant is reported.     

A Generalized Conjugate Gradient Algorithm

We present modifications of the generalized conjugate gradient algorithm of Liu and Storey for unconstrained optimization problems (Ref. 1), extending its applicability to situations where the search directions are not defined. The use of new search directions is proposed and one additional condition is imposed on the inexact line search. The convergence of the resulting algorithm can be established under standard conditions for a twice continuously differentiable function with a bounded level set. Algorithms based on these modifications have been tested on a number of problems, showing considerable improvements. Comparisons with the BFGS and other quasi-Newton methods are also given.     

Global convergence and stabilization of unconstrained minimization methods without derivatives

In this paper, acceptability criteria for the stepsize and global convergence conditions are established for unconstrained minimization methods employing only function values. On the basis of these results, the convergence of an implementable line search algorithm is proved and some global stabilization schemes are described.The authors would like to thank the anonymous referees for their useful suggestions.     

A class of generalized variable penalty methods for nonlinear programming

A class of generalized variable penalty formulations for solving nonlinear programming problems is presented. The method poses a sequence of unconstrained optimization problems with mechanisms to control the quality of the approximation for the Hessian matrix, which is expressed in terms of the constraint functions and their first derivatives. The unconstrained problems are solved using a modified Newton's algorithm. The method is particularly applicable to solution techniques where an approximate analysis step has to be used (e.g., constraint approximations, etc.), which often results in the violation of the constraints. The generalized penalty formulation contains two floating parameters, which are used to meet the penalty requirements and to control the errors in the approximation of the Hessian matrix. A third parameter is used to vary the class of standard barrier or quasibarrier functions, forming a branch of the variable penalty formulation. Several possibilities for choosing such floating parameters are discussed. The numerical effectiveness of this algorithm is demonstrated on a relatively large set of test examples.The author is thankful for the constructive suggestions of the referees.     

On the resolution of monotone complementarity problems

A reformulation of the nonlinear complementarity problem (NCP) as an unconstrained minimization problem is considered. It is shown that any stationary point of the unconstrained objective function is a solution of NCP if the mapping F involved in NCP is continuously differentiable and monotone, and that the level sets are bounded if F is continuous and strongly monotone. A descent algorithm is described which uses only function values of F. Some numerical results are given.     

Nonmonotone Algorithms for Pattern Search Methods

This work deals with the solution of ill-conditioned unconstrained minimization problems by means of pattern search methods. To this end, the usual requirement of monotonic reduction of the objective function is relaxed and nonmonotone pattern search methods are proposed, which maintain the convergence properties of their monotone counterparts. Numerical experimentation on several well-known ill-conditioned functions is reported. The results highlight a class of pattern search methods which benefit very much by the introduction of nonmonotone strategies.     

解新锥模型信赖域子问题的折线法

本文以新锥模型信赖域子问题的最优性条件为理论基础,认真讨论了新子问题的锥函数性质,分析了此函数在梯度方向及与牛顿方向连线上的单调性.在此基础上本文提出了一个求解新锥模型信赖域子问题折线法,并证明了这一子算法保证解无约束优化问题信赖域法全局收敛性要满足的下降条件.本文获得的数值实验表明该算法是有效的.     

An improved version of the original leap-frog dynamic method for unconstrained minimization: LFOP1(b)

A modified version of the author's original dynamic algorithm for unconstrained minimization is proposed. It employs time step selection procedure which results in a more efficient utilization of the original dynamic algorithm. The performance of the new algorithm is compared with that of a well established conjugate gradient algorithm when applied to three different extended test functions. Based on a comparison of the respective CPU times required for convergence, the new algorithm appears to be competitive.