Approximating Gradients with Continuous Piecewise Polynomial Functions

Motivated by conforming finite element methods for elliptic problems of second order, we analyze the approximation of the gradient of a target function by continuous piecewise polynomial functions over a simplicial mesh. The main result is that the global best approximation error is equivalent to an appropriate sum in terms of the local best approximation errors on elements. Thus, requiring continuity does not downgrade local approximation capability and discontinuous piecewise polynomials essentially do not offer additional approximation power, even for a fixed mesh. This result implies error bounds in terms of piecewise regularity over the whole admissible smoothness range. Moreover, it allows for simple local error functionals in adaptive tree approximation of gradients.     

Universal Polynomial Expansions of Harmonic Functions

Let Ω be a domain in ? ^N such that $\left(\mathbb{R}^{N}\cup\lbrace\infty\rbrace\right)\setminus\Omega$ is connected. It is known that, for each w?∈?Ω, there exist harmonic functions on Ω that are universal at w, in the sense that partial sums of their homogeneous polynomial expansion about w approximate all plausibly approximable functions in the complement of Ω. Under the assumption that Ω omits an infinite cone, it is shown that the connectedness hypothesis on $\left(\mathbb{R}^{N}\cup\lbrace\infty\rbrace\right)\setminus\Omega$ is essential, and that a harmonic function which is universal at one point is actually universal at all points of Ω.     

Universal Overconvergence of Polynomial Expansions of Harmonic Functions

For each compact subset K of ^N let (K) denote the space of functions that are harmonic on some neighbourhood of K. The space (K) is equipped with the topology of uniform convergence on K. Let Ω be an open subset of ^N such that 0Ω and ^N\Ω is connected. It is shown that there exists a series ∑H_n, where H_n is a homogeneous harmonic polynomial of degree n on ^N, such that (i) ∑H_n converges on some ball of centre 0 to a function that is continuous on Ω and harmonic on Ω, (ii) the partial sums of ∑H_n are dense in (K) for every compact subset K of ^N\Ω with connected complement. Some refinements are given and our results are compared with an analogous theorem concerning overconvergence of power series.     

Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis

Computing the convex envelope is a core operation in nonsmooth analysis that bridges the convex with the nonconvex world. Although efficient algorithms to compute fundamental transforms of convex analysis have been proposed over the years, they are limited to convex functions until an efficient algorithm becomes available to compute the convex envelope of a piecewise linear-quadratic function (of one variable) efficiently. We present two such algorithms, one based on maximum and conjugate computation that is easy to implement but has quadratic time complexity, and another based on direct computation that requires more work to implement but has optimal (linear time) complexity. We prove their time (and space) complexity, and compare their performances.     

Topological Graph Polynomial and Quantum Field Theory Part II: Mehler Kernel Theories

We define a new topological polynomial extending the Bollobás–Riordan one, which obeys a four-term reduction relation of the deletion/contraction type and has a natural behaviour under partial duality. This allows to write down a completely explicit combinatorial evaluation of the polynomials, occurring in the parametric representation of the non-commutative Grosse–Wulkenhaar quantum field theory. An explicit solution of the parametric representation for commutative field theories based on the Mehler kernel is also provided.     

Modified Defect Correction Algorithms for ODEs. Part I: General Theory

The well-known method of Iterated Defect Correction (IDeC) is based on the following idea: Compute a simple, basic approximation and form its defect w.r.t. the given ODE via a piecewise interpolant. This defect is used to define an auxiliary, neighboring problem whose exact solution is known. Solving the neighboring problem with the basic discretization scheme yields a global error estimate. This can be used to construct an improved approximation, and the procedure can be iterated. The fixed point of such an iterative process corresponds to a certain collocation solution. We present a variety of modifications to this algorithm. Some of these have been proposed only recently, and together they form a family of iterative techniques, each with its particular advantages. These modifications are based on techniques like defect quadrature (IQDeC), defect interpolation (IPDeC), and combinations thereof. We investigate the convergence on locally equidistant and nonequidistant grids and show how superconvergent approximations can be obtained. Numerical examples illustrate our considerations. The application to stiff initial value problems will be discussed in Part II of this paper.     

Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective

In previous work (Krasnogor, . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol, UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474–488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When “syntactic sugar” is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover, we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical applications) also give rise to PLS-complete problems.

---

Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users.      

Variable Programming: A Generalized Minimax Problem. Part II: Algorithms

In this part of the two-part series of papers, algorithms for solving some variable programming (VP) problems proposed in Part I are investigated. It is demonstrated that the non-differentiability and the discontinuity of the maximum objective function, as well as the summation objective function in the VP problems constitute difficulty in finding their solutions. Based on the principle of statistical mechanics, we derive smooth functions to approximate these non-smooth objective functions with specific activated feasible sets. By transforming the minimax problem and the corresponding variable programming problems into their smooth versions we can solve the resulting problems by some efficient algorithms for smooth functions. Relevant theoretical underpinnings about the smoothing techniques are established. The algorithms, in which the minimization of the smooth functions is carried out by the standard quasi-Newton method with BFGS formula, are tested on some standard minimax and variable programming problems. The numerical results show that the smoothing techniques yield accurate optimal solutions and that the algorithms proposed are feasible and efficient.This work was supported by the RGC grant CUHK 152/96H of the Hong Kong Research Grant Council.     

On Optimal Defuzzification and Learning Algorithms: Theory and Applications

In this paper, the issue of optimal defuzzification which is advocated in the Optimality Principle of Defuzzification (Song and Leland (1996)) is addressed. It was shown that defuzzification can be treated as a mapping from a high dimensional space to the real line. When system performance indices are considered, the defuzzification mapping which optimizes the performance indices for the given fuzzy sets is known as the optimal defuzzification mapping. Thus, finding this optimal defuzzification mapping becomes the essence of defuzzification. The problem with this idea, however, is that the space formed by all possible continuous defuzzification mappings is so large to search that the only recourse is an approximation to the optimal defuzzification mapping. With this, learning algorithms can be devised to find the optimal parameters of defuzzifiers with fixed structures. The proposed method is rigorously examined and compared with some well-known defuzzification methods. To overcome the resultant enormous computational load problem with this algorithm, the concept of defuzzification filter is additionally proposed. An application of the method to the power system stabilization problem is presented.     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

Algorithms for special functions. II

Numerische Mathematik -     

Unified Duality Theory for Constrained Extremum Problems. Part II: Special Duality Schemes

In the first part of this paper series, a unified duality scheme for a constrained extremum problem is proposed by virtue of the image space analysis. In the present paper, we pay our attention to study of some special duality schemes. Particularly, the Lagrange-type duality, Wolfe duality and Mond–Weir duality are discussed as special duality schemes in a unified interpretation. Moreover, three practical classes of regular weak separation functions are also considered.     

Piecewise Monotonicity for Unary Functions in o-Stable Groups

Algebra and Logic - Unary functions definable in o-stable ordered groups of nonvaluational type are studied. Such functions are proved to be piecewise monotone and continuous.     

Piecewise Polynomial Collocation for Volterra-type Integral Equations of the Second Kind

The exact solution of a given integral equation of the secondkind of Volterra type(with regular or weakly singular kernel)is projected into the space of (continuous) piecewise polynomialsof degree m 1 and with prescribed knots by using collocationtechniques. It is shown that a number of discrete methods forthe numerical solution of such equations based on product integrationtechniques or on finite-difference methods are particular discreteversions of collocation methods of the above type. The errorbehaviour of approximate solutions obtained by collocation (includingtheir discretizations) is discussed.     

Asymptotic Properties of Collocation Matrix Norms 2: Piecewise Polynomial Approximation

This paper considers a matrix related to the solution by piecewisepolynomial collocation using n subintervals of an mth-orderordinary differential boundary-value problem. It is shown thatif the maximum subinterval size tends to zero as the matrix norm tends to the norm of an operator related tothe differential equation, under the assumption that the collocationpoints in each subinterval are assumed to be distributed identicallyand their associated interpolatory quadrature weights are positive.     

Polynomial bounds for probability generating functions. II

Summary Consider the set of proper probability distributions on the nonnegative integers having the first k moments (fixed) in common. It is desired to find the element of this set whose corresponding probability generating function (p.g.f.) lies entirely above or below the others. Using convexity arguments, it is shown that the extremal distribution exists, is unique, and is necessarily an element of a certain subclass of the class of all (k + 1)-point distributions. This subclass is entirely characterized by the geometrical properties of its set of support. The alternation of upper and lower bounds with the parity of k is also explained. There is mention of how the techniques developed here apply to more general discrete optimization problems, and the connection with the theory of cyclic polytopes is also discussed.This work was partially supported by Army Research Office Grant #DAHCO 04-74-G-0178 awarded to the Department of Statistics, Princeton University