20093.基于sdp松弛的01二次規(guī)劃全局算法

1、碩士學(xué)位論文論文題目：基于SDP松弛的01二次規(guī)劃全局算法作者姓名：_________蔡偉榮指導(dǎo)教師:_________羅和治教授學(xué)科專(zhuān)業(yè):________數(shù)學(xué)運(yùn)籌學(xué)所在學(xué)院：理學(xué)院提交日期：2015年4月15日浙江工業(yè)大學(xué)碩士學(xué)位論文基于SDP松弛的01二次規(guī)劃全局算法摘要01二次規(guī)劃是整數(shù)規(guī)劃中一類(lèi)重要的最優(yōu)化問(wèn)題，廣泛應(yīng)用于工程、經(jīng)濟(jì)管理、金融和管理科學(xué)等許多重要領(lǐng)域，是近年來(lái)國(guó)際優(yōu)化領(lǐng)域中重要而富有挑戰(zhàn)性的課題。近年來(lái)半定規(guī)劃(

2、簡(jiǎn)記SDP)方法的發(fā)展更促進(jìn)了01二次規(guī)劃研宄。本文研宄01二次規(guī)劃的SDP松弛和全局算法。我們給出了基于矩陣分解方法的緊SDP松弛，給出了基于SDP松弛的分枝定界算法。以下是本文的主要工作：(1)利用矩陣分解方法給出了帶線性約束01二次規(guī)劃的一個(gè)緊的SDP松弛。通過(guò)目標(biāo)函數(shù)的矩陣分解并利用二次項(xiàng)的片段線性逼近技術(shù)得到了原問(wèn)題的一個(gè)凸松弛。證明了尋找凸松弛中的最優(yōu)參數(shù)問(wèn)題可以歸結(jié)為一個(gè)SDP問(wèn)題。數(shù)值結(jié)果表明該SDP松弛能提供原問(wèn)題的一