An augmented filled function for global nonlinear integer optimization
- PDF / 2,288,998 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 106 Downloads / 199 Views
An augmented filled function for global nonlinear integer optimization Juan Di Mauro2 · Hugo D. Scolnik1,2 Received: 18 November 2019 / Accepted: 26 March 2020 © Sociedad de Estadística e Investigación Operativa 2020
Abstract The problem of finding global minima of nonlinear discrete functions arises in many fields of practical matters. In recent years, methods based on discrete filled functions have become popular as ways of solving these sort of problems. However, they rely on the steepest descent method for local searches. Here, we present an approach that does not depend on a particular local optimization method, and a new discrete filled function with the useful property that a good continuous global optimization algorithm applied to it leads to an approximation of the solution of the nonlinear discrete problem (Theorem 4). Numerical results are given showing the efficiency of the new approach. Keywords Discrete global optimization · Discrete filled function · Nonlinear optimization · Approximate algorithms. Mathematics Subject Classification 90-08
1 Introduction This paper is concerned with the analysis and performance of an algorithm designed to “try to” solve the model (1) efficiently.
min f (x) x∈X
(1)
f ∶ X → ℝ;X = {x ∈ ℤn ∶ ai ≤ x ≤ bi , i = 1, … , n}, * Hugo D. Scolnik [email protected] Juan Di Mauro [email protected] 1
Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
2
Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-Universidad de Buenos Aires, Buenos Aires, Argentina
13
Vol.:(0123456789)
J. Di Mauro, H. D. Scolnik
where ai , bi are, respectively, the lower and the upper bound of the variable xi , for i = 1, … , n . We warn the reader that in general, no algorithm ensures convergence to a global minimum. Nonetheless, we obtained global convergence on 77.5% of the preliminary numerical experiments reported in the Appendix, on small problems. It is well known that discrete models are NP. Solving model (1) in particular has shown to be a difficult task, even for polynomial functions with a few number of variables Manders and Adleman (1974). Moreover, the existence of multiple local minima may cause an optimization algorithm to stop at one of such minima, eventually giving minimizers of poor quality. Ways to overcome the last issue include metaheuristics methods such as tabu search or simulated annealing and also exact methods such as branch and bound, cutting planes or Lagrangian relaxation. In recent years, a technique that makes use of an auxiliary function to escape from local minima, known as the filled functions approach, has gained attention. Ge (1990), Ge and Qin (1990) originally introduced the filled function method for continuous optimization. Later, Zhu (1998) carried that technique into the field of discrete optimization. Several discrete filled functions have been proposed with one or more parameters and with additional features. However, in all cases, the discrete steepest desc
Data Loading...
