非線性雙層規(guī)劃的算法研究.pdf

1、本文的主要內(nèi)容是探討雙層規(guī)劃中的非線性雙層規(guī)劃的算法。通過分析非線性雙層規(guī)劃的數(shù)學(xué)模型、性質(zhì)，以線性－二次雙層規(guī)劃為研究的起點(diǎn)，延伸到上層為非線性、下層為二次的情形，給出算法并證明其收斂性。
　　論文首先通過一個(gè)交通網(wǎng)絡(luò)中路段收費(fèi)問題介紹雙層規(guī)劃的實(shí)際背景、定義、主要特點(diǎn)和復(fù)雜性。這種最優(yōu)化問題的特殊性在于：約束條件中包含一個(gè)最優(yōu)化問題。雙層規(guī)劃的解有兩種基本形式，樂觀形式和悲觀形式。由于其內(nèi)在的困難，算法研究舉步維艱，一方面，有

2、人證明了雙層規(guī)劃是NP-hard問題，另一方面，局限在某些特殊類型上，人們已提出了較為有效的算法。
　　目前，非線性雙層規(guī)劃的算法大致上分為三類，分枝定界法（枚舉法）、下降法和罰函數(shù)法。本文選擇線性—二次雙層規(guī)劃為突破口，給出了它的數(shù)學(xué)模型、基本理論和最優(yōu)性條件，并將其化為混合整數(shù)單層規(guī)劃求解，為后面的算法研究打下基礎(chǔ)。
　　對(duì)于上層非線性、下層為二次規(guī)劃的雙層規(guī)劃，充分利用二次規(guī)劃的研究成果，以K-T條件代替下層問題，將下

3、層問題線性化，借助旋轉(zhuǎn)步驟找到誘導(dǎo)域極點(diǎn)，沿誘導(dǎo)域極點(diǎn)下降方向不斷改進(jìn)上層目標(biāo)函數(shù)值，但由于上層目標(biāo)函數(shù)非線性，極小值不一定在誘導(dǎo)域極點(diǎn)取到，所以，這種方法未必能找到局部極小點(diǎn)。信賴域算法在單層規(guī)劃中是很有效的近似算法，把它遷移到雙層規(guī)劃中來也是一個(gè)不錯(cuò)的想法，用線性—二次雙層規(guī)劃作為模型可以構(gòu)造信賴域算法，但其收斂性難以證明。
　　在以上工作的基礎(chǔ)上，綜合下降算法和信賴域算法各自的優(yōu)勢(shì)，提出了兩階段算法，并在較強(qiáng)的假設(shè)下給出收斂