LASSO 问题的近似点梯度法求解
对于 LASSO 问题
利用近似点梯度法进行优化。
该算法被外层连续化策略调用,在连续化策略下完成某一固定正则化系数的内层迭代优化。
对于上述目标函数,近似点梯度法考虑令 ,
, 对光滑部分做梯度下降,并对非光滑部分使用近似点算子,得到迭代格式
。
在此问题中,近似点算子可以解析地写出: 。
目录
初始化和迭代准备
函数在 LASSO 连续化策略下,完成内层迭代的优化。
输入信息: ,
,
,迭代初始值
,原问题对应的正则化系数
, 以及提供各参数的结构体 opts 。
输出信息: 迭代得到的解 和结构体 out 。
- out.fvec :每一步迭代的原始 LASSO 问题目标函数值(对应于原问题的
)
- out.fval :迭代终止时的原始 LASSO 问题目标函数值(对应于原问题的
)
- out.nrmG :迭代终止时的梯度范数
- out.tt :运行时间
- out.itr :迭代次数
- out.flag :记录是否收敛
function [x, out] = LASSO_proximal_grad_inn(x0, A, b, mu, mu0, opts)
从输入的结构体 opts 中读取参数或采取默认参数。
- opts.maxit :最大迭代次数
- opts.ftol :针对函数值的收敛判断条件,当相邻两次迭代函数值之差小于该值时认为该条件满足
- opts.gtol :针对梯度的收敛判断条件,当当前步梯度范数小于该值时认为该条件满足
- opts.alpha0 :步长的初始值
- optsz.verbose :不为 0 时输出每步迭代信息,否则不输出
- opts.ls :标记是否线搜索
- opts.bb :标记是否采用 BB 步长
if ~isfield(opts, 'maxit'); opts.maxit = 10000; end if ~isfield(opts, 'ftol'); opts.ftol = 1e-12; end if ~isfield(opts, 'gtol'); opts.gtol = 1e-6; end if ~isfield(opts, 'verbose'); opts.verbose = 1; end if ~isfield(opts, 'alpha0'); opts.alpha0 = 1e-3; end if ~isfield(opts, 'ls'); opts.ls = 1; end if ~isfield(opts, 'bb'); opts.bb = 0; end
初始化, 为步长,初始步长由 opts.alpha0 提供。
为可微部分的梯度,
为优化的目标函数, nrmG 在初始时刻用一步近似点梯度法(步长为
)的位移作为梯度的估计,用于收敛性的判断。
out = struct(); k = 0; tt = tic; x = x0; t = opts.alpha0; fp = inf; r = A*x0 - b; g = A'*r; tmp = .5*norm(r,2)^2; tmpf = tmp + mu*norm(x,1); f = tmp + mu0*norm(x,1); nrmG = norm(x - prox(x - g,mu),2); out.fvec = f;
线搜索参数。
Cval = tmpf; Q = 1; gamma = 0.85; rhols = 1e-6;
迭代主循环
当达到最大迭代次数,或梯度或函数值的变化大于阈值时,退出迭代。
while k < opts.maxit && nrmG > opts.gtol && abs(f - fp) > opts.ftol
记录上一步的迭代信息。
gp = g; fp = f; xp = x;
一步近似点梯度法。令 ,
, 近似点梯度法的迭代格式为
, 近邻算子 prox 的计算见辅助函数。
x = prox(xp - t * g, t * mu);
事实上,近似点梯度法的迭代格式根据定义可以写作
检验是否满足非精确线搜索条件。 令 ,针对
考虑线搜索准则,即为
,其中
。
nls 记录线搜索循环的迭代次数, 直到满足条件或进行 5 次步长衰减后退出线搜索循环,得到更新的 。
为 (Zhang & Hager) 线搜索准则中的量。
如果不满足线搜索条件,对当前步长进行衰减,当前线搜索次数加一。
if opts.ls nls = 0; while 1 tmp = 0.5 * norm(A*x - b, 2)^2; tmpf = tmp + mu*norm(x,1); if tmpf <= Cval - rhols*0.5*t*norm(x-xp,2)^2 || nls == 5 break; end t = 0.2*t; nls = nls + 1; x = prox(xp - t * g, t * mu); end f = tmp + mu0*norm(x,1);
当 opts.ls=0 时,不进行线搜索。
else f = 0.5 * norm(A*x - b, 2)^2 + mu0*norm(x,1); end
用 作为梯度范数的估计。
nrmG = norm(x - xp,2)/t; r = A * x - b; g = A' * r;
如果 opts.bb=1 且 opts.ls=1 则计算 BB 步长作为下一步迭代的初始步长。令 ,
, 这里在偶数与奇数步分别对应
和
两个 BB 步长。
if opts.bb && opts.ls dx = x - xp; dg = g - gp; dxg = abs(dx'*dg); if dxg > 0 if mod(k,2) == 0 t = norm(dx,2)^2/dxg; else t = dxg/norm(dg,2)^2; end end
将更新得到的 BB 步长限制在阈值 [t_0,10^{12}] 内。
t = min(max(t,opts.alpha0),1e12); Qp = Q; Q = gamma*Qp + 1; Cval = (gamma*Qp*Cval + tmpf)/Q;
如果不使用 BB 步长,则使用设定的初始步长开始下一次迭代。
else t = opts.alpha0; end
迭代步数加一,记录当前函数值,输出信息。
k = k + 1; out.fvec = [out.fvec, f]; if opts.verbose fprintf('itr: %d\tt: %e\tfval: %e\tnrmG: %e\n', k, t, f, nrmG); end
特别地,除了每次迭代开始处的收敛条件外,如果连续 8 步的函数值最小值比 8 步之前的函数值超过阈值, 则停止内层循环。
if k > 8 && min(out.fvec(k-7:k)) - out.fvec(k-8) > opts.ftol break; end end
当退出循环时,向外层迭代(连续化策略)报告内层迭代的退出方式,当达到最大迭代次数退出时, out.flag 记为 1 ,否则则为达到收敛标准,记为 0. 这个指标用于判断是否进行正则化系数的衰减。
if k == opts.maxit out.flag = 1; else out.flag = 0; end
记录输出信息。
out.fvec = out.fvec(1:k); out.fval = f; out.itr = k; out.tt = toc(tt); out.nrmG = nrmG;
end
辅助函数
函数 对应的邻近算子
。
function y = prox(x, mu) y = max(abs(x) - mu, 0); y = sign(x) .* y; end
参考页面
该函数由连续化策略调用,关于连续化策略参见 LASSO问题连续化策略。
在页面 实例:近似点梯度法和 Nesterov 加速算法求解 LASSO 问题 我们展示该算法的应用。另外,基于该算法的加速算法参考 LASSO问题的 FISTA 算法、 LASSO问题的第二类 Nesterov 加速算法。
此页面的源代码请见: LASSO_proximal_grad_inn.m。
版权声明
此页面为《最优化:建模、算法与理论》、《最优化计算方法》配套代码。 代码作者:文再文、刘浩洋、户将,代码整理与页面制作:杨昊桐。
著作权所有 (C) 2020 文再文、刘浩洋、户将