Global optimization with space-filling curves

It is shown that, contrary to a claim of Törn and Zilinskas, it is possible to efficiently optimize functions on n dimensions by projecting them into a single dimension using a space-filling curve.     

Dimensions of the coordinate functions of space-filling curves

The graphs of coordinate functions of space-filling curves such as those described by Peano, Hilbert, Pólya and others, are typical examples of self-affine sets, and their Hausdorff dimensions have been the subject of several articles in the mathematical literature. In the first half of this paper, we describe how the study of dimensions of self-affine sets was motivated, at least in part, by these coordinate functions and their natural generalizations, and review the relevant literature. In the second part, we present new results on the coordinate functions of Pólya's one-parameter family of space-filling curves. We give a lower bound for the Hausdorff dimension of their graphs which is fairly close to the box-counting dimension. Our techniques are largely probabilistic. The fact that the exact dimension remains elusive seems to indicate the need for further work in the area of self-affine sets.     

Locality and bounding-box quality of two-dimensional space-filling curves

Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the bounding-box quality of space-filling curves that express how effective different space-filling curves are for this purpose. We give general lower bounds on the bounding-box quality measures and on locality according to Gotsman and Lindenbaum for a large class of space-filling curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and the bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with relatively bad locality by Gotsman and Lindenbaum's measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves

Some powerful algorithms for multi-extremal non-convex-constrained optimization problems are based on reducing these multi-dimensional problems to those of one dimension by applying Peano-type space-filling curves mapping a unit interval on the real axis onto a multi-dimensional hypercube. Here is presented and substantiated a new scheme simultaneously employing several joint Peano-type scannings which conducts the property of nearness of points in many dimensions to a property of nearness of pre-images of these points in one dimension significantly better than in the case of a scheme with a single space-filling curve. Sufficient conditions of global convergence for the new scheme are investigated.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Pesenti-Szpiro inequality for optimal elliptic curves

We study Pesenti-Szpiro inequality in the case of elliptic curves over F_q(t) which occur as subvarieties of Jacobian varieties of Drinfeld modular curves. In general, we obtain an upper-bound on the degrees of minimal discriminants of such elliptic curves in terms of the degrees of their conductors and q. In the special case when the level is prime, we bound the degrees of discriminants only in terms of the degrees of conductors. As a preliminary step in the proof of this latter result we generalize a construction (due to Gekeler and Reversat) of 1-dimensional optimal quotients of Drinfeld Jacobians.     

Chaotic effects on disease spread in simple eco-epidemiological system

In this paper, an eco-epidemiological model where prey disease is structured as a susceptible-infected model is investigated. Thresholds that control disease spread and population persistence are obtained. Existence, stability and instability of the system are studied. Hopf bifurcation is shown to occur where a periodic solution bifurcates from the coexistence equilibrium. Simulations show that the system exhibits chaotic phenomena when the transmission rate is varied.     

On the spread of the spectrum of a graph

Some new upper bounds and lower bounds are obtained for the spread λ₁−λ_n of the eigenvalues λ₁≥λ₂≥?≥λ_n of the adjacency matrix of a simple graph.     

Rational torsion on optimal curves and rank-one quadratic twists

When an elliptic curve E^′/Q of square-free conductor N has a rational point of odd prime order l?N, Dummigan (2005) in [Du] explicitly constructed a rational point of order l on the optimal curve E, isogenous over Q to E^′, under some conditions. In this paper, we show that his construction also works unconditionally. And applying it to Heegner points of elliptic curves, we find a family of elliptic curves E^′/Q such that a positive proportion of quadratic twists of E^′ has (analytic) rank 1. This family includes the infinite family of elliptic curves of the same property in Byeon, Jeon, and Kim (2009) [B-J-K].     

Behavior of integral curves in the neighborhood of optimal integral manifolds

We describe an explicit construction of optimal integral manifolds [1] for a quasilinear system of differential equations that uses the method of successive approximations. We study the behavior of integral curves in the neighborhood of optimal integral manifolds. We cite a numerical method of synthesis of optimal control and prove its justification.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 8, pp. 1049–1060, August, 1992.     

Belt distance between facets of space-filling zonotopes

To every d-dimensional polytope P with centrally symmetric facets one can assign a “subway map” such that every line of this “subway” contains exactly the facets parallel to one of the ridges of P. The belt diameter of P is the maximum number of subway lines one needs to use to get from one facet to another. We prove that the belt diameter of a d-dimensional space-filling zonotope does not exceed ?log₂(4/5)d?.     

Type (II) regions between curves of the Fucik spectrum

The Fucik spectrum for a semilinear problem with asymptotic linearities has been shown to consist, at least locally, of curves emanating from a sequence of points in the plane. Regions between curves emanating from different points (referred to as type (I) regions in this paper) have a different nature than those between curves emanating from the same point (referred to as type (II) regions). Problems for which asymptotic limits fall in regions of type (I) have been solved by several authors, but not those for which the limits fall in a type (II) region. In the present paper we solve problems in which the asymptotic limits fall in type (II) regions. Received March 5, 1996