Power Series Kernels

We introduce a class of analytic positive definite multivariate kernels which includes infinite dot product kernels as sometimes used in machine learning, certain new nonlinearly factorizable kernels, and a kernel which is closely related to the Gaussian. Each such kernel reproduces in a certain “native” Hilbert space of multivariate analytic functions. If functions from this space are interpolated in scattered locations by translates of the kernel, we prove spectral convergence rates of the interpolants and all derivatives. By truncation of the power series of the kernel-based interpolants, we constructively generalize the classical Bernstein theorem concerning polynomial approximation of analytic functions to the multivariate case. An application to machine learning algorithms is presented.      

Multistep approximation algorithms: Improved convergence rates through postconditioning with smoothing kernels

We show how certain widely used multistep approximation algorithms can be interpreted as instances of an approximate Newton method. It was shown in an earlier paper by the second author that the convergence rates of approximate Newton methods (in the context of the numerical solution of PDEs) suffer from a “loss of derivatives”, and that the subsequent linear rate of convergence can be improved to be superlinear using an adaptation of Nash–Moser iteration for numerical analysis purposes; the essence of the adaptation being a splitting of the inversion and the smoothing into two separate steps. We show how these ideas apply to scattered data approximation as well as the numerical solution of partial differential equations. We investigate the use of several radial kernels for the smoothing operation. In our numerical examples we use radial basis functions also in the inversion step. This revised version was published online in June 2006 with corrections to the Cover Date.     

A multi-local optimization algorithm

The development of efficient algorithms that provide all the local minima of a function is crucial to solve certain subproblems in many optimization methods. A “multi-local” optimization procedure using inexact line searches is presented, and numerical experiments are also reported. An application of the method to a semi-infinite programming procedure is included. This work was partially supported by Ministerio de Educación y Ciencia, Spain, DGICYT grant PB93-0703. Author (*) was supported by the Consellería d'Educació i Ciència of the Generalitat Valenciana.     

Numerical integration of ordinary differential equations on manifolds

Summary This paper is concerned with the problem of developing numerical integration algorithms for differential equations that, when viewed as equations in some Euclidean space, naturally evolve on some embedded submanifold. It is desired to construct algorithms whose iterates also evolve on the same manifold. These algorithms can therefore be viewed as integrating ordinary differential equations on manifolds. The basic method “decouples” the computation of flows on the submanifold from the numerical integration process. It is shown that two classes of single-step and multistep algorithms can be posed and analyzed theoretically, using the concept of “freezing” the coefficients of differential operators obtained from the defining vector field. Explicit third-order algorithms are derived, with additional equations augmenting those of their classical counterparts, obtained from “obstructions” defined by nonvanishing Lie brackets.     

Kernel Decompositions for Schur Functions on the Polydisk

A certain kernel (sometimes called the Pick kernel) associated to Schur functions on the disk is always positive semi-definite. A generalization of this fact is well-known for Schur functions on the polydisk. In this article, we show that the “Pick kernel” on the polydisk has a great deal of structure beyond being positive semi-definite. It can always be split into two kernels possessing certain shift invariance properties.     

Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.     

Sharp estimates for\bar \partial on convex domains of finite typeon convex domains of finite type

Let Ω be a bounded convex domain in C _n , with smooth boundary of finite typem. The equation is solved in Ω with sharp estimates: iff has bounded coefficients, the coefficients of our solutionu are in the Lipschitz space Λ. Optimal estimates are also given when data have coefficients belonging toL ^p(Ω),p≥1. We solve the -equation by means of integral operators whose kernels are not based on the choice of a “good” support function. Weighted kernels are used; in order to reflect the geometry ofbΩ, we introduce a weight expressed in terms of the Bergman kernel of Ω.     

Classification of Irreducible Weight Modules with a Finite-dimensional Weight Space over Twisted Heisenberg-Virasoro Algebra

We show that the support of an irreducible weight module over the twisted Heisenberg-Virasoro algebra, which has an infinite-dimensional weight space, coincides with the weight lattice and that all nontrivial weight spaces of such a module are infinite dimensional. As a corollary, we obtain that every irreducible weight module over the twisted Heisenber-Virasoro algebra, having a nontrivial finite-dimensional weight space, is a Harish-Chandra module （and hence is either an irreducible highest or lowest weight module or an irreducible module from the intermediate series）.     

Computable classes of constructivizations of 2-constructivizable models

It is known that a class of constructivizations of a nonautostable 2-constructivizable model is infinite. Whether that class is effectively infinite or at least noncomputable is still not known, though there are grounds to believe that it is effectively infinite. Here, we argue for the effective infinity of a class of constructivizations of a nonautostable 2-constructivizable model which is not 1-prime in any finite enrichment by constants. Supported by RFFR grant No. 99-01-00485, by the Federal Research Program (FRP) “Integration,” and by the Program “Universities of Russia. Fundamental Research”. Translated fromAlgebra i Logika, Vol. 38, No. 6, pp. 697–722, November–December, 1999.     

Some new closures on orders

For each of the relations “less than or equal to”, “less than”, “covered by”, and “covered by or equal to”, we characterize finite orders (also called posets) with the property that the pair of Galois closure operators induced by the relation in question coincides with the pair of closure operators introduced and applied in our previous paper in 2007. We also consider the “less than or equal to” relation between the set of join-irreducible elements and the set of meet-irreducible elements, and we show that the above-mentioned pairs of closure operators coincide for finite modular lattices.     

First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

Logical analysis of numerical data

“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization” consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others. The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083).     

A Note on the Strong Approximation of the Smoothed Empirical Process of α-mixing Sequences

A strong approximation of the smoothed empirical process of strictly stationary α-mixing random variables by a sequence of iid Gaussian processes will be studied. Here, the smoothing is done via kernel density estimators. No assumptions are made on the support of the kernel; in fact, our main results are stated for kernels with possibly an infinite support. Received June 2003; Accepted February 2004.     

Queues with boundary assistance: the effects of truncation

We study a system of two queues with boundary assistance, represented as a continuous-time Quasi-Birth-and-Death process (QBD). Under our formulation, this QBD has a ‘doubly infinite’ number of phases. We determine the convergence norm of Neuts’ R-matrix and, consequently, the interval in which the decay rate of the infinite system can lie.     

Strong non-Noetherity of polynomial reduction

It is a well-known result by A. Reeves and B. Sturmfels that the reduction modulo a marked set of polynomials is Noetherian if and only if the marking is induced from an admissible term ordering. For finite sets of polynomials with a nonadmissible ordering, there is a constructive proof of the existence of an infinite reduction sequence, although a finite one might still be possible. On the base of our specialized software for combinatorics of monomial orderings, we have found some examples for which there is no finite reduction sequence. This is what we call “strong” non-Noetherity. Bibliography: 3 titles.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

Parametric Duality Models for Semi-infinite Discrete Minmax Fractional Programming Problems Involving Generalized （η,ρ）-Invex Functions

A semi-infinite programming problem is a mathematical programming problem with a finite number of variables and infinitely many constraints. Duality theories and generalized convexity concepts are important research topics in mathematical programming. In this paper, we discuss a fairly large number of paramet- ric duality results under various generalized （η,ρ）-invexity assumptions for a semi-infinite minmax fractional programming problem.     

Logical analysis of data: classification with justification

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of such algorithms is frequently carried out ex post, on an experimental basis: their performance is measured either by cross validation on benchmark data sets, or by clinical trials. Few of these approaches evaluate the learning process ex ante, on its own merits. In this paper, we discuss a property of rule-based classifiers which we call “justifiability”, and which focuses on the type of information extracted from the given training set in order to classify new observations. We investigate some interesting mathematical properties of justifiable classifiers. In particular, we establish the existence of justifiable classifiers, and we show that several well-known learning approaches, such as decision trees or nearest neighbor based methods, automatically provide justifiable classifiers. We also identify maximal subsets of observations which must be classified in the same way by every justifiable classifiers. Finally, we illustrate by a numerical example that using classifiers based on “most justifiable” rules does not seem to lead to overfitting, even though it involves an element of optimization.