【作者】 王鑫；

【导师】 彭定涛；

【作者基本信息】 贵州大学 ， 数学， 2018， 硕士

【摘要】 稀疏优化在信号重构、图像恢复、模型识别、变量选择等领域具有广泛的应用。例如,在实际生活中,信号往往是稀疏的,即使信号本身不稀疏,在一定的变换域(如傅里叶变化、小波变换、曲波变换等)下,信号的表示也是呈现出多数稀疏近似为零的特征,只需对较大的系数进行存储和传输,仍可构建出原始信号。本文针对稀疏优化问题的最优性理论及算法进行了研究。具体内容如下:(1)定义了限制性Slater约束规格,建立稀疏约束非线性规划问题局部解与其Karush-Kuhn-Tucker(KKT)条件之间的联系。此外,给出箱约束情况下稀疏约束非线性规划问题的一阶必要性条件的具体形式。(2)考虑三类稀疏非线性规划问题:1)带稀疏约束的非线性规划问题;2)带稀疏正则项的非线性规划问题;3)带正则项和约束惩罚项的无约束优化问题。分析了在限制性线性独立约束规格和限制性Mangasarian-Fromovitz约束规格成立的条件下,这三类问题之间稳定点的关系。通过连续可微函数、稀疏正则项的局部性质及稳定点性质,分析了不同模型之间局部最优解的关系。通过限制迭代的方法,分析了前两类问题之间全局最优解的关系。(3)针对带箱约束稀疏约束的优化问题设计有效算法。对一般箱约束稀疏约束优化问题,提出了一类坐标梯度算法(Coordinate gradient algorithm),分析算法的收敛性质。对非负箱约束稀疏约束优化问题,分析点到可行域的投影过程,引入改进的迭代硬阈值算法(Improved terative hard thresholding algorithm)。(4)最后,我们介绍了上述两种算法的随机生成问题模拟、稀疏信号恢复以及图像恢复三种算法数值实验及实验结果。更多还原

【Abstract】 Sparse optimization has wide applications in signal reconstruction,image restoration,model identification,variable selection and other fields.For example,in real life,the signal is often sparse or under some transform domains--such as Fourier transform,wavelet transform and curvelet transform,etc.--the representation of a signal which is not sparse also shows characteristics of the most sparse approximation is zero.In this case,we only need store and transfer the signal with large coefficient and it is enough to reconstruct the original signal.In this paper,we study the theory and algorithm for sparse nonlinear programming.The details are given as follows:(1)We define the restricted Slater constraint qualification.Based on the constraint qualification,we establish the relationship between local solution and Karush-Kuhn-Tucker(KKT)conditions of sparse nonlinear programming.In addition,we provide the specific expression of the first order necessary optimality condition of sparse constraint nonlinear programming with box constraint.(2)We consider three types of sparse nonlinear programming problems: 1)Nonlinear programming with sparse constraints;2)Nonlinear programming with sparse regular item;3)Nonlinear programming with sparse regular item and penalty item.We introduce their optimality conditions,which include first order and second order optimality conditions.Using restricted Mangasarian Fromovitz constraint qualification and the decomposition properties of normal cones to the sparse constrained feasible set,we analyze the relationship of stable points among these problems.Base on properties of continuous differentiable functions,sparse regular item and local optimal solutions,we get the relationship of local optimal solutions among these problems.Finally,we analyze the relationship of global optimal solutions by limiting iterative method.(3)For sparse constraint optimization problem with box constraint,we design two effective algorithms.Under the condition with a general box constraint,we design the coordinate gradient algorithm and analyze its convergence property.For the problem with a nonnegative box constraint,we analyze the project process of a point to feasible set and usethe improved iterative hard thresholding algorithm to solve this problem.(4)Finally,by our algorithm,we introduce three kinds of numerical experiments:Stochastic problem simulation,Sparse signal recovery and Image restoration and corresponding results.更多还原