摘要
近年来，带箱型约束的L2-L p(0<p<1)最小化问题在信号还原、变量选择等方面有着广泛的应用。然而，这是一类非凸非光滑非Lipschitz连续的约束优化问题，求解非常困难。一般而言，这类问题都是NP难的。本论文致力于研究该类问题的数值算法，主要工作如下：
第一个方面，我们通过变量替换，将原问题转化为目标函数在约束域上连续可微且其梯度函数是Lipschitz连续的箱型约束最小化问题。我们证明了原问题和转化问题是等价的，且给出了等价问题的KKT条件。此外，我们还利用投影算子给出了可行解是KKT点的充要条件。
第二个方面，基于等价问题，我们设计了一阶内点法、积极集法和梯度投影法来求解该带箱型约束的L2-L p最小化问题。对于一阶内点法，我们首先给出了ε−KKT点的定义，并证明了算法在O(ε−2)次迭代后可以得到等价问题的一个ε−KKT点。对于积极集法，我们给出了工作集的划分法则，用共轭梯度法求解迭代子问题来得到搜索方向，我们还证明了该算法产生的迭代点序列收敛到等价问题的一个KKT点。对于梯度投影法，我们证明了迭代点序列也能收敛到等价问题的一个KKT点。
最后我们通过将这三类算法用于求解压缩传感问题，来验证这些算法的有效性，数值结果表明梯度投影算法较优。
关键词：L2-L p最小化问题；内点算法；积极集算法；梯度投影算法
正则化与稀疏
Abstract
In recent years,the L2-L p(0<p<1)box-constrained minimization problem has been widely applied in signal reconstruction and variable selection.However,it is a class of nonsmooth,nonconvex and non-Lipschitz continuous constrained optimiza-tion problem,which is very difficult to solve.In general,this type of problem is NP hard.This thesis is devoted to the research of numerical algorithms for solving such problems.The main tasks of this paper are as follows:
First of all,we transform the original problem to a box-constrained minimization problem whose objective function is continuously differentiable on the constraint do-main and its gradient function is Lipschitz continuous by variable substitution.We prove that the original problem is equivalent to the transformation problem and show the KKT condition for the equivalent problem.In addition,we also use the projection operator to obtain the necessary and sufficient conditions that the feasible solution is a KKT point.
Secondly,based on the equivalent problem,we have designed thefirst-order in-terior point method,active set method and gradient projection method to solve the problem of L2-L p box-constrained minimization problem.Forfirst-order interior point method,wefirst give the definition ofε−KK
T point and prove that after iterating O(ε−2)times,we can get aε−KKT point by the algorithm.For active set method,we present the classification rules of the working set and we solve iterative subproblems for obtaining the search direction by the conjugate gradient method.we also show that the iteration point sequence generated by the active set algorithm converges to a KKT point of the equivalent problem.For the gradient projection method,we prove that the iteration point sequence generated by the gradient projection algorithm converges to a KKT point of the equivalent problem.
Last but not least,By using these three algorithms to solve the compression sens-ing problem,we verify the validity of these algorithms and the numerical results show
that the gradient projection algorithm is superior.
Key words:L2-L p minimization problem;Interior point algorithm;Active set algo-rithm;Gradient projection algorithm
目录
第1章引言 (1)
1.1问题背景 (1)
1.2已有研究 (3)
1.3论文结构 (5)
第2章带约束L2-L p优化问题的等价问题 (6)
2.1变量替换 (6)
2.2KKT条件 (10)
2.3投影算子 (10)
第3章求解带约束L2-L p优化问题的内点算法 (12)
3.1内点算法 (12)
3.2收敛性分析 (14)
第4章求解带约束L2-L p优化问题的积极集算法 (17)
4.1积极集算法 (17)
4.2收敛性分析 (21)
第5章求解带约束L2-L p优化问题的梯度投影算法 (23)
5.1梯度投影算法 (23)
5.2收敛性分析 (24)
第6章L2-L p优化问题的数值算例 (27)
第7章总结 (31)
参考文献 (32)
致谢 (34)
声明 (35)
个人简历、在学期间发表的学术论文与研究成果 (36)
主要符号对照表
主要符号对照表
R n n维列向量空间.
N自然数集.
‖·‖1L1范数.
‖·‖L2范数.
‖·‖∞无穷范数.
‖·‖0L0范数，表示向量中非零分量的个数.‖·‖p L p范数，其中0<p<1.
e i第i个分量为1，其余的分量为0的n维列向量. Diag(x)对角线元素是向量x的分量的对角阵.
x T y向量x与y的内积.
|x|p列向量(|x1|p,···,|x n|p)T.
x∘y列向量(x1y1,···,x n y n)T.
X⪰0矩阵X是一个半正定阵.
N(0,1)均值为0，标准差为1的正态分布.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。