L1正则化问题的对偶性理论*

2015-06-13 04:37:22吴焚供
关键词:理论优化

吴焚供

(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型对偶。

登录APP查看全文

猜你喜欢
理论优化
超限高层建筑结构设计与优化思考
房地产导刊(2022年5期)2022-06-01 06:20:14
坚持理论创新
当代陕西(2022年5期)2022-04-19 12:10:18
神秘的混沌理论
民用建筑防烟排烟设计优化探讨
理论创新 引领百年
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
由“形”启“数”优化运算——以2021年解析几何高考题为例
相关于挠理论的Baer模
理论宣讲如何答疑解惑
学习月刊(2015年21期)2015-07-11 01:51:44