Tracking local optimality for cost parameterized optimization problems

In this paper, a procedure for computing local optimal solution curves of the cost parameterized optimization problem is presented. We recast the problem to a parameterized nonlinear equation derived from its Lagrange function and show that the point where the positive definiteness of the projected Hessian matrix vanishes must be a bifurcation point on the solution curve of the equation. Based on this formulation, the local optimal curves can be traced by the continuation method, coupled with the testing of singularity of the Jacobian matrix. Using the proposed procedure, we successfully compute the energy diagram of rotating Bose–Einstein condensates.     

Hypothesis testing: a framework for analyzing and optimizing Houghtransform performance

In this paper a formal, quantitative approach to designing optimum Hough transform (HT) algorithms is proposed. This approach takes the view that a HT is a hypothesis testing method. Each sample in the HT array implements a test to determine whether a curve with the given parameters fits the edge point data. This view allows the performance of HT algorithms to be quantified. The power function, which gives the probability of rejection as a function of the underlying parametric distribution of data points, is shown to be the fundamentally important characteristic of HT behaviour. Attempting to make the power function narrow is a formal approach to optimizing HT performance. To illustrate how this framework is useful the particular problem of line detection is discussed in detail. It is shown that the hypothesis testing framework leads to a redefinition of the HT in which the values are a measure of the distribution of points around a curve rather than the number of points on a curve. This change dramatically improves the sensitivity of the method to small structures. The solution to many HT design problems can be posed within the framework, including optimal quantizations and optimum sampling of the parameter space. In this paper the authors consider the design of optimum I-D filters, which can be used to sharpen the peak structure in parameter space. Results on several real images illustrate the improvements obtained     

The characterization of parametric surface sections

An important class of surface intersection problems involves the sectioning of finite parametric polynomial patches by an unbounded algebraic surface. The section curve may be represented precisely by a high order algebraic curve F(u,ν) = 0 in the parameter space of the patch. It is then desired to evaluate the curve, i.e., to identify each of its open segments and closed loops, singular features such as cusps or self-intersections, and to generate ordered sequences of points along each segment or loop. Concepts from algebraic curve theory are employed to determine a set of characteristic points for the section curve. These comprise all curve points on the parameter domain boundary, all turning points where the curve tangent is parallel to u = 0 or ν = 0, and all singular points. The characteristic points dissect the section curve into a set of monotonic branches. Each characteristic point is assigned a link multiplicity, giving the number of branches entering or leaving that point. The number of monotonic curve branches is then uniquely determined by the sum of the link multiplicities. To complete the section curve evaluation, it is necessary to trace the curve branches between characteristic points. Two methods are described to identify and generate ordered point sequences along each branch: (1) locating curve points on an isoparametric grid and employing a heuristic sorting procedure; (2) marching along branches in small steps by local power-series expansions.The identification of all characteristic points coupled with the power series curve-tracing procedure provides an essentially deterministic method for evaluating parametric surface sections. This is a substantial improvement over current heuristic numerical algorithms.     

辨识非线性曲线的非线性极大似然—优化法

工程上经常碰到非线性曲线辨识问题。本文探讨一种非线性极大似然-优化法并结合三次样条函数拟配法,形成统一的逐次逼近的直接辨识非线性曲线的非线性辨识方法。该法兼有极大似然法的唯一性、很好的收敛性和优化法直接处理非线性系统的能力,辨识出的样条函数曲线能无限地光滑地逼近非线性曲线。     

On Computing Structural Changes in Evolving Surfaces and their Appearance

As a surface undergoes a one-parameter family of deformations, its shape and its appearance change smoothly except at certain critical parameter values where abrupt structural changes occur. This paper considers the case of surfaces defined as the zero set of smooth density functions undergoing a Gaussian diffusion process and addresses the problem of computing the critical parameter values corresponding to structural changes in the parabolic curves of a surface and in its aspect graph. An algorithm based on homotopy continuation and curve tracing is proposed in the case of polynomial density functions, whose zero set is an algebraic surface. It has been implemented and examples are presented.     

Semiclassical spectral confinement for the sine-Gordon equation

The inverse scattering method for solving the sine-Gordon equation in laboratory coordinates requires the analysis of the Faddeev–Takhtajan eigenvalue problem. This problem is not self-adjoint and the eigenvalues may lie anywhere in the complex plane, so it is of interest to determine conditions on the initial data that restrict where the eigenvalues can be. We establish bounds on the eigenvalues for a broad class of zero-charge initial data that are applicable in the semiclassical or zero-dispersion limit. It is shown that no point off the coordinate axes or turning point curve can be an eigenvalue if the dispersion parameter is sufficiently small.     

Shape modeling based on specifying the initial B-spline curve and scaled BFGS optimization method

In this paper, we consider the problem of fitting the B-spline curves to a set of ordered points, by finding the control points and the location parameters. The presented method takes two main steps: specifying initial B-spline curve and optimization. The method determines the number and the position of control points such that the initial B-spline curve is very close to the target curve. The proposed method introduces a length parameter in which this allows us to adjust the number of the control points and increases the precision of the initial B-spline curve. Afterwards, the scaled BFGS algorithm is used to optimize the control points and the foot points simultaneously and generates the final curve. Furthermore, we present a new procedure to insert a new control point and repeat the optimization method, if it is necessary to modify the fitting accuracy of the generated B-spline fitting curve. Associated examples are also offered to show that the proposed approach performs accurately for complex shapes with a large number of data points and is able to generate a precise fitting curve with a high degree of approximation.     

Geometric properties estimation from discrete curves using discrete derivatives

Accurate geometric properties estimation from discrete curves is an important problem in many application domains, such as computer vision, pattern recognition, image processing, and geometric modeling. In this paper, we propose a novel method for estimating the geometric properties from discrete curves based on derivative estimation. We develop derivative estimation by defining the derivative of a discrete function at a point, which will be called the discrete derivative. Similarly, the second and higher order discrete derivatives at that point are also defined, and their convergence is demonstrated by theory analysis. These definitions of the different order discrete derivatives provide a simple and reliable way to estimate the derivatives from discrete curves. Based on the discrete derivatives, classical differential geometry can be discretized, and the geometric properties are estimated from discrete curves by using differential geometry theory. The proposed method is independent of any analytic curve and estimates the geometric properties directly from discrete data points, which makes it robust to the geometric shapes of discrete curves. Another advantage of the proposed method is the robustness to noise because of the calculation characteristics of the discrete derivatives. The proposed method is evaluated and compared with other existing methods in the experiments with both synthetic and real discrete curves. The test results show that the proposed method has good performance, and is robust to noise and suitable for different curve shapes.     

带法向约束的隐式T样条曲线重构

目的 隐式曲线能够描述复杂的几何形状和拓扑结构,而传统的隐式B样条曲线的控制网格需要大量多余的控制点满足拓扑约束。有些情况下,获取的数据点不仅包含坐标信息,还包含相应的法向约束条件。针对这个问题,提出了一种带法向约束的隐式T样条曲线重建算法。方法 结合曲率自适应地调整采样点的疏密,利用二叉树及其细分过程从散乱数据点集构造2维T网格;基于隐式T样条函数提出了一种有效的曲线拟合模型。通过加入偏移数据点和光滑项消除额外零水平集,同时加入法向项减小曲线的法向误差,并依据最优化原理将问题转化为线性方程组求解得到控制系数,从而实现隐式曲线的重构。在误差较大的区域进行T网格局部细分,提高重建隐式曲线的精度。结果 实验在3个数据集上与两种方法进行比较,实验结果表明,本文算法的法向误差显著减小,法向平均误差由10^-3数量级缩小为10^-4数量级,法向最大误差由10^-2数量级缩小为10^-3数量级。在重构曲线质量上,消除了额外零水平集。与隐式B样条控制网格相比,3个数据集的T网格的控制点数量只有B样条网格的55.88%、39.80%和47.06%。结论 本文算法能在保证数据点精度的前提下,有效降低法向误差,消除了额外的零水平集。与隐式B样条曲线相比,本文方法减少了控制系数的数量,提高了运算速度。     

Quadratic robust tracking control — A Polynomial Matrix Approach

A quadratic robust tracking problem is solved using a polynomial matrix approach. Because of the possibly unstable mode of the control sequence we propose a new quadratic cost function of error and control sequences to facilitate the optimization. The optimal controller makes the plant output track the reference sequence robustly and minimizes the proposed quadratic cost function. We also present the parametrized set of suboptimal controllers which yield finite costs so that there exists the central optimal controller in the set when the parameter is set to zero. The usefulness of our proposed cost function is demonstrated by simulation examples. Our design procedure has advantages over two other possible approaches: the LQ state-space approach and the Wiener–Hopf approach which may be tried to tackle the same problem. Our approach obviates the need to construct a dynamic observer compared to the state-space approach and it is computationally attractive compared to the Wiener–Hopf approach.     

Local bifurcations analysis of a state-dependent delay differential equation

In this paper, a first-order equation with state-dependent delay and a nonlinear right-hand side is considered. The conditions of the existence and uniqueness of the solution of the initial value problem are supposed to be executed.The task is to study the behavior of solutions of the considered equation in a small neighborhood of its zero equilibrium. The local dynamics depends on real parameters, which are coefficients of the right-hand side decomposition in a Taylor series.The parameter, which is a coefficient at the linear part of this decomposition, has two critical values that determine the stability domain of the zero equilibrium. We introduce a small positive parameter and use the asymptotic method of normal forms in order to investigate local dynamics modifications of the equation near each two critical values. We show that the stability exchange bifurcation occurs in the considered equation near the first of these critical values, and the supercritical Andronov–Hopf bifurcation occurs near the second of these values (provided the sufficient condition is executed). Asymptotic decompositions according to correspondent small parameters are obtained for each stable solution. Next, a logistic equation with state-dependent delay is considered to be an example. The bifurcation parameter of this equation has the only critical value. A simple sufficient condition of the occurrence of the supercritical Andronov–Hopf bifurcation in the considered equation near a critical value has been obtained as a result of applying the method of normal forms.     

曲线曲面逼近与插值的统一表示

为了用一种模型实现从逼近到插值的转换,在多项式空间上构造了含一个参数的调配函数,由之定义了基于4点分段的曲线,该曲线可以理解为由相同的一组控制顶点定义的逼近曲线和插值曲线的线性组合,其中的逼近曲线为3次均匀B样条曲线,插值曲线经过除首末点以外的所有控制点。在均匀参数分割下,曲线具有C2连续性,取特殊参数时可达C3连续。在参数变化过程中,曲线各段起点、终点的位置发生改变,但这些点处的一阶、二阶导矢始终保持不变,即始终与3次B样条曲线相同。曲线形状与端点条件密切相关,而B样条曲线具有良好的保形性,这些综合因素使得曲线在形状变化的过程中始终可以较好地保持控制多边形的特征。采用张量积方法将曲线推广至曲面,曲线曲面图例显示了该方法在造型设计中的有效性。     

Numerical continuation of the solution at bifurcation points of mathematical models

A problem of numerical continuation of the solution set for a system of nonlinear algebraic or transcendental equations with a parameter at some singular points of a curve is considered.     

On the detection of dominant points on digital curves

A parallel algorithm is presented for detecting dominant points on a digital closed curve. The procedure requires no input parameter and remains reliable even when features of multiple sizes are present on the digital curve. The procedure first determines the region of support for each point based on its local properties, then computes measures of relative significance (e.g. curvature) of each point, and finally detects dominant points by a process of nonmaximum suppression. This procedure leads to the observation that the performance of dominant points detection depends not only on the accuracy of the measure of significance, but also on the precise determination of the region of support. This solves the fundamental problem of scale factor selection encountered in various dominant point detection algorithms. The inherent nature of scale-space filtering in the procedure is addressed, and the performance of the procedure is compared to those of several other dominant point detection algorithms, using a number of examples     

Process design in SISO systems with input multiplicity using bifurcation analysis and optimisation

This paper presents an approach using continuation and optimisation methods for modifying a process design to avoid control difficulties caused by input multiplicity. The approach assumes an initial design, with a preassigned SISO control structure, has been obtained and is useful where there is an input multiplicity in the operating region. The condition for input multiplicity is obtained by inflating the state space model with a state representing the locus of the point of zero gain. The multiplicity condition is determined using the bifurcation analysis package, AUTO, which allows the study of the influence of operating conditions and parameters on input multiplicity behaviour to obtain an expression for the point of zero gain as a function of the design and disturbance variables. A process modification problem is formulated within an optimisation framework and solved to determine the minimal design parameter changes necessary to avoid input multiplicity given an assumed maximal disturbance. Results are presented for the application of the algorithm to a CSTR system demonstrating that small changes in some design variables can avoid input multiplicity problems in this case, and that the method can determine the changes necessary.     

Optimal grids for five-axis machining

This paper presents a new grid generation method for tool path planning for five-axis machining based on minimization of the kinematics error. First, the procedure constructs a space-filling curve so that the scallops between the resulting tracks of the tool do not exceed a prescribed tolerance. At the second stage (which is the subject of this paper) a one-dimensional grid along the space-filling curve is generated using direct minimization of the kinematics error. A closed form representation of the kinematics error as a function of locations cutter contact points is derived from the inverse kinematics transformations associated with a particular five-axis machine and obtained through automatic symbolic calculations. The grid of cutter location points is generated so that it minimizes the kinematics error. Numerical and cutting experiments demonstrate that the proposed procedure outperforms distribution of points based on the equi-arc-length principle. Finally, we show that our optimization routine requires less points than that based on sequential point insertion and numerical evaluation of the cost function, such as bisection.     

DFP优化的数据点渐进迭代拟合方法

DFP方法(由Davidon,Fletcher和Powell 3人共同提出)是求解无约束优化问题的一种经典方法,文中指出数据点的拟合问题可转化为无约束优化问题的求解,并基于DFP优化方法给出了一种大规模数据点拟合方法,称之为DFP渐进迭代拟合方法.文中证明了该方法生成的极限曲线为初始数据点的最小二乘拟合曲线;它承袭了经典最小二乘渐进迭代逼近算法的众多优良性质,如具备直观的几何意义、可灵活地拟合大规模数据点、初始控制顶点的选择不影响最终迭代结果等.数值实例进一步表明,同等条件下,文中方法的收敛速度明显优于现有的几种数据点拟合方法.     

Fast computation of equispaced Pareto manifolds and Pareto fronts for multiobjective optimization problems

In this paper, we consider the problem of generating a well sampled discrete representation of the Pareto manifold or the Pareto front corresponding to the equilibrium points of a multi-objective optimization problem. We show how the introduction of simple additional constraints into a continuation procedure produces equispaced points in either of those two sets. Moreover, we describe in detail a novel algorithm for global continuation that requires two orders of magnitude less function evaluations than evolutionary algorithms commonly used to solve this problem. The performance of the methods is demonstrated on problems from the current literature.     

曲线数据压缩算法的研究及应用

针对经典的道格拉斯-普克数据压缩算法存在递归计算效率低、阈值选取不确定等不足，提出了一种改进的特征点提取方法，该算法通过直方图统计数据点的频数，根据数据点到基线的距离、数据点与相邻数据点间的夹角，考虑数据点的“孤立性”和频数，利用熵值法确定最终评价值，自动按照给定数据压缩率进行曲线数据压缩.在MATLAB上进行了仿真实验，利用自主研发的控制系统平台，对进油计量阀流量特性进行增量自学习，并在油泵台架和发动机台架上完成了相应的实验.实验结果表明，本算法可以有效的对数据进行压缩处理，满足测量系统和控制系统的数据压缩需求.     

Brachistochrone with dry and arbitrary viscous friction

The brachistochrone problem in the case of dry (Coulomb) and viscous friction with the coefficient that arbitrarily depends on speed is solved. According to the principle of constraint release, the normal component of the supporting curve is used as control. The standard problem of the fastest descent from a given initial point to a given terminal point assuming that the initial velocity is zero is formulated. The Okhotsimskii-Pontryagin method is used to analyze the differential of the objective function. Necessary optimality conditions are found, and a formula for the optimal control that does not involve adjoint variables is derived from them. Differential equations that allow one to obtain extremals by solving a Cauchy problem are set up. Properties of these equations are investigated. A class of simple brachistochrones is distinguished, for which singular points constituting the terminal curve and the reachability domain in the vertical plane are found. Conditions for the existence of zero controls are obtained. For some friction laws, numerical results demonstrating the shape of the determined brachistochrones and optimal time are presented.