【作者】 谷伟哲；

【导师】 黄正海；

【作者基本信息】 天津大学 ， 系统工程， 2010， 博士

【摘要】 光滑算法已经成功地应用于求解各类优化问题.在其全局收敛性分析中,提出了各种涉及到所考虑问题的可行性与可解性的假设,这样的假设在文献中被称做正则性假设.然而,这些假设在很多情况下是很难验证的.众所周知:齐次自对偶内点算法能够求解一些优化问题且在不需要任何正则性假设的情况下可获得全局收敛性.一个自然的问题是光滑算法是否也具有这样好的收敛性?本博士论文将对这一问题做出探讨.具体如下:首先,本文基于单调线性互补问题(LCP)新构造的扩充系统,提出了一个求解LCP的光滑算法,并且证明算法在不需要任何正则性假设的情况下是全局收敛的.特别地,若LCP可解,则算法给出LCP的一个极大互补解,或者给出一个指标表明LCP是可解的,对于后一种情况,用已有的光滑算法直接求解,不需添加任何假设,可以得到LCP的一个极大互补解;若LCP是不可行的,则算法给出一个指标表明LCP是不可行的.其次,本文针对对称锥线性规划(SCLP),构造一个齐次自对偶模型,提出了一个光滑算法.在对SCLP不做任何正则性假设的情况下,可以得到算法的全局收敛性.此算法在每一次迭代过程中,只需要求解一个线性系统和执行一次线搜索.特别地,若SCLP可解,则通过使用算法求得的解可以得到SCLP的一个解;若SCLP是强不可行的,则算法给出一个指标表明SCLP是不可行的.本文对算法做了一些数值计算,实验表明:实际计算的结果与得到的理论结果是相符的.最后,本文基于已提出的SCLP的齐次自对偶模型,结合非精确牛顿法的技术,提出了一个非精确光滑算法.该算法具备了前面光滑算法所有的性质,而且在每个迭代步中,用共轭梯度法近似地求解牛顿方程,因而它可以用于求解大规模问题.我们将其应用于目前信号处理领域的研究热点之一――压缩感知理论.作为压缩感知理论中信号恢复的重构算法,与其它流行的算法相比,它能更准确地恢复信号.更多还原

【Abstract】 Smoothing algorithms have been proposed for solving various optimiza-tion problems successfully. In the analysis of their global convergence, variousassumptions have been presented in the literature, such as the existence ofstrictly feasible points or optimal solutions, which are called regularity as-sumptions. However, it is possible that it is very di?cult to check whetherthese assumptions hold or not. It is well known that the homogeneous andself-dual interior point methods have been proposed for solving some opti-mization problems and shown to be globally convergent without requiring anyregularity assumption. A natural question is whether a smoothing algorithmhas such a good property? This thesis gives some studies on this topic.Firstly, we present a smoothing algorithm for solving an augmented sys-tem constructed by the standard monotone linear complementarity problem(LCP). The algorithm is showed to be globally convergent without requiringany regularity assumption. In particular, if the LCP has a solution, then thealgorithm either generates a maximal complementary solution of the LCP ordetects correctly solvability of the LCP, and in the latter case, an existingsmoothing algorithm can be directly applied to solve the LCP without anyadditional assumption and it generates a maximal complementary solution ofthe LCP; and if the LCP is infeasible, then the algorithm detects correctlyinfeasibility of the LCP.Secondly, we propose a smoothing algorithm for solving the symmetriccone linear program (SCLP) by making use of an homogeneous and self-dualmodel constructed by the SCLP. This algorithm is proved to be globally con-vergent without requiring any regularity assumption. It only needs to solveone system of linear equations and to perform one line search at each itera-tion. In particular, if the SCLP has a solution, the algorithm will generate asolution of the SCLP; and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of the SCLP. We also reported some prelimi-nary numerical results of the algorithm. The numerical results show that ourtheoretical findings coincide with the practical results.Finally, based on the proposed homogeneous and self-dual model of theSCLP and the technique from inexact Newton methods, we present an inexactsmoothing algorithm for the SCLP, which has all the properties that the formersmoothing algorithm has. Since we solve the Newton equation approximatelyby using the conjugate gradient method at each iteration, the proposed inexactsmoothing algorithm can solve large-scale problems. We apply the algorithmto recovery problems in compressive sensing theory, which is one of the populartopics in signal processing field. As one of the compressive sensing recoveryalgorithms, this algorithm could recover sparse signals more exactly than theother state-of-the-art algorithms.更多还原