最小包容圆问题的算法

发布时间：2022-02-20 00:34

　　最小包容圆问题是求解包容所有给定圆的半径最小的圆.本文主要提出了两种算法来求解最小包容圆问题,分别是基于非凸约束的二次规划算法和基于线性重制技术的算法.全文共分为三章,内容如下:第一章,介绍最小包容圆问题的研究背景和论文各章节主要内容.第二章,考虑最小包容圆的非凸二次规划问题并给出求解该问题的算法.运用“升维”的思想并引入新变量,把求解非凸二次规划问题转化为求解一系列线性约束的二次规划问题.此外,在数值实验中,我们与文献[3]中最好的二次规划法进行比较.在数据规模小时,两种算法的计算速度几乎相等.然而,在数据规模较大时,本章的算法比文献[3]的二次规划法的计算速度更快.第三章,考虑最小包容圆的二阶锥规划问题并给出求解该问题的算法.运用线性重制技术,把求解二阶锥规划问题转化为求解一系列的线性规划问题.此外,在数值实验中,我们与CPLEX的二阶锥规划算法及文献[4]中最好的切平面法进行比较.本章的算法比它们的计算速度更快.进一步,运用该算法到三维空间中求解最小包容球问题.本章算法的计算速度是优于CPLEX的二阶锥规划算法和文献[4]的切平面法。 

【文章来源】：四川师范大学四川省

【文章页数】：44 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
1 引言
    1.1 研究背景
    1.2 各章节主要内容
2 基于非凸约束的二次规划算法
    2.1 算法
    2.2 数值实验
3 基于线性重制技术的算法
    3.1 算法
    3.2 二维空间中的数值实验
    3.3 三维空间中的数值实验
参考文献
附录
致谢
在校期间的科研成果



本文编号：3633934