最小包容圓問題是求解包容所有給定圓的半徑最小的圓.本文主要提出了兩種算法來求解最小包容圓問題,分別是基于非凸約束的二次規(guī)劃算法和基于線性重制技術(shù)的算法.全文共分為三章,內(nèi)容如下:第一章,介紹最小包容圓問題的研究背景和論文各章節(jié)主要內(nèi)容.第二章,考慮最小包容圓的非凸二次規(guī)劃問題并給出求解該問題的算法.運(yùn)用“升維”的思想并引入新變量,把求解非凸二次規(guī)劃問題轉(zhuǎn)化為求解一系列線性約束的二次規(guī)劃問題.此外,在數(shù)值實驗中,我們與文獻(xiàn)[3]中最好的二次規(guī)劃法進(jìn)行比較.在數(shù)據(jù)規(guī)模小時,兩種算法的計算速度幾乎相等.然而,在數(shù)據(jù)規(guī)模較大時,本章的算法比文獻(xiàn)[3]的二次規(guī)劃法的計算速度更快.第三章,考慮最小包容圓的二階錐規(guī)劃問題并給出求解該問題的算法.運(yùn)用線性重制技術(shù),把求解二階錐規(guī)劃問題轉(zhuǎn)化為求解一系列的線性規(guī)劃問題.此外,在數(shù)值實驗中,我們與CPLEX的二階錐規(guī)劃算法及文獻(xiàn)[4]中最好的切平面法進(jìn)行比較.本章的算法比它們的計算速度更快.進(jìn)一步,運(yùn)用該算法到三維空間中求解最小包容球問題.本章算法的計算速度是優(yōu)于CPLEX的二階錐規(guī)劃算法和文獻(xiàn)[4]的切平面法。 

【文章來源】：四川師范大學(xué)四川省

【文章頁數(shù)】：44 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
1 引言
    1.1 研究背景
    1.2 各章節(jié)主要內(nèi)容
2 基于非凸約束的二次規(guī)劃算法
    2.1 算法
    2.2 數(shù)值實驗
3 基于線性重制技術(shù)的算法
    3.1 算法
    3.2 二維空間中的數(shù)值實驗
    3.3 三維空間中的數(shù)值實驗
參考文獻(xiàn)
附錄
致謝
在校期間的科研成果



本文編號：3633934