連續(xù)與離散單調(diào)優(yōu)化和不定二次規(guī)劃算法研究.pdf

1、全局優(yōu)化問題主要研究如何尋找一個非凸優(yōu)化問題的全局最優(yōu)解。隨著社會的進步以及科學技術的發(fā)展，全局最優(yōu)化廣泛應用于企業(yè)生產(chǎn)管理、金融工程、工程設計及控制、交通運輸、農(nóng)業(yè)預測、國防軍事等重要領域．因此研究全局優(yōu)化問題在理論和應用方面都有重要的意義。 本文主要研究兩類特殊結構的全局優(yōu)化問題-單調(diào)優(yōu)化和不定二次規(guī)劃。單調(diào)優(yōu)化是指目標函數(shù)和約束函數(shù)都是單調(diào)函數(shù)的全局優(yōu)化問題。把單調(diào)優(yōu)化問題中的變量取值限制為整數(shù)，即為離散單調(diào)優(yōu)化問題(通常

2、也稱為多維不可分離背包問題。單調(diào)優(yōu)化問題的目標函數(shù)和約束函數(shù)不要求是凸。的或是可分離的。不定二次規(guī)劃問題是指目標函數(shù)是不定二次函數(shù)，約束函數(shù)是線性函數(shù)或二次函數(shù)的全局優(yōu)化問題。把不定二次規(guī)劃問題中的變量取值限制為整數(shù)，即為整數(shù)(離散)不定二次規(guī)劃問題。本文將著重研究帶線性約束的連續(xù)和離散不定二次規(guī)劃問題。 本文分為七章，各章內(nèi)容簡要介紹如下： 第一章給出了單調(diào)優(yōu)化和不定二次規(guī)劃及其離散問題的描述及一些應用模型，同時對本論

3、文的主要工作作了簡要介紹。 第二章首先介紹了一般全局優(yōu)化的基本算法，然后介紹文獻中連續(xù)和離散單調(diào)優(yōu)化及不定二次規(guī)劃的現(xiàn)有算法。 第三章給出了一個求解單調(diào)優(yōu)化問題的精確算法。該算法的框架是分枝定界，并且與區(qū)域剖分、凸化、局部搜索三種基本策略相結合。區(qū)域剖分就是把區(qū)域剖分成若干個子箱的并集，而且這些子箱的并集覆蓋了可行域的邊界；在每個子箱上使用凸化外逼近方法得到目標函數(shù)最優(yōu)值的上界；再結合局部搜索改進下界。我們對該算法進行了

4、數(shù)值實驗，數(shù)值實驗結果表明該算法是有效的，能在合理的時間內(nèi)求解中小規(guī)模的單調(diào)優(yōu)化問題。 第四章對離散型的單調(diào)優(yōu)化問題進行研究，提出了一個離散的Polyblock算法，并且在此基礎上結合凸化思想，對離散Polyblock算法進行改進，提高了界的質量，從而提高算法效率。數(shù)值實驗結果表明兩個算法是有效的，而且數(shù)值比較結果表明改進后的算法對具有較大區(qū)域的問題計算效果優(yōu)于改進前的離散Polyblock算法。 第五章給出了一個求不定

5、二次規(guī)劃問題全局最優(yōu)解的新算法。首先給出了不定二次規(guī)劃問題的三種下界的確定方法：線性逼近、拉格朗日對偶松弛和凸松弛，然后利用這些下界并結合超長方形的兩分法建立一個分枝定界算法。而且還證明了經(jīng)正交變換所得的不定二次可分離問題的凸松弛與拉格朗日對偶松弛是等價的。數(shù)值實驗結果表明該算法是有效的。 第六章給出了不定二次整數(shù)規(guī)劃問題的幾種新的下界并且證明了它們之間的關系。首先構造了問題的線性下方估計，以及通過D．C．分解構造了問題的兩種凸