25,861 research outputs found
A two-phase approach in a global optimization algorithm using multiple estimates of Hölder constants
No full textIn this paper, the global minimization problem of a multi-dimensional black-box Lipschitzian function is considered. In order to pass from the original Lipschitz multi-dimensional problem to a univariate one, an approach using space-filling curves to reduce the dimension is applied. The method does not use derivatives and, at each iteration, works with a set of estimates of the Hölder constant of the reduced one-dimensional problem. A two-phase technique is applied to accelerate the search of the global minimum. Numerical experiments carried out on several hundreds of test functions show a promising performance of the discussed algorithm in comparison with its direct competitors
Grossone Methodology for Lexicographic Mixed-Integer Linear Programming Problems
No full textIn this work we have addressed lexicographic multi-objective linear programming problems where some of the variables are constrained to be integer. We have called this class of problems LMILP, which stands for Lexicographic Mixed Integer Linear Programming. Following one of the approach used to solve mixed integer linear programming problems, the branch and bound technique, we have extended it to work with infinitesimal/infinite numbers, exploiting the Grossone Methodology. The new algorithm, called GrossBB, is able to solve this new class of problems, by using internally the GrossSimplex algorithm (a recently introduced Grossone extension of the well-known simplex algorithm, to solve lexicographic LP problems without integer constraints). Finally we have illustrated the working principles of the GrossBB on a test problem
Space-filling curves for numerical approximation and visualization of solutions to systems of nonlinear inequalities with applications in robotics
No full textThe problem of approximating and visualizing the solution set of systems of nonlinear inequalities can be frequently met in practice, in particular, when it is required to find the working space of some robots. In this paper, a method using Peano-Hilbert space-filling curves for the dimensionality reduction has been proposed for functions satisfying the Lipschitz condition. Theoretical properties of the introduced algorithm showing advantages of this reduction in the context of the present problem have been established and convergence properties of this method have been studied. A number of experiments executed on test functions and problems regarding finding workspace of robots confirm theoretical results and show a promising character of the new methodology
Lipschitz and Hölder global optimization using space-filling curves
No full textIn this paper, the global optimization problem min F(y) y∈S, with S=[a,b], a, b ∈ R^N, and F(y) satisfying the Lipschitz condition, is considered. To deal with it four algorithms are proposed. All of them use numerical approximations of space filling curves to reduce the
original Lipschitz multi-dimensional problem to a univariate one satisfying the Hölder condition. The Lipschitz constant is adaptively estimated by the introduced methods during the search. Local tuning on the behavior of the objective function and a newly proposed technique, named local improvement, are used in order to accelerate the search. Convergence conditions are given. A theoretical relation between the order of a Hilbert
space-filling curve approximation used to reduce the problem dimension and the accuracy of the resulting solution is established, as well. Numerical experiments carried out on several hundreds of test functions show a quite promising performance of the new algorithms
Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives
No full textThis paper deals with two kinds of the one-dimensional global optimization problem over a closed finite interval: (i) the objective function f(x) satisfies the Lipschitz condition with a constant L; (ii) the first derivative of f(x) satisfies the Lipschitz condition with a constant M. In the paper, six algorithms are presented for the case (i) and six algorithms for the case (ii). In both cases, auxiliary functions are constructed and adaptively improved during the search. In the case (i), piecewise linear functions are constructed and in the case (ii) smooth piecewise quadratic functions are used. The constants L and M either are taken as values known a priori or are dynamically estimated during the search. A recent technique that adaptively estimates the local Lipschitz constants over different zones of the search region is used to accelerate the search. A new technique called the local improvement is introduced in order to accelerate the search in both cases (i) and (ii). The algorithms are described in a unique framework, their properties are studied from a general viewpoint, and convergence conditions of the proposed algorithms are given. Numerical experiments executed on 120 test problems taken from the literature show quite a promising performance of the new acceleration techniques
Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants
No full textIn this paper, the global optimization problem miny∈SF(y) with S being a hyperinterval in RN and F(y) satisfying the Lipschitz condition with an unknown Lipschitz constant is considered. It is supposed that the function F(y) can be multiextremal, non-differentiable, and given as a 'black-box'. To attack the problem, a new global optimization algorithm based on the following two ideas is proposed and studied both theoretically and numerically. First, the new algorithm uses numerical approximations to space-filling curves to reduce the original Lipschitz multi-dimensional problem to a univariate one satisfying the Hölder condition. Second, the algorithm at each iteration applies a new geometric technique working with a number of possible Hölder constants chosen from a set of values varying from zero to infinity showing so that ideas introduced in a popular DIRECT method can be used in the Hölder global optimization. Convergence conditions of the resulting deterministic global optimization method are established. Numerical experiments carried out on several hundreds of test functions show quite a promising performance of the new algorithm in comparison with its direct competitors
Algorithm 829: Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization
No full textSolving the Lexicographic Multi-Objective Mixed-Integer Linear Programming Problem Using Branch-and-Bound and Grossone Methodology
No full textIn the previous work (see [1]) the authors have shown how to solve a Lexicographic Multi-Objective Linear Programming (LMOLP) problem using the Grossone methodology described in [2]. That algorithm, called GrossSimplex, was a generalization of the well-known simplex algorithm, able to deal numerically with infinitesimal/infinite quantities. The aim of this work is to provide an algorithm able to solve a similar problem, with the addition of the constraint that some of the decision variables have to be integer. We have called this problem LMOMILP (Lexicographic Multi-Objective Mixed-Integer Linear Programming). This new problem is solved by introducing the GrossBB algorithm, which is a generalization of the Branch-and-Bound (BB) algorithm. The new method is able to deal with lower-bound and upper-bound estimates which involve infinite and infinitesimal numbers (namely, Grossone-based numbers). After providing theoretical conditions for its correctness, it is shown how the new method can be coupled with the GrossSimplex algorithm described in [1], to solve the original LMOMILP problem. To illustrate how the proposed algorithm finds the optimal solution, a series of LMOMILP benchmarks having a known solution is introduced. In particular, it is shown that the GrossBB combined with the GrossSimplex is able solve the proposed LMOMILP test problems with up to 200 objectives
To the special issue dedicated to the 3rd international conference “Numerical Computations: Theory and Algorithms—NUMTA 2019” June 15–21, 2019, Isola Capo Rizzuto, Italy
No full textForewords to special issue dedicated to “Numerical Computations: Theory and Algorithms—NUMTA 2019” June 15–21, 2019, Isola Capo Rizzuto, Ital
- …
