[發明專利]一種基于凹凸規劃的快速近似方法

在審

• 申請號: 201810526436.2
• 申請日: 2018-05-29
• 公開（公告）號: CN108763156A
• 公開（公告）日: 2018-11-06
• 發明（設計）人: 楊杰;劉方輝;黃曉霖
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F17/15
• 分類號: G06F17/15;G06F17/16
• 代理公司: 上海恒慧知識產權代理事務所(特殊普通合伙) 31317
• 代理人: 徐紅銀

本發明提供了一種基于凹凸規劃的快速近似方法，應用在采用非正定核的邏輯回歸模型中，所述方法包括：將非正定核的邏輯回歸模型拆解成兩個凸函數之差的形式，對其中一個凸函數進行一階泰勒展開，得到一個凸優化問題，并對所述凸優化問題進行迭代求解直到得到相應的求解結果，在所述求解結果的基礎上繼續對所述凸函數進行一階泰勒展開，交替迭代以上流程，直至收斂。從而可以實現凹凸規劃的快速求解過程，對大數據規模下的高維數據具有很好的分類效果以及收斂速度，方法實現簡單，易于操作。

技術領域

本發明涉及非凸優化、數據處理技術領域，具體地，涉及一種基于凹凸規劃的快速近似方法。

背景技術

核方法在機器學習、計算機視覺、生物信息學等諸多領域被廣泛的應用。核方法要求核矩陣必須半正定，進而保證相應的模型是凸優化問題且備選函數處于再生希爾伯特空間。但是，在圖像處理、流形學習、穩健學習等領域，人們越來越多地遇見不滿足半正定性條件的核函數，例如：采用KL散度所定義的相似性度量就不滿足正定性的限制；由于測量的不準確性，使得獲取的核矩陣受到噪聲的污染，變成非正定核矩陣。由于核函數的非正定性，傳統的再生希爾伯特空間理論不在成立，問題的求解也從一個凸優化問題變成一個非凸優化問題。如何在理論和實際算法上對非正定核進行研究，這也正是核方法所研究的內容。

在現有的非凸優化方法中，凹凸規劃是一種非常常見的方法，它的思路在于將待求解的目標函數拆分成兩個凸函數之差的形式，通過對其中一個凸函數在當前點進行泰勒展開，從而得到一個關于原問題的凸近似，求得關于該凸近似問題的最優解；隨后在該最優解處進行泰勒展開，直至整體目標函數收斂。但是，傳統的凹凸規劃需要進行兩重交替迭代，外層循環在當前點獲得原問題的凸近似，內層循環精確求解一個凸優化問題。隨著外層循環迭代次數的增加，算法的計算復雜度呈線性增長。對于數據規模較大的情況，該方法的計算效率較低，具有較大的局限性。

現有技術中，出現的上述凹凸規劃技術用以求解非凸優化問題，比如：

[1]Francois Bertrand Akoa,“Combining DC algorithms(DCAs)anddecomposition techniques for the training of nonpositive-semidefinitekernels,”IEEE Transactions on Neural Networks,vol.19,no.11,pp.1854–1872,2008.

[2]Haiming Xu,Hui Xue,Xiaohong Chen,and Yunyun Wang,“Solvingindefinite kernel support vector machine with difference ofconvexfunctions programming,”in Proceedings of AAAI Conference onArtificialIntelligence,2017,pp.1610–1616.

然而上述技術均采用傳統的凹凸規劃方法進行求解，計算效率較低。因此，隨著現在各個領域實驗數據的不斷增多，在數據容量、維數越來越大的情況下，亟待有一種方法在保證計算效果不出現明顯降低的前提下，能夠快速求解凹凸規劃問題。

發明內容

針對現有技術中的缺陷，本發明的目的是提供一種基于凹凸規劃的快速近似求解方法，可以有效的加速求解過程，方法實現簡單，易于操作，非常適合大數據規模下的高維數據處理應用。

本發明提供一種基于凹凸規劃的快速近似方法，包括：

將非正定核的邏輯回歸模型拆解成兩個凸函數之差的形式；

對其中任一個凸函數進行一階泰勒展開，得到第一凸優化問題，并對所述第一凸優化問題進行迭代求解，直到得到相應的第一求解結果；