【作者】 黎健玲；

【导师】 孙小玲；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2007， 博士

【摘要】 全局优化问题主要研究如何寻找一个非凸优化问题的全局最优解．随着社会的进步以及科学技术的发展，全局最优化广泛应用于企业生产管理、金融工程、工程设计及控制、交通运输、农业预测、国防军事等重要领域．因此研究全局优化问题在理论和应用方面都有重要的意义．本论文主要研究两类特殊结构的全局优化问题——单调优化和不定二次规划．单调优化是指目标函数和约束函数都是单调函数的全局优化问题．把单调优化问题中的变量取值限制为整数，即为离散单调优化问题(通常也称为多维不可分离背包问题)．单调优化问题的目标函数和约束函数不要求是凸的或是可分离的．不定二次规划问题是指目标函数是不定二次函数，约束函数是线性函数或二次函数的全局优化问题．把不定二次规划问题中的变量取值限制为整数，即为整数(离散)不定二次规划问题．本文将着重研究带线性约束的连续和离散不定二次规划问题．本论文分为七章，各章内容简要介绍如下：第一章给出了单调优化和不定二次规划及其离散问题的描述及一些应用模型，同时对本论文的主要工作作了简要介绍．第二章首先介绍了一般全局优化的基本算法，然后介绍文献中连续和离散单调优化及不定二次规划的现有算法．第三章给出了一个求解单调优化问题的精确算法．该算法的框架是分枝定界，并且与区域剖分、凸化、局部搜索三种基本策略相结合．区域剖分就是把区域剖分成若干个子箱的并集，而且这些子箱的并集覆盖了可行域的边界；在每个子箱上使用凸化外逼近方法得到目标函数最优值的上界；再结合局部搜索改进下界．我们对该算法进行了数值实验，数值实验结果表明该算法是有效的，能在合理的时间内求解中小规模的单调优化问题．第四章对离散型的单调优化问题进行研究，提出了一个离散的Polyblock算法，并且在此基础上结合凸化思想，对离散Polyblock算法进行改进，提高了界的质量，从而提高算法效率．数值实验结果表明两个算法是有效的，而且数值比较结果表明改进后的算法对具有较大区域的问题计算效果优于改进前的离散Polyblock算法．第五章给出了一个求不定二次规划问题全局最优解的新算法．首先我们给出了不定二次规划问题的三种下界的确定方法：线性逼近、拉格朗日对偶松弛和凸松弛．然后利用这些下界并结合超长方形的两分法建立一个分枝定界算法．而且我们还证明了经正交变换所得的不定二次可分离问题的凸松弛与拉格朗日对偶松弛是等价的．数值实验结果表明该算法是有效的．第六章给出了不定二次整数规划问题的几种新的下界并且证明了它们之间的关系．首先我们构造了问题的线性下方估计，以及通过D．C．分解构造了问题的两种凸松弛；然后通过矩阵的Cholesky分解把不定二次整数规划化为等价的可分离问题，进而应用对偶分解导出两种拉格朗日对偶界，并建立了凸松弛界和拉格朗日对偶界的关系．本章提出的某些下界估计方法也可以应用到求(连续)不定二次规划问题的算法中．最后，我们在第七章总结了本文的主要工作，并讨论了有待进一步研究的问题．更多还原

【Abstract】 Global optimization aims to find the global optimal solution of a nonconvex optimization problem. With the progress of the modern society and the development of science and technology, global optimization plays an important role in many fields, such as production planning and management, financial engineering, engineering design and control, traffic transportation, agricultural forecast, national defence and so on. The significance of the algorithmic studies on global optimization is therefore evident.In this thesis, two classes of global optimization problems with special structures are studied: monotone optimization problem and indefinite quadratic programming problem. Monotone optimization deals with the problems of optimizing a monotone function subject to monotone constraints. Discrete monotone optimization problem is a monotone optimization problem with all variables restricted to integers. Such problems are also referred to as multi-dimensional nonseparable knapsack problems. The objective function and the constraint functions of a monotone optimization problem are not necessarily convex or separable. Indefinite quadratic programming deals with the problems of optimizing an indefinite quadratic function subject to linear constraints or quadratic constraints. Indefinite quadratic integer (discrete) programming is an indefinite quadratic programming with all variables restricted to integers. In this thesis, we focus on continuous and discrete indefinite quadratic programming with linear constraints.This thesis consists of seven chapters. In Chapter 1, monotone optimization problem, indefinite quadratic programming problem and their discrete versions are formally described. Several examples of applications of continuous and discrete monotone optimization and indefinite quadratic programming are presented. Finally, the main contributions of the thesis are briefly introduced in this chapter. In Chapter 2, some basic solution algorithms for general global optimization problems are first introduced. We then give literature survey of algorithms for continuous and discrete monotone optimization problems and indefinite quadratic programming problems.In Chapter 3, a new exact method for monotone optimization problems is proposed. The method is of branch-and-bound framework that combines three basic strategies: partition, convexification and local search. The partition scheme is used to construct a union of subboxes that covers the boundary of the feasible region. The convexification outer approximation is then applied to each subbox to obtain an upper bound of the objective function on the subbox. The performance of the method can be further improved by incorporating the method with local search procedure. The numerical results show the feasibility and effectiveness of the proposed algorithm, and the algorithm can solve medium size monotone optimization problems in reasonable time.In Chapter 4, we study discrete monotone optimization. A discrete polyblock algorithm is first proposed. The polyblock algorithm is then incorporated with convexification method to improve the efficiency of the algorithm. Numerical results show that the two algorithms are effective for discrete monotone optimization problems and the comparison results indicate that the improved algorithm outperforms the discrete polyblock algorithm for the problems with large domain region.In Chapter 5, we present a new algorithm for finding global solution of indefinite quadratic programming problems. Three lower bounding techniques, linear approximation, Lagrangian dual relaxation and convex relaxation, are derived. A branch-and-bound algorithm based on these lower bounding techniques and rectangular bisection is established. We also show that the convex relaxation of transformed separable indefinite quadratic problem by orthogonal transformation is equivalent to the Lagrangian dual relaxation. Preliminary computational results indicate the effectiveness of the proposed algorithm. In Chapter 6, several new lower bounds are derived for indefinite quadratic integer programming problems and their relations are established. We first construct convex relaxations by D. C. decomposition and linear underestimation. Cholesky factorization is used to reduce the original problem into the separable problems. Two Lagrangian bounds are then derived by applying dual decomposition schemes to the separable reformulations. Relationships between the convex relaxation bounds and Lagrangian bounds are also established. These underestimation methods are applicable to the algorithms for (continuous) indefinite quadratic programming problems.Finally, we conclude the thesis in Chapter 7 by summarizing the main results and discussing some possible future research directions.更多还原