线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

Improved Strategies for Radial basis Function Methods for Global Optimization

We propose some strategies that can be shown to improve the performance of the radial basis function (RBF) method by Gutmann [J. Global optim. 19(3), 201–227 (2001a)] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [J. Global optim. 31, 153–171 (2005)] (CORS–RBF) on some test problems when they are initialized by symmetric Latin hypercube designs (SLHDs). Both methods are designed for the global optimization of computationally expensive functions with multiple local optima. We demonstrate how the original implementation of Gutmann-RBF can sometimes converge slowly to the global minimum on some test problems because of its failure to do local search. We then propose Controlled Gutmann-RBF (CG-RBF), which is a modification of Gutmann-RBF where the function evaluation point in each iteration is restricted to a subregion of the domain centered around a global minimizer of the current RBF model. By varying the size of this subregion in different iterations, we ensure a better balance between local and global search. Moreover, we propose a complete restart strategy for CG-RBF and CORS-RBF whenever the algorithm fails to make any substantial progress after some threshold number of consecutive iterations. Computational experiments on the seven Dixon and Szegö [Towards Global optimization, pp. 1–13. North-Holland, Amsterdam (1978)] test problems and on nine Schoen [J. Global optim. 3, 133–137 (1993)] test problems indicate that the proposed strategies yield significantly better performance on some problems. The results also indicate that, for some fixed setting of the restart parameters, the two modified RBF algorithms, namely CG-RBF-Restart and CORS-RBF-Restart, are comparable on the test problems considered. Finally, we examine the sensitivity of CG-RBF-Restart and CORS-RBF-Restart to the restart parameters.     

Complexity Results for Some Global Optimization Problems

We discuss the complexity of a class of highly structured global optimization problems, namely the maximization of separable functions, with each one-dimensional component convex and nondecreasing, over polytopes defined by a 0-1 constraint matrix with at most two variables involved in each constraint. In particular, we prove some inapproximability and approximability results.     

Global Method for Monotone Variational Inequality Problems with Inequality Constraints

We consider optimization methods for monotone variational inequality problems with nonlinear inequality constraints. First, we study the mixed complementarity problem based on the original problem. Then, a merit function for the mixed complementarity problem is proposed, and some desirable properties of the merit function are obtained. Through the merit function, the original variational inequality problem is reformulated as simple bounded minimization. Under certain assumptions, we show that any stationary point of the optimization problem is a solution of the problem considered. Finally, we propose a descent method for the variational inequality problem and prove its global convergence.     

A Globally Derivative-Free Descent Method for Nonlinear Complementarity Problems

Based on a class of functions, which generalize the squared Fischer-Burmeister NCP function and have many desirable properties as the latter function has, we reformulate nonlinear complementarity problem (NCP for short) as an equivalent unconstrained optimization problem, for which we propose a derivative-free descent method in monotone case. We show its global convergence under some mild conditions. If $F$, the function involved in NCP, is $R_0$-function, the optimization problems has bounded level sets. A local property of the merit function is discussed. Finally,we report some numerical results.     

Selective Search for Global Optimization of Zero or Small Residual Least-Squares Problems: A Numerical Study

In this paper, we consider approximating global minima of zero or small residual, nonlinear least-squares problems. We propose a selective search approach based on the concept of selective minimization recently introduced in Zhang et al. (Technical Report TR99-12, Rice University, Department of Computational and Applied Mathematics MS-134, Houston, TX 77005, 1999). To test the viability of the proposed approach, we construct a simple implementation using a Levenberg-Marquardt type method combined with a multi-start scheme, and compare it with several existing global optimization techniques. Numerical experiments were performed on zero residual nonlinear least-squares problems chosen from structural biology applications and from the literature. On the problems of significant sizes, the performance of the new approach compared favorably with other tested methods, indicating that the new approach is promising for the intended class of problems.     

A path following method for box-constrained multiobjective optimization with applications to goal programming problems

We propose a path following method to find the Pareto optimal solutions of a box-constrained multiobjective optimization problem. Under the assumption that the objective functions are Lipschitz continuously differentiable we prove some necessary conditions for Pareto optimal points and we give a necessary condition for the existence of a feasible point that minimizes all given objective functions at once. We develop a method that looks for the Pareto optimal points as limit points of the trajectories solutions of suitable initial value problems for a system of ordinary differential equations. These trajectories belong to the feasible region and their computation is well suited for a parallel implementation. Moreover the method does not use any scalarization of the multiobjective optimization problem and does not require any ordering information for the components of the vector objective function. We show a numerical experience on some test problems and we apply the method to solve a goal programming problem.     

New Reflection Generator for Simulated Annealing in Mixed-Integer/Continuous Global Optimization

To reduce the well-known jamming problem in global optimization algorithms, we propose a new generator for the simulated annealing algorithm based on the idea of reflection. Furthermore, we give conditions under which the sequence of points generated by this simulated annealing algorithm converges in probability to the global optimum for mixed-integer/continuous global optimization problems. Finally, we present numerical results on some artificial test problems as well as on a composite structural design problem.     

An experimental methodology for response surface optimization methods

Response surface methods, and global optimization techniques in general, are typically evaluated using a small number of standard synthetic test problems, in the hope that these are a good surrogate for real-world problems. We introduce a new, more rigorous methodology for evaluating global optimization techniques that is based on generating thousands of test functions and then evaluating algorithm performance on each one. The test functions are generated by sampling from a Gaussian process, which allows us to create a set of test functions that are interesting and diverse. They will have different numbers of modes, different maxima, etc., and yet they will be similar to each other in overall structure and level of difficulty. This approach allows for a much richer empirical evaluation of methods that is capable of revealing insights that would not be gained using a small set of test functions. To facilitate the development of large empirical studies for evaluating response surface methods, we introduce a dimension-independent measure of average test problem difficulty, and we introduce acquisition criteria that are invariant to vertical shifting and scaling of the objective function. We also use our experimental methodology to conduct a large empirical study of response surface methods. We investigate the influence of three properties—parameter estimation, exploration level, and gradient information—on the performance of response surface methods.     

Simplicial Lipschitz optimization without the Lipschitz constant

In this paper we propose a new simplicial partition-based deterministic algorithm for global optimization of Lipschitz-continuous functions without requiring any knowledge of the Lipschitz constant. Our algorithm is motivated by the well-known Direct algorithm which evaluates the objective function on a set of points that tries to cover the most promising subregions of the feasible region. Almost all previous modifications of Direct algorithm use hyper-rectangular partitions. However, other types of partitions may be more suitable for some optimization problems. Simplicial partitions may be preferable when the initial feasible region is either already a simplex or may be covered by one or a manageable number of simplices. Therefore in this paper we propose and investigate simplicial versions of the partition-based algorithm. In the case of simplicial partitions, definition of potentially optimal subregion cannot be the same as in the rectangular version. In this paper we propose and investigate two definitions of potentially optimal simplices: one involves function values at the vertices of the simplex and another uses function value at the centroid of the simplex. We use experimental investigation to compare performance of the algorithms with different definitions of potentially optimal partitions. The experimental investigation shows, that proposed simplicial algorithm gives very competitive results to Direct algorithm using standard test problems and performs particularly well when the search space and the numbers of local and global optimizers may be reduced by taking into account symmetries of the objective function.     

A General Nonconvex Multiduality Principle

We introduce a (possibly infinite) collection of mutually dual nonconvex optimization problems, which share a common optimal value, and give a characterization of their global optimal solutions. As immediate consequences of our general multiduality principle, we obtain Toland–Singer duality theorem as well as an analogous result involving generalized perspective functions. Based on our duality theory, we propose an extension of an existing algorithm for the minimization of d.c. functions, which exploits Toland–Singer duality, to a more general class of nonconvex optimization problems.     

On augmented Lagrangians for Optimization Problems with a Single Constraint

We examine augmented Lagrangians for optimization problems with a single (either inequality or equality) constraint. We establish some links between augmented Lagrangians and Lagrange-type functions and propose a new kind of Lagrange-type functions for a problem with a single inequality constraint. Finally, we discuss a supergradient algorithm for calculating optimal values of dual problems corresponding to some class of augmented Lagrangians.     

A Class of penalty functions for optimization problema with bound constraints

In this paper we propose a new class of continuously differentiable globally exact penalty functions for the solution of minimization problems with simple bounds on some (all) of the variables. The penalty functions in this class fully exploit the structure of the problem and are easily computable. Furthermore we introduce a simple updating rule for the penalty parameter that can be used in conjunction with unconstrained minimization techniques to solve the original problem.     

Stochastic Global Optimization: Problem Classes and Solution Techniques

There is a lack of a representative set of test problems for comparing global optimization methods. To remedy this a classification of essentially unconstrained global optimization problems into unimodal, easy, moderately difficult, and difficult problems is proposed. The problem features giving this classification are the chance to miss the region of attraction of the global minimum, embeddedness of the global minimum, and the number of minimizers. The classification of some often used test problems are given and it is recognized that most of them are easy and some even unimodal. Global optimization solution techniques treated are global, local, and adaptive search and their use for tackling different classes of problems is discussed. The problem of fair comparison of methods is then adressed. Further possible components of a general global optimization tool based on the problem classes and solution techniques is presented.     

On global quadratic growth condition for min-max optimization problems with quadratic functions

Second-order sufficient condition and quadratic growth condition play important roles both in sensitivity and stability analysis and in numerical analysis for optimization problems. In this article, we concentrate on the global quadratic growth condition and study its relations with global second-order sufficient conditions for min-max optimization problems with quadratic functions. In general, the global second-order sufficient condition implies the global quadratic growth condition. In the case of two quadratic functions involved, we have the equivalence of the two conditions.     

无记忆非拟 Newton 算法的导出和全局收敛性

In this paper, a new class of memoryless non-quasi-Newton method for solving unconstrained optimization problems is proposed, and the global convergence of this method with inexact line search is proved. Furthermore, we propose a hybrid method that mixes both the memoryless non-quasi-Newton method and the memoryless Perry-Shanno quasi-Newton method. The global convergence of this hybrid memoryless method is proved under mild assumptions. The initial results show that these new methods are efficient for the given test problems. Especially the memoryless non-quasi-Newton method requires little storage and computation, so it is able to efficiently solve large scale optimization problems.     

Sufficient global optimality conditions for weakly convex minimization problems

In this paper, we present sufficient global optimality conditions for weakly convex minimization problems using abstract convex analysis theory. By introducing (L,X)-subdifferentials of weakly convex functions using a class of quadratic functions, we first obtain some sufficient conditions for global optimization problems with weakly convex objective functions and weakly convex inequality and equality constraints. Some sufficient optimality conditions for problems with additional box constraints and bivalent constraints are then derived.      

Dual estimates in multiextremal problems

We propose a technique of improving the dual estimates in nonconvex multiextremal problems of mathematical programming, by adding some additional constraints which are the consequences of the original constraints. This technique is used for the problems of finding the global minimum of polynomial functions, and extremal quadratic and boolean quadratic problems. In the article one ecological multiextremal problem and an algorithm for finding the dual estimate for it also considered. This algorithm is based upon a scheme of decomposition and nonsmooth optimization methods.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

AN IMPLEMENTABLE ALGORITHM AND ITS CONVERGENCE FOR GLOBAL MINIMIZATION WITH CONSTRAINS

With the integral-level approach to global optimization, a class of discontinuous penalty functions is proposed to solve constrained minimization problems. In this paper we propose an implementable algorithm by means of the good point set of uniform distribution which conquers the default of Monte-Carlo method. At last we prove the convergence of the implementable algorithm.     

Test Functions with Variable Attraction Regions for Global Optimization Problems

Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima.