張量分析的若干新發(fā)展

張量分析的若干新發(fā)展

0張量并特征值的理論和算法本文主要介紹了張量分析和多項式優(yōu)化的內(nèi)容。張量分析主要包括張量分解和張量特征值，其內(nèi)容主要包括張量分解和張量特征值的理論和算法。多項式優(yōu)化是指目標函數(shù)和限制函數(shù)是一種分布式優(yōu)化問題?？紤]到兩者的研究背景、出發(fā)點和研究內(nèi)容，我們在這兩篇文章中介紹了這兩部分，并在算法上討論了它們之間的聯(lián)系。1張量分析的最新成果1.1張量的描述及應(yīng)用張量雖然早在19世紀微分幾何的研究中就被引入,但我們這里的張量主要是指高維數(shù)據(jù)的一種排列及它們在高階數(shù)理統(tǒng)計、信號處理、圖像處理和化學(xué)計量等領(lǐng)域中的含義,它可以被看成是矩陣的一種推廣,和微分幾何中張量的含義及著眼點不同(如見).本文中張量分析主要指張量分解和張量特征值問題的理論及解法.張量分解最初是由Hitchcock在1927年提出.到20世紀60—70年代,越來越多的研究者開始在心理測量、化學(xué)計量等研究領(lǐng)域使用張量.隨著這些學(xué)科的發(fā)展及更多的領(lǐng)域?qū)埩考捌溆嘘P(guān)性質(zhì)、解法等知識的進一步需求,深入而系統(tǒng)的理論研究就越來越重要了,并逐漸引起數(shù)學(xué)家,特別是應(yīng)用數(shù)學(xué)家的重視.從2004年開始,在美國、歐洲等地陸續(xù)舉辦了張量分解及其應(yīng)用的學(xué)術(shù)會議,2007年Qi等對張量的運算、張量分解、張量特征值及其應(yīng)用做了綜述:2009年,Kolda等在《SIAMReview》上對張量分解及其應(yīng)用做了更詳細的綜述.2009年,Cichocki等在他們的著作《NonnegativeMatrixandTensorFactorizations》中,詳細介紹了張量分解中的各種概念及運算規(guī)則,各種非負矩陣和非負張量分解及它們在腦科學(xué)、盲源分離等領(lǐng)域中的應(yīng)用,并介紹了幾種經(jīng)典的非線性優(yōu)化方法.這表明了張量分解中的一些計算可以歸結(jié)為優(yōu)化問題或使用優(yōu)化方法去求解.由于在心理統(tǒng)計學(xué)、化學(xué)計量學(xué)、信號處理、數(shù)值線性代數(shù)、計算機可視化、數(shù)值分析、圖的分析和生物信息等越來越多的領(lǐng)域中需要用張量去表述一些問題,而且在有些情形下使用張量表述會比使用矩陣更有優(yōu)勢,這進一步促進了對張量分解的研究.正如矩陣分解和逼近那樣,之所以需要研究張量的分解及逼近,一方面是希望通過分解,能從大量的數(shù)據(jù)中得到對表征對象特點的刻畫;另一方面,通過張量的低秩逼近,可以緩解處理海量數(shù)據(jù)在存儲、傳輸、分析等方面的壓力,以便能夠比較準確且高效地處理各類數(shù)據(jù).張量是指數(shù)據(jù)的一種排列,一個m階n維的張量,是指其中的元素下標是m個,而每一個指標的變化范圍是從1到n,這里m,n都是正整數(shù).顯然,當(dāng)m取1和2時,所表示的張量分別是n維向量和rn階方陣.設(shè)A是一個張量,可以記A=(a1…im),這里ij=1,…,n,j=1,…,m,稱A是一個m階n維(正方)張量.如果其下標的任意置換不改變元素的值,則稱該張量是對稱的.與矩陣一樣,可以定義張量之間的加、減、乘法運算,也可以定義張量和矩陣、向量之間的乘積.反之,可以定義一個張量的分解.張量分解的定義方式有多種,其中常用的兩種是:(1)CP分解,即將張量寫為若干CP秩為1的張量(若一個m階n維張量A可以寫為m個非零n維向量的外積,則稱這個外積是張量A的CP秩1分解,并稱張量A的CP秩為1)的和;(2)Tucker分解,它是矩陣奇異值分解的推廣,比CP分解復(fù)雜.CP分解是Tucker分解的特殊情形.還有一些其他的分解.采用什么樣的分解與問題的屬性和要求有關(guān).如果一個張量可以寫為若干個CP秩為1的張量的和,且求和的秩1張量個數(shù)不可減少,則稱這個最小數(shù)為該張量的CP秩.CP秩1逼近是盲源分離(BSS)的直接的數(shù)學(xué)模型.另外,與矩陣情形一樣,用低秩的張量逼近高階張量,在精度許可的條件下,可能會大大減少張量的存儲、傳輸、分析等工作量.但和矩陣情形不同的是,這時CP最佳逼近問題會出現(xiàn)解不存在的情況,但若限定在某些特殊情形,比如非負張量的非負分解,則解是存在的(如見).盡管已有各種計算CP分解、Tucker分解的方法,但算法的理論分析十分缺乏,其中一種較為得到認可的算法是交替最小二乘法(ALS),這類算法和矩陣計算的交替最小二乘法、可分離凸優(yōu)化問題和可分離變分不等式中的交替方向法在思想上和算法步驟上類似.在張量分解和最佳低秩逼近中,主要有兩類方法:一類是直接法,這類方法主要借助矩陣理論中已有的結(jié)論和方法,得到關(guān)于張量分解的結(jié)論,如高階奇異值分解(HOSVD);另一類是非線性最優(yōu)化中的迭代算法和松弛技術(shù),該方法一般結(jié)合問題的具體特點,得到相關(guān)的算法或松弛的凸優(yōu)化問題與原問題的近似比.從20世紀70年代起,張量分解、逼近及其在各領(lǐng)域中的應(yīng)用研究在國外開始得到重視和有較快的發(fā)展,已經(jīng)取得了十分豐富的結(jié)果.相對而言,國內(nèi)這方面的研究還處于起步階段,為數(shù)不多的研究工作主要集中在用優(yōu)化的方法對張量秩1最佳逼近等方面所做的理論研究(如見).2005年,Qi和Lim分別獨立提出了張量特征值與特征向量的概念,它們可以被看成是矩陣特征值與特征向量的推廣.可以說,張量特征值、特征向量最初的提出,主要是從數(shù)學(xué)角度出發(fā)對矩陣特征值、特征向量的自然發(fā)展和推廣,與張量分解的發(fā)展背景和動機有很大不同.Qi和Lim都是考慮張量是對稱及特征值、特征向量為實的情形.后來,Chang等給出了張量特征值、特征向量的一般定義.隨后張量特征值的理論及應(yīng)用得到了快速發(fā)展.1.2非負張量perron-frobenius定理張量特征值與特征向量的定義主要有如下兩種:和這里Axm-1表示n維向量,其第i個分量定義為可見,當(dāng)m=2時,二者是一致的.在實數(shù)域中,稱第一種定義中的λ,x分別為對應(yīng)于張量A的H-特征值和H-特征向量,第二種定義中的λ,x為對應(yīng)的Z-特征值和Z-特征向量.如果將第二種定義中的2-范數(shù)改為1-范數(shù),這時,λ,x分別稱為Z1-特征值和Z1-特征向量.與矩陣情形類似,可以對長方的張量定義奇異值和相應(yīng)的特征向量.在矩陣理論方面,利用特征多項式求解矩陣特征值是一個基本方法.類似地,利用張量行列式概念可以引進張量特征多項式,并以此為基礎(chǔ)研究張量特征值及其重要性質(zhì).這可以為進一步研究張量特征值及其相關(guān)問題提供必要的理論基礎(chǔ)和新思路.已有的相關(guān)成果見.Qi討論了H-特征值的個數(shù)及所有特征值的和、積、重數(shù)、特征值在正交等變換下的不變性、圓盤估計等結(jié)果,并利用結(jié)式理論研究了齊次張量特征值的個數(shù)等.Qi等還指出了張量特征值在偶數(shù)階張量的正性判別、醫(yī)學(xué)圖像、量子糾纏、彈性力學(xué)和控制論等領(lǐng)域中的應(yīng)用.Lim利用變分方法引出了張量特征值、奇異值的定義并定義了張量的不可約性及非負不可分張量的Perron-Frobenius定理的初步結(jié)果.隨后Chang等系統(tǒng)地研究了關(guān)于H-特征值的Perron-Frobenius定理,Yang等進一步將Perron-Frobenius理論推廣到一般非負張量情形并得到進一步的結(jié)果.Friedland等對一般齊次多元多項式定義了更一般的特征值和特征向量,并通過圖論中連通性的概念提出了弱不可約張量的定義,并在這個條件下進一步推廣了Perron-Frobenius定理.Chang等對非負長方張量的情形,給出了推廣的min-max定理等結(jié)果.Yang等進一步推廣了長方張量最大奇異值的有關(guān)結(jié)果,并在一定條件下證明了推廣的冪法的收斂性.H-特征值的Perron-Frobenius定理及其他理論結(jié)果多數(shù)是由非負矩陣特征值中的相關(guān)結(jié)果發(fā)展而來,這方面的結(jié)果可以說已經(jīng)比較完善了.最近Chang,Qi和Zhang對非負張量特征值理論給出了一個詳細的綜述,Yang等也編輯了以非負張量研究為主要內(nèi)容的專輯.非負不可約條件下譜半徑對應(yīng)的特征向量的重數(shù)問題也是H-特征值理論中一個重要的研究課題,不同于矩陣情形,這里一個特征值對應(yīng)的特征向量實幾何重數(shù)和復(fù)幾何重數(shù)可能是不等的.Chang等首先提出和研究了該問題,Yang等對譜半徑對應(yīng)的特征向量為實幾何單的和復(fù)幾何單的做了進一步研究.張量的分類及不同類之間的關(guān)系是張量研究中的一個重要課題,這種分類的必要性在于刻畫張量性質(zhì)的理論結(jié)果和算法收斂性等理論分析結(jié)果,都是在一定條件下,對某一類張量才成立的.首先從矩陣發(fā)展推廣到張量是不可約的、素的、本質(zhì)正的等概念.但由于張量要比矩陣復(fù)雜,通過張量的矩陣展開或基于對應(yīng)圖的不同定義,衍生出弱不可約、弱素、部分對稱、弱對稱、弱本質(zhì)正等一系列新的在矩陣情形不會有的概念和定義,一個主要原因是由二階(平面)矩陣情形擴展到三階(立體)及以上情形,帶來了新的問題.在這些新的更弱的條件下,已有的命題是否成立或只是部分成立,都需要檢查、證明或通過反例予以否定.Hu,Huang和Qi研究了各種不同類的張量,并討論了這幾類張量之間的包含關(guān)系或交叉關(guān)系.Ng,Qi和Zhou首先將矩陣中求最大模特征值的冪法推廣到計算張量的最大模H-特征值問題,Chang等在張量是素的條件下證明了算法的收斂性,Zhang和Qi在張量本質(zhì)正的條件下證明了算法的線性收斂性結(jié)果.這個結(jié)果后來被Chang等推廣到長方張量最大奇異值解法的研究中.Qi,Wang和Wang對Z-特征值低階情形提出了求最大模特征值的直接方法.對一般非負張量情形,Chen等通過對原張量加一個正擾動及內(nèi)迭代不精確技巧,給出了一種求解一般張量譜半徑的算法,并證明了算法的收斂性,還在一定條件下給出了算法的計算復(fù)雜度;另外,對長方張量,他們還通過嵌入技巧,把長方張量最大奇異值的計算轉(zhuǎn)化為正方張量譜半徑的計算.數(shù)值結(jié)果表明了這種處理方法的有效性.Hu等采用對一般非負張量分解的方式,把求解譜半徑問題轉(zhuǎn)化為求解小規(guī)模不可約張量譜半徑的辦法,然后調(diào)用對不可約非負張量的冪法求解一般非負張量的譜半徑.Yang等已經(jīng)證明,對H-特征值,求非負不可約張量譜半徑等價于求一個特殊的凸多項式優(yōu)化問題,從而為可以在多項式時間內(nèi)求解不可約張量H-譜半徑提供了理論依據(jù).Zhou等使用這種等價變換,再根據(jù)相關(guān)問題的特點,使用凸優(yōu)化松弛技術(shù),提出了求解非負不可約張量譜半徑的算法.相對來說,Z-特征值的應(yīng)用背景更明確,但由于其非齊次性,導(dǎo)致對H-特征值的多數(shù)結(jié)論(如Perron-Frobenius理論)對Z-特征值和Z1-特征值不成立.Chang等對Z-特征值和Z1-特征值的性質(zhì)做了詳細的研究.對稱情形的最大Z-特征值模的計算可以歸結(jié)為單位球面上齊次張量函數(shù)全局最大值的計算,長方偏對稱張量最大Z-奇異值的計算可以歸結(jié)為雙齊次函數(shù)在兩個單位球面上的全局最大值的計算.這是一類特殊的等式約束優(yōu)化問題,也是特殊的多項式優(yōu)化問題.但不同于H-特征值情形,由于對H-特征值成立的min-max定理對Z(Z1)-特征值不再成立,無法象H-特征值那樣把求最大Z-特征值(奇異值)問題轉(zhuǎn)化為一個等價的凸優(yōu)化問題.實際上,求非負張量最大Z(Z1)-特征值(奇異值)問題本質(zhì)上是一個非凸優(yōu)化問題,是NP-難問題.對這類問題的求解目前主要有三類方法:一類是采用約束優(yōu)化中已有的算法或根據(jù)問題特點做適當(dāng)變化去求解;另一類是采用類似于求最大H-特征值冪法的格式求解;還有一類是采用為求解非凸二次規(guī)劃問題或離散優(yōu)化全局最優(yōu)而發(fā)展起來的半定規(guī)劃松弛技術(shù),其想法是將要求的非凸優(yōu)化問題的最優(yōu)值估計在一個區(qū)間內(nèi),而區(qū)間兩端的值通過求解原問題的一類凸松弛優(yōu)化問題得到,再通過某種隨機技術(shù)生成近似解.Kolda等采用第二種方法提出了一種求最大(小)Z-特征值的方法,為了克服Kofidis等提出的算法可能不收斂的缺點,在目標函數(shù)加了偏移項,以保證其中參數(shù)充分大或充分小時,目標函數(shù)是凸的或凹的,然后再使用冪法.但這種方法也無法保證求得最大Z-特征值.Qi,Wang和Wang對低階低維的特殊情形,給出了求解特征值、特征向量的直接方法.可以說,前兩種方法一般均無法保證求得最大或最小Z-特征值.第三種求解技術(shù)可以納入多項式全局最優(yōu)化的求解方法中.Hu,Huang和Qi將求解張量的最大(及最小)Z-特征值問題轉(zhuǎn)化為求解一系列半定規(guī)劃問題,其中使用的主要方法是多項式優(yōu)化中的平方和(SOS)方法.在下一部分將對對稱張量最大或最小Z-特征值或更一般多項式優(yōu)化問題的解法及有關(guān)結(jié)果做較詳細的論述.1.3使用張量替代矩陣(1)目前張量用于和超圖理論有關(guān)的研究已得到一些有趣的結(jié)果(見[33-36]).2013年5月在福州大學(xué)召開了超圖譜理論的學(xué)術(shù)會議.張量方法已滲透到大數(shù)據(jù)、壓縮感知、視頻技術(shù)、矩陣完備化等問題的研究中.在這些問題的研究中,用張量代替矩陣是其主要變化.這種推廣有什么優(yōu)點,及研究新的模型時遇到的新問題,都是需要研究的.(2)張量分解、逼近及最大(小)Z-特征值或其他類型的特征值的計算會越來越多地使用多項式優(yōu)化、非線性分析中的結(jié)論和方法,特別是這里遇到的非線性優(yōu)化問題的全局最優(yōu)解的計算,屬于多項式優(yōu)化中需要研究的重要問題.進一步發(fā)展的趨勢及問題可參考下面多項式優(yōu)化部分.(3)張量的秩有好幾種定義,且這幾種定義的值一般是不同的,這是和矩陣情形有重要區(qū)別的地方.每一種定義的含義和特點,彼此之間的關(guān)系,秩的估計和計算是需要進一步研究的問題.(4)進一步研究求解更多特征值的方法.在一些具體問題中,特征值的含義也有待進一步研究.2一些新的因素優(yōu)化2.1分布式優(yōu)化研究多項式優(yōu)化是指目標函數(shù)和約束函數(shù)均為多項式的一類特殊的非線性規(guī)劃問題,由于多項式優(yōu)化問題的KKT條件仍然為一個多項式系統(tǒng),因此,多項式優(yōu)化問題的研究也包括多項式方程組問題.下面簡要從多項式優(yōu)化問題的數(shù)學(xué)模型、應(yīng)用和數(shù)值算法等方面,對其發(fā)展歷史、現(xiàn)狀與前景做一介紹.多項式優(yōu)化的研究歷史可追溯至Hilbert于1900年在巴黎召開的第二屆國際數(shù)學(xué)家大會上提出的第17個問題,即非負多項式與有理多項式(即兩個多項式的比)的平方和(SOS)的等價性討論.當(dāng)時,Hilbert猜想:任何一個實的非負多項式都能表示成有理多項式的平方和.1927年Artin證明該猜想成立.為建立一個實的非負多項式的有理多項式的平方和的表達式,Delzell給出了一類構(gòu)造性算法.多項式優(yōu)化不僅在非線性規(guī)劃問題中有基礎(chǔ)性應(yīng)用(如序列二次規(guī)劃算法、信賴域算法子問題等),一些混合整數(shù)規(guī)劃也可轉(zhuǎn)化成多項式優(yōu)化模型,而且經(jīng)濟、管理、交通、通信和工程中的大量實際問題都可以用多項式優(yōu)化來建模(如可見[40—50]).因此,多項式優(yōu)化問題的研究不但吸引了許多優(yōu)化研究學(xué)者的興趣,而且也引起了一批從事代數(shù)學(xué)研究學(xué)者的注意.他們分別從理論分析和數(shù)值計算等角度對該問題展開研究,取得了一系列重要研究成果.其中,由于二次優(yōu)化的特殊地位,其研究歷史尤為悠久、所得成果尤為豐富(可見[37,50-54]).另外,從量子力學(xué)和醫(yī)學(xué)成像中提煉出的多項式優(yōu)化問題屬于一類特殊的齊次多項式優(yōu)化問題.基于齊次(特別是高次齊次)多項式優(yōu)化與張量計算之間的密切關(guān)系,人們對這類多項式優(yōu)化問題進行了系統(tǒng)研究,得到很多有意義的結(jié)果,如張量的低秩逼近和分解等[27,31,43,55,56,57].多項式優(yōu)化問題一般是非凸的.因此在多數(shù)情況下是NP-難的,甚至在單位球上的齊次多項式極值問題也是如此.所以,要得到多項式優(yōu)化模型的全局最優(yōu)解是非常困難的.對于多項式優(yōu)化問題,早期的工作多是基于代數(shù)學(xué)的Grobner基和結(jié)式(Resultant)理論來尋求一個多項式優(yōu)化問題的所有臨界點(criticalpoints),從中尋求問題的最優(yōu)解.這類算法的缺陷是計算量太大,它只適用于稀疏和低維問題.但對于超圖譜理論、高階數(shù)理統(tǒng)計、復(fù)雜網(wǎng)絡(luò)設(shè)計、多板塊金融投資中的多項式優(yōu)化模型,由于所涉及的多項式往往重數(shù)或次數(shù)較高,問題的規(guī)模較大,因此這種Grobner基和結(jié)式算法難以執(zhí)行.多項式優(yōu)化問題的重要性及其在理論和算法設(shè)計上的困難成為推動多項式優(yōu)化研究不斷發(fā)展的動力.作為非線性優(yōu)化的特殊情形,設(shè)計求解其全局最優(yōu)解的(近似)算法成為優(yōu)化研究者的主要任務(wù).特別是,結(jié)合實際背景而提出的模型結(jié)構(gòu)特殊.研究全局最優(yōu)性條件并設(shè)計更為有效的近似算法成為多項式優(yōu)化研究的主要內(nèi)容之一-2.2分布式優(yōu)化的sos方法多項式優(yōu)化的研究大致分為連續(xù)型和離散型兩類,有時根據(jù)實際問題需要又包含分離出混合型多項式優(yōu)化模型.不論是連續(xù)型還是離散型二次規(guī)劃,由于其在非線性規(guī)劃中的獨特地位和在許多實際領(lǐng)域的廣泛應(yīng)用而受到特別關(guān)注.近年來,高次多項式優(yōu)化問題特別是具有特殊結(jié)構(gòu)的齊次多項式優(yōu)化問題的理論和算法研究取得重要進展,齊次高次模型也成為多項式優(yōu)化領(lǐng)域的研究熱點之一.對于多項式優(yōu)化問題,一個很自然的想法是使用已有的非線性規(guī)劃方法求解.但由于多項式優(yōu)化問題的特殊性,特別是問題的規(guī)模往往非常大,直接用這些方法來求解一般效率很低.多項式優(yōu)化問題的另一直接的解法是借助最優(yōu)性條件將其轉(zhuǎn)化為一個非線性方程組問題,然后設(shè)計求解方法.但在問題的規(guī)模很大時,這類方法計算量大的缺陷便凸顯出來.單位球面(可以在不同范數(shù)的意義下)約束的齊次多項式優(yōu)化模型是一類特殊的多項式優(yōu)化問題,此模型中的多項式目標函數(shù)次數(shù)可能相對較高.這類模型在材料科學(xué)、統(tǒng)計學(xué)中有廣泛應(yīng)用,也是高階張量特征值與特征向量概念的優(yōu)化模型再現(xiàn),正如前一部分所說,高階張量低秩逼近與分解問題也可以表示為單位球面約束的齊次多項式優(yōu)化模型.對這種特殊結(jié)構(gòu)的多項式優(yōu)化問題,Qi等通過引入張量特征值給出了一個循環(huán)遞進的求解算法.對于從證券投資組合問題提出的一類非凸多項式優(yōu)化問題,Rustem等提出了一類擴散求解方法.對于多項式整數(shù)規(guī)劃問題,一個比較有效的技術(shù)是將其轉(zhuǎn)化為最大全中的獨立集問題.對于連續(xù)型多項式優(yōu)化問題,一個比較流行的技術(shù)是將其松弛成一個可以在多項式時間內(nèi)(近似)求解的凸優(yōu)化模型,如線性規(guī)劃(LP)、半定規(guī)劃(SDP)、矩的對偶松弛等.由于SDP問題有許多類似于線性規(guī)劃的特征與性質(zhì),如SDP模型具有結(jié)構(gòu)優(yōu)良的對偶形式,在適當(dāng)?shù)募s束規(guī)格(如Slater約束規(guī)格)下,強對偶定理成立.這些性質(zhì)成為設(shè)計各種求解SDP模型有效算法的理論基礎(chǔ).20世紀90年代,Alizadelh、Nesterov和Nemirovskii分別獨立地提出了求解SDP模型的內(nèi)點算法,這為多項式優(yōu)化問題的求解提供了方便.SDP內(nèi)點算法不僅使SDP模型在理論上更為重要,實際應(yīng)用也更為廣泛.由于SDP模型在理論上多項式時間可解,也有一些有效的算法,能以此用來得到許多整數(shù)規(guī)劃和全局優(yōu)化中難問題的緊逼近,所以在控制論、線路設(shè)計、傳感網(wǎng)絡(luò)定位和主成分分析等許多領(lǐng)域有廣泛應(yīng)用,同時也為近似求解多項式規(guī)劃特別是非凸二次規(guī)劃等NP-難問題提供了一個極為有效的途徑.多項式優(yōu)化問題的另一種常見技術(shù)是基于非負多項式和多項式的平方和之間的關(guān)系而建立的SOS方法.該方法主要通過對原多項式優(yōu)化問題進行松弛得到序列半定規(guī)劃問題使其最優(yōu)值單調(diào)收斂于原問題的最優(yōu)值.從理論上講,SOS方法可以求解任何多項式優(yōu)化問題并達到所要求的計算精度.對于一元多項式優(yōu)化問題,Nesterov證明SOS方法在多項式時間內(nèi)可以得到問題的最優(yōu)解.該結(jié)論同樣適用于無約束的可以表示成SOS形式的多元二次多項式和二元四次多項式優(yōu)化問題.對于一般的多項式優(yōu)化問題,Shor等通過某種轉(zhuǎn)換將其轉(zhuǎn)化為一個目標函數(shù)和約束函數(shù)均為二次多項式的優(yōu)化問題,然后通過松弛技術(shù)再將該問題轉(zhuǎn)化為一個標準形式下的凸線性矩陣不等式問題(LMI).利用現(xiàn)成的算法可以在較短的時間內(nèi)得到原問題最優(yōu)值的一個下界.為使得到的下界更接近原問題的最優(yōu)值,需要在中間轉(zhuǎn)換的(二次)多項式優(yōu)化問題中增加二次約束函數(shù).該類方法后來通過結(jié)合平方和(SOS)方法被Parrilo等進一步改進.盡管并非所有的非負多項式都能表示成多項式的平方和,但這類方法在實際計算過程中非常有效.SOS方法與半定規(guī)劃問題密切相關(guān),作為其變種,Lasserre等通過矩(moment)矩陣建立了多項式優(yōu)化問題的半定規(guī)劃問題的轉(zhuǎn)化形式,并通過半定規(guī)劃問題的最優(yōu)值序列來界定原問題的最優(yōu)值,以達到所想要的精度.SOS方法需要求解半定規(guī)劃問題,所以在問題的規(guī)模較大的時候,該算法變得不再實用.用矩-SOS方法有時可在有限步內(nèi)得到多項式優(yōu)化的全局最優(yōu)值,而且有比較好的理論性質(zhì)和數(shù)值效果.但由于求解過程中需要計算的半定規(guī)劃問題的規(guī)模關(guān)于原問題中的變量維數(shù)和多項式的最高次數(shù)成近似指數(shù)函數(shù),因此也只能用來計算規(guī)模較小或具有特殊形式(如對稱、稀疏)的較大規(guī)模多項式優(yōu)化問題,而且要得到原問題的最優(yōu)解有時需要對中間問題增加新的約束重新計算,從而導(dǎo)致計算量的陡增.這成為制約多項式優(yōu)化發(fā)展的一個瓶頸.對于張量形式的多項式優(yōu)化,由于算法的計算量與張量的階數(shù)呈指數(shù)增長,為減少每一迭代步的計算量,人們使用交替優(yōu)化方法或分層技術(shù)求解對于偶齊次多項式優(yōu)化問題,引進平移技術(shù)可在一般情況下建立冪法的全局收斂性,但該方法的計算效率有待提高.基于上述分析,人們從另外一個角度對該問題展開研究:尋求多項式優(yōu)化問題的近似解.針對最大割(Max-Cut)問題中的二次規(guī)劃模型,Goemans和Williamsorn使用松弛方法得到原問題的0.878近似比算法.隨后,這一重要思想相繼被許多學(xué)者推廣到更一般的二次規(guī)劃情形([26,77-81]).特別地,對于“1,-1”約束下的半正定二次多項式優(yōu)化問題,Nesterov得到0.636近似比算法.這些近似算法是迄今為止最有效的算法.對于定義在多個橢球的交集上的二次規(guī)劃問題,Nemirovski等提出了一個近似算法,該模型后來被Luo等推廣.在以上所涉及的近似算法中,目標函數(shù)均是二次的.而對于次數(shù)較高的多項式優(yōu)化問題,其近似算法的研究仍處于起步階段.針對具有簡單約束的特殊形式高次多項式優(yōu)化問題,DeKlerk等給出了首個多項式時間近似方案(PTAS).隨后,Barvinok等推廣了該方法,對定義在單位球面上的多項式優(yōu)化問題,給出了一類新的近似算法.對定義在多個橢球的交集上的四次多項式優(yōu)化問題,Luo和Zhang將其松弛成二次半定規(guī)劃問題,并進一步通過線性化方法建立了有效算法.如前所述,對稱張量或偏對稱長方張量最大(小)Z-特征值(奇異值)可以歸結(jié)為單位球上齊次張量函數(shù)全局最優(yōu)問題.Ling等提出了雙二次齊次函數(shù)在兩個球面約束下的最優(yōu)化模型,通過將其松弛為雙線性半定規(guī)劃模型給出了近似算法,其近似比值與中結(jié)果相當(dāng).Yang等考慮了更一般的模型,推廣了已有的結(jié)果.另外,和非凸二次規(guī)劃半定松弛不同的是,雙二次或四次張量函數(shù)的半定松弛,得到的優(yōu)化問題仍然是非凸優(yōu)化問題,一種技術(shù)是再采用一次松弛,以便得到一個可以計算的凸優(yōu)化問題.Ling等和Zhang等通過雙線性半定規(guī)劃考慮了帶二次約束的雙二次多項式優(yōu)化問題,給出了多項式時間的近似算法.此外,Zhang等考慮了單位球面上的三次齊次多項式優(yōu)化問題,并給出了近似度估計.對于任意次齊次多項式優(yōu)化在多個二次約束下的近似算法的突破來自于He等的工作,他們首次提出了張量松弛的方法,通過將齊次多項式松弛為多重線性函數(shù)并建立其中的橋梁來處理一般的齊次多項式,給出了相應(yīng)的近似算法.后來,He等又對定義在任意閉凸集上的非齊次多項式優(yōu)化問題給出了多項式時間的近似算法,這是目前多項式優(yōu)化近似算法研究中唯一能處理任意次非齊次多項式的研究結(jié)果.此后,So又采取計算幾何與張量松弛相結(jié)合的方法,對球面約束下齊次多項式優(yōu)化問題提出了新的近似算法,提高了近似比值.此外,He等還考慮了整數(shù)多項式優(yōu)化問題和混合多項式優(yōu)化問題.有關(guān)多項式優(yōu)化問題近似算法的最新發(fā)展,可參考Li等最近的專著.近來,從對偶角度對多項式優(yōu)化問題最優(yōu)值界的研究也逐漸興起,其中包括DeK-lerk等和Nie所做的初步工作.與近似算法不同,這類方法只能給出最大值問題的上界(或者最小值問題的下界),也不能得到近似解.但所用方法都是基于SOS松弛分析.從實用角度來看,如果對于某個特殊的多項式優(yōu)化問題例子,此類估計恰好能達到近似算法的界,也就相當(dāng)于找到了此問題的最優(yōu)解.除了連續(xù)型的多項式優(yōu)化模型,決策變量僅取離散值的多項式優(yōu)化模型也是一類被廣泛應(yīng)用和研究的多項式優(yōu)化問題.這類多項式優(yōu)化模型不僅在圖論而且在神經(jīng)網(wǎng)絡(luò)、代碼糾差等研究領(lǐng)域有廣泛應(yīng)用.離散決策變量的二次規(guī)劃和雙線性模型已被廣泛研究,尤其是離散決策變量的二次規(guī)劃模型,由于其與各種圖劃分問題密切相關(guān)而被深入研究.自然地,離散決策變量的高次齊次多項式優(yōu)化和多重線性優(yōu)化模型都是值得研究的問題.求解多項式優(yōu)化問題軟件目前相對較少,早期的軟件有Gloptipoly,SOSTOOLS和基于稀疏結(jié)構(gòu)多項式優(yōu)化問題的軟件SparsePOP等.這些軟件大都基于SOS松弛方法并借助半定規(guī)劃的求解算法編寫而成,因此只能解決較小規(guī)模的多項式優(yōu)化模型.但是,隨著計算機、高速網(wǎng)絡(luò)的不斷發(fā)展與并行計算技術(shù)的不斷開發(fā),求解較大規(guī)模特別稀疏的SDP模型成為可能.2.3非負4.4.2初心電lamm和c.3.2次政府分布式問題多項式優(yōu)化問題是一類特殊的數(shù)學(xué)規(guī)劃問題.一方面,它與連續(xù)優(yōu)化、離散優(yōu)化和凸優(yōu)化等數(shù)學(xué)規(guī)劃的其他分支融合與交叉;另一方面,它在理論上又與代數(shù)幾何、交換代數(shù)和矩理論等純數(shù)學(xué)領(lǐng)域有著密切聯(lián)系,內(nèi)容相當(dāng)廣泛.我們將從理論、算法與應(yīng)用三個方面簡要敘述該領(lǐng)域今后發(fā)展的若干趨勢和重要問題.(1)理論方面基于矩理論的SOS方法的進一步研究和多項式錐性質(zhì)分析等將成為關(guān)鍵研究問題.a.目前,基于Lasserre等級分解的SOS方法在多項式優(yōu)化理論研究中占有主導(dǎo)地位,這也將是多項式優(yōu)化理論研究的一個重要發(fā)展方向,其主要內(nèi)容包括:Lasserre等級的有限收斂分析,Nie對此已做了一些初步的工作;某些特殊多項式優(yōu)化問題的SOS方法對稱性研究,例如Riener的研究;逆多項式優(yōu)化問題.b.線性錐優(yōu)化特別是半定規(guī)劃在許多領(lǐng)域中的應(yīng)用已非常顯著.自從Burer證明一大類非凸(含連續(xù)和離散變量)的二次規(guī)劃問題可以等價轉(zhuǎn)換為雙正錐規(guī)劃(copositiveprogramming)后,對于雙正錐本身的研究已引起重要關(guān)注,進一步引發(fā)了對一些“難錐”的研究.Jiang等研究了非負四次型錐,并證明一大類四次非齊次多項式問題亦可等價轉(zhuǎn)換為線性四次型錐規(guī)劃問題.與一般的非負二次型錐(半正定矩陣錐)不同,非負四次型錐研究內(nèi)容遠比二次型錐豐富.目前,相關(guān)研究僅處于初始階段.最近,Ahmadi等證明了判別一般四次多項式的凹凸性是強NP-難的.這些初步研究表明,對于高次多項式錐的理論研究非常重要,它將是推動多項式優(yōu)化理論發(fā)展的重要課題之一.c.探析一般形式或具有實際背景且特殊結(jié)構(gòu)的多項式優(yōu)化問題的全局最優(yōu)解的結(jié)構(gòu)性質(zhì)和判定準則.充分利用多項式函數(shù)的特殊性建立最優(yōu)性條件,也許可為求解一些特殊的多項式優(yōu)化問題(如張量的最小Z-特征值問題)提供新途徑.雖已有一些研究(見),但這類問題的研究結(jié)果仍不是很多,它們是多項式全局優(yōu)化的重要內(nèi)容之一.(2)算法方面多項式優(yōu)化問題的全局最優(yōu)算法設(shè)計是一項艱難的任務(wù).目前,雖有許多不同類型的算法,但總體來說尚不完備.進一步的有效