本文選題：低秩半定矩陣恢復(fù) + 最優(yōu)解��； 參考：《北京交通大學(xué)》2015年博士論文

【摘要】：低秩半定矩陣恢復(fù)問(wèn)題在信號(hào)與圖像處理、金融學(xué)、控制、圖理論、系統(tǒng)識(shí)別等眾多領(lǐng)域中都有著廣泛的應(yīng)用.它是最優(yōu)化及其相關(guān)領(lǐng)域的一個(gè)熱點(diǎn)研究課題.通常,低秩半定矩陣恢復(fù)問(wèn)題是NP-難的.為了克服這個(gè)困難,凸的核范數(shù)松弛技術(shù)被廣泛應(yīng)用在文獻(xiàn)中,但它并不總是有效的.本文主要針對(duì)低秩半定矩陣恢復(fù)問(wèn)題的非凸松弛模型、不松弛的秩正則化模型以及秩在約束條件下的最小二乘模型分別設(shè)計(jì)有效且穩(wěn)定的算法.針對(duì)低秩半定矩陣恢復(fù)問(wèn)題的特例：低秩半定矩陣完備化問(wèn)題,首先證明在一定條件下,低秩半定矩陣完備化問(wèn)題與它的S1/2松弛模型有相同的唯一解.接著建立了S1/2正則化模型解的漸近性.進(jìn)一步證明了S1/2正則化模型的全局最優(yōu)解是某個(gè)對(duì)稱(chēng)矩陣半閾值算子的不動(dòng)點(diǎn).基于此條件,設(shè)計(jì)了一種求解S1/2正則化模型的算法框架,分析了它的收斂性.結(jié)合最優(yōu)的正則化參數(shù)設(shè)計(jì)及截?cái)嗉夹g(shù),進(jìn)一步設(shè)計(jì)了求解S1/2正則化模型可執(zhí)行的半閾值特征值算法.數(shù)值實(shí)驗(yàn)表明該算法的有效性和魯棒性.針對(duì)低秩半定矩陣恢復(fù)問(wèn)題,建立了它的非凸Sp(0p1)正則化模型.通過(guò)發(fā)展對(duì)稱(chēng)矩陣p-閾值算子表示理論,建立了其全局最優(yōu)解的必要性條件,并給出了全局最優(yōu)解正特征值的精確下界.進(jìn)一步得到了全局最優(yōu)解具有一定低秩性的一個(gè)充分條件.設(shè)計(jì)了p-閾值特征值算法,并給出收斂性分析.數(shù)值實(shí)驗(yàn)表明該算法能有效地求解這類(lèi)問(wèn)題.針對(duì)低秩半定矩陣恢復(fù)問(wèn)題,建立了它的秩正則化模型.利用特殊秩函數(shù)全局極小解具有顯式表達(dá)式,證明了其全局最優(yōu)解是某一對(duì)稱(chēng)矩陣硬閾值算子的不動(dòng)點(diǎn).基于此不動(dòng)點(diǎn)方程,設(shè)計(jì)了一種硬閾值算法,并給出相應(yīng)的收斂性分析.數(shù)值實(shí)驗(yàn)表明所設(shè)計(jì)算法的有效性及穩(wěn)定性.針對(duì)低秩半定矩陣恢復(fù)問(wèn)題秩在約束條件下的最小二乘模型,通過(guò)目標(biāo)函數(shù)的優(yōu)超函數(shù),將原問(wèn)題轉(zhuǎn)化成非凸集上的投影.利用非凸集上投影的顯式表達(dá)式,給出了原問(wèn)題全局最優(yōu)解的一個(gè)必要性條件.進(jìn)而設(shè)計(jì)了求解該問(wèn)題的優(yōu)超算法,并證明了其迭代點(diǎn)列的任何一個(gè)聚點(diǎn)都是原問(wèn)題的一階穩(wěn)定點(diǎn).
[Abstract]:Low-rank semidefinite matrix restoration problem has been widely used in many fields such as signal and image processing, finance, control, graph theory, system recognition and so on. It is a hot research topic in optimization and related fields. In general, the restoration problem of low rank semidefinite matrices is NP- difficult. In order to overcome this difficulty, convex kernel norm relaxation technique is widely used in literature, but it is not always effective. In this paper, an efficient and stable algorithm is designed for the non-convex relaxation model, the non-relaxed rank regularization model and the least square model of the rank under the constraint conditions for the restoration of the low-rank semidefinite matrix. For the special case of the low rank semidefinite matrix restoration problem: the low rank semidefinite matrix completion problem, it is first proved that, under certain conditions, the low rank semidefinite matrix completeness problem has the same unique solution as its S 1 / 2 relaxation model. Then the asymptotic behavior of the solution of S 1 / 2 regularization model is established. It is further proved that the global optimal solution of the S1 / 2 regularization model is a fixed point of the semi-threshold operator of a symmetric matrix. Based on this condition, an algorithm framework for solving S1 / 2 regularization model is designed and its convergence is analyzed. Based on the optimal regularization parameter design and truncation technique, an executable semi-threshold eigenvalue algorithm for S1 / 2 regularization model is designed. Numerical experiments show that the algorithm is effective and robust. A non-convex Spn0p1) regularization model is established for the restoration of low rank semidefinite matrices. By developing the representation theory of symmetric matrix p-threshold operator, the necessary conditions for the global optimal solution are established, and the exact lower bound of the positive eigenvalue of the global optimal solution is given. Furthermore, a sufficient condition for the global optimal solution to have a certain low rank is obtained. The p-threshold eigenvalue algorithm is designed and the convergence analysis is given. Numerical experiments show that the algorithm can solve this kind of problem effectively. A rank regularization model is established for the restoration of low rank semidefinite matrices. It is proved that the global optimal solution is a fixed point of a symmetric matrix hard threshold operator by using the explicit expression of the global minimal solution of a special rank function. Based on the fixed point equation, a hard threshold algorithm is designed and the convergence analysis is given. Numerical experiments show the effectiveness and stability of the proposed algorithm. For the least square model of the low rank semidefinite matrix restoration problem under the constraint condition, the original problem is transformed into a projection on a non-convex set by the optimal superfunction of the objective function. By using the explicit expression of projection on the non-convex set, a necessary condition for the global optimal solution of the original problem is given. Furthermore, an optimal superalgorithm for solving the problem is designed, and it is proved that any accumulation point of the iterative point sequence is the first order stable point of the original problem.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O151.21

【相似文獻(xiàn)】

相關(guān)博士學(xué)位論文 前1條

1 陳永強(qiáng);低秩半定矩陣恢復(fù)算法研究[D];北京交通大學(xué);2015年

，

本文編號(hào)：1866369