‘Fat’ triangulations,or solving certain nonconvex matrix optimization problems

In an earlier paper, the author proposed the problems of determining ‘optimal’ linear transformations of the triangulationsJ ₁ andK ₁, in the sense of minimizing their average directional density for a given mesh size. These tasks were also formulated as optimization problems where the variable is a matrix. Here we solve these problems, and another one which is analogously related to finding an ‘optimal’ linear transformation of the new triangulationJ′. We show thatJ ₁ andJ′ are themselves optimal, while the (α*β*) ofK ₁ developed by van der Laan and Talman is optimal. The latter theorem extends partial results of van der Laan and Talman and Eaves. The optimality of these linear transformations is quite robust: we may change the objective function to maximizing the volume of each simplex, or the constraints to limiting the sum of squares of edge lengths of each simplex, or both, without changing the optimal solutions. Research partially supported by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ENG82-15361     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

An ‘Emergent Model’ for Rate of Change

Does speed provide a ‘model for’ rate of change in other contexts? Does JavaMathWorlds (JMW), animated simulation software, assist in the development of the ‘model for’ rate of change? This project investigates the transference of understandings of rate gained in a motion context to a non-motion context. Students were 27 14–15 year old students at an Australian secondary school. The instructional sequence, utilising JMW, provided rich learning experiences of rate of change in the context of a moving elevator. This context connects to students’ prior knowledge. The data taken from pre- and post-tests and student interviews revealed a wide variation in students’ understanding of rate of change. The variation was mapped on a hypothetical learning trajectory and interpreted in the terms of the ‘emergent models’ theory (Gravemeijer, Math Think Learn 1(2):155–177, 1999) and illustrated by specific examples from the data. The results demonstrate that most students were able to use the ‘model of’ rate of change developed in a vertical motion context as a ‘model for’ rate of change in a horizontal motion context. A smaller majority of students were able to use their, often incomplete, ‘model of’ rate of change as a ‘model for’ reasoning about rate of change in a non-motion context.     

On Estimating a Dynamic Function of a Stochastic System with Averaging

We consider a two-scaled diffusion system, when drift and diffusion parameters of the ‘slow’ component are contaminated by the ‘fast’ unobserved component. The goal is to estimate the dynamic function which is defined by averaging the drift coefficient of the ‘slow’ component w.r.t. the stationary distribution of the ‘fast’ one. We apply a locally linear smoother with a data-driven bandwidth choice. The procedure is fully adaptive and nearly optimal up to a log log factor. This revised version was published online in June 2006 with corrections to the Cover Date.     

On a class of second order variational problems with constraints

We study the structure of optimal solutions for a class of constrained, second order variational problems on bounded intervals. We show that, for intervals of length greater than some positive constant, the optimal solutions are bounded inC ¹ by a bound independent of the length of the interval. Furthermore, for sufficiently large intervals, the ‘mass’ and ‘energy’ of optimal solutions are almost uniformly distributed.     

Interactions between government and firms: a differential game approach

In this paper we study an extended version of the model described in Gradus (J. Econ. 81:1092–1109, 1989) in order to determine the optimal taxation policy of a government and its effects on the stock of capital goods growth as a result of the activity developed by firms. It is shown that, by introducing a wealth tax, there exists an optimal wealth tax rate for which the open-loop/feedback Nash/Stackelberg equilibria coincide, maximizing the payments for both agents (government and firms), so that the open-loop Stackelberg equilibrium becomes both time consistent and subgame perfect. Partially supported by MEC (Spain) Grants MTM2006-13468, BMF2002-03493 and project ‘Ingenio Mathematica (i-MATH)’ No. CSD2006-00032 (Consolider-Ingenio 2010).     

Extending the Ehresmann-Schein-Nambooripad Theorem

We extend the ‘∨-premorphisms’ part of the Ehresmann-Schein-Nambooripad Theorem to the case of two-sided restriction semigroups and inductive categories, following on from a result of Lawson (J. Algebra 141:422–462, 1991) for the ‘morphisms’ part. However, it is so-called ‘∧-premorphisms’ which have proved useful in recent years in the study of partial actions. We therefore obtain an Ehresmann-Schein-Nambooripad-type theorem for (ordered) ∧-premorphisms in the case of two-sided restriction semigroups and inductive categories. As a corollary, we obtain such a theorem in the inverse case.     

A duality theorem for semi-infinite convex programs and their finite subprograms

In this paper, we first establish a general recession condition under which a semi-infinite convex program and its formal lagrangian dual have the same value. We go on to show that, under this condition, the following hold. First, every finite subprogram, with ‘enough’ of the given constraints, has the same value as its Lagrangian dual. Second, the weak value of the primal program is equal to the optimal value of the primal. The first draft of this work, entitled ‘Asymptotic Convex Programming’ was completed while the author was a member of the Department of Mathematical Sciences at the University of Delaware, Newark, DE 19711.     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

An inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

Bootstrap bandwidth selection in kernel density estimation from a contaminated sample

In this paper we consider kernel estimation of a density when the data are contaminated by random noise. More specifically we deal with the problem of how to choose the bandwidth parameter in practice. A theoretical optimal bandwidth is defined as the minimizer of the mean integrated squared error. We propose a bootstrap procedure to estimate this optimal bandwidth, and show its consistency. These results remain valid for the case of no measurement error, and hence also summarize part of the theory of bootstrap bandwidth selection in ordinary kernel density estimation. The finite sample performance of the proposed bootstrap selection procedure is demonstrated with a simulation study. An application to a real data example illustrates the use of the method. This research was supported by ‘Projet d’Actions de Recherche Concertées’ (No. 98/03-217) from the Belgian government. Financial support from the IAP research network nr P5/24 of the Belgian State (Federal Office for Scientific, Technical and Cultural Affairs) is also gratefully acknowledged.     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

A Canonical Compatible Metric for Geometric Structures on Nilmanifolds

Let (N, γ) be a nilpotent Lie group endowed with an invariant geometric structure (cf. symplectic, complex, hypercomplex or any of their ‘almost’ versions). We define a left invariant Riemannian metric on N compatible with γ to be minimal, if it minimizes the norm of the invariant part of the Ricci tensor among all compatible metrics with the same scalar curvature. We prove that minimal metrics (if any) are unique up to isometry and scaling, they develop soliton solutions for the ‘invariant Ricci’ flow and are characterized as the critical points of a natural variational problem. The uniqueness allows us to distinguish two geometric structures with Riemannian data, giving rise to a great deal of invariants.Our approach proposes to vary Lie brackets rather than inner products; our tool is the moment map for the action of a reductive Lie group on the algebraic variety of all Lie algebras, which we show to coincide in this setting with the Ricci operator. This gives us the possibility to use strong results from geometric invariant theory.Communicated by: Nigel Hitchin (Oxford) Mathematics Subject Classifications (2000): Primary: 53D05, 53D55; Secondary: 22E25, 53D20, 14L24, 53C30.     

Properties of residuals for spatial point processes

For any point process in that has a Papangelou conditional intensity λ, we define a random measure of ‘innovations’ which has mean zero. When the point process model parameters are estimated from data, there is an analogous random measure of ‘residuals’. We analyse properties of the innovations and residuals, including first and second moments, conditional independence, a martingale property, and lack of correlation. Some large sample asymptotics are studied. We derive the marginal distribution of smoothed residuals by solving a distributional equivalence.     

On the compactification of hyperconcave ends and the theorems of Siu-Yau and Nadel

We show that the ‘pseudoconcave holes’ of some naturally arising class of manifolds, called hyperconcave ends, can be filled in, including the case of complex dimension two. As a consequence we obtain a stronger version of the compactification theorem of Siu-Yau and extend Nadel’s theorems to dimension two. Mathematics Subject Classification (1991) 32J05, 32C22, 53C55     

The Blackwell and Dubins Theorem and Rényi’s Amount of Information Measure: Some Applications

This survey paper provides first for an overview of how quantum-like concepts could be used in macroscopic environments like economics. The paper then argues for the use of the concept of a quantum mechanical wave function as an ‘information wave function’. A rationale is provided on why such interpretation is reasonable. After having defined the ‘information wave function’, Ψ(q), we argue how | Ψ(q)| ² can be interpreted as a Radon-Nikodym derivative. We consider how we can connect, using the | Ψ(q)| ², the Blackwell and Dubins (Ann. Math. Stat. 33:882–886, 1961) Theorem with Rényi’s (Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1961) measure of quantity of information. We also define ‘ambiguity of information’ and ‘multi-sourced information’.