学位论文 > 优秀研究生学位论文题录展示

连续和整数非凸二次规划理论和方法研究

作　者: 郑小金
导　师: 孙小玲；李端
学　校: 上海大学
专　业: 运筹学与控制论
关键词: 连续和整数非凸二次规划问题对偶松弛方法 SDP松弛 (-1,1)-二次整数规划问题二次背包问题半单模变换分枝定界方法最优D.C.分解
分类号: O221.2
类　型: 博士论文
年　份: 2010年
下　载: 167次
引　用: 0次
阅　读: 论文下载

内容摘要

连续和整数非凸二次规划是一类重要的最优化问题,在工程、经济和管理等领域有广泛的应用.其包含了许多重要的具有挑战性的NP-难优化问题,如二次约束非凸二次规划(QCQP),线性约束非凸二次规划(QF),二次整数规划(QIP),0-1二次规划(0-1QP)和二次背包问题(QKP)等.本文旨在研究连续和整数非凸二次规划问题的对偶理论和方法、SDP松弛和其它松弛方法及其应用.以下是本文的主要工作.(1)我们给出了一般二次/线性约束非凸二次规划问题零对偶间隙(强对偶性)和非零对偶间隙的若干新的充分条件.我们首先利用鞍点条件刻画强对偶性,然后给出了一个基于对偶最优解的零对偶间隙的新的充分条件,由于该条件只与对偶最优解有关,因而是多项式时间可检验的.对线性约束非凸二次规划问题,我们利用与鞍点条件有关的集合距离来刻画对偶间隙,该距离可用离散几何中的胞形枚举技术计算.最后,我们指出,对两类非凸二次规划问题,文献中基于原始可行解的最优性充分性条件实际上隐含了零对偶间隙成立.(2)我们提出了线性等式约束(-1,1)-二次整数规划的对偶(SDP)间隙的估计方法,从而得到了该问题SDP界的改进方法.首先,我们研究了线性等式约束(-1,1)-二次整数规划的拉格朗日对偶性质,基于{-1,1}n到一仿射空间的距离,我们给出该问题的对偶间隙的估计.另外,通过精确罚函数法或将线性约束条件化为等价范数平方约束的方法,分别得到不同的对偶松弛.进而,我们给出了这些不同松弛问题产出的界之间的关系.(3)我们给出了二次背包问题的SDP松弛及其界的改进方法.首先建立了二次背包问题对偶问题的基本性质,并给出零对偶间隙成立的充分条件.我们给出了二次背包问题对偶最优解不唯一的反例,进而给出了保证对偶最优解唯一的充要条件.通过{0,1}n到一仿射空间的距离来刻画二次背包问题的对偶间隙,并给出了在不同的情况下SDP界的改进公式.(4)我们给出了一种新的方法求线性方程组Ax=b在有界整数集合X上的解.通过计算有界整数集合X到{x∈Rn|Ax=b}的距离δ,我们可以判断线性方程组Ax=b在有界整数集X上是否有解并在有解的情况下求其一个解.该方法的关键在于把δ的计算和离散几何中胞形枚举联系起来.我们证明了判断线性方程组Ax=b在X={-1,1}n的可解性和求解可在O(nn-d)时间内完成,讨论了当X={-1,1}n时的一些多项式时间可解的情况,并将该方法推广到X={-m,…,m}n的情况,证明了线性方程组在X={-m,…,m}n可解性判断和求解可在O((2mn)n-d)时间内完成.(5)我们对线性约束非凸二次整数规划提出了一种新的整数对角化方法.通过引进矩阵半单模变换的概念,使对称矩阵对角化并同时保留可行集的整点性质,由于半单模变换得到的可分离整数规划是原问题的一个松弛,我们得到原问题的一个新的下界.我们还引入了整数对角化对偶问题并分析了半单模变换的基本性质.对非奇异的2阶有理对称矩阵,我们给出了所有半单模变换的集合.对松弛的可分离二次整数规划,我们还研究了它的拉格朗日对偶及凸松弛,并比较二者之间的关系.(6)我们对多约束二次背包问题提出了拉格朗日对偶和替代(surrogate)约束方法,该方法中所需的拉格朗日对偶界是由外逼近法和Bundle方法求解得到的,而其中的拉格朗日松弛则是用最大流算法求解.我们用替代约束启发式算法寻找可行解.对中小规模多维二次背包问题,我们给出了初步计算结果.(7)我们对线性约束非凸二次规划提出了一种新的最优D.C.分解方法.我们首先给出了一个基于最优D.C.分解的带参数的凸松弛方法,证明了最优D.C.分解-即基于D.C.分解的最紧凸松弛,可以通过求解一个SDP问题得到.该方法的优点在于：在得到一个SDP界的同时还可以通过求一个凸二次规划问题得到原问题的近似最优解.我们研究了三种特殊的D.C.分解：对角扰动,线性约束平方化,合同变换及它们的组合.最后,通过数值试验比较了不同的D.C.分解产生的下界以及文献中现有的下界之间的关系.(8)我们进一步研究了二次约束非凸二次规划的最优D.C.分解方法.对凸二次约束非凸二次规划问题,给出了几类带参数的D.C.分解,证明了其最优的D.C.分解可通过求解一个SDP问题得到.进而我们提出了一类基于约束矩阵和分片线性下逼近的最优D.C.分解,证明了相应的SDP界比经典SDP界紧.与线性约束的情况类似,该最优D.C.分解方案的优点是可以在得到SDP界的同时通过求解一个二阶锥规划得到原问题的一个近似最优解.数值试验表明,最优D.C.分解方法可以得到比较紧的SDP界及较好的近似最优解。特别地,对单二次约束非凸二次规划问题,我们给出了一个求解原问题精确最优解的算法.

全文目录

摘要  6-8
Abstract  8-14
详细中文摘要  14-42
  一、问题提出  14-15
  二、研究现状概述  15-19
    1.整数非凸二次规划问题  15-17
    2.连续非凸二次规划问题  17-19
  三、本文主要结果  19-42
    1.强对偶性及最优性条件  19-22
    2.线性等式约束(-1,1)-二次整数规划的SDP松弛及其改进  22-25
    3.二次背包问题的SDP松弛及其改进  25-26
    4.线性方程组的有界整数解  26-29
    5.线性约束非凸二次整数规划的整数对角化方法  29-31
    6.多约束二次背包问题的对偶和替代约束方法  31-35
    7.线性约束非凸二次规划的最优D.C.分解及SDP松弛  35-38
    8.二次约束非凸二次规划的最优D.C.分解及SDP松弛  38-42
Chapter 1 Duality Gap in Nonconvex Quadratic Programming Problems  42-56
  §1.1 Introduction  42-43
  §1.2 Sufficient Conditions for Zero Duality Gap  43-47
  §1.3 A Distance Measure and Duality Gap  47-52
  §1.4 Optimality Conditions and Zero Duality Gap  52-56
Chapter 2 Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming  56-75
  §2.1 Introduction  56-57
  §2.2 Lagrangian Dual and SDP Relaxations  57-63
    2.2.1.Lagrangian dual and SDP relaxations  58-60
    2.2.2.Optimality conditions  60-61
    2.2.3.Uniqueness of optimal dual solution  61-63
  §2.3 Estimation of Duality Gap  63-70
  §2.4 Alternative Lagrangian Bounds  70-75
    2.4.1. Lagrangian dual scheme via exact penalty formulation  70-72
    2.4.2. Lagrangian dual scheme via squared norm constraint  72-75
Chapter 3 SDP Relaxation and Reduction of Duality Gap for Quadratic Knapsack Problems  75-95
  §3.1 Introduction  75-77
  §3.2 Lagrangian Relaxation and Optimality Conditions  77-78
  §3.3 SDP Relaxation  78-81
    3.3.1.Lagrangian dual and SDP relaxation  78-80
    3.3.2.The dual of(D_s)  80-81
  §3.4 Uniqueness of the Optimal Solution to SDP Relaxation  81-89
    3.4.1.A non-uniqueness case  82-83
    3.4.2.Uniqueness for the SDP relaxation  83-89
  §3.5 Duality Gap and Reduction  89-95
Chapter 4 A New Method for Bounded Linear Diophantine Equations  95-103
  §4.1 Introduction  95-96
  §4.2 Linear Equations Over Binary Set  96-99
  §4.3 Linear Equations Over General Bounded Integer Set  99-103
Chapter 5 An Integer Diagonalization Approach for Nonconvex Quadratic Integer Programming  103-126
  §5.1 Introduction  103-106
  §5.2 Semi-Unimodular Transformation and Diagonalization  106-112
    5.2.1.Semi-unimodular transformation  106-108
    5.2.2.Integer diagonalization and separable quadratic problem  108-112
  §5.3 Integer Diagonalization Dual and the Set of Semi-Unimodular Matrices  112-116
  §5.4 Lagrangian Relaxation and Convex Relaxation of(P(U))  116-126
    5.4.1.Lagrangian relaxation  117-120
    5.4.2.Convex relaxation  120-122
    5.4.3.Relations among different relaxations  122-124
    5.4.4.Numerical results  124-126
Chapter 6 A Lagrangian Dual and Surrogate Method for Multi-Dimensiona #1 Quadratic Knapsack Problems  126-141
  §6.1 Introduction  126-127
  §6.2 Lagrangian Relaxation and Dual Search Schemes  127-133
    6.2.1. Outer approximation dual search method  128-129
    6.2.2. Bundle-based dual search method  129-133
  §6.3 Heuristic for Finding Feasible Solutions  133
  §6.4 The Main Algorithm  133-137
  §6.5 Computational Results  137-141
Chapter 7 Optimal D.C.Decompositions and SDP Relaxations for Non-convex QP  141-159
  §7.1 Introduction  141-143
  §7.2 A General Convex Relaxation Scheme via D.C.Decomposition  143-146
  §7.3 Convex Relaxations via Diagonal Perturbation and Squared Linear Con-straints  146-149
  §7.4 Convex Relaxation via Congruent Transformation  149-154
    7.4.1.Convex relaxation and Lagrangian dual of separable problem  149-152
    7.4.2.Relation to the general convex relaxation scheme  152-153
    7.4.3.Improvement of convex relaxation via congruent transformation  153-154
  §7.5 Numerical Results  154-159
Chapter 8 Optimal D.C.Decompositions and SDP Relaxations for Non-convex QCQP  159-184
  §8.1 Introduction  159-161
  §8.2 General Parametric D.C. Decomposition  161-164
  §8.3 Two Special D.C. Decomposition Schemes  164-167
    8.3.1.D.C.decomposition via diagonal perturbation  164-165
    8.3.2.D.C.decomposition via orthogonal transformation  165-167
  §8.4 D.C.Decomposition via Coefficient Matrices Ai  167-173
  §8.5 Computational Results  173-176
  §8.6 An Exact Algorithm for Singly Constrained QCQP  176-184
    8.6.1.Optimal D.C. decomposition and SDP relaxation  179-180
    8.6.2. An exact algorithm  180-182
    8.6.3. Numerical result  182-184
Chapter 9 Conclusions  184-188
参考文献  188-198
作者在攻读博士学位期间发表和完成的论文  198-200
致谢  200

连续和整数非凸二次规划理论和方法研究

内容摘要

全文目录

相似论文