线性约束凸规划的一个新原-对偶路径-跟踪内点算法

In this paper, a primal-dual path-following interior-point algorithm for linearly constrained convex optimization （LCCO） is presented. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, only full-Newton steps are used. Finally, the favorable polynomial complexity bound for the algorithm with the small-update method is deserved, namely, O（√nlog n/ε）.     

凸二次规划的一个新原-对偶内点算法

In this paper, a new primal-dual interior-point algorithm for convex quadratic optimization (CQO) based on a kernel function is presented. The proposed function has some properties that are easy for checking. These properties enable us to improve the polynomial complexity bound of a large-update interior-point method (IPM) to O (√nlognlogn/ε), which is the currently best known polynomial complexity bound for the algorithm with the large-update method. Numerical tests were conducted to investigate the behavior of the algorithm with different parameters p, q and θ, where p is the growth degree parameter, q is the barrier degree of the kernel function and θ is the barrier update parameter.     

一类关于半正定规划的多项式原对偶内点算法

1 Introduction Interior-point methods (IPMs) for semidefinite opti-mization (SDO) have been studied intensively,due totheir polynomial complexity and practical efficiency.In the past decade , SDO has become a popular re-search area in mathematical programming when it be-came clear that the algorithm for linear opti mization(LO) can often be extended to the more general SDOcase. Other two factors are also responsible for thisincreasing interest in SDO. Firstly, SDO has a wideapplication…     

优化问题的新步长法则

The step-size procedure is very important for solving optimization problems. The Armijo step-size rule, the Armijo-Goldstein step-size rule and the Wolfe-Powell step-size rule are three well-known line search methods. On the basis of the above three types of line search methods and the idea of the proximal point methods, a new class of step-size rules was proposed. Instead of a single objective function f, f ＋1/2（x - xk）^TBk（x-Xk） was used as the merit function in iteration k, where Sk is a given symmetric positive definite matrix. The existence of the steplength for the new rules was proved. Some convergence properties were also discussed.     

用于线性优化的基于核函数的动态步长原-对偶内点算法

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.     

Prime-composition approach to Ramanujan-Fourier transform computation

Ramanujan sums （RS） and their Fourier transforms have attracted more and more attention in signal processing in recent years. Due to their non-periodic and non-uniform spectrum, RS are widely used in low-frequency noise processing, Doppler spectrum estimation and time-frequency analysis. However, the traditional method for calculating RS values is rather complex since it requires two numbers＇ factorization in two arithmetic functions. For a length-n vector, its Ramanujan-Fourier transform usually involves a series of RS values which will occupy O（n2） memory units. Thus, in this paper an approach based on prime-composition is proposed to reduce the complexity of RS calculation to O（n）. Meanwhile, the complexity of Ramanujan-Fourier transform can be further reduced from O（n2） to O（n In（In（n））） .     

Simulation of scattering in dense medium by Monte Carlo method

We present a Monte Carlo （MC） method to simulate the scattering for medium within randomly distributed particles, discuss the convergence of this method by varying the size parameter ka. volume parameter η and calculation parameter Ni, then compare this method with the classical iteration method with the same parameters. The calculation results showed that this method has good convergence and accords with the iteration method while consuming less CPU time. At the end of this paper, this method is used to discuss the visual light scatter in the c-Si/α-Si films.     

无约束全局最优化中的无参数填充函数

The filled function method is an approach for finding a global minimum of multi-dimensional functions.With more and more relevant research,it becomes a promising way used in unconstrained global optimization.Some filled functions with one or two parameters have already been suggested.However,there is no certain criterion to choose a parameter appropriately.In this paper,a parameter-free filled function was proposed.The definition of the original filled function and assumptions of the objective function given by Ge were improved according to the presented parameter-free filled function.The algorithm and numerical results of test functions were reported.Conclusions were drawn in the end.     

A practical iterative two-view metric reconstruction with uncalibrated cameras

This paper presents a practical iterative algorithm for two-view metric reconstruction without any prior knowledge about the scene and motion in a nonsingular geometry configuration. The principal point is assumed to locate at the image center with zero skew and the same aspect ratio, and the interior parameters are fixed, so the self-calibration becomes focal-length cali- bration. Existing focal length calibration methods are direct solutions of a quadric composed of fundamental matrix, which are sensitive to noise. A quaternion-based linear iterative Least-Square Method is proposed in this paper, and one-dimensional searching for optimal focal length in a constrained region instead of solving optimization problems with inequality constraints is applied to simplify the computation complexity, then unique rotational matrix and translate vector are recovered. Experiments with simulation data and real images are given to verify the algorithm.     

Memetic algorithms-based neural network learning for basic oxygen furnace endpoint prediction

Based on the critical position of the endpoint quality prediction for basic oxygen furnaces （BOFs） in steelmaking, and the latest results in computational intelligence （C1）, this paper deals with the development of a novel memetic algorithm （MA） for neural network （NN） lcarnmg. Included in this is the integration of extremal optimization （EO） and Levenberg-Marquardt （LM） pradicnt search, and its application in BOF endpoint quality prediction. The fundamental analysis reveals that the proposed EO-LM algorithm may provide superior performance in generalization, computation efficiency, and avoid local minima, compared to traditional NN learning methods. Experimental results with production-scale BOF data show that the proposed method can effectively improve the NN model for BOF endpoint quality prediction.     

用矩阵近似分解方法求解第二类积分方程

基于区域分解和多项式插值，对积分算子进行离散，得到高精确度的近似离散矩阵．这一方法适应于核函数为光滑、振动较小、只有有限弱奇点的情形．如果采用ｎ个离散点，近似矩阵可以经过Ｏ（ｎ）次计算得到，存储也只要Ｏ（ｎ）．矩阵－向量相乘的计算量为Ｏ（ｎｌｏｇｎ）．所以，此方法特别适合共轭梯度类型算法     

Reduction of truss topology optimization

A reduction of truss topology design problem formulated by semidefinite optimization (SDO) is considered. The finite groups and their representations are introduced to reduce the stiffness and mass matrices of truss in size. Numerical results are given for both the original problem and the reduced problem to make a comparison.     

在模2~k剩余类环中求逆元的左位移算法

讨论在模n=2k剩余类环上求逆元的算法.文中引入阶的概念.利用元素的阶,文中给出求逆元的左位移算法,该算法时间复杂度为O(log2n)=O(k).     

对称锥上基于宽邻域的预估矫正算法

在对称锥上提出了一种新的Mehrotra型预估矫正算法,每部迭代都跟踪宽领域N-∞（τ）,但不一定属于该邻域,但是总在更宽的邻域N（τ,β）,我们给出了比原邻域更好的复杂性O（√nL）,在对称锥规划上,它具有路径跟踪算法最好的复杂性．     

凸二次规划问题基于核函数的全牛顿步内点算法

针对凸二次规划问题,构造了新的核函数.通过构造的核函数来确定搜索方向和逼近度量,接着给出了求解凸二次规划问题的全牛顿步内点算法,最后给出了算法的复杂性界.     

一种新的求解P＊（k）阵原始一对偶路径跟踪算法

对P＊（k）阵线性互补问题提出了一种新的原始一对偶路径跟踪算法,算法是基于一种新的工具找到搜寻方向和中心路径邻域,并证明了此算法的迭代复杂性为O（√n log [n＋4（1＋k）δ2/ε] μ0）,与目前最好的算法迭代复杂性一致。     

Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods. Project supported by the National Natural Science Foundation of China (Grant No.10771133), the Shanghai Leading Academic Discipline Project (Grant No.S30101), and the Research Foundation for the Doctoral Program of Higher Education (Grant No.200802800010)