L1正则化问题的对偶性理论*
2015-06-13吴焚供
吴焚供
(1. 华南师范大学数学科学学院,广州 广东 510631;2. 广东第二师范学院数学系,广州 广东 510303)
L1正则化问题的对偶性理论*
吴焚供1,2
(1. 华南师范大学数学科学学院,广州 广东 510631;2. 广东第二师范学院数学系,广州 广东 510303)
L1正则化问题是一个非光滑的无约束最优化问题,在变量选择,数据压缩和图像处理等领域有广泛的应用。给出了L1问题最优解存在的新的必要条件和充分条件,利用这些条件构造出L1正则化问题的一个Mond-Weir型对偶问题,最后给出了相应的弱对偶定理和强对偶定理。
L1正则化;最优解;对偶问题
正则化问题近年来备受关注,许多研究者考虑如下的Lp最小化问题
minF(x)=f(x)+ρ‖
其中f(x):Rn→R 为一光滑函数,ρ为一给定的非负正则化参数,p∈[0,1],变量x∈Rn,‖x‖p为定义在Rn上的Lp拟范数,当0
‖
Lp正则化问题的一个重要的情况是如下的L2-
Lp最小化问题
(1)
其中‖·‖为欧几里得范数,A∈Rm×n,m minF(x)=f(x)+ρ‖x‖1 (2) 该问题在文[7]和文[1]中分别被称为LASSO和BasisPursuit。他们证明了L1正则化问题与L0正则化问题在稀疏重建的意义下是等价的,从而L0正则化所要求的NP组合优化问题可以转化为L1罚优化问题。基于上述学者的工作,L1正则化成为当今数据分析的主流工具之一。 (3) 其中▽if(x)=∂f(x)/∂xi,sign(t)为符号函数。条件(3)在文[9]中被叙述为如下的等价形式在这些理论的基础上 x= sign (x-τ▽f(x))⊙ max{ |x-τ▽f(x)|-τρ,0} ,τ> 0 或 max{▽f(x)-ρ,min{x,▽f(x)+ρ}}=0 在这些理论的基础上,一些有效求解L1问题的算法得以建立,具体可参考文[9-11]等。 然而L1正则化问题毕竟是非光滑优化问题,若能构造出其光滑的对偶问题,则更有效的求解该问题便是有可能的。另一方面,早在1974年Mond[12]和1981年Mond和Weir[13]便考虑了一类特殊的不可微优化问题的对偶问题, 受其工作的启发,运用类似的方法构造出L1正则化问题的一个光滑的对偶问题,我们称之为Mond-Weir型对偶。……p>
