A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

求解二阶波动方程的三次样条差分方法

有限差分法在求解二阶波动方程初边值问题过程中通常受到精度和稳定性的限制.本文对二阶波动方程的时间、空间项分别采用三次样条公式进行离散,推导出精度分别为O(τ2+h2),0(τ2+h4),O(τ4+h2)和O(τ4+h4)的四种三层隐式差分格式,以及与之相匹配的第一个时间步的同阶离散格式,并采用Fourier方法分析了格...     

On Lower Bounds for the L 1-Norm of Exponential Sums

In the paper a method for finding lower bounds of the L ₁-norm of some exponential sums is described.     

L 1-optimization in linear systems with bounded controls

In a linear control system over a fixed time interval, we treat steering to the origin by controls (i) having realistic constraints on their values, while minimizing theL ₁-cost of control, (ii) without such constraints, and (iii) minimizing the coordinate bound, with or without a givenL ₁-cost restriction. Existence (also, nonexistence) results are obtained, together with further necessary conditions for control optimality.The author was introduced to these problems by Professors P. Hagedorn and W. Krabs and profited much by discussions with them and with other workers at the TH Darmstadt. The incisive idea that feedback controls still exist if state space is augmented by one dimension (see Example, Section 1) is due to Professor Hagedorn and obviously merits further treatment. Professor E. N. Chukwu pointed out an error in a preprint version of this paper, and the present formulation of Theorem 4.6 is the result of discussions with him. In a colloquium at Würzburg University, Professor P. C. Parks made the point that a portion ofmodern control theory is implicit in the work of Achiezer: in connection with the present material, the so-called M-moment problem, and our Theorem 4.6. The referee kindly pointed out the reference for the example in Section 1. This paper is a revised version of a report, Preprint No. 279, prepared while the author held a Humboldt Award at the TH Darmstadt.     

Superapproximation and Commutator Properties of Discrete Orthogonal Projections for Continuous Splines

This paper builds upon the L_p-stability results for discrete orthogonal projections on the spaces S_h of continuous splines of order r obtained by R. D. Grigorieff and I. H. Sloan in (1998, Bull. Austral. Math. Soc.58, 307–332). Properties of such projections were proved with a minimum of assumptions on the mesh and on the quadrature rule defining the discrete inner product. The present results, which include superapproximation and commutator properties, are similar to those derived by I. H. Sloan and W. Wendland (1999, J. Approx. Theory97, 254–281) for smoothest splines on uniform meshes. They are expected to have applications (as in I. H. Sloan and W. Wendland, Numer. Math. (1999, 83, 497–533)) to qualocation methods for non-constant-coefficient boundary integral equations, as well as to the wide range of other numerical methods in which quadrature is used to evaluate L₂-inner products. As a first application, we consider the most basic variable-coefficient boundary integral equation, in which the constant-coefficient operator is the identity. The results are also extended to the case of periodic boundary conditions, in order to allow appplication to boundary integral equations on closed curves.     

A Lower Bound for the L 1-norm of Fourier Series of Polynomial Type

Mathematical Notes -     

Bivariate Sign Tests Based on the Sup, L 1 and L 2 Norms

The bivariate location problem is considered. The sup, L ₁ and L ₂ norms are used to construct bivariate sign tests from the univariate sign statistics computed on the projected observations on all lines passing through the origin. The tests so obtained are affine-invariant and distribution-free under the null hypothesis. The sup-norm gives rise to Hodges' test. A class of tests derived from the L ₂-norm, with Blumen's test as a member, is seen to be related to a class proposed by Oja and Nyblom (1989, J. Amer. Statist. Assoc., 84, 249-259). The L ₁-norm gives rise to a new test. Its asymptotic null distribution is seen to be the same as that of the L ₁-norm of a certain normal process related to the standard Wiener process. An explicit expression of its cumulative distribution function is given. A simulation study will examine the merits of the three approaches.     

Minimum L1-Distance Projection onto the Boundary of a Convex Set: Simple Characterization

We show that the minimum distance projection in the L ₁-norm from an interior point onto the boundary of a convex set is achieved by a single, unidimensional projection. Application of this characterization when the convex set is a polyhedron leads to either an elementary minmax problem or a set of easily solved linear programs, depending upon whether the polyhedron is given as the intersection of a set of half spaces or as the convex hull of a set of extreme points. The outcome is an easier and more straightforward derivation of the special case results given in a recent paper by Briec (Ref. 1).     

On Minimal-Moment Generating Functions

A formula expressing the inverse cumulative distribution function of a non-negative random variable in terms of contour integrals of its minimal-moment generating function is proved as well as an analog of the classical continuity theorem for characteristic functions.     

Geometric interpolation by planar cubic <Emphasis Type="Italic">G</Emphasis><Superscript>1</Superscript> splines

In this paper, geometric interpolation by G ¹ cubic spline is studied. A wide class of sufficient conditions that admit a G ¹ cubic spline interpolant is determined. In particular, convex data as well as data with inflection points are included. The existence requirements are based upon geometric properties of data entirely, and can be easily verified in advance. The algorithm that carries out the verification is added. AMS subject classification (2000)  65D05, 65D07, 65D17     

Approximating term structure of interest rates using cubic L1 splines

Classical spline fitting methods for estimating the term structure of interest rates have been criticized for generating highly fluctuating fitting curves for bond price and discount function. In addition, the performance of these methods usually relies heavily on parameter tuning involving human judgement. To overcome these drawbacks, a recently developed cubic L₁ spline model is proposed for term structure analysis. Cubic L₁ splines preserve the shape of the data, exhibit no extraneous oscillation and have small fitting errors. Cubic L₁ splines are tested using a set of real financial data and compared with the widely used B-splines.     

Exact L 2-norm plane separation

We consider the problem of separating two sets of points in an n-dimensional real space with a (hyper)plane that minimizes the sum of L _p -norm distances to the plane of points lying on the wrong side of it. Despite recent progress, practical techniques for the exact solution of cases other than the L ₁ and L _∞-norm were unavailable. We propose and implement a new approach, based on non-convex quadratic programming, for the exact solution of the L ₂-norm case. We solve in reasonable computing times artificial problems of up to 20000 points (in 6 dimensions) and 13 dimensions (with 2000 points). We also observe that, for difficult real-life instances from the UCI Repository, computation times are substantially reduced by incorporating heuristic results in the exact solution process. Finally, we compare the classification performance of the planes obtained for the L ₁, L ₂ and L _∞ formulations. It appears that, despite the fact that L ₂ formulation is computationally more expensive, it does not give significantly better results than the L ₁ and L _∞ formulations.     

An Algorithm for Strictly Convex Quadratic Programming with Box Constraints

1IntroductionWeconsiderastrictlyconvex(i.e.,positivedefinite)quadraticprogrammingproblemsubjecttoboxconstraints:t-iereA=[aij]isannxnsymmetricpositivedefinitematrix,andb,canddaren-vectors.Letg(x)bethegradient,Ax b,off(x)atx.Withoutlossofgeneralityweassumebothcianddiarefinitenumbers,ci相似文献   

Geometric dual formulation for first-derivative-based univariate cubic <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript> splines

With the objective of generating “shape-preserving” smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based -smooth univariate cubic L ₁ splines. An L ₁ spline minimizes the L ₁ norm of the difference between the first-order derivative of the spline and the local divided difference of the data. Calculating the coefficients of an L ₁ spline is a nonsmooth non-linear convex program. Via Fenchel’s conjugate transformation, the geometric dual program is a smooth convex program with a linear objective function and convex cubic constraints. The dual-to-primal transformation is accomplished by solving a linear program.     

The L p -curvature images of convex bodies and L p -projection bodies

Associated with the L _p -curvature image defined by Lutwak, some inequalities for extended mixed p-affine surface areas of convex bodies and the support functions of L _p -projection bodies are established. As a natural extension of a result due to Lutwak, an L _p -type affine isoperimetric inequality, whose special cases are L _p -Busemann-Petty centroid inequality and L _p -affine projection inequality, respectively, is established. Some L _p -mixed volume inequalities involving L _p -projection bodies are also established.     

Bivariate C1 Cubic Spline Spaces Over Even Stratified Triangulations

It is well-known that the basic properties of a bivariate spline space such as dimension and approximation order depend on the geometric structure of the partition. The dependence of geometric structure results in the fact that the dimension of a C ¹ cubic spline space over an arbitrary triangulation becomes a well-known open problem. In this paper, by employing a new group of smoothness conditions and conformality conditions, we determine the dimension of bivariate C ¹ cubic spline spaces over a so-called even stratified triangulation.     

An Efficient Algorithm for Min-Max Convex Semi-Infinite Programming Problems

In this article, we consider the convex min-max problem with infinite constraints. We propose an exchange method to solve the problem by using efficient inactive constraint dropping rules. There is no need to solve the maximization problem over the metric space, as the algorithm has merely to find some points in the metric space such that a certain criterion is satisfied at each iteration. Under some mild assumptions, the proposed algorithm is shown to terminate in a finite number of iterations and to provide an approximate solution to the original problem. Preliminary numerical results with the algorithm are promising. To our knowledge, this article is the first one conceived to apply explicit exchange methods for solving nonlinear semi-infinite convex min-max problems.     

An Efficient Genetic Algorithm for the p-Median Problem

We propose a new genetic algorithm for a well-known facility location problem. The algorithm is relatively simple and it generates good solutions quickly. Evolution is facilitated by a greedy heuristic. Computational tests with a total of 80 problems from four different sources with 100 to 1,000 nodes indicate that the best solution generated by the algorithm is within 0.1% of the optimum for 85% of the problems. The coding effort and the computational effort required are minimal, making the algorithm a good choice for practical applications requiring quick solutions, or for upper-bound generation to speed up optimal algorithms.     

An analogue of Montel's theorem for some classes of rational functions

For sequences of rational functions, analytic in some domain, a theorem of Montel's type is proved. As an application, sequences of rational functions of the best L _p -approximation with an unbounded number of finite poles are considered.     

求解二层线性规划问题的一种算法

对下层含有约束的二层线性规划问题,提出了求全局最优解的一种算法.首先由该算法求出约束凸集的全部极点,再对极点进行可行性检验,从而得到了二层线性规划问题的全局最优解,最后以实例验证了算法的有效性.