全局优化问题的一个无参数填充函数算法

填充函数法是求解全局优化问题的一种有效的确定性算法,方法的关键在于填充函数的构造.对于一般无约束优化问题提出了一个新的无参数填充函数,通过定义证明了此填充函数能保持填充性质.利用其理论性质设计了相应的算法并对几个经典的算例进行了数值实验,实验结果表明算法有效可行.     

两类新的填充函数

给出了填充函数的一个新的定义,并在此基础上,构造了两类新的填充函数,之后对其性质进行了分析和讨论.最后基于构造的第二类填充函数,建立了一种全局优化算法,并对该算法进行了数值试验.数值结果表明该填充函数算法是可行有效的.     

求全局最优化问题的一种新定义的填充函数

提出了一种新的填充函数定义和填充函数,这种填充函数只含有一个参数且可以用来寻找全局优化问题的最优点.经过理论分析提出了一种新的填充函数算法.数值实验验证了此算法的有效性.     

全局最优化问题的一个无参数的填充函数算法

本文研究了全局最优化问题.利用构造填充函数的方法,提出了一个新的无参数填充函数,它是目标函数的一个明确表达式.得到了一个新的无参数填充函数算法,数值试验结果表明该填充函数算法是有效的,从而推广了填充函数算法在求解全局最优化问题方面的应用.     

求解带箱式约束全局优化问题的滤子填充函数方法

提出一个基于滤子技术的填充函数算法, 用于求解带箱式约束的非凸全局优化问题. 填充函数算法是求解全局优化问题的有效方法之一, 而滤子技术以其良好的数值效果广泛应用于局部优化算法中. 为优化填充函数方法, 应用滤子来监控迭代过程. 首先给出一个新的填充函数并讨论了其特性, 在此基础上提出了理论算法及算法性质. 最后列出数值实验结果以说明算法的有效性.     

一个无参数的填充函数算法

自从1990年Ge R.P.教授在文章【A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables[J].Math.Programming,1990,46:191-204】中提出了求全局最优化的填充函数算法以来,此类算法的有效性一直受到调整参数的困扰,在上述文章最后他也期待出现无参数的填充函数.作为一种尝试,本文提出了一种新的无参数的填充函数,并在此基础上,构造出一个无参数填充函数算法.数值试验证明该算法是有效的,同时与已有的填充函数算法比较具有计算量小的优势.     

一个新的非线性整数规划问题的单参数填充函数算法

非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法.构造一个新的单参数填充函数,分析并证明了其填充性质;然后,基于该填充函数并结合离散最速下降法提出了一种新的填充函数算法;最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的.     

约束优化问题的单参数填充函数算法

本文研究约束优化问题的全局优化确定性方法.基于填充函数的定义,具体构造出了一个新的单参数填充函数并做了相关理论证明.结合SQP和BFGS局部极小化算法设计了新的填充函数全局优化算法.数值实验表明,该算法可行有效,具有良好的全局寻优能力.     

一类关于非光滑全局优化的双参数填充函数

为在有界闭集上寻找非光滑函数的全局极小点,本文在文献[12]的基础上提出了一个改进的填充函数定义,然后给出了一个新的双参数填充函数.讨论了所给填充函数的理论和数值性质并设计了相应的算法.分析表明所给填充函数对参数的选择优于相关文献中的结果.数值实验表明,本文所给出的新的填充函数算法是有效的.     

非线性整数规划的一个新的无参数填充函数算法

离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的.     

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.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

约束装箱问题的混合遗传算法求解

本将最佳适应法和遗传算法相结合，提出了一种新的启发式混合遗传算法对具有时间约束的装箱问题进行求解，给出了具体的算法步骤，试算结果表明基于启发式算法的混合遗传算法适合于求解各种约束条件下的大规模装箱问题。     

A DIRECT SEARCH FRAME-BASED CONJUGATE GRADIENTS METHOD

A derivative-free frame-based conjugate gradients algorithm is presented.Convergenceis shown for C~1 functions,and this is verified in numerical trials.The algorithm is tested ona variety of low dimensional problems,some of which are ill-conditioned,and is also testedon problems of high dimension.Numerical results show that the algorithm is effectiveon both classes of problems.The results are compared with those from a discrete quasi-Newton method,showing that the conjugate gradients algorithm is competitive.Thealgorithm exhibits the conjugate gradients speed-up on problems for which the Hessian atthe solution has repeated or clustered eigenvalues.The algorithm is easily parallelizable.     

Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest and evaluate an optimization procedure which specializes in solving a wide variety of optimization problems. The proposed algorithm is designed as a generic multi-objective, multi-optima optimizer. Care has been taken while designing the algorithm such that it automatically degenerates to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-optimal problems, single-objective multi-optima problems and multi-objective uni-optimal problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems chosen from the literature. Because of its efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

A New Quadratic Semi-infinite Programming Algorithm Based on Dual Parametrization

The so called dual parameterization method for quadratic semi-infinite programming (SIP) problems is developed recently. A dual parameterization algorithm is also proposed for numerical solution of such problems. In this paper, we present and improved adaptive algorithm for quadratic SIP problems with positive definite objective and multiple linear infinite constraints. In each iteration of the new algorithm, only a quadratic programming problem with a limited dimension and a limited number of constraints is required to be solved. Furthermore, convergence result is given. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

A partial enumeration algorithm for pure nonlinear integer programming

In this paper, a partial enumeration algorithm is developed for a class of pure IP problems. Then, a computational algorithm, named PE_SPEEDUP (partial enumeration speedup), has been developed to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many pure IP problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed algorithm and the PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.