【作者】 秦林霞；

【导师】 修乃华；

【作者基本信息】 北京交通大学 ， 运筹学与控制论， 2013， 博士

【摘要】 非负稀疏优化是指利用待恢复变量的稀疏性,寻找一个带有非负约束的欠定线性等式系统最稀疏的解.在向量空间,该问题实质上是非负l0极小问题；而在矩阵空间,该问题表现为半定秩极小问题.非负稀疏优化在DNA微阵列、量子成像、医学成像、光谱学、网络定位及隐马尔可夫模型等领域有广泛应用,并与反问题、主成分分析、组合优化、线性规划、半定规划等问题联系密切,近年来逐渐引起数学及众多应用领域专家的重视,成为一个热点研究课题.本文主要研究非负稀疏优化的解集性质及精确松弛条件.第一章绪论部分.主要对非负稀疏优化问题的研究意义、数学模型做了简单介绍,并全面综述了非负稀疏优化松弛理论的研究现状.第二章探讨了非负稀疏优化问题的解集特征.针对向量空间非负稀疏优化,首先借助零范数的不同取值,引入n维向量空间的特殊划分,并由此证明了该问题任意两个不同的最优解必有不同的支撑集,从而证得其最优解必然在其可行域的极点上达到.这为直接利用启发式算法求解此组合问题,或者寻找更多合适的松弛模型奠定了基础.针对矩阵空间非负稀疏优化,我们证明若其任意两个不同最优解的特征值分解中有相同的正交矩阵,则对应的特征值向量必有不同的支撑集.第三章针对向量空间非负稀疏优化问题的凸松弛及非凸松弛,提出了广义Z-矩阵精确松弛条件.第一节通过引入广义Z-矩阵概念和最小元素理论,我们研究了特殊条件下非负稀疏优化问题的可行性.第二节我们证明如果测量矩阵是一个广义Z-矩阵且观测向量b非负,则向量空间非负稀疏优化问题与其线性松弛及lp(0<p<1)松弛具有共同的唯一最优解.事实上,此最优解也恰恰是最小元素解.同时,在我们的条件下,精确恢复一个k-稀疏信号只需利用不少于k个线性观测值.第三节通过分析SISO干扰信道问题的应用实例,验证其完全满足我们的精确松弛条件.第四章针对非负稀疏优化的凸松弛与非凸松弛,提出了RIP类精确松弛条件.第一节介绍了实对称矩阵特征值的若干性质.第二节通过定义非负限制等距/正交常数,我们给出了向量空间非负稀疏优化问题解的存在性及唯一性条件,并进一步提出其线性松弛及lp松弛的精确松弛条件.第三节通过定义半定限制等距/正交常数,我们给出了矩阵空间非负稀疏优化问题解的唯一性条件,并进一步得到其凸松弛及Schatten p-松弛的精确松弛条件.特别地,我们得到了与参数p无关的精确松弛条件.第五章是推广与展望部分.对称锥可以看作是非负向量锥和半定矩阵锥的推广,故而第一节我们给出关于对称锥上问题的一些研究结果.第二节通过深入分析非负稀疏优化的研究现状,我们列举了目前值得考虑的几个问题,这些问题有可能成为下一步工作的方向.更多还原

【Abstract】 The nonnegative sparse optimization is to find the sparsest solution of an underdeter-mined linear equation with the nonnegative constraints, making use of the sparsity of the variable under consideration. In the vector space, it is essentially the nonnegative l0norm minimization; while in the matrix space, it becomes the semidefinite matrix rank minimiza-tion. Owing to the wide applications in DNA microarrays, quantum state tomography, medical imaging, spectroscopy, sensor location and hidden Markov models together with the close connection with inverse problems,principal component analysis, combinatorial optimization, linear optimization and semidefinite optimization, the nonnegative sparse optimization has attracted much attention of both mathematicians and engineers in many application areas, and obtained rapid development in recent years. This thesis is mainly concerned with the solution property and the exact relaxation conditions.Chapter1briefly introduces the significance and mathematical models of nonnegative sparse optimization, and reviews the research status of the relaxation theory.In chapter2, we discuss the solution property of the nonnegative sparse optimiza-tion. For the nonnegative sparse optimization over vector space, we introduce the special partition for the space Rn in the light of the l0norm function, based on which we show that any two distinct solutions of the desired problem must have different support sets. hence we prove that any solution to the underlying problem must be one of the extreme points of the feasible set. This can lay the foundation for the heuristic algorithms or some new relaxations of the underlying combinatorial problem. For the nonnegative sparse op- timization over matrix space, we show that when the eigenvalue decomposition of any two different solutions share the same orthogonal matrix, the corresponding eigenvalue vectors can not share the same support set.In chapter3, we investigate the generalized Z-matrix exact relaxation condition for both the convex and nonconvex relaxations of the nonnegative sparse optimization over vector space. Firstly, by introducing the concept of generalized Z-matrix and least ele-ment theory, we investigate the feasibility of the nonnegative l0norm optimization under some conditions. Moreover, we show that if the observation vector is nonnegative and the measurement matrix is a generalized Z-matrix, the aforementioned problem and its linear/lp (0<p<1) relaxation share the unique common solution, which is exactly the least element solution.Meanwhile, under our condition, one can accurately recover a k-sparse vector with only no less than k linear measurements.At the end of this part, we analyze the application in the single input single output interference channel where our recovery condition fit perfectly.In chapter4, we devote to the RIP type exact relaxation conditions for both convex and nonconvex relaxations of the nonnegative sparse optimization. Section1provides some properties of the eigenvalue decomposition of real symmetric matrices. In section2, by defining the constants NRIC and NROC. we give the existence and uniqueness condition of the solution to the nonnegative sparse optimization over vector space, and further get the exact recovery condition of the above program via both the linear and lp relaxation. In section3we discuss the uniqueness condition of the solution to the nonnegative sparse optimization over matrix space, and propose sufficient condition for the exact recovery via both the semidefinite and Schatten p-norm relaxations. In particular, we get the recovery condition that is independent of the parameter p.In chapter5, some generalizations are studied and several future issues are discussed. Since the nonnegative orthant and the semidefinite matrix cone are special cases of the so-called symmetric cone, some useful properties of solution sets of symmetric cone opti-mization problems are explored in the first section. By reviewing the existing results on the nonnegative optimization, four possible research issues are pointed out which deserve future study.更多还原