A continuous approach to inductive inference

In this paper we describe an interior point mathematical programming approach to inductive inference. We list several versions of this problem and study in detail the formulation based on hidden Boolean logic. We consider the problem of identifying a hidden Boolean function:{0, 1} ⁿ {0, 1} using outputs obtained by applying a limited number of random inputs to the hidden function. Given this input—output sample, we give a method to synthesize a Boolean function that describes the sample. We pose the Boolean Function Synthesis Problem as a particular type of Satisfiability Problem. The Satisfiability Problem is translated into an integer programming feasibility problem, that is solved with an interior point algorithm for integer programming. A similar integer programming implementation has been used in a previous study to solve randomly generated instances of the Satisfiability Problem. In this paper we introduce a new variant of this algorithm, where the Riemannian metric used for defining the search region is dynamically modified. Computational results on 8-, 16- and 32-input, 1-output functions are presented. Our implementation successfully identified the majority of hidden functions in the experiment.     

On the Representation of Approximate Subdifferentials for a Class of Generalized Convex Functions

Given a family of real-valued functions defined in a normed vector space X, we study a class of -convex functions having a simpler representation for the --subdifferential. The case =X^* with X being a Banach space (the Fenchel case) is particularly analysed, and we find that the sublinear lower semicontinuous functions satisfy the simpler representation with respect to X^*. As a side result, we provide various new subdifferential-type charaterizations of positively homogeneous functions among those which are lower semicontinuous and convex. In addition, we also discuss that family related to the the so-called prox-bounded functions. In this more general framework our simpler representation may give rise to a new notion of enlargement of the subdifferential.Mathematics Subject Classifications (2000) 47H05, 46B99, 47H17.This work is based on research material supported in part by CONICYT-Chile through FONDECYT 101-0116 and FONDAP-Matemáticas Aplicadas II.     

On Generating Discrete Orthogonal Bivariate Polynomials

In this paper we present an algorithm for recursively generating orthogonal bivariate polynomials on a discrete set S ². For this purpose we employ commuting pairs of real symmetric matrices H, K ^n×n to obtain, in a certain sense, a two dimensional Hermitian Lanczos method. The resulting algorithm relies on a recurrence having a slowly growing length. Practical implementation issues an applications are considered. The method can be generalized to compute orthogonal polynomials depending on an arbitrary number of variables.     

Convolution kernels based on thin-plate splines

Quasi-interpolation using radial basis functions has become a popular method for constructing approximations to continuous functions in many space dimensions. In this paper we discuss a procedure for generating kernels for quasi-interpolation, using functions which have series expansions involving terms liker logr. It is shown that such functions are suitable if and only if is a positive even integer and the spatial dimension is also even.     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

The chaotic behaviour of search algorithms

Certain search algorithms produce a sequence of decreasing regions converging to a pointx ^*. After renormalizing to a standard region at each iteration, the renormalized location ofx ^*, sayx _x, may obey a dynamic process. In this case, simple ergodic theory might be used to compute asymptotic rates. The family of second-order line search algorithms which contains the Golden Section (GS) method have this property. The paper exhibits several alternatives to GS which have better almost sure ergodic rates of convergence for symmetric functions despite the fact that GS is asymptotically minimax. The discussion in the last section includes weakening of the symmetry conditions and announces a backtracking bifurcation algorithm with optimum asymptotic rate.     

How to be sure of finding a root of a complex polynomial using Newton's method

The trouble with Newton's method for finding the roots of a complex polynomial is knowing where to start the iteration. In this paper we apply the theory of rational maps and some estimates based on distortion theorems for univalent functions to find lower bounds, depending only on the degreed, for the size of regions from which the iteration will certainly converge to a root. We can also bound the number of iterations required and we give a method that works for every polynomial and takes at most some constant timesd ²(logd)² log(d ³/) iterations to find one root to within an accuracy of .     

Computing a global optimal solution to a design centering problem

In this paper we present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over ³ and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here we prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a pointx amounts to computing the distance, with respect to a Minkowski gauge, fromx to a finite number of planes. We propose a method for finding these planes and we report some numerical results.     

Parallel Computation of Invariant Measures

Let S:[0,1][0,1] be a nonsingular transformation and let P:L ¹(0,1)L ¹(0,1) be the corresponding Frobenius–Perron operator. In this paper we propose a parallel algorithm for computing a fixed density of P, using Ulam's method and a modified Monte Carlo approach. Numerical results are also presented.     

Limit theorems for non-linear functionals of Gaussian sequences

Summary We prove limit theorems for sums of non-linear functionals of Gaussian sequences. In certain cases we obtain a non-Gaussian limit with a norming factor n , 0<<1/2. The class of functionals we are investigating is a natural enlargement of the class investigated by M. Rosenblatt in [7]. We prove our results by refining the method of the paper [3].This research was done during the author's visit to Göttingen University. It was supported by the Deutsche Forschungsgemeinschaft     

The Fermat—Weber location problem revisited

The Fermat—Weber location problem requires finding a point in ^N that minimizes the sum of weighted Euclidean distances tom given points. A one-point iterative method was first introduced by Weiszfeld in 1937 to solve this problem. Since then several research articles have been published on the method and generalizations thereof. Global convergence of Weiszfeld's algorithm was proven in a seminal paper by Kuhn in 1973. However, since them given points are singular points of the iteration functions, convergence is conditional on none of the iterates coinciding with one of the given points. In addressing this problem, Kuhn concluded that whenever them given points are not collinear, Weiszfeld's algorithm will converge to the unique optimal solution except for a denumerable set of starting points. As late as 1989, Chandrasekaran and Tamir demonstrated with counter-examples that convergence may not occur for continuous sets of starting points when the given points are contained in an affine subspace of ^N . We resolve this open question by proving that Weiszfeld's algorithm converges to the unique optimal solution for all but a denumerable set of starting points if, and only if, the convex hull of the given points is of dimensionN.     

On the convergence of the projected gradient method

We study the projected gradient algorithm for linearly constrained optimization. Wolfe (Ref. 1) has produced a counterexample to show that this algorithm can jam. However, his counterexample is only ¹( ⁿ ), and it is conjectured that the algorithm is convergent for ²-functions. We show that this conjecture is partly right. We also show that one needs more assumptions to prove convergence, since we present a family of counterexamples. We finally give a demonstration that no jamming can occur for quadratic objective functions.This work was supported by the Natural Sciences and Engineering Research Council of Canada     

An interior point multiplicative method for optimization under positivity constraints

We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x _j ^k+1 =x _j ^k (1-_kf(x ^k)_j) with _k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86.     

Cauchy's equation on Δ+: Further results

Summary In a previous paper [Cauchy's equation on ⁺, Aequationes Math.41 (1991), 192–211], we began the study of Cauchy's equation on ⁺, the space of probability distribution functions of nonnegative random variables. In this paper we continue this study and extend our previous results to triangle functions of the form _{T, L} , whereT is a continuous Archimedean t-norm andL a binary operation onR ⁺, which is iseomorphic to a strict t-conorm. We again use a lattice theoretic approach, and introduce first a theorem on the powers and roots of certain elements of ⁺ under _T,L . Under certain additional restrictions we obtain a representation of sup-continuous solutions, similar to the one found in the first paper.     

On the classical logarithmic barrier function method for a class of smooth convex programming problems

In this paper, we describe a natural implementation of the classical logarithmic barrier function method for smooth convex programming. It is assumed that the objective and constraint functions fulfill the so-called relative Lipschitz condition, with Lipschitz constantM>0.In our method, we do line searches along the Newton direction with respect to the strictly convex logarithmic barrier function if we are far away from the central trajectory. If we are sufficiently close to this path, with respect to a certain metric, we reduce the barrier parameter. We prove that the number of iterations required by the algorithm to converge to an -optimal solution isO((1+M ²) log) orO((1+M ²)nlog), depending on the updating scheme for the lower bound.on leave from Eötvös University, Budapest, Hungary.     

On the Construction of Cosine Operator Functions and Semigroups on Function Spaces with Generator a(x)(d2dx2)+b(x)(d/dx)+c(x); Theory

In this paper we develop a method to solve exactly partial differential equations of the type ( ⁿ /t ⁿ )f(x,t)=(a(x)( ⁿ /x ⁿ )+b(x) (/x+c(x))f(x,t); n=1,2, with several boundary conditions, where f·,t) lies in a function space. The most powerful tool here is the theory of cosine operator functions and their connection to (holomorphic) semigroups. The method is that generally we are able to unify and generalize many theorems concerning problems in the theories of holomorphic semigroups, cosine operator functions, and approximation theory, especially these dealing with approximation by projections. These applications will be found in [14].     

An Algorithm for l∞ Regression with Quadratic Complexity

Using a few very basic observations, we proposed recently a direct and finite algorithm for the computation of the l regression line on a discrete set under the assumption that In this paper, we extend the algorithm to the case with at least one, possibly multiple y-values for each distinct x_i. Our algorithm finds all the regression lines in O(n ²) operations in the worst-case scenario and improves the existing best-known computational complexity result for this problem. Numerical results on random problems are included.     

Stable approximation of fractional derivatives of rough functions

The process of numerical fractional differentiation is well known to be an ill-posed problem, and it has been discussed by many authors, and a large number of different solution methods has been proposed. However, available approaches require a knowledge of a bound of the second or third derivatives of the function under consideration which are not always available. In this paper the following mollification method is suggested for this problem: if the data are given inexactly then we mollify them by elements of well-posedness classes of the problem, namely, by elements of an appropriater-regular multiresolution approximation {V _j } _j ofL ²(). WithinV _j the problem of fractional differentiation is well-posed, and we can find a mollification parameterJ depending on the noise level in the data, such that the error estimation is of Hölder type. The method can be numerically implemented by fundamental results by Beylkin, Coifman and Rokhlin ([2]) on representing differential operators in wavelet bases. It is worthwhile to note that there are very few papers concerning the question of stable numerical fractional differentiation of very rough functions. It is interesting that by our method, in a certain sense, we can approximate the derivatives of very rough functions (functions fromH _s (),s ) which have no derivative in the classical sense, like the hat functions, step functions..., in a stable way. Our method is of interest, since it is local. This means that to approximate the fractional derivative of a function at a point with improperly given data, we need only local information about this function in an appropriate neighbourhood of this point.On leave from Hanoi Institute of Mathematics, supported by the Deutsche Forschungs-gemeinschaft     

On the bigℳ in the affine scaling algorithm

When we apply the affine scaling algorithm to a linear program, we usually construct an artificial linear program having an interior feasible solution from which the algorithm starts. The artificial linear program involves a positive number called the big. Theoretically, there exists an ^* such that the original problem to be solved is equivalent to the artificial linear program if > ^*. Practically, however, such an ^* is unknown and a safe estimate of is often too large. This paper proposes a method of updating to a suitable value during the iteration of the affine scaling algorithm. As becomes large, the method gives information on infeasibility of the original problem or its dual.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Supported by Grant-in-Aids for Co-Operative Research (03832017) of the Japan Ministry of Education, Science and Culture.     

Removable singularities for analytic functions in BMO and locally Lipschitz spaces

In this paper we study removable singularities for holomorphic functions such that sup_z|f⁽ⁿ⁾(z)|dist(z,)^s<. Spaces of this type include spaces of holomorphic functions in Campanato classes, BMO and locally Lipschitz classes. Dolzhenko (1963), Král (1976) and Nguyen (1979) characterized removable singularities for some of these spaces. However, they used a different removability concept than in this paper. They assumed the functions to belong to the function space on and be holomorphic on \ E, whereas we only assume that the functions belong to the function space on \ E, and are holomorphic there. Koskela (1993) obtained some results for our type of removability, in particular he showed the usefulness of the Minkowski dimension. Kaufman (1982) obtained some results for s=0.In this paper we obtain a number of examples with certain important properties. Similar examples have earlier been obtained for Hardy H^p classes and weighted Bergman spaces, mainly by the author. Because of the similarities in these three cases, an axiomatic approach is used to obtain some results that hold in all three cases with the same proofs. Supported by the Swedish Research Council and Gustaf Sigurd Magnusons fund of the Royal Swedish Academy of Sciences.Mathematics Subject Classification (2000):30B40, 30D45, 30D55, 46E15.