Proceedings
home
preface
contents
authors
keywords
copyright
reference ©2012 Civil-Comp Ltd

Paper 63

Searching for Multiple Minima of Bound Constrained Optimization Problems using Derivative Free Optimization Techniques

U.M. García Palomares
Departamento de Enxeñaría Telemática, Escola de Enxeñaría de Telecomunicación, Universidade de Vigo, Spain

Keywords: derivative free, bound constraint, multi processing, global minimum.

full paper (pdf) - reference

This paper is concerned with the search for multiple minima of bound constrained optimization problems. It is assumed that the optimization model cannot integrate all the important features which describe a system, and it is essential for the practitioner to asses the quality of several local minima.

The paper uses derivative free optimization techniques for solving a sequence of models in interior subdomains, also defined with bounded variables. Conceptually, this approach can be generalised to more general problems and subdomains can be defined for regions of different shapes. However, as a first step in this line of research problems with bounded variables are solved, because there are some efficient serial and parallel algorithms for their solution, and because it is easier to convey the main concepts of the approach described in this paper.

The scheme in unconstrained optimization is as follows: The algorithm works with a population and each individual is surrounded by a box, where an approximate solution, identified as a discrete quasi minimal point (DQMP), is located. These new exemplars replace the old ones and the procedure is repeated. To ensure convergence the accuracy of the solution improves as the algorithm proceeds.

In those cases where the solution of a small box occurs at its boundary the box is expanded and a new box surrounds the individual. If necessary, this process is repeated until an interior solution occurs, which is obviously a solution to the original model.

The algorithm can incorporate several techniques, among them: i) techniques usually recommended for global optimization: genetic algorithms and simulated annealing, ii) an estimate of a Lipschitz constant that allow the removal from the population of those individuals with large functional values, and iii) multi processing: each individual becomes the starting point of the algorithm that solves the BCOP inside inner boxes, and we can use the recent results on parallel methods for solving a BCOP [1].

Two small problems are solved to detect the influence of the many parameters that must be known to start the method. Fortunately, these preliminary results seem to indicate that our approach is not sensible to the choice of these parameters; however, more numerical results are needed before reaching conclusive statements.

To conclude: This paper proposes an algorithm that converges to multiple minima of strict differentiable functions with multiple minimizers, subjected to bounds on the variables. Multi processing can be easily incorporated using the latest techniques that have appeared recently in the literature.

References

1
U.M. García Palomares, I.J. García Urrea, P.S. Rodríguez Hernández, "On sequential and parallel non-monotone derivative free algorithms for box constrained optimization", Optimization Methods & Software, accepted, 2012.