A general construction of barycentric coordinates over convex polygons

Barycentric coordinates are unique for triangles, but there are many possible generalizations to convex polygons. In this paper we derive sharp upper and lower bounds on all barycentric coordinates over convex polygons and use them to show that all such coordinates have the same continuous extension to the boundary. We then present a general approach for constructing such coordinates and use it to show that the Wachspress, mean value, and discrete harmonic coordinates all belong to a unifying one-parameter family of smooth three-point coordinates. We show that the only members of this family that are positive, and therefore barycentric, are the Wachspress and mean value ones. However, our general approach allows us to construct several sets of smooth five-point coordinates, which are positive and therefore barycentric. Dedicated to Charles A. Micchelli on his 60th Birthday Mathematics subject classifications (2000) 26C15, 65D05.     

Barycentric coordinates for convex polytopes

An extension of the standard barycentric coordinate functions for simplices to arbitrary convex polytopes is described. The key to this extension is the construction, for a given convex polytope, of a unique polynomial associated with that polytope. This polynomial, theadjoint of the polytope, generalizes a previous two-dimensional construction described by Wachspress. The barycentric coordinate functions for the polytope are rational combinations of adjoints of various dual cones associated with the polytope.     

Residue formulae, vector partition functions and lattice points in rational polytopes

We obtain residue formulae for certain functions of several variables. As an application, we obtain closed formulae for vector partition functions and for their continuous analogs. They imply an Euler-MacLaurin summation formula for vector partition functions, and for rational convex polytopes as well: we express the sum of values of a polynomial function at all lattice points of a rational convex polytope in terms of the variation of the integral of the function over the deformed polytope.

     

A class of piecewise interpolating functions based on barycentric coordinates

Piecewise interpolation methods, as spline or Hermite cubic interpolation methods, define the interpolant function by means of polynomial pieces and ensure that some regularity conditions are guaranteed at the break-points. In this work, we propose a novel class of piecewise interpolating functions whose expression depends on the barycentric coordinates and a suitable weight function. The underlying idea is to specialize to the 1D settings some aspects of techniques widely used in multi-dimensional interpolation, namely Shepard’s, barycentric and triangle-based blending methods. We show the properties of convergence for the interpolating functions and discuss how, in some cases, the properties of regularity that characterize the weight function are reflected on the interpolant function. Numerical experiments, applied to some case studies and real scenarios, show the benefit of our method compared to other interpolant models.     

Bivariate polynomial and continued fraction interpolation over ortho-triples

By means of the barycentric coordinates expression of the interpolating polynomial over each ortho-triple, some properties are obtained. Moreover, the explicit coefficients in terms of B-net for one ortho-triple, and two ortho-triples are worked out, respectively. Thus the computation of multiple integrals can be converted into the sum of the coefficients in terms of the B-net over triangular domain much effectively and conveniently. Based on a new symmetrical algorithm of partial inverse differences, a novel continued fractions interpolation scheme is presented over arbitrary ortho-triples in R², which is a bivariate osculatory interpolation formula with one-order partial derivatives at all corner points in the ortho-triples. Furthermore, its characterization theorem is presented by three-term recurrence relations. The new scheme is advantageous over the polynomial one with some numerical examples.     

Convex functions with continuous epigraph or continuous level sets

Convex functions with continuous epigraph in the sense of Gale and Klée have been studied recently by Auslender and Coutat in a finite-dimensional setting. Here, we provide characterizations of such functionals in terms of the Legendre-Fenchel transformation in general locally convex spaces. Also, we show that the concept of continuous convex sets is of interest in these spaces. We end with a characterization of convex functions on Euclidean spaces with continuous level sets.     

Ratios of affine functions

Aratio of affine functions is a function which can be expressed as the ratio of a vector valued affine function and a scalar affine functional. The purpose of this note is to examine properties of sets which are preserved under images and inverse images of such functions. Specifically, we show that images and inverse images of convex sets under such functions are convex sets. Also, images of bounded, convex polytopes under such functions are bounded, convex polytopes. In addition, we provide sufficient conditions under which the extreme points of images of convex sets are images of extreme points of the underlying domains. Of course, this result is useful when one wishes to maximize a convex function over a corresponding set. The above assertions are well known for affine functions. Applications of the results include a problem that concerns the control of stochastic eigenvectors of stochastic matrices.     

Convex combination maps over triangulations, tilings, and tetrahedral meshes

In a recent paper by the first author, a simple proof was given of a result by Tutte on the validity of barycentric mappings, recast in terms of the injectivity of piecewise linear mappings over triangulations. In this note, we make a short extension to the proof to deal with arbitrary tilings. We also give a simple counterexample to show that convex combination mappings over tetrahedral meshes are not necessarily one-to-one. Mathematics subject classifications (2000) 05C10, 05C85, 65D17, 58E20     

Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.     

On convex envelopes for bivariate functions over polytopes

In this paper we discuss convex envelopes for bivariate functions, satisfying suitable assumptions, over polytopes. We first propose a technique to compute the value and a supporting hyperplane of the convex envelope over a general two-dimensional polytope through the solution of a three-dimensional convex subproblem with continuously differentiable constraint functions. Then, for quadratic functions as well as for some polynomial and rational ones, again satisfying suitable assumptions, we show how the same computations can be carried out through the solution of a single semidefinite problem.     

Convex composite functions in Banach spaces and the primal lower-nice property

Primal lower-nice functions defined on Hilbert spaces provide examples of functions that are ``integrable' (i.e. of functions that are determined up to an additive constant by their subgradients). The class of primal lower-nice functions contains all convex and lower- functions. In finite dimensions the class of primal lower-nice functions also contains the composition of a convex function with a mapping under a constraint qualification. In Banach spaces certain convex composite functions were known to be primal lower-nice (e.g. a convex function had to be continuous relative to its domain). In this paper we weaken the assumptions and provide new examples of convex composite functions defined on a Banach space with the primal lower-nice property. One consequence of our results is the identification of new examples of integrable functions on Hilbert spaces.

     

任意三角形区域中一组完备正交基的构造与分类

1.引言 正交函数基底在函数逼近、图像压缩和模式识别等领域中起着重要的作用.在二维区域中,通常采用分离变量法构造张量积形式的基底.然而,这种方法本质上只适用于规则的矩形区域.如何构造非规则区域,如三角形上的正交基底,是一个值得研究的课题[1][2][3][4][5].在一维情形下,通过求解Sturm—Liouville特征方程可以得到一组完备的正交基底.通过求解相应区域的特征方程,我们可以将这种方法推广到高维的基底构造.以三角区域为例,我们可以通过求解形式如下的特征方程来构造正交基底函数:     

Conjugacy relationship between M-convex and L-convex functions in continuous variables

By extracting combinatorial structures in well-solved nonlinear combinatorial optimization problems, Murota (1996,1998) introduced the concepts of M-convexity and L-convexity to functions defined over the integer lattice. Recently, Murota–Shioura (2000, 2001) extended these concepts to polyhedral convex functions and quadratic functions in continuous variables. In this paper, we consider a further extension to more general convex functions defined over the real space, and provide a proof for the conjugacy relationship between general M-convex and L-convex functions.Mathematics Subject Classification (1991): 90C10, 90C25, 90C27, 90C35This work is supported by Grant-in-Aid of the Ministry of Education, Culture, Sports, Science and Technology of Japan     

A technique to derive the analytical form of convex envelopes for some bivariate functions

In the recent paper (Locatelli and Schoen in Math Program, 2013) it is shown that the value of the convex envelope of some bivariate functions over polytopes can be computed by solving a continuously differentiable convex problem. In this paper we show how this result can be exploited to derive in some cases the analytical form of the envelope. The technique is illustrated through two examples.     

When is rounding allowed in integer nonlinear optimization?

In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.     

Chebfun and numerical quadrature

Chebfun is a Matlab-based software system that overloads Matlab's discrete operations for vectors and matrices to analogous continuous operations for functions and operators.We begin by describing Chebfun's fast capabilities for Clenshaw-Curtis and also Gauss-Legendre,-Jacobi,-Hermite,and-Laguerre quadrature,based on algorithms of Waldvogel and Glaser,Liu and Rokhlin.Then we consider how such methods can be applied to quadrature problems including 2D integrals over rectangles,fractional derivatives and integrals,functions defined on unbounded intervals,and the fast computation of weights for barycentric interpolation.     

One-to-one piecewise linear mappings over triangulations

We call a piecewise linear mapping from a planar triangulation to the plane a convex combination mapping if the image of every interior vertex is a convex combination of the images of its neighbouring vertices. Such mappings satisfy a discrete maximum principle and we show that they are one-to-one if they map the boundary of the triangulation homeomorphically to a convex polygon. This result can be viewed as a discrete version of the Radó-Kneser-Choquet theorem for harmonic mappings, but is also closely related to Tutte's theorem on barycentric mappings of planar graphs.

     

The initial convergence rate of adaptive methods for polyhedral approximation of convex bodies

The convergence rate at the initial stage is analyzed for a previously proposed class of asymptotically optimal adaptive methods for polyhedral approximation of convex bodies. Based on the results, the initial convergence rate of these methods can be evaluated for arbitrary bodies (including the case of polyhedral approximation of polytopes) and the resources sufficient for achieving optimal asymptotic properties can be estimated.     

Convexity results and sharp error estimates in approximate multivariate integration

An interesting property of the midpoint rule and the trapezoidal rule, which is expressed by the so-called Hermite-Hadamard inequalities, is that they provide one-sided approximations to the integral of a convex function. We establish multivariate analogues of the Hermite-Hadamard inequalities and obtain access to multivariate integration formulae via convexity, in analogy to the univariate case. In particular, for simplices of arbitrary dimension, we present two families of integration formulae which both contain a multivariate analogue of the midpoint rule and the trapezoidal rule as boundary cases. The first family also includes a multivariate analogue of a Maclaurin formula and of the two-point Gaussian quadrature formula; the second family includes a multivariate analogue of a formula by P.C. Hammer and of Simpson's rule. In both families, we trace out those formulae which satisfy a Hermite-Hadamard inequality. As an immediate consequence of the latter, we obtain sharp error estimates for twice continuously differentiable functions.

     

广义凸函数的特征性质

提出广义凸集、广义凸函数、中间点广义凸函数、端点广义凸函数四个定义,通过定义条件P1,研究条件P1所蕴含的等式关系,进而得到一个基础性定理一稠密性定理和一个相对条件较弱的推论,最后将结果应用于若干不同类型的广义凸函数类,尤其是s-凸函数、几何凸函数、rp-凸函数,得到它们所共有的一个特征性质,即满足稠密性定理．