3-分片线性NCP函数的滤子QP-free算法

本文定义一个3-分片线性的NCP函数,并对非线性约束优化问题,提出了带有这分片NCP函数的QP-free非可行域算法.根据优化问题的一阶KKT条件,利用乘子和NCP函数,得到非光滑方程,本文给出一个非光滑方程的迭代算法.这算法包含原始-对偶变量,在局部意义下,可看成关于一阶KKT最优条件的的扰动拟牛顿迭代算法.在线性搜索时,这算法采用滤子方法.本文给出的算法是可实现的并具有全局收敛性,且在适当假设下具有超线性收敛性.     

分片线性NCP函数滤子QP-free算法

本文定义了分片线性NCP函数,并对非线性约束优化问题,提出了带有这分片NCP函数的QP-free非可行域算法.利用优化问题的一阶KKT条件,乘子和NCP函数,得到对应的非光滑方程组.本文给出解这非光滑方程组算法,它包含原始-对偶变量,在局部意义下,可看成关扰动牛顿-拟牛顿迭代算法.在线性搜索时,这算法采用滤子方法.本文给出的算法是可实现的并具有全局收敛性,在适当假设下算法具有超线性收敛性.     

带有P0函数的非线性互补问题的一个新的非内点连续算法

研究带有P₀函数的非线性互补问题. 基于一个新的光滑函数, 把问题近似成参数化的光滑方程组, 并且给出一个新的非内点连续算法. 所给算法在每步迭代只需要求解一个线性方程组和执行一次Armijo类型的线搜索. 在不需要严格互补条件的情况下, 证明了算法是全局收敛和超线性收敛的. 并且, 在一个较弱的条件下该算法具有局部二阶收敛性. 数值实验证实了算法的可行性和有效性.     

非光滑非线性互补问题的牛顿法

研究了非光滑的非线性互补问题. 首先将非光滑的非线性互补问题转化为一个非光滑方程组,然后用牛顿法求解这个非光滑方程组. 在该牛顿法中,每次迭代只需一个原始函数B-微分中的一个元素. 最后证明了该牛顿法的超线性收敛性.     

解非线性互补问题的光滑牛顿方法

由于退化解会导致再生方程的奇异性,非线性互补问题的求解通常采用基于半光滑技术的广义牛顿法.基于2-正则性的概念,提出了一类利用光滑互补函数求解互补问题的光滑牛顿算法.算法采用积极集技术,能在解的附近估计出退化指标,并把原问题降阶为一个非奇异方程组,从而保证了迭代效率.算法具有整体收敛性和局部超线性收敛性,数值实验显示算法是有效的.     

无罚函数和滤子的QP-free非可行域方法

提出了求解光滑不等式约束最优化问题的无罚函数和无滤子QP-free非可行域方法. 通过乘子和非线性互补函数, 构造一个等价于原约束问题一阶KKT条件的非光滑方程组. 在此基础上, 通过牛顿-拟牛顿迭代得到满足KKT最优性条件的解, 在迭代中采用了无罚函数和无滤子线搜索方法, 并证明该算法是可实现,具有全局收敛性. 另外, 在较弱条件下可以证明该方法具有超线性收敛性.     

求解无限维非线性互补问题的光滑化牛顿法

研究一类无限维非线性互补问题的光滑化牛顿法.借助于非线性互补函数,将无限维非线性互补问题转化为一个非光滑算子方程.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化牛顿法具有超线性收敛性.     

一个光滑化函数的两个性质

本文考虑文[6]中提出的光滑化函数,证明了：该光滑化函数拥有两个在求解变分不等式和互补问题的非内部连续化算法的全局线性和局部超线性（或二次）收敛性分析中非常有用的两个性质。     

新的滤子方法

本文定义了一种新的滤子方法,并提出了求解光滑不等式约束最优化问题的滤子QP-free非可行域方法.通过乘子和分片线性非线性互补函数,构造一个等价于原约束问题一阶KKT条件的非光滑方程组.在此基础上,通过牛顿-拟牛顿迭代得到满足KKT最优条件的解,在迭代中采用了滤子线搜索方法,证明了该算法是可实现,并具有全局收敛性.另外,在较弱条件下可以证明该方法具有超线性收敛性.     

光滑化牛顿法求解广义绝对值方程

本文研究了广义绝对值方程Ax-|Bx-c|=b的求解问题.利用一个光滑的NCP函数将广义绝对值方程转化为等价的光滑方程组,获得了算法全局超线性收敛性的结果.并给出数值实验验证了理论分析及算法的有效性.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Investigation of temperature parallel simulated annealing for optimizing continuous functions with application to hyperspectral tomography

The simulated annealing (SA) algorithm is a well-established optimization technique which has found applications in many research areas. However, the SA algorithm is limited in its application due to the high computational cost and the difficulties in determining the annealing schedule. This paper demonstrates that the temperature parallel simulated annealing (TPSA) algorithm, a parallel implementation of the SA algorithm, shows great promise to overcome these limitations when applied to continuous functions. The TPSA algorithm greatly reduces the computational time due to its parallel nature, and avoids the determination of the annealing schedule by fixing the temperatures during the annealing process. The main contributions of this paper are threefold. First, this paper explains a simple and effective way to determine the temperatures by applying the concept of critical temperature (T_C). Second, this paper presents systematic tests of the TPSA algorithm on various continuous functions, demonstrating comparable performance as well-established sequential SA algorithms. Third, this paper demonstrates the application of the TPSA algorithm on a difficult practical inverse problem, namely the hyperspectral tomography problem. The results and conclusions presented in this work provide are expected to be useful for the further development and expanded applications of the TPSA algorithm.     

A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties

In this paper, a hybrid genetic algorithm is developed to solve the single machine scheduling problem with the objective to minimize the weighted sum of earliness and tardiness costs. First, dominance properties of (the conditions on) the optimal schedule are developed based on the switching of two adjacent jobs i and j. These dominance properties are only necessary conditions and not sufficient conditions for any given schedule to be optimal. Therefore, these dominance properties are further embedded in the genetic algorithm and we call it genetic algorithm with dominance properties (GADP). This GADP is a hybrid genetic algorithm. The initial populations of schedules in the genetic algorithm are generated using these dominance properties. GA can further improve the performance of these initial solutions after the evolving procedures. The performances of hybrid genetic algorithm (GADP) have been compared with simple genetic algorithm (SGA) using benchmark instances. It is shown that this hybrid genetic algorithm (GADP) performs very well when compared with DP or SGA alone.     

A constrained optimization approach to solving certain systems of convex equations

This research presents a new constrained optimization approach for solving systems of nonlinear equations. Particular advantages are realized when all of the equations are convex. For example, a global algorithm for finding the zero of a convex real-valued function of one variable is developed. If the algorithm terminates finitely, then either the algorithm has computed a zero or determined that none exists; if an infinite sequence is generated, either that sequence converges to a zero or again no zero exists. For solving n-dimensional convex equations, the constrained optimization algorithm has the capability of determining that the system of equations has no solution. Global convergence of the algorithm is established under weaker conditions than previously known and, in this case, the algorithm reduces to Newton’s method together with a constrained line search at each iteration. It is also shown how this approach has led to a new algorithm for solving the linear complementarity problem.     

A parametric approach for solving a class of generalized quadratic-transformable rank-two nonconvex programs

The aim of this paper is to propose a solution algorithm for a particular class of rank-two nonconvex programs having a polyhedral feasible region. The algorithm is based on the so-called “optimal level solutions” method. Various global optimality conditions are discussed and implemented in order to improve the efficiency of the algorithm.     

The black-box Niederreiter algorithm and its implementation over the binary field

The most time-consuming part of the Niederreiter algorithm for factoring univariate polynomials over finite fields is the computation of elements of the nullspace of a certain matrix. This paper describes the so-called ``black-box' Niederreiter algorithm, in which these elements are found by using a method developed by Wiedemann. The main advantages over an approach based on Gaussian elimination are that the matrix does not have to be stored in memory and that the computational complexity of this approach is lower. The black-box Niederreiter algorithm for factoring polynomials over the binary field was implemented in the C programming language, and benchmarks for factoring high-degree polynomials over this field are presented. These benchmarks include timings for both a sequential implementation and a parallel implementation running on a small cluster of workstations. In addition, the Wan algorithm, which was recently introduced, is described, and connections between (implementation aspects of) Wan's and Niederreiter's algorithm are given.

     

Delaunay triangulation and the convex hull ofn points in expected linear time

An algorithm is presented which produces a Delaunay triangulation ofn points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull ofn points in the Euclidean plane.     

Minimax feature selection problem for constructing a classifier using support vector machines

A minimax feature selection problem for constructing a classifier using support vector machines is considered. Properties of the solutions of this problem are analyzed. An improvement of the saddle point search algorithm based on extending the bound for the step parameter is proposed. A new nondifferential optimization algorithm is developed that, together with the saddle point search algorithm, forms a hybrid feature selection algorithm. The efficiency of the algorithm for computing Dykstra’s projections as applied for the feature selection problem is experimentally estimated.     

Symplectic Householder transformations for a QR-like decomposition,a geometric and algebraic approaches

The aim of this paper is to show how geometric and algebraic approaches lead us to a new symplectic elementary transformations: the 2-D symplectic Householder transformations. Their features are studied in details. Their interesting properties allow us to construct a new algorithm for computing a SR factorization. This algorithm is based only on these 2-D symplectic Householder transformations. Its new features are highlighted. The study shows that, in the symplectic case, the new algorithm is the corresponding one to the classical QR factorization algorithm, via the Householder transformations. Some numerical experiments are given.     

解P_0非线性互补问题的光滑Levenberg-Marquardt方法

本文研究了一个P0非线性互补问题.利用信赖域技术获得了求解该问题的光滑Levenberg-Marquardt算法,该算法在一定条件下具有全局性.利用局部误差界还获得了该算法的超线性和二次收敛.数值结果表明该算法是有效的.