Search

Formalization decisions in mathematical programming could significantly influence the complexity of the problem, and so the efficiency of the applied solver methods. This widely accepted statement induced investigations for the reformulation of optimization problems in the hope of getting easier to solve problem forms, e.g. in integer programming. These transformations usually go hand in hand with relaxation of some constraints and with the increase in the number of the variables. However, the quick evolution and the widespread use of computer algebra systems in the last few years motivated us to use symbolic computation techniques also in the field of global optimization. We are interested in potential simplifications generated by symbolic transformations in global optimization, and especially in automatic mechanisms producing equivalent expressions that possibly decrease the dimension of the problem. As it was pointed out by Csendes and Rapcsák (J Glob Optim 3(2):213-221, ), it is possible in some cases to simplify the unconstrained nonlinear objective function by nonlinear coordinate transformations. That means mostly symbolic replacement of redundant subexpressions expecting less computation, while the simplified task remains equivalent to the original in the sense that a conversion between the solutions of the two forms is possible. We present a proper implementation of the referred theoretical algorithm in a modern symbolic programming environment, and testing on some examples both from the original publications and from the set of standard global optimization test problems to illustrate the capabilities of the method. [ABSTRACT FROM AUTHOR]

GLOBAL is a multi-start type stochastic method for bound constrained global optimization problems. Its goal is to find the best local minima that are potentially global. For this reason it involves a combination of sampling, clustering, and local search. The role of clustering is to reduce the number of local searches by forming groups of points around the local minimizers from a uniformly sampled domain and to start few local searches in each of those groups. We evaluate the performance of the GLOBAL algorithm on the BBOB 2009 noiseless testbed, containing problems which reflect the typical difficulties arising in real-world applications. The obtained results are also compared with those obtained form the simple multi-start procedure in order to analyze the effects of the applied clustering rule. An improved parameterization is introduced in the GLOBAL method and the performance of the new procedure is compared with the performance of the MATLAB GlobalSearch solver by using the BBOB 2010 test environment [ABSTRACT FROM AUTHOR]

We describe a new implementation of an interval optimization algorithm with focus on the software related issues. The algorithm implemented in MATLAB that uses the INTLAB package supporting interval calculations and automatic differentiation solves the bound constrained global optimization problem. The method itself is a simplified version of those interval techniques much investigated in the past, that was first developed from the global optimization algorithm of the Numerical Toolbox for Verified Computing. According to the numerical studies completed, the new INTLAB-based implementation is closely as efficient as its C-XSC-based basis algorithm - with the exception of the CPU time needed (the longer computations are due to the interpreter nature of MATLAB). [ABSTRACT FROM AUTHOR]

We report on experiences with an adaptive subdivision method supported by interval arithmetic that enables us to prove subset relations of the form $\mathcal{T}(W) \subset U$, and thus check certain sufficient conditions for chaotic behavior of dynamical systems in a rigorous way. Our proof of the underlying abstract theorem avoids referring to any results of applied algebraic topology and relies only on the Brouwer fixed point theorem. The second novelty is that the process of gaining the subset relations to be checked is, to a large extent, also automatized. The promising subset relations come from solving a constrained optimization problem via the penalty function approach. Abstract results and computational methods are demonstrated by finding embedded copies of the standard horseshoe dynamics in iterates of the classical Hénon mapping. [ABSTRACT FROM AUTHOR]

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

Presents a theoretical justification for the empirical heuristic sub-box selection criterion for interval global optimization. Invariant indicator functions; Optimality criterion.

A posteriori direction selection rules are studied for interval global optimization methods to allow the user to choose the one best fitting for the problems at hand. Earlier interval subdivision direction selection rules involved easy to use a priori selection rules with more ore less argumentation why they can be appropriate. Although extensive computational investigations were made on the five most often used selection rules, the underlying reasons why these can improve the efficiency of the optimization algorithms remained unknown. The present paper aims to contribute to the understanding of the functioning of these interval subdivision direction selection rules. [ABSTRACT FROM AUTHOR]