A General Hybrid Optimization Strategy for Curve Fitting in the Non-uniform Rational Basis Spline Framework

In this paper, a general methodology to approximate sets of data points through Non-uniform Rational Basis Spline (NURBS) curves is provided. The proposed approach aims at integrating and optimizing the full set of design variables (both integer and continuous) defining the shape of the NURBS curve. To this purpose, a new formulation of the curve fitting problem is required: it is stated in the form of a constrained nonlinear programming problem by introducing a suitable constraint on the curvature of the curve. In addition, the resulting optimization problem is defined over a domain having variable dimension, wherein both the number and the value of the design variables are optimized. To deal with this class of constrained nonlinear programming problems, a global optimization hybrid tool has been employed. The optimization procedure is split in two steps: firstly, an improved genetic algorithm optimizes both the value and the number of design variables by means of a two-level Darwinian strategy allowing the simultaneous evolution of individuals and species; secondly, the optimum solution provided by the genetic algorithm constitutes the initial guess for the subsequent gradient-based optimization, which aims at improving the accuracy of the fitting curve. The effectiveness of the proposed methodology is proven through some mathematical benchmarks as well as a real-world engineering problem.     

平面点列的自动光顺算法

本文考虑平面点列的光顺问题并将该问题化成最小能量曲线的构成问题，即在原点列和相应允许误差构成的带状区域内构造一条最小能量曲线并给出一种自动算法．整个光顺过程分成两步，第一步利用凸分析原理在原点列的允许变动范围内除去多余拐点；第二步在保凸的前提下构造插值点列的最小能量曲线并通过对最小能量曲线进行修正而达到对原型值点列进行光顺的目的．光顺结果不仅可以得到一光顺点列，同时还得到了一条插值点列的光顺曲线．该方法可以对分布不均匀甚至有较大转角的点列进行光顺，与已有的方法比起来具有光顺能力强光顺范围广的特点．     

基于轮廓关键点的B样条曲线拟合算法

针对逆向工程中的点云切片轮廓数据点列,提出一种基于轮廓关键点的B样条曲线拟合算法.在确保扫描线点列形状保真度的前提下,首先对其进行等距重采样等预处理,并遴选出曲线轮廓关键点,生成初始插值曲线;再利用邻域点比较法求出初始曲线与各采样点间的偏差值,在超过拟合允差处增加新的关键点,并生成新的插值曲线,重复该步骤至拟合曲线满足预定精度要求.实验表明,在对稠密的二维断面数据点进行B样条逼近时,该算法能有效压缩控制顶点数目,并具有较高的计算效率.同时,由于所得控制顶点的分布能准确反映曲线的曲率变化,该方法还可作为误差约束的曲线逼近中的迭代步骤之一.     

The String Method as a Dynamical System

This paper is devoted to the theoretical analysis of the zero-temperature string method, a scheme for identifying minimum energy paths (MEPs) on a given energy landscape. By definition, MEPs are curves connecting critical points on the energy landscape which are everywhere tangent to the gradient of the potential except possibly at critical points. In practice, MEPs are mountain pass curves that play a special role, e.g., in the context of rare reactive events that occur when one considers a steepest descent dynamics on the potential perturbed by a small random noise. The string method aims to identify MEPs by moving each point of the curve by steepest descent on the energy landscape. Here we address the question of whether such a curve evolution necessarily converges to an MEP. Surprisingly, the answer is no, for an interesting reason: MEPs may not be isolated, in the sense that there may be families of them that can be continuously deformed into one another. This degeneracy is related to the presence of critical points of Morse index 2 or higher along the MEP. In this paper, we elucidate this issue and completely characterize the limit set of a curve evolving by the string method. We establish rigorously that the limit set of such a curve is again a curve when the MEPs are isolated. We also show under the same hypothesis that the string evolution converges to an MEP. However, we identify and classify situations where the limit set is not a curve and may contain higher dimensional parts. We present a collection of examples where the limit set of a path contains a 2D region, a 2D surface, or a region of an arbitrary dimension up to the dimension of the space. In some of our examples the evolving path wanders around without converging to its limit set. In other examples it fills a region, converging to its limit set, which is not an MEP.     

Restructuring forward step of MARS algorithm using a new knot selection procedure based on a mapping approach

In high dimensional data modeling, Multivariate Adaptive Regression Splines (MARS) is a popular nonparametric regression technique used to define the nonlinear relationship between a response variable and the predictors with the help of splines. MARS uses piecewise linear functions for local fit and apply an adaptive procedure to select the number and location of breaking points (called knots). The function estimation is basically generated via a two-stepwise procedure: forward selection and backward elimination. In the first step, a large number of local fits is obtained by selecting large number of knots via a lack-of-fit criteria; and in the latter one, the least contributing local fits or knots are removed. In conventional adaptive spline procedure, knots are selected from a set of all distinct data points that makes the forward selection procedure computationally expensive and leads to high local variance. To avoid this drawback, it is possible to restrict the knot points to a subset of data points. In this context, a new method is proposed for knot selection which bases on a mapping approach like self organizing maps. By this method, less but more representative data points are become eligible to be used as knots for function estimation in forward step of MARS. The proposed method is applied to many simulated and real datasets, and the results show that it proposes a time efficient forward step for the knot selection and model estimation without degrading the model accuracy and prediction performance.     

Variable selection and estimation using a continuous approximation to the $$L_0$$ penalty

Variable selection problems are typically addressed under the regularization framework. In this paper, an exponential type penalty which very closely resembles the \(L_0\) penalty is proposed, we called it EXP penalty. The EXP penalized least squares procedure is shown to consistently select the correct model and is asymptotically normal, provided the number of variables grows slower than the number of observations. EXP is efficiently implemented using a coordinate descent algorithm. Furthermore, we propose a modified BIC tuning parameter selection method for EXP and show that it consistently identifies the correct model, while allowing the number of variables to diverge. Simulation results and data example show that the EXP procedure performs very well in a variety of settings.     

An automated curve fairing algorithm for cubic B-spline curves

The fairing of contours is an important part of the computerised production of curved objects. A number of different fairing strategies have been proposed. In a recent paper we have introduced an extension of Kjellander's algorithm for fairing parametric B-splines, which can be applied to a wide range of two- and three-dimensional curves. In this paper we describe developments towards a fully automated fairing procedure based on our new algorithm. Like that of Kjellander, our algorithm fairs by an iterative process. The key problems are to decide which points need to be faired and how many times to iterate. Sapidis (1992) has proposed a curve fairness indicator to locate points to be faired and a criterion for termination of fairing. However, we have found that for interpolating curves with great variation in curvature Sapidis' criterion tends to concentrate fairing on regions with large curvature. Therefore we have developed a new scale-independent curve fairness indicator which does not suffer from this drawback. A number of examples of faired curves are presented.     

The discrete Plateau Problem: Algorithm and numerics

We solve the problem of finding and justifying an optimal fully discrete finite element procedure for approximating minimal, including unstable, surfaces. In this paper we introduce the general framework and some preliminary estimates, develop the algorithm, and give the numerical results. In a subsequent paper we prove the convergence estimate. The algorithmic procedure is to find stationary points for the Dirichlet energy within the class of discrete harmonic maps from the discrete unit disc such that the boundary nodes are constrained to lie on a prescribed boundary curve. An integral normalisation condition is imposed, corresponding to the usual three point condition. Optimal convergence results are demonstrated numerically and theoretically for nondegenerate minimal surfaces, and the necessity for nondegeneracy is shown numerically.

     

Estimation of the Bezout number for piecewise algebraic curve

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function.In this paper.a coniecture on trianguation is confirmed The relation between the piecewise linear algebraiccurve and four-color conjecture is also presented.By Morgan-Scott triangulation, we will show the instabilityof Bezout number of piecewise algebraic curves. By using the combinatorial optimization method,an upper     

A boosting method for maximization of the area under the ROC curve

We discuss receiver operating characteristic (ROC) curve and the area under the ROC curve (AUC) for binary classification problems in clinical fields. We propose a statistical method for combining multiple feature variables, based on a boosting algorithm for maximization of the AUC. In this iterative procedure, various simple classifiers that consist of the feature variables are combined flexibly into a single strong classifier. We consider a regularization to prevent overfitting to data in the algorithm using a penalty term for nonsmoothness. This regularization method not only improves the classification performance but also helps us to get a clearer understanding about how each feature variable is related to the binary outcome variable. We demonstrate the usefulness of score plots constructed componentwise by the boosting method. We describe two simulation studies and a real data analysis in order to illustrate the utility of our method.     

An energy-minimization framework for monotonic cubic spline interpolation

This paper describes the use of cubic splines for interpolating monotonic data sets. Interpolating cubic splines are popular for fitting data because they use low-order polynomials and have C² continuity, a property that permits them to satisfy a desirable smoothness constraint. Unfortunately, that same constraint often violates another desirable property: monotonicity. It is possible for a set of monotonically increasing (or decreasing) data points to yield a curve that is not monotonic, i.e., the spline may oscillate. In such cases, it is necessary to sacrifice some smoothness in order to preserve monotonicity.The goal of this work is to determine the smoothest possible curve that passes through its control points while simultaneously satisfying the monotonicity constraint. We first describe a set of conditions that form the basis of the monotonic cubic spline interpolation algorithm presented in this paper. The conditions are simplified and consolidated to yield a fast method for determining monotonicity. This result is applied within an energy minimization framework to yield linear and nonlinear optimization-based methods. We consider various energy measures for the optimization objective functions. Comparisons among the different techniques are given, and superior monotonic C² cubic spline interpolation results are presented. Extensions to shape preserving splines and data smoothing are described.     

Amortized multi-point evaluation of multivariate polynomials

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.     

A new approach based on the surrogating method in the project time compression problems

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is Mixed Integer Linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach.     

Circular spline fitting using an evolution process

We propose a new method to approximate a given set of ordered data points by a spatial circular spline curve. At first an initial circular spline curve is generated by biarc interpolation. Then an evolution process based on a least-squares approximation is applied to the curve. During the evolution process, the circular spline curve converges dynamically to a stable shape. Our method does not need any tangent information. During the evolution process, the number of arcs is automatically adapted to the data such that the final curve contains as few arc arcs as possible. We prove that the evolution process is equivalent to a Gauss-Newton-type method.     

导数振荡与应变能极小的平面分段三次参数Hermite插值

由于分段三次参数Hermite插值的切矢往往被作为变量,故可对其进行优化以使得构造的插值曲线满足特定的要求.为了构造兼具保形性与光顺性的平面分段三次参数Hermite插值曲线,给出了一种通过同时极小化导数振荡和应变能来确定切矢的方法.首先以导数振荡函数和应变能函数为双目标建立了切矢满足的方程系统;然后证明了方程系统存在唯一解,并给出了解的具体表达式;最后给出了误差分析,并通过数值算例表明方法的有效性.结果表明,相对于导数振荡极小化方法和应变能极小化方法,所提出的导数振荡和应变能极小化方法同时兼顾了平面分段三次参数Hermite插值曲线的保形性和光顺性.     

Extension of multivariate regression trees to interval data. Application to electricity load profiling

Summary  Several data can be presented as interval curves where intervals reflect a within variability. In particular, this representation is well adapted for load profiles, which depict the electricity consumption of a class of customers. Electricity load profiling consists in assigning a daily load curve to a customer based on their characteristics such as energy requirement. Within the load profiling scope, this paper investigates the extension of multivariate regression trees to the case of interval dependent (or response) variables. The tree method aims at setting up simultaneously load profiles and their assignment rules based on independent variables. The extension of multivariate regression trees to interval responses is detailed and a global approach is defined. It consists in a first stage of a dimension reduction of the interval response variables. Thereafter, the extension of the tree method is applied to the first principal interval components. Outputs are the classes of the interval curves where each class is characterized both by an interval load profile (e.g. the class prototype) and an assignment rule based on the independent variables.     

The conditioning of least‐squares problems in variational data assimilation

In variational data assimilation a least‐squares objective function is minimised to obtain the most likely state of a dynamical system. This objective function combines observation and prior (or background) data weighted by their respective error statistics. In numerical weather prediction, data assimilation is used to estimate the current atmospheric state, which then serves as an initial condition for a forecast. New developments in the treatment of observation uncertainties have recently been shown to cause convergence problems for this least‐squares minimisation. This is important for operational numerical weather prediction centres due to the time constraints of producing regular forecasts. The condition number of the Hessian of the objective function can be used as a proxy to investigate the speed of convergence of the least‐squares minimisation. In this paper we develop novel theoretical bounds on the condition number of the Hessian. These new bounds depend on the minimum eigenvalue of the observation error covariance matrix and the ratio of background error variance to observation error variance. Numerical tests in a linear setting show that the location of observation measurements has an important effect on the condition number of the Hessian. We identify that the conditioning of the problem is related to the complex interactions between observation error covariance and background error covariance matrices. Increased understanding of the role of each constituent matrix in the conditioning of the Hessian will prove useful for informing the choice of correlated observation error covariance matrix and observation location, particularly for practical applications.     

Efficient computation of the Gauss-Newton direction when fitting NURBS using ODR

We consider a subproblem in parameter estimation using the Gauss-Newton algorithm with regularization for NURBS curve fitting. The NURBS curve is fitted to a set of data points in least-squares sense, where the sum of squared orthogonal distances is minimized. Control-points and weights are estimated. The knot-vector and the degree of the NURBS curve are kept constant. In the Gauss-Newton algorithm, a search direction is obtained from a linear overdetermined system with a Jacobian and a residual vector. Because of the properties of our problem, the Jacobian has a particular sparse structure which is suitable for performing a splitting of variables. We are handling the computational problems and report the obtained accuracy using different methods, and the elapsed real computational time. The splitting of variables is a two times faster method than using plain normal equations.     

Transversal walls versus vortex walls in magnetic nanowires

In numeric simulations of magnetic nanowires several groups have observed two different types of reversal modes. It is suggested that the reversal mode corresponds to an energetically optimal domain wall profile. We investigate the energy minimisation problem in different regimes of thickness. When the radius goes to zero, the energy minimisation problem Γ-converges to a reduced local one dimensional problem. Thus for small radii, minimisers of the energy functional are almost constant on the cross section. This is not the case for big radii. For radius to infinity, a class of magnetisations with a vortex has the optimal energy scaling. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)