Generating Sum-of-Ratios Test Problems in Global Optimization

A method is presented for the construction of test problems involving the minimization over convex sets of sums of ratios of affine functions. Given a nonempty, compact convex set, the method determines a function that is the sum of linear fractional functions and attains a global minimum over the set at a point that can be found by convex programming and univariate search. Generally, the function will have also local minima over the set that are not global minima.     

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.     

An Algorithm of Global Optimization for Rational Functions with Rational Constraints

To solve a system of nonlinear equations, Wu wen-tsun introduced a new formative elimination method. Based on Wu's method and the theory of nonlinear programming, we here propose a global optimization algorithm for nonlinear programming with rational objective function and rational constraints. The algorithm is already programmed and the test results are satisfactory with respect to precision and reliability.     

A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems

There is a need for a methodology to fairly compare and present evaluation study results of stochastic global optimization algorithms. This need raises two important questions of (i) an appropriate set of benchmark test problems that the algorithms may be tested upon and (ii) a methodology to compactly and completely present the results. To address the first question, we compiled a collection of test problems, some are better known than others. Although the compilation is not exhaustive, it provides an easily accessible collection of standard test problems for continuous global optimization. Five different stochastic global optimization algorithms have been tested on these problems and a performance profile plot based on the improvement of objective function values is constructed to investigate the macroscopic behavior of the algorithms. The paper also investigates the microscopic behavior of the algorithms through quartile sequential plots, and contrasts the information gained from these two kinds of plots. The effect of the length of run is explored by using three maximum numbers of function evaluations and it is shown to significantly impact the behavior of the algorithms.     

Rational Functions with Prescribed Global and Local Minimizers

A family of multivariate rational functions is constructed. It has strong local minimizers with prescribed function values at prescribed positions. While there might be additional local minima, such minima cannot be global. A second family of multivariate rational functions is given, having prescribed global minimizers and prescribed interpolating data.     

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.     

New Classes of Globally Convexized Filled Functions for Global Optimization

We propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the proposed functions can be extended to the case of box constrained minimization problems. We also report the results of a preliminary numerical experience.     

A Global Optimization Algorithm for Multivariate Functions with Lipschitzian First Derivatives

In this paper we propose a new multi-dimensional methodto solve unconstrained global optimization problems with Lipschitzianfirst derivatives. The method is based on apartition scheme that subdivides the search domain into a set of hypercubesin the course of optimization. This partitioning is regulated by thedecision rule that provides evaluation of the "importance"of each generated hypercube and selection of some partition element to performthe next iteration. Sufficient conditions of global convergence for the newmethod are investigated. Results of numerical experiments are alsopresented.     

Application of Stochastic Global Optimization Algorithms to Practical Problems

We describe global optimization problems from three different fields representing many-body potentials in physical chemistry, optimal control of a chemical reactor, and fitting a statistical model to empirical data. Historical background for each of the problems as well as the practical significance of the first two are given. The problems are solved by using eight recently developed stochastic global optimization algorithms representing controlled random search (4 algorithms), simulated annealing (2 algorithms), and clustering (2 algorithms). The results are discussed, and the importance of global optimization in each respective field is focused.     

Second-Order Global Optimality Conditions for Optimization Problems

Second-order optimality conditions are studied for the constrained optimization problem where the objective function and the constraints are compositions of convex functions and twice strictly differentiable functions. A second-order sufficient condition of a global minimizer is obtained by introducing a generalized representation condition. Second-order minimizer characterizations for a convex program and a linear fractional program are derived using the generalized representation condition     

A Rigorous Global Optimization Algorithm for Problems with Ordinary Differential Equations

The optimization of systems which are described by ordinary differential equations (ODEs) is often complicated by the presence of nonconvexities. A deterministic spatial branch and bound global optimization algorithm is presented in this paper for systems with ODEs in the constraints. Upper bounds for the global optimum are produced using the sequential approach for the solution of the dynamic optimization problem. The required convex relaxation of the algebraic functions is carried out using well-known global optimization techniques. A convex relaxation of the time dependent information is obtained using the concept of differential inequalities in order to construct bounds on the space of solutions of parameter dependent ODEs as well as on their second-order sensitivities. This information is then incorporated in the convex lower bounding NLP problem. The global optimization algorithm is illustrated by applying it to four case studies. These include parameter estimation problems and simple optimal control problems. The application of different underestimation schemes and branching strategies is discussed.     

A Multivariate Global Optimization Using Linear Bounding Functions

Recently linear bounding functions (LBFs) were proposed and used to find -global minima. This paper presents an LBF-based algorithm for multivariate global optimization problems. The algorithm consists of three phases. In the global phase, big subregions not containing a solution are quickly eliminated and those which possibly contain the solution are detected. An efficient scheme for the local phase is developed using our previous local minimization algorithm, which is globally convergent with superlinear/quadratic rate and does not require evaluation of gradients and Hessian matrices. To ensure that the found minimizers are indeed the global solutions or save computation effort, a third phase called the verification phase is often needed. Under adequate conditions the algorithm finds the -global solution(s) within finite steps. Numerical testing results illustrate how the algorithm works, and demonstrate its potential and feasibility.     

On the Convergence of the P-Algorithm for One-Dimensional Global Optimization of Smooth Functions

The Wiener process is a widely used statistical model for stochastic global optimization. One of the first optimization algorithms based on a statistical model, the so-called P-algorithm, was based on the Wiener process. Despite many advantages, this process does not give a realistic model for many optimization problems, particularly from the point of view of local behavior. In the present paper, a version of the P-algorithm is constructed based on a stochastic process with smooth sampling functions. It is shown that, in such a case, the algorithm has a better convergence rate than in the case of the Wiener process. A similar convergence rate is proved for a combination of the Wiener model-based P-algorithm with quadratic fit-based local search.     

Trace-Based Methods for Solving Nonlinear Global Optimization and Satisfiability Problems

In this paper we present a method called NOVEL (Nonlinear Optimization via External Lead) forsolving continuous and discrete global optimization problems. NOVEL addresses the balance between global search and local search, using a trace to aid in identifying promising regions before committing to local searches. We discuss NOVEL for solving continuous constrained optimization problems and show how it can be extended to solve constrained satisfaction and discrete satisfiability problems. We first transform the problem using Lagrange multipliers into an unconstrained version. Since a stable solution in a Lagrangian formulation only guarantees a local optimum satisfying the constraints, we propose a global search phase in which an aperiodic and bounded trace function is added to the search to first identify promising regions for local search. The trace generates an information-bearing trajectory from which good starting points are identified for further local searches. Taking only a small portion of the total search time, this elegant approach significantly reduces unnecessary local searches in regions leading to the same local optimum. We demonstrate the effectiveness of NOVEL on a collection of continuous optimization benchmark problems, finding the same or better solutions while satisfying the constraints. We extend NOVEL to discrete constraint satisfaction problems (CPSs) by showing an efficient transformation method for CSPs and the associated representation in finite-difference equations in NOVEL. We apply NOVEL to solve Boolean satisfiability instances in circuit fault detection and circuit synthesis applications, and show comparable performance when compared to the best existing method.     

Global Optimization of Marginal Functions with Applications to Economic Equilibrium

We discuss the applicability of the cutting angle method to global minimization of marginal functions. The search of equilibrium prices in the exchange model can be reduced to the global minimization of certain functions, which include marginal functions. This problem has been approximately solved by the cutting angle method. Results of numerical experiments are presented and discussed.     

弹性力学问题的最小二乘混合有限元法

该文给出弹性力学问题的混合有限元法及其整体估计．该方法不受经典的B．一B．条件约束．因此,其有限元空间可以自由地选择,并得到最优的误差估计．     

Global Optimization Techniques for Mixed Complementarity Problems

We investigate the theoretical and numerical properties of two global optimization techniques for the solution of mixed complementarity problems. More precisely, using a standard semismooth Newton-type method as a basic solver for complementarity problems, we describe how the performance of this method can be improved by incorporating two well-known global optimization algorithms, namely a tunneling and a filled function method. These methods are tested and compared with each other on a couple of very difficult test examples.     

Deterministic Global Optimization in Nonlinear Optimal Control Problems

The accurate solution of optimal control problems is crucial in many areas of engineering and applied science. For systems which are described by a nonlinear set of differential-algebraic equations, these problems have been shown to often contain multiple local minima. Methods exist which attempt to determine the global solution of these formulations. These algorithms are stochastic in nature and can still get trapped in local minima. There is currently no deterministic method which can solve, to global optimality, the nonlinear optimal control problem. In this paper a deterministic global optimization approach based on a branch and bound framework is introduced to address the nonlinear optimal control problem to global optimality. Only mild conditions on the differentiability of the dynamic system are required. The implementa-tion of the approach is discussed and computational studies are presented for four control problems which exhibit multiple local minima.     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.