| 摘要 | 第1-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页 |
| ·Lagrangian dual and SDP relaxations | 第58-60页 |
| ·Optimality conditions | 第60-61页 |
| ·Uniqueness of optimal dual solution | 第61-63页 |
| §2.3 Estimation of Duality Gap | 第63-70页 |
| §2.4 Alternative Lagrangian Bounds | 第70-75页 |
| ·Lagrangian dual scheme via exact penalty formulation | 第70-72页 |
| ·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页 |
| ·Lagrangian dual and SDP relaxation | 第78-80页 |
| ·The dual of(D_s) | 第80-81页 |
| §3.4 Uniqueness of the Optimal Solution to SDP Relaxation | 第81-89页 |
| ·A non-uniqueness case | 第82-83页 |
| ·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页 |
| ·Semi-unimodular transformation | 第106-108页 |
| ·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页 |
| ·Lagrangian relaxation | 第117-120页 |
| ·Convex relaxation | 第120-122页 |
| ·Relations among different relaxations | 第122-124页 |
| ·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页 |
| ·Outer approximation dual search method | 第128-129页 |
| ·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页 |
| ·Convex relaxation and Lagrangian dual of separable problem | 第149-152页 |
| ·Relation to the general convex relaxation scheme | 第152-153页 |
| ·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页 |
| ·D.C.decomposition via diagonal perturbation | 第164-165页 |
| ·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页 |
| ·Optimal D.C. decomposition and SDP relaxation | 第179-180页 |
| ·An exact algorithm | 第180-182页 |
| ·Numerical result | 第182-184页 |
| Chapter 9 Conclusions | 第184-188页 |
| 参考文献 | 第188-198页 |
| 作者在攻读博士学位期间发表和完成的论文 | 第198-200页 |
| 致谢 | 第200页 |
