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.     

A parallel variable-metric dynamic programming algorithm

This paper presents a potentially parallel iterative algorithm for the solution of the unconstrainedN-stage decision problem of dynamic programming. The basis of the algorithm is the use of variable-metric minimization techniques to develop a quadratic approximation to the cost function at each stage. The algorithm is applied to various problems, and comparisons with other algorithms are made.This research forms part of the author's PhD program, and is supported by the Department of Scientific and Industrial Research of the New Zealand Government. The author is indebted to Dr. B. A. Murtagh, PhD supervisor, for his encouragement and support during the preparation of this paper.     

New variable-metric algorithms for nondifferentiable optimization problems

This paper deals with new variable-metric algorithms for nonsmooth optimization problems, the so-called adaptive algorithms. The essence of these algorithms is that there are two simultaneously working gradient algorithms: the first is in the main space and the second is in the space of the matrices that modify the main variables. The convergence of these algorithms is proved for different cases. The results of numerical experiments are also given.     

A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization

Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is derived that include existing and several new approaches for concave minimization problems.     

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.     

Supermemory descent methods for unconstrained minimization

The supermemory gradient method of Cragg and Levy (Ref. 1) and the quasi-Newton methods with memory considered by Wolfe (Ref. 4) are shown to be special cases of a more general class of methods for unconstrained minimization which will be called supermemory descent methods. A subclass of the supermemory descent methods is the class of supermemory quasi-Newton methods. To illustrate the numerical effectiveness of supermemory quasi-Newton methods, some numerical experience with one such method is reported.The authors are indebted to Dr. H. Y. Huang for his helpful criticism of this paper.     

Proximity control in bundle methods for convex nondifferentiable minimization

Proximal bundle methods for minimizing a convex functionf generate a sequence {x ^k } by takingx ^k+1 to be the minimizer of , where is a sufficiently accurate polyhedral approximation tof andu ^k > 0. The usual choice ofu ^k = 1 may yield very slow convergence. A technique is given for choosing {u ^k } adaptively that eliminates sensitivity to objective scaling. Some encouraging numerical experience is reported.This research was supported by Project CPBP.02.15.     

Generalization of conjugate direction methods in the optimization of functions

An erratic formulation of the construction of anA-conjugate pair given in Ref. 1 is corrected.     

On the convergence of a class of derivative-free minimization algorithms

A convergence analysis is presented for a general class of derivative-free algorithms for minimizing a functionf(x) for which the analytic form of the gradient and the Hessian is impractical to obtain. The class of algorithms accepts finite-difference approximation to the gradient, with stepsizes chosen in such a way that the length of the stepsize must meet two conditions involving the previous stepsize and the distance from the last estimate of the solution to the current estimate. The algorithms also maintain an approximation to the second-derivative matrix and require that the change inx made at each iteration be subject to a bound that is also revised automatically. The convergence theorems have the features that the starting pointx ¹ need not be close to the true solution andf(x) need not be convex. Furthermore, despite the fact that the second-derivative approximation may not converge to the true Hessian at the solution, the rate of convergence is still Q-superlinear. The theorry is also shown to be applicable to a modification of Powell's dog-leg algorithm.     

Generalization of conjugate direction methods in the optimization of functions

The unconstrained optimization of a function of several variables is considered. An algorithm is constructed using the notion of generalized conjugate directions. It is proved that this method will find the minimum of a quadratic function in a finite number of steps. Some well-known conjugate direction methods are shown to be special cases of the generalized method.     

Solving the nonlinear least square problem: Application of a general method

An algorithm for solving the general nonlinear least-square problem is developed. An estimate for the Hessian matrix is constructed as the sum of two matrices. The first matrix is the usual first-order estimate used by the Gauss method, while the second matrix is generated recursively using a rank-one formula. Test results indicate that the method is superior to the standard Gauss method and compares favorably with other methods, especially for problems with nonzero residuals at the solution.This work was supported by the US Air Force under Contract No. F04701-73-C-0074.The author expresses his appreciation to Dr. H. E. Pickett and Dr. J. L. Searcy for their continuing support in the theoretical and practical development of the algorithm. The recursive method for generating the estimate of the Hessian matrix was developed jointly with Drs. Pickett and Searcy and is included here with their permission. The author would also like to acknowledge the contribution made by the stimulating environment of an optimal control seminar held at The Aerospace Corporation since 1970. Principle members of the seminar have been H. E. Pickett, J. L. Searcy, R. W. Reid, and the author.     

Extended conjugate-gradient methods with restarts

Three variants of the classical conjugate-gradient method are presented. Two of these variants are based upon a nonlinear function of a quadratic form. A restarting procedure due to Powell, and based upon some earlier work of Beale, is discussed and incorporated into two of the variants. Results of applying the four algorithms to a set of benchmark problems are included, and some tentative conclusions about the relative merits of the four schemes are presented.     

A variable-metric variant of the Karmarkar algorithm for linear programming

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company.     

A variable-metric method using a nonquadratic model

In this paper, a new variable-metric method based on a rational, rather than a quadratic, model is proposed. A switching algorithm is also introduced which selects either the standard quadratic model or the new rational model, depending on which has the smallest condition number. Several functions are used to test the new method, and it is concluded that it is as efficient as the standard model in general and is superior for problems of high dimensionality. Considerable improvement is also obtained for high-dimensional problems when the switching algorithm is used.     

On the convergence of asynchronous parallel algorithm for large-scale linearly constrained minimization problem

As a synchronization parallel framework, the parallel variable transformation (PVT) algorithm is effective to solve unconstrained optimization problems. In this paper, based on the idea that a constrained optimization problem is equivalent to a differentiable unconstrained optimization problem by introducing the Fischer Function, we propose an asynchronous PVT algorithm for solving large-scale linearly constrained convex minimization problems. This new algorithm can terminate when some processor satisfies terminal condition without waiting for other processors. Meanwhile, it can enhances practical efficiency for large-scale optimization problem. Global convergence of the new algorithm is established under suitable assumptions. And in particular, the linear rate of convergence does not depend on the number of processors.     

Method of dual matrices for function minimization

In this paper, the method of dual matrices for the minimization of functions is introduced. The method, which is developed on the model of a quadratic function, is characterized by two matrices at each iteration. One matrix is such that a linearly independent set of directions can be generated, regardless of the stepsize employed. The other matrix is such that, at the point where the first matrix fails to yield a gradient linearly independent of all the previous gradients, it generates a displacement leading to the minimal point. Thus, the one-dimensional search is bypassed. For a quadratic function, it is proved that the minimal point is obtained in at mostn + 1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn + 2.Three algorithms of the method are presented. A reverse algorithm, which permits the use of only one matrix, is also given. Considerations pertaining to the applications of this method to the minimization of a quadratic function and a nonquadratic function are given. It is believed that, since the one-dimensional search can be bypassed, a considerable amount of computational saving can be achieved.This paper, supported by the National Science Foundation, Grant No. GP-32453, is based on Ref. 1.     

Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization

This paper presents new versions of proximal bundle methods for solving convex constrained nondifferentiable minimization problems. The methods employ ₁ or exact penalty functions with new penalty updates that limit unnecessary penalty growth. In contrast to other methods, some of them are insensitive to problem function scaling. Global convergence of the methods is established, as well as finite termination for polyhedral problems. Some encouraging numerical experience is reported. The ideas presented may also be used in variable metric methods for smooth nonlinear programming.This research was supported by the Polish Academy of Sciences.     

Deterministic global optimization with partition sets whose feasibility is not known: Application to concave minimization,reverse convex constraints,DC-programming,and Lipschitzian optimization

A crucial problem for many global optimization methods is how to handle partition sets whose feasibility is not known. This problem is solved for broad classes of feasible sets including convex sets, sets defined by finitely many convex and reverse convex constraints, and sets defined by Lipschitzian inequalities. Moreover, a fairly general theory of bounding is presented and applied to concave objective functions, to functions representable as differences of two convex functions, and to Lipschitzian functions. The resulting algorithms allow one to solve any global optimization problem whose objective function is of one of these forms and whose feasible set belongs to one of the above classes. In this way, several new fields of optimization are opened to the application of global methods.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250