整数规划的新算法

整数规划是NP困难的经典问题之一，将传统的二分搜索方法推广应用到整数规划的解空间中，提出一种求解整数规划的新算法。当问题变量数固定时，算法的时间复杂性为0(Llog^L)，其中L为问题实例的输入规模，理论分析和实验结果表明：新算法不仅初步解决了目前求解系数呈指数增长的整数规划问题时存在的实质性困难，可直接用于此类大规模问题的求解，同时由于其特剐适合并行处理的算法结构，可望为一般大规模整数规划问题的精确求解提供新的途径。     

求解混合整数非线性规划问题的改进差分进化算法

针对混合整数非线性规划问题的特点,在差分进化算法的变异操作中加入取整运算,提出了一种适合于求解各种混合整数非线性规划问题的改进差分进化算法.同时,采用时变交叉概率因子的方法以提高算法的全局搜索能力和收敛速率.用四个典型测试函数进行了实验研究,实验结果表明,改进的差分进化算法用于求解混合整数非线性规划问题时收敛速度快,精度高,鲁棒性强.     

求解二层规划的混合微粒群算法

对于二层规划问题有许多经典的求解方法，如极点搜索法、分支定界法和罚函数法等。文中给出了基于微粒群算法的二层规划的一种新的求解方法。提出了分别先用单纯形法和内部映射牛顿法的子空间置信域法求解下层规划，然后用微粒群算法求解上层规划的求解方法，这两种混合微粒群算法分别用于求解线性二层规划和非线性二层规划。并结合实例的对比分析，说明了这两种混合微粒群算法求解二层规划的可行性和有效性。     

一种求非线性整数规划最优解的仿生算法

从大自然植物生长中得到启发,提出了一种求解非线性整数规划全局最小解的仿生算法。该算法将植物生长过程及生长模式应用到非线性整数规划问题的求解,能够快速得到最优解。通过对各种不同类型非线性整数规划问题的具体求解,表明了该方法十分有效。     

混合整数非线性规划问题的改进差分进化算法*

提出一种改进差分进化算法求解混合整数非线性规划问题。该算法利用同态映射方法,解决差分进化算法无法直接处理整数决策变量问题;提出改进的自适应交替变异算子,提高算法的搜索性能;提出一种自适应保留不可行解的方法处理约束条件,并对差分进化算法的选择算子进行改进,提出一种直接处理约束条件的新选择算子。六个常用的混合整数非线性规划问题的实验结果表明了该方法的有效性和适用性。     

一类非线性两层规划问题的递阶优化解法

提出一种求解一类非线性两层规划问题的新方法．通过引入解耦向量将非线性两层规划问题分解为独立且易于求解的子问题，利用两级递阶结构第1级求解若干优化的子问题，而在第2级利用第1级求解的结果调整解耦向量．所提出的方法借助于分解一协调原理并按迭代方式最终求得问题的最优解．对于含整数的规划问题，通过连续化处理后也可按该方法方便地求解．算例表明所提出的算法是简便而有效的．     

求解二层规划的混合微粒群算法

对于二层规划问题有许多经典的求解方法,如极点搜索法、分支定界法和罚函数法等。文中给出了基于微粒群算法的二层规划的一种新的求解方法。提出了分别先用单纯形法和内部映射牛顿法的子空间置信域法求解下层规划,然后用微粒群算法求解上层规划的求解方法,这两种混合微粒群算法分别用于求解线性二层规划和非线性二层规划。并结合实例的对比分析,说明了这两种混合微粒群算法求解二层规划的可行性和有效性。     

一种求解混合整数非线性规划问题的模拟退火算法

通过适当处理离散变量，将求解无约束非凸ＮＬＰ问题的高效模拟退火全局优化算法推广到求解一般非凸混合整数非线性规划问题。数值计算结果表明，文中模拟退火算法在适用性、解的质量和计算效率等方面优于其它方法，是求解一般非凸ＭＩＮＬＰ问题的一种有效的全局优化算法。     

非线性整数规划的粒子群优化算法

提出了一种新的粒子群优化算法来求解无约束的整数规划问题，粒子在[0，1]空间内运动，并与整数空间对应。对粒子群优化算法参数的合理选取进行了实验分析，给出了算法参数选取的基本原则。数值试验计算结果表明该方法比较有效，并具有通用性。     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

A Robust Algorithm for Solving Nonlinear Programming Problems

In this paper, we introduce a new algorithm for solving nonlinear programming (NLP) problems. It is an extension of Guo's algorithm [1] which possesses enhanced capabilities for solving NLP problems. These capabilities include: a) extending the variable subspace, b) adding a search process over subspaces and normalized constraints, c) using an adaptive penalty function, and d) adding the ability to deal with integer NLP problems, 0-1 NLP problems, and mixed-integer NLP problems which have equality constraints. These four enhancements increase the capabilities of the algorithm to solve nonlinear programming problems in a more robust and universal way. This paper will present results of numerical experiments which show that the new algorithm is not only more robust and universal than its competitors, but also its performance level is higher than any others in the literature.     

A feasible method for sensor network localization

A nonlinear programming (NLP) model with partial orthogonality constraints, relaxed from the polynomial optimization problem, is proposed and analysed for solving sensor network localization. The NLP model is difficult to solve as the orthogonality constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with this difficulty, we apply the Cayley transform (a Crank–Nicolson-like update scheme) to preserve it. Combining with the gradient descent method, we develop a curvilinear search algorithm, and analyse its convergence. In practice, we accelerate our method by taking nonlinear conjugate gradient method and Barzilai–Borwein steps. Numerical experiments are given to demonstrate the efficiency of the proposed method, for the problems with the number of sensors up to 15,000 and the distance constraints up to 135,817.     

A Hybrid Particle Swarm Branch-and-Bound (HPB) Optimizer for Mixed Discrete Nonlinear Programming

This paper proposes a new algorithm for solving mixed discrete nonlinear programming (MDNLP) problems, designed to efficiently combine particle swarm optimization (PSO), which is a well-known global optimization technique, and branch-and-bound (BB), which is a widely used systematic deterministic algorithm for solving discrete problems. The proposed algorithm combines the global but slow search of PSO with the rapid but local search capabilities of BB, to simultaneously achieve an improved optimization accuracy and a reduced requirement for computational resources. It is capable of handling arbitrary continuous and discrete constraints without the use of a penalty function, which is frequently cumbersome to parameterize. At the same time, it maintains a simple, generic, and easy-to-implement architecture, and it is based on the sequential quadratic programming for solving the NLP subproblems in the BB tree. The performance of the new hybrid PSO–BB architecture algorithm is evaluated against real-world MDNLP benchmark problems, and it is found to be highly competitive compared with existing algorithms.      

Newton-conjugate gradient （CG） augmented Lagrangian method for path constrained dynamic process optimization

In this paper, a Newton-conjugate gradient (CG) augmented Lagrangian method is proposed for solving the path constrained dynamic process optimization problems. The path constraints are simplified as a single final time constraint by using a novel constraint aggregation function. Then, a control vector parameterization (CVP) approach is applied to convert the constraints simplified dynamic optimization problem into a nonlinear programming (NLP) problem with inequality constraints. By constructing an augmented Lagrangian function, the inequality constraints are introduced into the augmented objective function, and a box constrained NLP problem is generated. Then, a linear search Newton-CG approach, also known as truncated Newton (TN) approach, is applied to solve the problem. By constructing the Hamiltonian functions of objective and constraint functions, two adjoint systems are generated to calculate the gradients which are needed in the process of NLP solution. Simulation examples demonstrate the effectiveness of the algorithm.     

Extension of a hybrid Genetic Algorithm for nonlinear programming problems with equality and inequality constraints

As an extension of the hybrid Genetic Algorithm-HGA proposed by Tang et al. (Comput. Math. Appl. 36 (1998) 11), this paper focuses on the critical techniques in the application of the GA to nonlinear programming (NLP) problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible points/chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are proposed to formulate and evaluate the infeasible chromosomes. The extended version of concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain are introduced. Combining the new evaluation functions and weighted gradient direction search into the Genetic Algorithm, an extended hybrid Genetic Algorithm (EHGA) is developed to solve nonlinear programming (NLP) problems with equality and inequality constraints. Simulation shows that this new algorithm is efficient.Scope and purposeNon-linear Programming (NLP) problems with equality and inequality constraints is an important type of constrained optimization problems. Genetic Algorithm (GA) is one of the well known evolutionary computation techniques. In the application of GA to NLP problems, chromosomes randomly generated at the beginning and/or generated by genetic operators during the evolutionary process usually violate the constraints, resulting in infeasible chromosomes. Therefore, the handling of system constraints, particularly the nonlinear equation constraints, and the measurement and evaluation of infeasible chromosomes, are major concerns in GA. Penalty strategy in the construction of fitness function is commonly used to evaluate the infeasible chromosomes in some traditional AG methods. However, this approach essentially narrows down the search space by eliminating all infeasible chromosomes from the evolutionary process, and it may reduce the chances of finding better candidates for the global optimization. In particular, it absolutely ignores the information carried by the infeasible chromosomes itself. Therefore, formulating the infeasible chromosomes by embedding the relevant information into the evaluation function are important when applying GA to NLP.As an extension of the Hybrid Genetic Algorithm-HGA proposed by Tang et al. (1998), this paper focuses on the critical techniques in the application of GA to NLP problems with equality and inequality constraints. Taking into account the equality constraints and embedding the information of infeasible chromosomes into the evaluation function, an extended fuzzy-based methodology and three new evaluation functions are designed to formulate and evaluate the infeasible chromosomes. By introducing an extended version of the concepts of dominated semi-feasible direction (DSFD), feasibility degree (FD₁) of semi-feasible direction, feasibility degree (FD₂) of infeasible points ‘belonging to’ feasible domain, an extended hybrid Genetic Algorithm (EHGA) is developed for solving NLP problems with equality and inequality constraints.     

基于评价函数的遗传算法求解非线性规划问题

针对具有待式约束和非等式约束的非线性规划问题,通过引进准可行方向、主导准可行方向和可行度等概念,提出描述和度量非可行点（梁色体）的新方法;通过嵌入非可行染色体的信息于评价函数,提出３种改进的评价非可行染色体的新方法;基于新的评价函数方法,提出一种沿权重梯度方向变异的遗传算法（ＥＧＡ）。对测试问题的仿真结果表明了ＥＧＡ算法的有效性。     

Wei–Yao–Liu conjugate gradient projection algorithm for nonlinear monotone equations with convex constraints

In this paper, the Wei–Yao–Liu (WYL) conjugate gradient projection algorithm will be studied for nonlinear monotone equations with convex constraints, which can be viewed as an extension of the WYL conjugate gradient method for solving unconstrained optimization problems. These methods can be applied to solving large-scale nonlinear equations due to the low storage requirement. We can obtain global convergence of our algorithm without requiring differentiability in the case that the equation is Lipschitz continuous. The numerical results show that the new algorithm is efficient.     

结合序列线性规划法的混合遗传算法

通过将遗传算法与改进的序列线性规划法相结合，形成混合遗传算法．当迭代点没有发生交叉和变异时，将目标函数和约束条件在迭代点处线性化，为使迭代点邻域仍然满足约束条件，加入软约束项，用线性规划方法进行寻优．该方法具有全局收敛性，不要求迭代点一定为可行点．仿真结果验证了此法的有效性和合理性．     

Applications of mathematical models: An expert system for selecting solution methods for solving nonlinear programming problems

This paper presents an expert system for selecting solution methods for solving nonlinear programming problems. No general method exists for solving nonlinear programming problems in the same manner as the Simplex algorithm solves linear programming problems. Hence to some extent nonlinear programming even today exists as an experimental field of research. It has advanced to this date through the proposal and programming of particular algorithms, examinations of the results of the implementation of the algorithms to problems of interest, and the construction of better algorithms based on the experience gained. Computational experiences of many numerical methods such as direct search methods, method of multipliers, and linear approximation methods have been widely reported in literature int he past two decades. However, there is no unified approach to solve a genral NLP problem.

A small scale expert system has been developed using the Texas Instruments Personal Consultant Plus (PCPLUS) software to provide an organised approach for solving NLP problems. A knowledge base has been constructed to represent the past computational experiences of different solution methods on different classes of NLP problems. The system can be effectively used in conjunction with OPTLIB (1), which is a optimization program library for solving NLP problems. The purpose of the system is to guide inexperienced engineers to choose a proper NLP solution method and to serve as teaching aid. In selecting the methods more stress has been laid on the sure-footedness of the method, than on computational time and storage space requirement to make it more reliable for users. This paper presents the knowledge organisation, rules and the testing results.