一种新的正定二次规划算法

论文摘要

二次规划是一类重要的优化问题,在实际应用中涉及到的很多问题都可以自然而然地表示成二次规划问题。本论文比较了几种常用算法的优缺点,着重研究了一种新的正定二次规划算法,并详细给出了算法的理论依据以及进行了数值试验。首先,概述了二次规划的模型及其研究现状,以及本文的章节安排。介绍了二次规划算法的基本知识和基本理论,以及求解等式二次规划和一般二次规划的已有算法,并比较了其优缺点。其次,给出了求解正定二次规划的单纯形法。证明了正定二次规划若不在约束内也不能在约束的边界面及边界面的交线上取得故只能在顶点上取得极值,构造了求解正定二次规划的单纯形法算法的一般步骤,并且进行了数值试验。第三,利用正定二次规划的几何意义给出了一种新的求解正定二次规划算法,进行了相关理论的证明和数值试验。一般的正定二次规划问题的目标函数都可以转化为范数(距离)形式,给出了把一般正定二次规划转化为“标准形式”及“归一化”的方法;构造了一种新的正定二次规划算法,该算法对有些问题,只需作简单的比较与判定,就可得到最优解,对有些问题则除过比较、判定,还需用单纯形法迭代得到最优解。数值试验也证实了当进行标准化和归一化之后,就已经完成了数值计算的主要部分,而这些计算也只是简单的加减乘除计算。数值试验证明该算法是可行有效的,和其他算法相比具有明显的数值优势。

论文目录

• 摘要
• ABSTRACT
• 1 绪论及预备知识
• 1.1 二次规划问题的模型及研究现状
• 1.2 二次规划算法的基本理论
• 1.2.1 基本概念
• 1.2.2 最优性条件
• 1.2.3 收敛性证明
• 1.2.4 停止准则
• 1.3 本文中的主要工作与内容安排
• 2 二次规划常见算法分析
• 2.1 求解等式约束二次规划的算法
• 2.1.1 Lagrange 方法
• 2.1.2 秩空间方法
• 2.1.3 零空间方法
• 2.2 求解一般二次规划的算法
• 2.2.1 积极集方法
• 2.2.2 分枝定界法
• 2.2.3 内点法和不可行内点法
• 2.2.4 对偶方法
• 2.2.5 线性互补问题
• 2.2.6 其他方法
• 2.3 算法的优缺点比较
• 2.4 本文创新点
• 3 正定二次规划的单纯形算法
• 3.1 问题的提出
• 3.2 取得极值的条件
• 3.3 算法描述
• 3.4 算法的具体步骤
• 3.5 数值试验
• 3.6 小结
• 4 一种新的正定二次规划算法
• 4.1 问题的提出
• 4.2 算法描述
• 4.3 算法的主要依据
• 4.3.1 范数的相关理论
• 4.3.2 解析几何中的相关理论
• 4.4 算法的推导
• 4.4.1 带有长方体约束的范数（距离）形式二次规划
• 4.4.2 一般约束的范数（距离）形式二次规划
• 4.4.3 一般形式的二次规划问题
• 4.4.4 算法步骤
• 4.5 小结
• 5 数值试验
• 5.1 数值试验
• 5.2 算例比较
• 5.3 实验分析
• 6 结论
• 致谢
• 参考文献
• 附录