Multidimensional Lipschitz global optimization based on efficient diagonal partitions

This is a summary of the author’s PhD thesis, supervised by Yaroslav D. Sergeyev and defended on May 5, 2006, at the University of Rome “La Sapienza”. The thesis is written in English and is available from the author upon request. In this work, the global optimization problem of a multidimensional “black-box” function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. The objective function is assumed hard to evaluate. A new efficient diagonal scheme for constructing fast algorithms for solving this problem is examined and illustrated by developing several powerful global optimization methods. A deep theoretical study is performed which highlights the benefit of the approach introduced over traditionally used diagonal algorithms. Theoretical conclusions are confirmed by results of extensive numerical experiments.      

Farey sequences

The connection between the distribution of the terms of a Farey sequence and the behavior of the Riemann zeta function is studied. Translated fromMatematicheskie Zametki, Vol. 61, No. 1, pp. 91–113, January, 1997. Translated by N. K. Kulman     

The parity of Farey denominators and the Farey index

A function E(b,s) is defined on the set implicitly, by a functional equation. Various conjectures arise from tables and some of these are proved. This function is then related to a partial sum of Farey indices weighted according to the parity of the Farey denominators. An explicit formula for E(b,s) is given, together with sharp bounds, and these show that the weighted partial sums of Farey indices are much smaller than expected. The explicit formula was determined from numerical trials: the question arises whether a constructive derivation from the functional equation should be possible in these and similar circumstances.     

Identities involving Farey fractions

The rational numbers a/q in [0, 1] can be counted by increasing height H(a/q) = max(a, q), or ordered as real numbers. Franel’s identity shows that the Riemann hypothesis is equivalent to a strong bound for a measure of the independence of these two orderings. We give a proof using Dedekind sums that allows weights w(q). Taking w(q) = χ(q) we find an extension to Dirichlet L-functions.     

Farey arcs and series

We find a finite subdivision of the interval [0, 1] into Farey's arcs in which the large as well as small arcs are explicitly presented. This subdivision is compared with Kloosterman's classical subdivision and the infinite subdivision by the group of modular transformations. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 226, 1996, pp. 52–59.     

Revisiting the Farey AF Algebra

In a recent paper, F. Boca investigates the AF algebra \mathfrakA{{\mathfrak{A}}} associated with the Farey-Stern-Brocot sequence. We show that \mathfrakA{{\mathfrak{A}}} coincides with the AF algebra \mathfrakM₁{{\mathfrak{M_{1}}}} introduced by the present author in 1988. As proved in that paper (Adv. Math., vol.68.1), the K ₀-group of \mathfrakA{\mathfrak{A}} is the lattice-ordered abelian group M₁{\mathcal{M}_{1}} of piecewise linear functions on the unit interval, each piece having integer coefficients, with the constant 1 as the distinguished order unit. Using the elementary properties of M₁{\mathcal{M}_{1}} we can give short proofs of several results in Boca’s paper. We also prove many new results: among others, \mathfrakA{{\mathfrak{A}}} is a *-subalgebra of Glimm universal algebra, tracial states of \mathfrakA{{\mathfrak{A}}} are in one-one correspondence with Borel probability measures on the unit real interval, all primitive ideals of \mathfrakA{{\mathfrak{A}}} are essential. We describe the automorphism group of \mathfrakA{{\mathfrak{A}}} . For every primitive ideal I of \mathfrakA{{{\mathfrak{A}}}} we compute K ₀(I) and K₀(\mathfrakA/I){{K_{0}(\mathfrak{A}/I)}}.     

The Correlations of Farey Fractions

It is proved that all correlations of the sequence of Fareyfractions exist and explicit formulas are provided for the correlationmeasures.     

Farey sequences and resistor networks

In this article, we employ the Farey sequence and Fibonacci numbers to establish strict upper and lower bounds for the order of the set of equivalent resistances for a circuit constructed from n equal resistors combined in series and in parallel. The method is applicable for networks involving bridge and non-planar circuits.     

A sieve result for Farey fractions

This paper is concerned with the sieve problem for Farey fractions (i.e., rational numbers with denominators less thanx) lying in an interval (λ₁, λ₂). An asymptotic formula for the sifting function is derived under the assumption that (λ₁, λ₂)x→∞ asx→∞. Two applications of this result are made. In the first one, the value distribution of the vector η(m/n)=(ξ(m), ξ(n)) is considered; here, fork=p ₁ p ₂...p _s ,p ₁≥p ₂>-..., ξk)_is defined by ξ(k)=(logp ₁/logk, logp ₂/logk,..., logp _s /logk, 0, ...); allp _i are prime numbers. It is shown that the limit distribution is π×π, where π is the Poisson-Dirichlet distribution. The asymptotical behavior of finite-dimensional distributions of ξ(k) for natural numbers was studied by Billingsley, Knuth, Trabb Pardo, Vershik, and others; the result of weak convergence to the Poisson-Dirichlet distribution appears in Donnelly and Grimmett. The second application is concerned with the density of sets {m/n: f(m/n)=a}, wheref is a function with the almost squareful kernel. Supported by the Lithuanian State Science and Studies Foundation. Vilnius University, Naugarduko 24, 2600, Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 1, pp. 108–127, January–March, 1999. Translated by V. Stakénas     

Farey nets and multidimensional continued fractions

A multidimensional continued fraction algorithm is a generalization of the ordinary continued fraction algorithm which approximates a vector η=(y ₁,...,y _n ) by a sequence of vectors \(\left( {\frac{{a_{j,1} }}{{a_{j,n + 1} }}, \ldots ,\frac{{a_{j,n} }}{{a_{j,n + 1} }}} \right)\) . If 1,y ₁,...,y _n are linearly independent over the rationals, then we say that the expansion of η isstrongly convergent if $$\mathop {\lim }\limits_{j \to \infty } \left| {\left( {\frac{{a_{j,1} }}{{a_{j,n + 1} }}, \ldots ,\frac{{a_{j,n} }}{{a_{j,n + 1} }}} \right) - \eta } \right| = 0.$$ This means that the algorithm converges at an asymptotically faster rate than would be guaranteed just by picking a denominator at random. The ordinary continued fraction algorithm can be defined using the Farey sequence, approximating a number by the endpoints of intervals which contain it. Analogously, we can define a Farey netF _{n, m} to be a triangulation of the set of all vectors \(\left( {\frac{{a_1 }}{{a_{n + 1} }}, \ldots ,\frac{{a_n }}{{a_{n + 1} }}} \right)\) witha _n+1 ≤m into simplices of determinant ±1, and use this algorithm to define a multidimensional continued fraction for η in which the approximations are the vertices of the simplices containing η in a sequence of Farey nets. The concept of a Farey net was proposed by A. Hurwitz, and R. Mönkemeyer developed a specific continued fraction algorithm based on it. We show that Mönkemeyer's algorithm discovers dependencies among the coordinates of η in two dimensions, but that no continued fraction algorithm based on Farey nets can discover dependencies in three or more dimensions, and none can be strongly convergent, even in two dimensions. Thus there are no good multidimensional algorithms based on Farey nets.     

Sequentially congruent partitions and partitions into squares

The Ramanujan Journal - In recent work, M. Schneider and the first author studied a curious class of integer partitions called “sequentiallyc congruent” partitions: the mth part is...     

Farey Series and the Riemann Hypothesis III

In this paper we shall make a further study on the the equivalence problem, i.e., equivalent conditions to the Riemann hypothesis in terms of Farey series by developing a rather analytical (-arithmetical) method to establish unexpected short interval results, namely results, therewith simultaneously clarifying the underlying reasons for results obtained in Part I.     

On Farey Fractions with Small Prime Factors

We investigate the Farey fractions, i.e., the set of irreducible fractions m /n, 0 < m < n x. We derive an asymptotic equality for the number of Farey fractions having no large prime factors.     

Optimal partitions

Consider a set of numbersZ={z ₁≥z ₂≥...≥z _n} and a functionf defined on subsets ofZ. LetP be a partition ofZ into disjoint subsetsS _i, say,g of them. The cost ofP is defined as $$C(P) = \sum\limits_{i = 1}^g {f(S_i )} .$$ By definition, in anordered partition, every pair of subsets has the property that the numbers in one subset are all greater than or equal to every number in the other subset. The problem of minimizingC(P) over all ordered partitions is called the optimal ordered partition problem. While no efficient method is known for solving the general optimal partition problem, the optimal ordered partition problem can be solved in quadratic time by dynamic programming. In this paper, we study the conditions onf under which an optimal ordered partition is indeed an optimal partition. In particular, we present an additive model and a multiplicative model for the functionf and give conditions such that the optimal partition problem can be reduced to the optimal ordered partition problem. We illustrate our results by applying them on problems which have been investigated previously in the literature.     

Gaussian partitions

Let V=V(n,q) denote the finite vector space of dimension n over the finite field with q elements. A subspace partition of V is a collection Π of subspaces of V such that each 1-dimensional subspace of V is in exactly one subspace of Π. In a recent paper, we proved some strong connections between the lattice of the subspace partitions of V and the lattice of the set partitions of n={1,…,n}. We now define a Gaussian partition of [n] _q =(q ⁿ −1)/(q−1) to be a nonincreasing sequence of positive integers formed by ordering all elements of some multiset {dim(W):W∈Π}, where Π is a subspace partition of V. The Gaussian partition function gp(n,q) is then the number of all Gaussian partitions of [n] _q , and is naturally analogous to the classical partition function p(n). In this paper, we initiate the study of gp(n,q) by exhibiting all Gaussian partitions for small n. In particular, we determine gp(n,q) as a polynomial in q for n≤5, and find a lower bound for gp(6,q).