Globally convergent algorithms for solving unconstrained optimization problems

New algorithms for solving unconstrained optimization problems are presented based on the idea of combining two types of descent directions: the direction of anti-gradient and either the Newton or quasi-Newton directions. The use of latter directions allows one to improve the convergence rate. Global and superlinear convergence properties of these algorithms are established. Numerical experiments using some unconstrained test problems are reported. Also, the proposed algorithms are compared with some existing similar methods using results of experiments. This comparison demonstrates the efficiency of the proposed combined methods.     

Chaotic harmony search algorithms

Harmony Search (HS) is one of the newest and the easiest to code music inspired heuristics for optimization problems. Like the use of chaos in adjusting note parameters such as pitch, dynamic, rhythm, duration, tempo, instrument selection, attack time, etc. in real music and in sound synthesis and timbre construction, this paper proposes new HS algorithms that use chaotic maps for parameter adaptation in order to improve the convergence characteristics and to prevent the HS to get stuck on local solutions. This has been done by using of chaotic number generators each time a random number is needed by the classical HS algorithm. Seven new chaotic HS algorithms have been proposed and different chaotic maps have been analyzed in the benchmark functions. It has been detected that coupling emergent results in different areas, like those of HS and complex dynamics, can improve the quality of results in some optimization problems. It has been also shown that, some of the proposed methods have somewhat increased the solution quality, that is in some cases they improved the global searching capability by escaping the local solutions.     

Two algorithms for solving systems of inclusion problems

The goal of this paper is to present two algorithms for solving systems of inclusion problems, with all components of the systems being a sum of two maximal monotone operators. The algorithms are variants of the forward-backward splitting method and one being a hybrid with the alternating projection method. They consist of approximating the solution sets involved in the problem by separating half-spaces which is a well-studied strategy. The schemes contain two parts, the first one is an explicit Armijo-type search in the spirit of the extragradient-like methods for variational inequalities. The second part is the projection step, this being the main difference between the algorithms. While the first algorithm computes the projection onto the intersection of the separating half-spaces, the second chooses one component of the system and projects onto the separating half-space of this case. In the iterative process, the forward-backward operator is computed once per inclusion problem, representing a relevant computational saving if compared with similar algorithms in the literature. The convergence analysis of the proposed methods is given assuming monotonicity of all operators, without Lipschitz continuity assumption. We also present some numerical experiments.     

On DC optimization algorithms for solving minmax flow problems

We formulate minmax flow problems as a DC optimization problem. We then apply a DC primal-dual algorithm to solve the resulting problem. The obtained computational results show that the proposed algorithm is efficient thanks to particular structures of the minmax flow problems.     

Parameter adaptive harmony search algorithm for unimodal and multimodal optimization problems

This paper presents a parameter adaptive harmony search algorithm (PAHS) for solving optimization problems. The two important parameters of harmony search algorithm namely Harmony Memory Consideration Rate (HMCR) and Pitch Adjusting Rate (PAR), which were either kept constant or the PAR value was dynamically changed while still keeping HMCR fixed, as observed from literature, are both being allowed to change dynamically in this proposed PAHS. This change in the parameters has been done to get the global optimal solution. Four different cases of linear and exponential changes have been explored. The change has been allowed during the process of improvization. The proposed algorithm is evaluated on 15 standard benchmark functions of various characteristics. Its performance is investigated and compared with three existing harmony search algorithms. Experimental results reveal that proposed algorithm outperforms the existing approaches when applied to 15 benchmark functions. The effects of scalability, noise, and harmony memory size have also been investigated on four approaches of HS. The proposed algorithm is also employed for data clustering. Five real life datasets selected from UCI machine learning repository are used. The results show that, for data clustering, the proposed algorithm achieved results better than other algorithms.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

Parallel evolutionary algorithms for optimization problems in aerospace engineering

This paper presents the recent developments in hierarchical genetic algorithms (HGAs) to speed up the optimization of aerodynamic shapes. It first introduces HGAs, a particular instance of parallel GAs based on the notion of interconnected sub-populations evolving independently. Previous studies have shown the advantages of introducing a multi-layered hierarchical topology in parallel GAs. Such a topology allows the use of multiple models for optimization problems, and shows that it is possible to mix fast low-fidelity models for exploration and expensive high-fidelity models for exploitation. Finally, a new class of multi-objective optimizers mixing HGAs and Nash Game Theory is defined. These methods are tested for solving design optimization problems in aerodynamics. A parallel version of this approach running a cluster of PCs demonstrate the convergence speed up on an inverse nozzle problem and a high-lift problem for a multiple element airfoil.     

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.     

Three new stochastic local search algorithms for continuous optimization problems

This paper introduces three new stochastic local search metaheuristics algorithms namely, the Best Performance Algorithm (BPA), the Iterative Best Performance Algorithm (IBPA) and the Largest Absolute Difference Algorithm (LADA). BPA and IBPA are based on the competitive nature of professional athletes, in them desiring to improve on their best recorded performances. LADA is modeled on calculating the absolute difference between two numbers. The performances of the algorithms have been tested on a large collection of benchmark unconstrained continuous optimization functions. They were benchmarked against two well-known local-search metaheuristics namely, Tabu Search (TS) and Simulated Annealing (SA). Results obtained show that each of the new algorithms delivers higher percentages of the best and mean function values found, compared to both TS and SA. The execution times of these new algorithms are also comparable. LADA gives the best performance in terms of execution time.     

Two algorithms for solving single-valued variational inequalities and fixed point problems

In this paper, we suggest two new iterative methods for finding a common element of the solution set of a variational inequality problem and the set of fixed points of a contraction mapping in Hilbert space. We also present weak and strong convergence theorems for these new methods, provided that the fixed point mapping is a θ-strict pseudocontraction and the mapping associated with the variational inequality problem is monotone. The results presented in this paper improve and unify important recent results announced by many authors.     

An improved three-term conjugate gradient algorithm for solving unconstrained optimization problems

In this article, we present an improved three-term conjugate gradient algorithm for large-scale unconstrained optimization. The search directions in the developed algorithm are proved to satisfy an approximate secant equation as well as the Dai-Liao’s conjugacy condition. With the standard Wolfe line search and the restart strategy, global convergence of the algorithm is established under mild conditions. By implementing the algorithm to solve 75 benchmark test problems with dimensions from 1000 to 10,000, the obtained numerical results indicate that the algorithm outperforms the state-of-the-art algorithms available in the literature. It costs less CPU time and smaller number of iterations in solving the large-scale unconstrained optimization.     

An improved penalty function method for solving constrained parameter optimization problems

An effective algorithm is described for solving the general constrained parameter optimization problem. The method is quasi-second-order and requires only function and gradient information. An exterior point penalty function method is used to transform the constrained problem into a sequence of unconstrained problems. The penalty weightr is chosen as a function of the pointx such that the sequence of optimization problems is computationally easy. A rank-one optimization algorithm is developed that takes advantage of the special properties of the augmented performance index. The optimization algorithm accounts for the usual difficulties associated with discontinuous second derivatives of the augmented index. Finite convergence is exhibited for a quadratic performance index with linear constraints; accelerated convergence is demonstrated for nonquadratic indices and nonlinear constraints. A computer program has been written to implement the algorithm and its performance is illustrated in fourteen test problems.     

Branch and win: OR tree search algorithms for solving combinatorial optimisation problems

Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose Branch and Win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.     

Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems

Mathematical Programming - Simple bilevel problems are optimization problems in which we want to find an optimal solution to an inner problem that minimizes an outer objective function. Such...     

Dynamic guiding particle swarm optimization with embedded chaotic search for solving multidimensional problems

The proposed approach incorporated dynamic guiding approach and chaotic search procedure into particle swarm optimization (PSO), named DCPSO. Chaotic search, enjoyed ergodicity, irregularity and pseudo-randomness in PSO, would refine global best position evidently. And, dynamic guiding approach with fluctuating property would easily conduct unpredictable migrations for PSO to break away from evolutionary stagnation. The experiment reports indicated that the proposed DCPSO approach could improve the evolution performance significantly, and present the superiority in solving complex multidimensional problems.     

Theoretical justification of interior point algorithms for solving optimization problems with nonlinear constraints

A family of interior point algorithms is considered. These algorithms can be used for solving mathematical programming problems with nonlinear inequality constraints. Some weighted Euclidean norms are applied to finding a descent direction for improving the solution. These norms vary with iterations. A theoretical justification of the algorithms with some assumptions (including the nonsingularity of the problem) is presented.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.     

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.