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