A global optimization method for the design of space trajectories

The problem of optimally designing a trajectory for a space mission is considered in this paper. Actual mission design is a complex, multi-disciplinary and multi-objective activity with relevant economic implications. In this paper we will consider some simplified models proposed by the European Space Agency as test problems for global optimization (GTOP database). We show that many trajectory optimization problems can be quite efficiently solved by means of relatively simple global optimization techniques relying on standard methods for local optimization. We show in this paper that our approach has been able to find trajectories which in many cases outperform those already known. We also conjecture that this problem displays a “funnel structure” similar, in some sense, to that of molecular optimization problems.     

Machine learning for global optimization

In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine (although different machine learning tools might be employed) to learn the relationship between the starting point of an algorithm and the final outcome (which is usually related to the function value at the point returned by the procedure). Numerical experiments performed both on classical test functions and on difficult space trajectory planning problems show that the proposed approach can be very effective in identifying good starting points for global optimization.     

Advances in Interval Methods for Deterministic Global Optimization in Chemical Engineering

In recent years, it has been shown that strategies based on an interval-Newton approach can be used to reliably solve a variety of nonlinear equation solving and optimization problems in chemical process engineering, including problems in parameter estimation and in the computation of phase behavior. These strategies provide a mathematical and computational guarantee either that all solutions have been located in an equation solving problem or that the global optimum has been found in an optimization problem. The primary drawback to this approach is the potentially high computational cost. In this paper, we consider strategies for bounding the solution set of the linear interval equation system that must be solved in the context of the interval-Newton method. Recent preconditioning techniques for this purpose are reviewed, and a new bounding approach based on the use of linear programming (LP) techniques is presented. Using this approach it is possible to determine the desired bounds exactly (within round out), leading to significant overall improvements in computational efficiency. These techniques will be demonstrated using several global optimization problems, with focus on problems arising in chemical engineering, including parameter estimation and molecular modeling. These problems range in size from under ten variables to over two hundred, and are solved deterministically using the interval methodology.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

A Global Optimization Approach to a Water Distribution Network Design Problem

In this paper, we address a global optimization approach to a waterdistribution network design problem. Traditionally, a variety of localoptimization schemes have been developed for such problems, each new methoddiscovering improved solutions for some standard test problems, with noknown lower bound to test the quality of the solutions obtained. A notableexception is a recent paper by Eiger et al. (1994) who present a firstglobal optimization approach for a loop and path-based formulation of thisproblem, using a semi-infinite linear program to derive lower bounds. Incontrast, we employ an arc-based formulation that is linear except forcertain complicating head-loss constraints and develop a first globaloptimization scheme for this model. Our lower bounds are derived through thedesign of a suitable Reformulation-Linearization Technique (RLT) thatconstructs a tight linear programming relaxation for the given problem, andthis is embedded within a branch-and-bound algorithm. Convergence to anoptimal solution is induced by coordinating this process with an appropriatepartitioning scheme. Some preliminary computational experience is providedon two versions of a particular standard test problem for the literature forwhich an even further improved solution is discovered, but one that isverified for the first time to be an optimum, without any assumed boundson the flows. Two other variants of this problem are also solved exactly forillustrative purposes and to provide researchers with additional test caseshaving known optimal solutions. Suggestions on a more elaborate study involving several algorithmic enhancements are presented for futureresearch.     

Dynamic location problems

A class of dynamic location problems is introduced. The relationship between a static problem and its corresponding dynamic one is studied. We concentrate on two types of dynamic problems. The first is the global optimization problem, in which one looks for the all-times optimum. The second is the steady-state problem in which one seeks to determine the steady-state behavior of the system if one exists. General approaches to these problems are discussed.Supported in part by the National Science Foundation under grants MCS-8300984, ECS-8218181 and ECS-8121741.     

Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1).     

Optimization of modular associative memory

Mathematical models are proposed for optimizing the structure of modular associative memory. Optimal hashing is considered. The optimization problem is solved using a genetic algorithm. Research supported by Ministry of Science grants 201.03.002 and 201.03.003. Translated from Chislennye Metody i Vychislitel'nyi Eksperiment, Moscow State University, pp. 97–106, 1998.     

Terminal repeller unconstrained subenergy tunneling (trust) for fast global optimization

A new method for unconstrained global function optimization, acronymedtrust, is introduced. This method formulates optimization as the solution of a deterministic dynamical system incorporating terminal repellers and a novel subenergy tunneling function. Benchmark tests comparing this method to other global optimization procedures are presented, and thetrust algorithm is shown to be substantially faster. Thetrust formulation leads to a simple stopping criterion. In addition, the structure of the equations enables an implementation of the algorithm in analog VLSI hardware, in the vein of artificial neural networks, for further substantial speed enhancement.This work was supported by the Department of Energy, Office of Basic Energy Sciences, Grant No. DE-A105-89-ER14086.     

A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms

Branch and Bound Algorithms based on Interval Arithmetic permit to solve exactly continuous (as well as mixed) non-linear and non-convex global optimization problems. However, their intrinsic exponential time-complexities do not make it possible to solve some quite large problems. The idea proposed in this paper is to limit the memory available during the computations of such a global optimization code in order to find some efficient feasible solutions. By this way, we introduce a metaheuristic frame to develop some new heuristic global optimization algorithms based on an exact code. We show in this paper, with a small assumption about the sorting by breadth first of elements in the data structure, that the time-complexity of such metaheuristic algorithms becomes polynomial instead of exponential for the exact code. In order to validate our metaheuristic approach, some numerical experiments about constrained global optimization problems coming from the COCONUT library were solved using a heuristic which certifies an enclosure of the global minimum value. The objective is not to solve completely the problem or find a better solution, but it is to know what is the highest precision which can be guaranteed reliably with the available memory.     

Global optimization by continuous grasp

We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus making it a well-suited approach for solving global optimization problems. We illustrate the effectiveness of the procedure on a set of standard test problems as well as two hard global optimization problems.     

A Population-based Approach for Hard Global Optimization Problems based on Dissimilarity Measures

When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be adopted like, e.g.:

Two related extremal problems for entire functions of several variables

We establish a relationship between the Logan problem for functions whose Fourier transform is supported in a centrally symmetric convex closed subset of ℝ ^m and whose mean value on ℝ ^m is nonnegative and the Chernykh problem on the optimal point for the Jackson inequality inL ₂(ℝ ^m ), which relates the best approximation of a function by the class of entire functions of exponential type to the first modulus of continuity. Both problems are solved exactly in several cases. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 336–350, September, 1999.     

Univariate Global Optimization with Multiextremal Non-Differentiable Constraints Without Penalty Functions

This paper proposes a new algorithm for solving constrained global optimization problems where both the objective function and constraints are one-dimensional non-differentiable multiextremal Lipschitz functions. Multiextremal constraints can lead to complex feasible regions being collections of isolated points and intervals having positive lengths. The case is considered where the order the constraints are evaluated is fixed by the nature of the problem and a constraint i is defined only over the set where the constraint i−1 is satisfied. The objective function is defined only over the set where all the constraints are satisfied. In contrast to traditional approaches, the new algorithm does not use any additional parameter or variable. All the constraints are not evaluated during every iteration of the algorithm providing a significant acceleration of the search. The new algorithm either finds lower and upper bounds for the global optimum or establishes that the problem is infeasible. Convergence properties and numerical experiments showing a nice performance of the new method in comparison with the penalty approach are given. This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 04-01-00455-a. The author thanks Prof. D. Grimaldi for proposing the application discussed in the paper. An erratum to this article is available at .     

An LQP Method for Pseudomonotone Variational Inequalities

In this paper, we proposed a modified Logarithmic-Quadratic Proximal (LQP) method [Auslender et al.: Comput. Optim. Appl. 12, 31–40 (1999)] for solving variational inequalities problems. We solved the problem approximately, with constructive accuracy criterion. We show that the method is globally convergence under that the operator is pseudomonotone which is weaker than the monotonicity and the solution set is nonempty. Some preliminary computational results are given.The author was supported by the NSFC grants Nos: 70571033 and 10571083.     

A Stochastic/Perturbation Global Optimization Algorithm for Distance Geometry Problems

We present a new global optimization approach for solving exactly or inexactly constrained distance geometry problems. Distance geometry problems are concerned with determining spatial structures from measurements of internal distances. They arise in the structural interpretation of nuclear magnetic resonance data and in the prediction of protein structure. These problems can be naturally formulated as global optimization problems which generally are large and difficult. The global optimization method that we present is related to our previous stochastic/perturbation global optimization methods for finding minimum energy configurations, but has several key differences that are important to its success. Our computational results show that the method readily solves a set of artificial problems introduced by Moré and Wu that have up to 343 atoms. On a set of considerably more difficult protein fragment problems introduced by Hendrickson, the method solves all the problems with up to 377 atoms exactly, and finds nearly exact solution for all the remaining problems which have up to 777 atoms. These preliminary results indicate that this approach has very good promise for helping to solve distance geometry problems.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

Parallel algorithms for continuous multifacility competitive location problems

We consider a continuous location problem in which a firm wants to set up two or more new facilities in a competitive environment. Both the locations and the qualities of the new facilities are to be found so as to maximize the profit obtained by the firm. This hard-to-solve global optimization problem has been addressed in Redondo et al. (Evol. Comput.17(1), 21–53, 2009) using several heuristic approaches. Through a comprehensive computational study, it was shown that the evolutionary algorithm uego is the heuristic which provides the best solutions. In this work, uego is parallelized in order to reduce the computational time of the sequential version, while preserving its capability at finding the optimal solutions. The parallelization follows a coarse-grain model, where each processing element executes the uego algorithm independently of the others during most of the time. Nevertheless, some genetic information can migrate from a processor to another occasionally, according to a migratory policy. Two migration processes, named Ring-Opt and Ring-Fusion2, have been adapted to cope the multiple facilities location problem, and a superlinear speedup has been obtained.     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.