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

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

A Fast Algorithm for S-Regression Estimates

Equivariant high-breakdown point regression estimates are computationally expensive, and the corresponding algorithms become unfeasible for moderately large number of regressors. One important advance to improve the computational speed of one such estimator is the fast-LTS algorithm. This article proposes an analogous algorithm for computing S-estimates. The new algorithm, that we call “fast-S”, is also based on a “local improvement” step of the resampling initial candidates. This allows for a substantial reduction of the number of candidates required to obtain a good approximation to the optimal solution. We performed a simulation study which shows that S-estimators computed with the fast-S algorithm compare favorably to the LTS-estimators computed with the fast-LTS algorithm.     

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.     

A genetic algorithm for solving linear fractional bilevel problems

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. In this paper a genetic algorithm is proposed for the class of bilevel problems in which both level objective functions are linear fractional and the common constraint region is a bounded polyhedron. The algorithm associates chromosomes with extreme points of the polyhedron and searches for a feasible solution close to the optimal solution by proposing efficient crossover and mutation procedures. The computational study shows a good performance of the algorithm, both in terms of solution quality and computational time.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

Solving Stochastic Linear Programs with Restricted Recourse Using Interior Point Methods

In this paper we present a specialized matrix factorization procedure for computing the dual step in a primal-dual path-following interior point algorithm for solving two-stage stochastic linear programs with restricted recourse. The algorithm, based on the Birge-Qi factorization technique, takes advantage of both the dual block-angular structure of the constraint matrix and of the special structure of the second-stage matrices involved in the model. Extensive computational experiments on a set of test problems have been conducted in order to evaluate the performance of the developed code. The results are very promising, showing that the code is competitive with state-of-the-art optimizers.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

PPA BASED PREDICTION-CORRECTION METHODS FOR MONOTONE VARIATIONAL INEQUALITIES

In this paper we study the proximal point algorithm (PPA) based prediction-correction (PC) methods for monotone variational inequalities. Each iteration of these methods consists of a prediction and a correction. The predictors are produced by inexact PPA steps. The new iterates are then updated by a correction using the PPA formula. We present two profit functions which serve two purposes: First we show that the profit functions are tight lower bounds of the improvements obtained in each iteration. Based on this conclusion we obtain the convergence inexactness restrictions for the prediction step. Second we show that the profit functions are quadratically dependent upon the step lengths, thus the optimal step lengths are obtained in the correction step. In the last part of the paper we compare the strengths of different methods based on their inexactness restrictions.     

The analysis of the number of fixed points in the key extending algorithm of RC4

The probabilities of the state transitions of the initial value So in the S table of RC4 are described by a kind of bistochastic matrices, and then a computational formula for such bistochastic matrices is given, by which the mathematical expectation of the number of fixed points in the key extending algorithm of RC4 is obtained. As a result, a statistical weakness of the key extending algorithm of RC4 is presented.     

A new approach for achievement of the equilibrium efficient frontier with fixed-sum outputs

In a recent paper, Yang et al developed an algorithm based on the extended minimal adjustment strategy and the equilibrium competition strategy to achieve a common equilibrium efficient frontier. However, the computational burden of their algorithm is challenging when a sample contains many inefficient decision-making units (DMUs). In this paper, we propose a linear programming model that can achieve a common equilibrium efficient frontier in a single step, regardless of the number of inefficient DMUs. Furthermore, we demonstrate the existence and the non-uniqueness of the equilibrium efficient frontier and identify its shortcomings through an example. Next, we extend our approach to incorporate weight restrictions to indicate the relative importance of the different inputs and outputs and introduce the secondary goal of minimizing the maximal relative deviation for each fixed-sum output, which can result in a unique equilibrium efficient frontier.     

一类非线性规划问题的信赖域内点算法

本文对约束为线性的一类非线性优化问题提出了一种依赖域内点算法的,其中约束非负性要求一个仿射变换阵实现,其子问题变成了与个带仿射变换的线性等式约束的求解,我们证明了算法的有效性,在一定条件下证明了由算法产生的序列收敛到优化总理２的一阶稳定,点。     

Finding a representative nondominated set for multi-objective mixed integer programs

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.     

The sphere method and the robustness of the ellipsoid algorithm

We present a method for implementing the ellipsoid algorithm, whose basic iterative step is a linear row manipulation on the matrix of inequalities. This step is somewhat similar to a simplex iteration, and may give a clue to the relation between the two algorithms. Geometrically, the step amounts to performing affine transformations which map the ellipsoids onto a fixed sphere. The method was tried successfully on linear programs with up to 50 variables, some of which required more than 24 000 iterations. Geometrical properties of the iteration suggest that the ellipsoid algorithm is numerically robust, which is supported by our computational experience.     

An algorithm for determining all extreme points of a convex polytope

An algorithm for determining all the extreme points of a convex polytope associated with a set of linear constraints, via the computation of basic feasible solutions to the constraints, is presented. The algorithm is based on the product-form revised simplex method and as such can be readily linked onto standard linear programming codes. Applications of such an algorithm are reviewed and limited computational experience given.     

Full Nesterov-Todd step infeasible interior-point method for symmetric optimization

Euclidean Jordan algebras were proved more than a decade ago to be an indispensable tool in the unified study of interior-point methods. By using it, we generalize the full-Newton step infeasible interior-point method for linear optimization of Roos [Roos, C., 2006. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM Journal on Optimization. 16 (4), 1110-1136 (electronic)] to symmetric optimization. This unifies the analysis for linear, second-order cone and semidefinite optimizations.     

A novel piecewise linear classifier based on polyhedral conic and max–min separabilities

In this paper, an algorithm for finding piecewise linear boundaries between pattern classes is developed. This algorithm consists of two main stages. In the first stage, a polyhedral conic set is used to identify data points which lie inside their classes, and in the second stage we exclude those points to compute a piecewise linear boundary using the remaining data points. Piecewise linear boundaries are computed incrementally starting with one hyperplane. Such an approach allows one to significantly reduce the computational effort in many large data sets. Results of numerical experiments are reported. These results demonstrate that the new algorithm consistently produces a good test set accuracy on most data sets comparing with a number of other mainstream classifiers.     

一个改进的线性规划预校正算法

本文我们提出了一个改进型线性规划预校正算法，我们的预步和校正步方向与Mizuno－Todd-Ye[4]的方向是不同的．我们的算法的迭代复杂度为，然而在校正步，我们降低对偶间隙一个常数因子．     

A parallel multiple reference point approach for multi-objective optimization

This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.     

Resource-optimal control of linear systems

A numerical method for minimizing the resource consumption for linear dynamical systems is proposed. It is based on forming a finite-time control that steers the linear system from an arbitrary initial state to the desired terminal state in a given fixed time; this control gives an approximate solution of the problem. It is shown that the structure of the finite-time control makes it possible to determine the structure of the resource-optimal control. A method for determining an initial approximation is described, and an iterative algorithm for calculating the optimal control is proposed. A system of linear algebraic equations relating the deviations of the initial conditions in the adjoint system to the deviations of the phase coordinates from the prescribed terminal state at the terminal point in time is obtained. A computational algorithm is described. The radius of local convergence is found and the quadratic rate of convergence is established. It is proved that the computational procedure and the sequence of controls converge to the resource-optimal control.     

一类变分不等式问题的信赖域算法

基于J.M.Peng研究一类变分不等式问题（简记为VIP）时所提出的价值函数，本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是：它在每步迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。这样，计算的复杂性一般来说可降低。在通常的假设条件下，文中还证明了算法的整体收敛性。最后，在梯度是半光滑和约束是矩形域的假设下，该算法还是超线性收敛的。