A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.     

Inherited conics in Hall planes

The existence of ovals and hyperovals is an old question in the theory of non-Desarguesian planes. The aim of this paper is to describe when a conic of $\mathrm{PG}(2,q)$ remains an arc in the Hall plane obtained by derivation. Some combinatorial properties of the inherited conics are obtained also in those cases when it is not an arc. The key ingredient of the proof is an old lemma by Segre–Korchmáros on Desargues configurations with perspective triangles inscribed in a conic.     

Algebraic methods and arithmetic filtering for exact predicates on circle arcs

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques leading to fast implementation as shown by the experimental results.     

Note on arithmetic convolution equations

We investigate the solvability of polynomial equations on the -algebra of arithmetic functions .

     

Representation formula for discrete indefinite affine spheres

We present a representation formula for discrete indefinite affine spheres via loop group factorizations. This formula is derived from the Birkhoff decomposition of loop groups associated with discrete indefinite affine spheres. In particular we show that a discrete indefinite improper affine sphere can be constructed from two discrete plane curves.     

Intuitionistic weak arithmetic

We construct -framed Kripke models of i₁ and i₁ non of whose worlds satisfies xy(x=2yx=2y+1) and x,yzExp(x, y, z) respectively. This will enable us to show that i₁ does not prove ¬¬xy(x=2yx=2y+1) and i₁ does not prove ¬¬x, yzExp(x, y, z). Therefore, i₁¬¬lop and i₁¬¬i₁. We also prove that HAl₁ and present some remarks about i₂. Mathematics Subject Classification (2000):03F30, 03F55, 03H15.     

Minimal graded free resolutions for monomial curves in 𝔸4 defined by almost arithmetic sequences

Let m = (m₀, m₁, m₂, n) be an almost arithmetic sequence, i.e., a sequence of positive integers with gcd(m₀, m₁, m₂, n) = 1, such that m₀ < m₁ < m₂ form an arithmetic progression, n is arbitrary and they minimally generate the numerical semigroup Γ =m₀? +m₁? +m₂? +n?. Let k be a field. The homogeneous coordinate ring k[Γ] of the affine monomial curve parametrically defined by X₀ = t^m₀, X₁ = t^m₁, X₂ = t^m₂, Y = tⁿ is a graded R-module, where R is the polynomial ring k[X₀, X₁, X₂, Y] with the grading degX_i: = m_i, degY: = n. In this paper, we construct a minimal graded free resolution for k[Γ].     

Orthomorphisms and the construction of projective planes

We discuss a simple computational method for the construction of finite projective planes. The planes so constructed all possess a special group of automorphisms which we call the group of translations, but they are not always translation planes. Of the four planes of order 9, three admit the additive group of the field as a group of translations, and the present construction yields all three. The known planes of order 16 comprise four self-dual planes and eighteen other planes (nine dual pairs); of these, the method gives three of the four self-dual planes and six of the nine dual pairs, including the ``sporadic' (not translation) plane of Mathon.

     

Nichols algebras that are quantum planes

We compute all Nichols algebras of rigid braided vector spaces of dimension 2 that admit a non-trivial quadratic relation.     

Long arithmetic progressions in critical sets

Given a density 0<σ?1, we show for all sufficiently large primes p that if S⊆Z/pZ has the least number of three-term arithmetic progressions among all sets with at least σp elements, then S contains an arithmetic progression of length at least log^1/4+o(1)p.     

Separations of first and second order theories in bounded arithmetic

We prove that PTC_N(n) (the polynomial time closure of the nonstandard natural number n in the model N of S₂.) cannot be a model of U¹₂. This implies that there exists a first order sentence of bounded arithmetic which is provable in U¹₂ but does not hold in PTC_N(n).     

Equational fragments of systems for arithmetic

We investigate the equational fragments of formal systems for arithmetic by means of the equational theory of f-rings and of their positive cones, starting from the observation that a model of arithmetic is the positive cone of a discretely ordered ring. A consequence of the discreteness of the order is the presence of a discriminator, which allows us to derive many properties of the models of our equational theories. For example, the spectral topology of discrete f-rings is a Stone topology. We also characterize the equational fragment of Iopen, and we obtain an equational version of G?del's First Incompleteness Theorem. Finally, we prove that the lattice of subvarieties of the variety of discrete f-rings is uncountable, and that the lattice of filters of the countably generated distributive free lattice can be embedded into it. Received April 17, 1998; accepted in final form January 23, 2001.     

Hearing the weights of weighted projective planes

Which properties of an orbifold can we “hear,” i.e., which topological and geometric properties of an orbifold are determined by its Laplace spectrum? We consider this question for a class of four-dimensional Kähler orbifolds: weighted projective planes \(M := {\mathbb{C}}P^2(N_1, N_2, N_3)\) with three isolated singularities. We show that the spectra of the Laplacian acting on 0- and 1-forms on M determine the weights N ₁, N ₂, and N ₃. The proof involves analysis of the heat invariants using several techniques, including localization in equivariant cohomology. We show that we can replace knowledge of the spectrum on 1-forms by knowledge of the Euler characteristic and obtain the same result. Finally, after determining the values of N ₁, N ₂, and N ₃, we can hear whether M is endowed with an extremal Kähler metric.     

Class field theory for arithmetic schemes

Let X be a regular arithmetic scheme, i.e. a regular integral separated scheme flat and of finite type over Spec . Generalising classical class field theory for number fields, we define a class group C _X and show there is a natural surjective map whose kernel is the connected component of 0.      

Unitary polarities in non commutative twisted field planes

In this paper the class of polarities in non commutative twisted field planes, defined in a paper of Biliotti, Jha and Johnson ([4]), is investigated. It is proved that these polarities are unitary and that the associated unitals have a collineation group that fixes a point and is transitive on the remaining ones. Received 9 October 1999; revised 8 January 2000.     

On blocking sets of inversive planes

Let S be a blocking set in an inversive plane of order q. It was shown by Bruen and Rothschild 1 that |S| ≥ 2q for q ≥ 9. We prove that if q is sufficiently large, C is a fixed natural number and |S = 2q + C, then roughly 2/3 of the circles of the plane meet S in one point and 1/3 of the circles of the plane meet S in four points. The complete classification of minimal blocking sets in inversive planes of order q ≤ 5 and the sizes of some examples of minimal blocking sets in planes of order q ≤ 37 are given. Geometric properties of some of these blocking sets are also studied. © 2004 Wiley Periodicals, Inc.     

Constructing arithmetic subgroups of unipotent groups

Let G be a unipotent algebraic subgroup of some defined over . We describe an algorithm for finding a finite set of generators of the subgroup . This is based on a new proof of the result (in more general form due to Borel and Harish-Chandra) that such a finite generating set exists.