Algorithms for ordering unorganized points along parametrized curves

Letn points be given on several arcs of curve. The equations of these curves are unknown. We give two algorithms, based on geometrical criteria, that allow to determine an order on these points: the order given by the curvilinear abscissa. The computational complexity of these algorithms is inO(n logn) and the space complexity inO(n).     

Bisectors of linearly separable sets

A bisector of two sets is the set of points equidistant form them. Bisectors arise naturally in several areas of computational geometry. We show that bisectors of weakly linearly separable sets inE ^d have many properties of interest. Among these, the bisector of a restricted class of linearly separated sets is a homeomorphic image of the linear separator. We also give necessary and sufficient conditions for the existence of a particular continuous map from (a portion of) any linear separator to the bisector.     

A tolerant algorithm for linearly constrained optimization calculations

Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with small residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the small residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua.     

A hybrid algorithm for linearly constrained minimax problems

Many real life problems can be stated as a minimax problem, such as economics, finance, management, engineering and other fields, which demonstrate the importance of having reliable methods to tackle minimax problems. In this paper, an algorithm for linearly constrained minimax problems is presented in which we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, it avoids possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Under weaker conditions, the global and superlinear convergence are achieved. Numerical experiments show that the new algorithm is robust and efficient.     

A linearly convergent algorithm for sparse signal reconstruction

For the sparse signal reconstruction problem in compressive sensing, we propose a projection-type algorithm without any backtracking line search based on a new formulation of the problem. Under suitable conditions, global convergence and its linear convergence of the designed algorithm are established. The efficiency of the algorithm is illustrated through some numerical experiments on some sparse signal reconstruction problem.     

A derivative-free algorithm for linearly constrained optimization problems

Based on the NEWUOA algorithm, a new derivative-free algorithm is developed, named LCOBYQA. The main aim of the algorithm is to find a minimizer $x^{*} \in\mathbb{R}^{n}$ of a non-linear function, whose derivatives are unavailable, subject to linear inequality constraints. The algorithm is based on the model of the given function constructed from a set of interpolation points. LCOBYQA is iterative, at each iteration it constructs a quadratic approximation (model) of the objective function that satisfies interpolation conditions, and leaves some freedom in the model. The remaining freedom is resolved by minimizing the Frobenius norm of the change to the second derivative matrix of the model. The model is then minimized by a trust-region subproblem using the conjugate gradient method for a new iterate. At times the new iterate is found from a model iteration, designed to improve the geometry of the interpolation points. Numerical results are presented which show that LCOBYQA works well and is very competing against available model-based derivative-free algorithms.     

Simple singularities of parametrized plane curves in positive characteristic

Let K be an algebraically closed field of characteristic p>0. The aim of the article is to give a classification of simple parametrized plane curve singularities over K. The idea is to give explicitly a class of families of singularities which are not simple such that almost all singularities deform to one of those and show that remaining singularities are simple.     

The embedding of linearly ordered sets

It is shown that if a linearly ordered set B does not contain as subsets sets of order type and ^* then B can be embedded in 2 . We construct an example of a set satisfying the above conditions which cannot be embedded in any 2 if < . Simultaneously we show that for any ordinal, 2 ⁺¹ cannot be embedded in 2 and that there exists at least ₊₁ distinct dense order types of cardinality 2 .Translated from Matematicheskie Zametki, Vol. 11, No. 1, pp. 83–88, January, 1972.In conclusion, I wish to take the opportunity to thank Yu. L. Ershov for kindness and assistance in this work.     

解线约束凸规划的势下降算法

A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints. At each step of the algorithm,a system of linear equations is solved toget a search direction and the Armijo‘s rule is used to determine a stepsize. It is proved that thealgorithm is globally convergent. Computational results are reported.     

Robust fitting of parametric curves

We consider the problem of fitting a parametric curve to a given point cloud (e.g., measurement data). Least-squares approximation, i.e., minimization of the ℓ₂ norm of residuals (the Euclidean distances to the data points), is the most common approach. This is due to its computational simplicity [1]. However, in the case of data that is affected by noise or contains outliers, this is not always the best choice, and other error functions, such as general ℓ_p norms have been considered [2]. We describe an extension of the least-squares approach which leads to Gauss-Newton-type methods for minimizing other, more general functions of the residuals, without increasing the computational costs significantly. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

Kakeya sets of curves

No Abstract. . Received: September 2004 Revision: January 2005 Accepted: January 2005     

A non-parametric method for fitting ROC curves for evaluation of industrial inspection performance

The use of signal detection theory (SDT) in evaluation of the performance of an inspector on certain tasks requires the identification of the receiver operating characteristic (ROC) curve of the inspector. In this paper a functional form, Y = f(X), for the ROC equation is proposed, and two alternative approaches are developed for estimation of its parameters. This method does not require prior assumptions on the statistical distribution of the noise and signal-plus-noise. The application of the method is illustrated by the use of an example data set.     

A trust-region and affine scaling algorithm for linearly constrained optimization

A new trust-region and affine scaling algorithm for linearly constrained optimization is presented in this paper. Under no nondegenerate assumption, we prove that any limit point of the sequence generated by the new algorithm satisfies the first order necessary condition and there exists at least one limit point of the sequence which satisfies the second order necessary condition. Some preliminary numerical experiments are reported. The work was done while visiting Institute of Applied Mathematics, AMSS, CAS.     

An expanding system of linearly closed sets

In this note it is proved that if an open cube in the Euclidean space Rⁿ can be represented in the form of the union of an expanding system of linearly closed sets, then at least one of them has an interior point. This result is applied to the investigation of real-valued functions of several variables.Translated from Matematicheskie Zametki, Vol. 19, No. 1, pp. 67–84, January, 1976.     

Some topological properties of the solution sets of parametrized minimax problems

Sufficient conditions are given to guarantee the closedness and uniform boundedness of the solution sets corresponding to a pair of dual parametrized minimax problems. The parameter of the minimax problems belongs to a metrizable space and affects not only the objective function, but also the feasible sets.This research was supported in part by Fondo Nacional de Ciencias, Proyecto No. 01273.     

A super-linear convergent gradient projection type algorithm for linearly constrained problems

A new super-linear convergent gradient projection type algorithm for linearly constrained problems is presented. This algorithm is more practical than the algorithm presented in [5].     

A NEW GENERALIZED GRADIENT PROJECTION TYPEALGORITHM FOR LINEARLY CONSTRAINED PROBLEMS

In this paper, we provide a new generalized gradient projection algorithm for nonlinear programming problems with linear constraints. This algorithm has simple structure and is very practical and stable. Under the weaker assumptions, we have proved the global convergence of our algorithm.