Approximately global optimization for assortment problems using piecewise linearization techniques

Recently, Li and Chang proposed an approximate model for assortment problems. Although their model is quite promising to find approximately global solution, too many 0–1 variables are required in their solution process. This paper proposes another way for solving the same problem. The proposed method uses iteratively a technique of piecewise linearization of the quadratic objective function. Numerical examples demonstrate that the proposed method is computationally more efficient than the Li and Chang method.     

A new global optimization approach for convex multiplicative programming

In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm.     

Interval oriented multi-section techniques for global optimization

This paper deals with two different optimization techniques to solve the bound-constrained nonlinear optimization problems based on division criteria of a prescribed search region, finite interval arithmetic and interval ranking in the context of a decision maker’s point of view. In the proposed techniques, two different division criteria are introduced where the accepted region is divided into several distinct subregions and in each subregion, the objective function is computed in the form of an interval using interval arithmetic and the subregion containing the best objective value is found by interval ranking. The process is continued until the interval width for each variable in the accepted subregion is negligible. In this way, the global optimal or close to global optimal values of decision variables and the objective function can easily be obtained in the form of an interval with negligible widths. Both the techniques are applied on several benchmark functions and are compared with the existing analytical and heuristic methods.     

A global optimization using linear relaxation for generalized geometric programming

Many local optimal solution methods have been developed for solving generalized geometric programming (GGP). But up to now, less work has been devoted to solving global optimization of (GGP) problem due to the inherent difficulty. This paper considers the global minimum of (GGP) problems. By utilizing an exponential variable transformation and the inherent property of the exponential function and some other techniques the initial nonlinear and nonconvex (GGP) problem is reduced to a sequence of linear programming problems. The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (GGP) on a microcomputer.     

Deterministic and stochastic global optimization techniques for planar covering with ellipses problems

Problems of planar covering with ellipses are tackled in this work. Ellipses can have a fixed angle or each of them can be freely rotated. Deterministic global optimization methods are developed for both cases, while a stochastic version of the method is also proposed for large instances of the latter case. Numerical results show the effectiveness and efficiency of the proposed methods.     

Inclusion functions and global optimization II

This paper discusses algorithms of Moore, Skelboe, Ichida, Fujii and Hansen for solving the global unconstrained optimization problem. These algorithms have been tried on computers, but a thorough theoretical discussion of their convergence properties has been missing. The discussion was started in part I of this paper (Mathematical Programming 33 (1985) 300–317) where the convergence to the global minimum was studied. The present paper is concerned with the different behaviours of these algorithms when they are used for the determination of global minimum points. The solution sets of the algorithms can be a subset of the set of global minimum points,G, a superset ofG, or exactlyG. The algorithms are applicable to a very general class of functions: functions which are continuous, and have suitable inclusion functions. The number of global minimum points can be infinite.This work was supported by the Deutsche Forschungsgemeinschaft.     

A global optimization method for the molecular replacement problem in X-ray crystallography

The primary technique for determining the three-dimensional structure of a protein molecule is X-ray crystallography, from which the molecular replacement (MR) problem often arises as a critical step. The MR problem is a global optimization problem to locate an optimal position of a model protein so that at this position the model will produce calculated intensities closest to those observed from an X-ray crystallography experiment involving a protein with unknown but similar atomic structure. Improving the applicability and robustness of MR methods is an important research topic because commonly used traditional MR methods, though often successful, have their limitations in solving difficult problems.We introduce a new global optimization strategy that combines a coarse-grid search, using a surrogate function, with extensive multi-start local optimization. A new MR code, called SOMoRe, based on this strategy is developed and tested on four realistic problems, including two difficult problems that traditional MR codes failed to solve directly. SOMoRe was able to solve each test problem without any complication, and SOMoRe solved an MR problem using a less complete model than the models required by three other programs. These results indicate that the new method is promising and should enhance the applicability and robustness of the MR methodology.     

New filled functions for nonsmooth global optimization

The filled function method is an effective approach to find a global minimizer for a general class of nonsmooth programming problems with a closed bounded domain. This paper gives a new definition for the filled function, which overcomes some drawbacks of the previous definition. It proposes a two-parameter filled function and a one-parameter filled function to improve the efficiency of numerical computation. Based on these analyses, two corresponding filled function algorithms are presented. They are global optimization methods which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Numerical results obtained indicate the efficiency and reliability of the proposed filled function methods.     

Optimal and sub-optimal stopping rules for the Multistart algorithm in global optimization

In this paper the problem of stopping the Multistart algorithm for global optimization is considered. The algorithm consists of repeatedly performing local searches from randomly generated starting points. The crucial point in this algorithmic scheme is the development of a stopping criterion; the approach analyzed in this paper consists in stopping the sequential sampling as soon as a measure of the trade-off between the cost of further local searches is greater than the expected benefit, i.e. the possibility of discovering a better optimum.Stopping rules are thoroughly investigated both from a theoretical point of view and from a computational one via extensive simulation. This latter clearly shows that the simple1-step look ahead rule may achieve surprisingly good results in terms of computational cost vs. final accuracy.The research of the second author was partially supported by Progetto MPI 40% Metodi di Ottimizzazione per le Decisioni.     

Two algorithms for global optimization

In this paper, we develop and compare two methods for solving the problem of determining the global maximum of a function over a feasible set. The two methods begin with a random sample of points over the feasible set. Both methods then seek to combine these points into “regions of attraction” which represent subsets of the points which will yield the same local maximums when an optimization procedure is applied to points in the subset. The first method for constructing regions of attraction is based on approximating the function by a mixture of normal distributions over the feasible region and the second involves attempts to apply cluster analysis to form regions of attraction. The two methods are then compared on a set of well-known test problems.     

A magnetic resonance device designed via global optimization techniques

In this paper we are concerned with the design of a small low-cost, low-field multipolar magnet for Magnetic Resonance Imaging with a high field uniformity. By introducing appropriate variables, the considered design problem is converted into a global optimization one. This latter problem is solved by means of a new derivative free global optimization method which is a distributed multi-start type algorithm controlled by means of a simulated annealing criterion. In particular, the proposed method employs, as local search engine, a derivative free procedure. Under reasonable assumptions, we prove that this local algorithm is attracted by global minimum points. Additionally, we show that the simulated annealing strategy is able to produce a suitable starting point in a finite number of steps with probability one.This work was supported by CNR/MIUR Research Program Metodi e sistemi di supporto alle decisioni, Rome, Italy.Mathematics Subject Classification (1991):65K05, 62K05, 90C56     

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.     

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.      

Enhancing PSO methods for global optimization

The Particle Swarm Optimization (PSO) method is a well-established technique for global optimization. During the past years several variations of the original PSO have been proposed in the relevant literature. Because of the increasing necessity in global optimization methods in almost all fields of science there is a great demand for efficient and fast implementations of relative algorithms. In this work we propose three modifications of the original PSO method in order to increase the speed and its efficiency that can be applied independently in almost every PSO variant. These modifications are: (a) a new stopping rule, (b) a similarity check and (c) a conditional application of some local search method. The proposed were tested using three popular PSO variants and a variety test functions. We have found that the application of these modifications resulted in significant gain in speed and efficiency.     

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.     

Generalized descent for global optimization

This paper introduces a new method for the global unconstrained minimization of a differentiable objective function. The method is based on search trajectories, which are defined by a differential equation and exhibit certain similarities to the trajectories of steepest descent. The trajectories depend explicitly on the value of the objective function and aim at attaining a given target level, while rejecting all larger local minima. Convergence to the gloal minimum can be proven for a certain class of functions and appropriate setting of two parameters.The author wishes to thank Professor R. P. Brent for making helpful suggestions and acknowledges the financial support of an Australian National University Postgraduate Scholarship.     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

Parallel algorithms for global optimization

In this paper, we report results of implementations of algorithms designed (i) to solve the global optimization problem (GOP) and (ii) to run on a parallel network of transputers. There have always been two alternative approaches to the solution of the GOP, probabilistic and deterministic. Interval methods can be implemented on our network of transputers using Concurrent ADA, and a secondary objective of the tests reported was to investigate the relative computer times required by parallel interval algorithms compared to probabilistic methods.     

Generalized primal-relaxed dual approach for global optimization

A generalized primal-relaxed dual algorithm for global optimization is proposed and its convergence is proved. The (GOP) algorithm of Floudas and Visweswaran (Refs. 1–2) is shown to be a special case of this general algorithm. Within the proposed framework, the algorithm of Floudas and Visweswaran (Refs. 1–2) is further extended to the nonsmooth case. A penalty implementation of the extended (GOP) algorithm is studied to improve its efficiency.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.