A new filled function method for unconstrained global optimization

In this paper, a new filled function which has better properties is proposed for identifying a global minimum point for a general class of nonlinear programming problems within a closed bounded domain. An algorithm for unconstrained global optimization is developed from the new filled function. Theoretical and numerical properties of the proposed filled function are investigated. The implementation of the algorithm on seven test problems is reported with satisfactory numerical results.     

Filled functions for unconstrained global optimization

The paper is concerned with the filled functions for global optimization of a continuous function of several variables. More general forms of filled functions are presented for smooth and nonsmooth optimizations. These functions have either two adjustable parameters or one adjustable parameter. Conditions on functions and on the values of parameters are given so that the constructed functions are desired filled functions.     

Filled functions for unconstrained global optimization

This paper is concerned with filled function techniques for unconstrained global minimization of a continuous function of several variables. More general forms of filled functions are presented for smooth and non-smooth optimization problems. These functions have either one or two adjustable parameters. Conditions on functions and on the values of parameters are given so that the constructed functions have the desired properties of filled functions.     

Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

An integral function and vector sequence method for unconstrained global optimization

This paper studies the relationship between the so-called bi-quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an O(r){\mathcal{O}(r)}-approximation solution of the original bi-quadratic optimization problem, where the constant in O(r){\mathcal{O}(r)} does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems.     

A filled function method with one parameter for unconstrained global optimization

The filled function method is considered as an efficient approach to solve the global optimization problems. In this paper, a new filled function method is proposed. Its main idea is as follows: a new continuously differentiable filled function with only one parameter is constructed for unconstrained global optimization when a minimizer of the objective function is found, then a minimizer of the filled function will be found in a lower basin of the objective function, thereafter, a better minimizer of the objective function will be found. The above process is repeated until the global optimal solution is found. The numerical experiments show the efficiency of the proposed filled function method.     

Global descent methods for unconstrained global optimization

We propose in this paper novel global descent methods for unconstrained global optimization problems to attain the global optimality by carrying out a series of local minimization. More specifically, the solution framework consists of a two-phase cycle of local minimization: the first phase implements local search of the original objective function, while the second phase assures a global descent of the original objective function in the steepest descent direction of a (quasi) global descent function. The key element of global descent methods is the construction of the (quasi) global descent functions which possess prominent features in guaranteeing a global descent.     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

An alternative globalization strategy for unconstrained optimization

We propose a new globalization strategy that can be used in unconstrained optimization algorithms to support rapid convergence from remote starting points. Our approach is based on using multiple points at each iteration to build a sequence of representative models of the objective function. Using the new information gathered from those multiple points, a local step is gradually improved by updating its direction as well as its length. We give a global convergence result and also provide the parallel implementation details accompanied with a numerical study. Our numerical study shows that the proposed algorithm is a promising alternative as a globalization strategy.     

Hybrid scatter tabu search for unconstrained global optimization

The problem of finding a global optimum of an unconstrained multimodal function has been the subject of intensive study in recent years, giving rise to valuable advances in solution methods. We examine this problem within the framework of adaptive memory programming (AMP), focusing particularly on AMP strategies that derive from an integration of Scatter Search and Tabu Search. Computational comparisons involving 16 leading methods for multimodal function optimization, performed on a testbed of 64 problems widely used to calibrate the performance of such methods, disclose that our new Scatter Tabu Search (STS) procedure is competitive with the state-of-the-art methods in terms of the average optimality gap achieved.     

A filter-line-search method for unconstrained optimization

A new filter-line-search algorithm for unconstrained nonlinear optimization problems is proposed. Based on the filter technique introduced by Fletcher and Leyffer (Math. Program. 91:239–269, 2002) it extends an existing technique of Wächter and Biegler (SIAM J. Comput. 16:1–31, 2005) for nonlinear equality constrained problem to the fully general unconstrained optimization problem. The proposed method, which differs from their approach, does not depend on any external restoration procedure. Global and local quadratic convergence is established under some reasonable conditions. The results of numerical experiments indicate that it is very competitive with the classical line search algorithm.     

A second-order method for unconstrained optimization

This paper presents a quadratically converging algorithm for unconstrained minimization. All the accumulation points that it constructs satisfy second-order necessary conditions of optimality. Thus, it avoids second-order saddle andinflection points, an essential feature for a method to be used in minimizing the modified Lagrangians in multiplier methods.The work of the first author was supported by NSF RANN AEN 73-07732-A02 and JSEP Contract No. F44620-71-C-0087; the work of the second author was supported by NSF Grant No. GK-37672 and the ARO Contract No. DAHCO4-730C-0025.     

A trajectory-following method for unconstrained optimization

A trajectory-following method with interesting properties is considered for solving unconstrained nonlinear programming problems. The trajectory is defined by a special system of ordinary differential equations. This system uses only the gradient of the objective function. Numerical examples are given.The work of the second author was supported by the DFG Schwerpunkt Anwendungs-bezogene Optimierung and Steuerung.     

A new integral filter algorithm for unconstrained global optimization

In this paper, making use a exponential integral filter, a new algorithm for unconstrained global optimization is proposed. Compared with Yang’s absolute value type integral filter method (Yang et al., Appl Math Comput 18:173–180, 2007), this algorithm is more effective and more sensitive. Numerical results for some typical examples show that in most cases, this algorithm works effectively and reliably.     

A parameter free filled function for unconstrained global optimization

The filled function method is considered as an efficient method to find the global minimum of multidimensional functions. A number of filled functions were proposed recently, most of which have one or two adjustable parameters. However, there is no efficient criterion to choose the parameter appropriately. In this paper, we propose a filled function without parameter. And this function includes neither exponential terms nor logarithmic terms so it is superior to the traditional ones. Theories of the filled function are investigated. And an algorithm which does not compute gradients during minimizing the filled function is presented. Moreover, the numerical experiments demonstrate the efficiency of the proposed filled function.     

The convergence rate of a three-term HS method with restart strategy for unconstrained optimization problems

Although the Hesteness and Stiefel (HS) method is a well-known method, if an inexact line search is used, researches about its convergence rate are very rare. Recently, Zhang, Zhou and Li [Some descent three-term conjugate gradient methods and their global convergence, Optim. Method Softw. 22 (2007), pp. 697–711] proposed a three-term Hestenes–Stiefel method for unconstrained optimization problems. In this article, we investigate the convergence rate of this method. We show that the three-term HS method with the Wolfe line search will be n-step superlinearly and even quadratically convergent if some restart technique is used under reasonable conditions. Some numerical results are also reported to verify the theoretical results. Moreover, it is more efficient than the previous ones.