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

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

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

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

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

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