對稱錐寬鄰域內(nèi)點(diǎn)算法研究.ppt

對稱錐的寬鄰域內(nèi)點(diǎn)算法研究,楊喜美 2014-4-15,目錄,Part 1 作品簡介 Part 2 作品創(chuàng)新點(diǎn),從題目我們可以看出，我們解決的問題是對稱錐規(guī)劃問題，我們使用的工具是內(nèi)點(diǎn)算法。,問題1：什么是對稱錐規(guī)劃問題？ 問題2：什么是內(nèi)點(diǎn)算法？,對稱錐規(guī)劃問題,對稱錐規(guī)劃問題是指帶有對稱錐約束的優(yōu)化問題，其目標(biāo)函數(shù)為線性函數(shù)，約束條件為仿射空間和閉凸錐的交集。其標(biāo)準(zhǔn)形式，如下：,對稱錐規(guī)劃問題的常見子類,包括三類常見的規(guī)劃問題 當(dāng) 時，線性規(guī)劃 當(dāng) 時，半定規(guī)劃 當(dāng) 時，二階錐規(guī)劃,研究意義：,研究對稱錐規(guī)劃問題可以為求解三類特殊的規(guī)劃問題以及非線性最優(yōu)化問題提供統(tǒng)一框架，能夠使我們更好的理解三類特殊規(guī)劃問題的本質(zhì)特性；因此，它是一類內(nèi)容新、涵蓋面寬、理論豐富、學(xué)術(shù)價值高的優(yōu)化問題。另外，它在經(jīng)濟(jì)、管理、交通、控制和信息等學(xué)科中有廣泛的應(yīng)用，所以，吸引了眾多優(yōu)化專家、學(xué)者從不同的角度致力于對稱錐優(yōu)化問題的研究。,內(nèi)點(diǎn)算法,1984年 ，Karmarka為求解線性規(guī)劃而提出的。由于該算法具有多項(xiàng)式復(fù)雜度被受關(guān)注。它成為了求解線性規(guī)劃、線性互補(bǔ)問題的一類十分有效的算法. 1988年 ，Nesterov和Nemirovskii將其推廣到半定規(guī)劃，這表明內(nèi)點(diǎn)算法的適用范圍有了實(shí)質(zhì)性的變化。 Nesterov和Todd提出self-scaled錐的第一個多項(xiàng)式時間原-對偶短步路徑跟蹤算法。Gler證明了self-scaled錐即是對稱錐。Faybusovich為推廣原-對偶內(nèi)點(diǎn)算法到對稱錐上做了基礎(chǔ)性工作。 至此，內(nèi)點(diǎn)算法求解對稱錐規(guī)劃問題才引起重視，并一直是研究的熱門課題。,研究目標(biāo) 窄鄰域算法具有較低的理論復(fù)雜度，但是實(shí)踐性較差； 寬鄰域算法實(shí)踐性較好，但是理論復(fù)雜度高； 我們的研究目標(biāo)就是設(shè)計(jì)出兼有兩者優(yōu)點(diǎn)的內(nèi)點(diǎn)算法。,作品創(chuàng)新點(diǎn),把Ai-Zhang鄰域推廣到對稱錐上，設(shè)計(jì)了一個不可行的寬鄰域路徑跟蹤算法 提出自己的寬鄰域，使用提出的寬鄰域設(shè)計(jì)了一個不可行的Mehrotra-型預(yù)估-矯正內(nèi)點(diǎn)算法 為了改善寬鄰域算法的實(shí)踐性我們也設(shè)計(jì)了一個二階矯正算法 為改善算法的有效性，設(shè)計(jì)了一個弧搜索內(nèi)點(diǎn)算法，該算法工作在常用的大鄰域，負(fù)無窮鄰域內(nèi)。,所做的工作,已獲得的成果,1 Ximei Yang, Hongwei Liu, Xiaoliang Dong. Polynomial convergence of Mehrotra-type predictioncorrector infeasible-IPM for symmetric optimization based on the commutative class directions. Applied Mathematics and Computation(AMC). Volume 230, 1 March 2014, Pages 616628. (SCI,二區(qū), IF1.454,已檢索,引用次數(shù)0) 2 Ximei Yang, Hongwei Liu, Yinkui Zhang. A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighborhood for semi-definite programming. International Journal of Computer Mathematics(IJCM). DOI:10.1080/00207160.2013.827784. (SCI,四區(qū),IF 0.542,未檢索，引用次數(shù)0) 3 Hongwei Liu, Ximei Yang, Changhe Liu. A New Wide Neighborhood Infeasible-Interior-Point Method for Symmetric Cone Programming. Journal of Optimization Theory and Applications(JOTA). September 2013, Volum158, Issue 3, pp 796-815. (SCI, 三區(qū),IF 1.423,已檢索,引用次數(shù)1) 4 Hongwei Liu, Changhe Liu,Ximei Yang. New complexity analysis of a Mehrotra-type predictorcorrector algorithm for semidefinite programming. Optimization Methods and